 |
 |
 |
 |
 |
 |
 |
| Кратко о теории чисел. |
|
| |
|
||||||||||
|
|
 |
§ 2. Цепные дробиПункт 10. Континуанты. Анализ алгоритма Евклида.В этом пункте я расскажу о вещах совсем малоизвестных, хотя абсолютно доступных для понимания. Сначала напомню забывчивым читателям рекуррентные соотношения для числителей и знаменателей подходящих дробей: P s = q s P s -1 + P s -2 - числители Q s = q s Q s -1 + Q s -2 - знаменатели. Начальные условия: P 1 = q 1 , P 0 = 1, Q 1 = 1, Q 0 = 0. Теперь, когда эти соотношения стоят как живые у нас перед глазами в удобном месте, давайте рассмотрим не их, а трехдиагональный определитель:
Определение. Определитель (а при устном рассказе, во избежание ненужной аллитерации "определение определителя", - детерминант), обозначенный несколькими строками выше через ( q 1 q 2 ... q n ), называется континуантой n -ого порядка. Числа q 1 , q 2 ,..., q n в дальнейшем будут у нас неполными частными из алгоритма Евклида, поэтому подразумеваются целыми. Разложим континуанту n -ого порядка по последнему столбцу (читатели наверняка натренировались делать это еще на первом курсе, когда вычисляли подобные определители из задачника Проскурякова по алгебре). Получим: ( q 1 q 2 ... q n ) = q n ( q 1 q 2 ... q n -1 ) + ( q 1 q 2 ... q n -2 ). Получившееся соотношение очень напоминает рекуррентные соотношения для числителей и знаменателей подходящих дробей. Это не случайно и две следующие леммы только подтверждают нашу зародившуюся догадку о явной связи континуант и цепных дробей. Лемма 1. Континуанта ( q 1 q 2 ... q n ) равна сумме всевозможных произведений элементов q 1 , q 2 , ..., q n одно из которых содержит все эти элементы, а другие получаются из него выбрасыванием одной или нескольких пар сомножителей с соседними номерами (Если выбросили все сомножители, то считаем, что осталась 1). Поясняющий пример. ( q 1 q 2 q 3 q 4 q 5 q 6 ) = q 1 q 2 q 3 q 4 q 5 q 6 + q 3 q 4 q 5 q 6 + q 1 q 4 q 5 q 6 + q 1 q 2 q 5 q 6 + q 1 q 2 q 3 q 6 + q 1 q 2 q 3 q 4 + q 5 q 6 + q 3 q 6 + q 1 q 6 + q 3 q 4 + q 1 q 4 + q 1 q 2 + 1. Достучался ли я до вас этим примером, дорогие друзья? Понятно? Доказательство. База индукции: ( q 1 ) = q 1 ,
и утверждение леммы справедливо для континуант первого и второго порядков. Шаг индукции. Пусть утверждение леммы верно для континуант ( n - 2)-го и ( n - 1)-ого порядков. Тогда имеем: ( q 1 q 2 ... q n ) = q n ( q 1 q 2 ... q n -1 ) + ( q 1 q 2 ... q n -2 ) и просто внимательное разглядывание этого равенства в сочетании с мысленным прикидыванием, какие произведения получатся от умножения континуанты ( q 1 q 2 ... q n -1 ) на q n , доказывает требуемое. Ё 
Наблюдение. Количество слагаемых в континуанте n -ого порядка есть сумма числа слагаемых в континуантах ( n - 1)-ого и ( n - 2)-го порядков, т.е. континуанта ( q 1 q 2 ... q n ) содержит F n +1 слагаемых, где F n +1 - ( n +1)-ое число Фибоначчи. Лемма 2.
Доказательство. База индукции:
Шаг индукции. Пусть верно, что
Тогда:
Ё Утверждение леммы 2, устанавливающее прямую связь континуант с цепными дробями, впервые заметил Леонард Эйлер. Этот гениальный математик еще много что заметил, но, боюсь, полный рассказ о его математических достижениях не уместится в эту книжку даже самым мелким шрифтом. Мы отложим должное небольшое историческое отступление про Эйлера до пункта 18, где будет рассказана теорема, носящая его имя. Приступим теперь к исполнению второй части названия этого пункта - анализу алгоритма Евклида. Нас будет интересовать наихудший случай - когда алгоритм работает особенно долго? Спросим точнее: какие два наименьших числа надо засунуть в алгоритм Евклида, чтобы он работал в точности заданное число шагов? Ответ на этот вопрос дает Теорема (Ламэ, 1845 г.). Пусть n О N , и пусть a > b > 0 такие, что алгоритму Евклида для обработки а и b необходимо выполнить точно n шагов (делений с остатком), причем а - наименьшее с таким свойством. Тогда а = F n +2 , b = F n +1 , где F k - k- ое число Фибоначчи. Доказательство. Разложим a / b в цепную дробь:
где q 1 , q 2 ,..., q n - неполные частные из алгоритма Евклида; по условию теоремы, их точно n штук. Согласно свойству 3 пункта 9, континуанты ( q 1 q 2 ... q n ) и ( q 2 q 3 ... q n ) взаимно просты, значит, если ( a , b ) = d - наибольший общий делитель, то
Заметим, что по смыслу конечной цепной дроби, q n і 2, a q 1 , q 2 ,..., q n -1 , d і 1. Поскольку континуанта суть многочлен с неотрицательными коэффициентами от всех этих переменных, минимальное значение достигается при q 1 = q 2 =...= q n -1 = d = 1, q n = 2. Подставляя эти значения в ( Є ), получим: а = F n +2 , b = F n +1 . Ё Следствие. Если натуральные числа a и b не превосходят N О N , то число шагов (операций деления с остатком), необходимых алгоритму Евклида для обработки a и b не превышает й log Ф ( Ц 5 N ) щ - 2, где й a щ - верхнее целое a , F = (1 + Ц 5)/2 - больший корень характеристического уравнения последовательности Фибоначчи (искусствоведы сказали бы: "золотое сечение"). Доказательство. Максимальное число шагов n достигается при а = F n +2 , b = F n +1 , где n - наибольший номер такой, что F n +2 < N . Рассматривая формулу для n -ого члена последовательности Фибоначчи (смотри, например, доказательство свойства 4 в пункте 9), легко понять, что F n +2 - ближайшее целое к (1/ Ц 5) F n +2 . Значит (1/ Ц 5) F n +2 < N , следовательно, n +2 < log Ф ( Ц 5 N ), откуда моментально даже n < й log Ф ( Ц 5 N ) щ - 3 (именно "минус три", ведь рассматривается верхнее целое, т.е., кажется, утверждение следствия можно усилить). Ё Для еще не купивших калькулятор сообщу, что log Ф ( Ц 5 N ) » 4,785 · lg N + 1,672, поэтому, например, с любой парой чисел, меньших миллиона, алгоритм Евклида разбирается не более, чем за й 4,785 · 6 + 1,672 щ - 3 = 31 - 3 = 28 шагов. Ну вот, используя теорему Ламэ, мы провели некоторый анализ быстродействия алгоритма Евклида и узнали наихудший случай для него - два последовательных числа Фибоначчи. Таким образом, давно висевшая перед нами народохозяйственная проблема об эффективности древнегреческого наследия решена полностью. На этом пункт и закончим.
|
||||||||||||||||||||
.
