AOP_Tom2 (1021737), страница 109
Текст из файла (страница 109)
Положим, что Хе = Л. Для всех и > О, таких, что Хп ф О, положим (10) А».1-) = (1/Хп), Лп+1 = 1/Х»» — А»1.) Если Хп = О, то величины Апе) и Х„.)1 не определены и правильной цепной дробью для Х будет //А),..., Ап//. Если Хп ф О» данное определение гарантирует, что О < Л"и+) < 1, так что любое А будет положительным целым числом. Из определений (10) следует также, что 1 1 А, + Л', А, -1- 1/(А2 + Л2) поэтому Х = //А),..., Ап ), Ап + Л„// для всех п > 1, для которых определено Хп.
В частности, если Хп = О, то Х = //А),..., Ап//. Если Х„ф О, то число Л всегда лежит между //А),...,А„// и //А),..., Ап + 1//» так как согласно (7) величина 9„= Кп(А), ..., Ап + Хп) монотонно возрастает от Кп(А),..., Ап) до Кп(А),..., Ап + 1) при возрастании Х„ от 0 до 1. Согласно равенству (9) при возрастании д„цепная дробь будет возрастать или убывать в зависимости от того, будет ли числа и четным или нечетным. Действительно, в силу (5), (7), (8) н (10) )Х вЂ” //Ай,...,А„//~ = )//Ам...,А„+ Л„// — /(Ам...,А„//) = )//Ай,..., А„, 1(Х„// — //Ай,..., А„//( К„(Аы..., А„, 1/Х„) К„й(Ам ., ., А„) К„„(А„..., А„,1(Х„) К„(А,,..., А„) = 1/(К„(А„..., А„) К„+,А„„..., А„, 1(Х„)) < 1/(К„(Ай,...,А„)К„+й(Ам...,А„,А„,!)).
(12) Поэтому //Ай,..., А„// — экстремально близкое приближение к Х, если и не малб. Если Х„не равно нулю для всех и, получаем бесконечную цепную дробь //Ай, Аю Аз .. /(, значение которой определяется как !пп //Ай,Ат,...,А„//; н из неравенства (12) ясно, что этот предел равен Х. Разложение вещественных чисел в правильную цепную дробь обладает рядом свойств, аналогичных свойствам чисел, представленных в десятичной системе счисления. Если при помощи приведенных выше формул разложить в правильные цепные дроби некоторые известные вещественные числа, получим, например, в 29 //3, 1, 1, 1, 2//; //1, 1, 9, 2, 2, 3, 2, 2, 9, 1, 2, 1, 9, 2, 2, 3, 2, 2, 9, 1, 2, 1, 9, 2, 2, 3, 2, 2, 9, 1,...
//; 1 + //3, 1, 5, 1, 1, 4, 1, 1,8, 1, 14, 1, 10, 2, 1, 4, 12, 2, 3, 2, 1, 3, 4, 1, 1, 2, 14, 3,... //; 3+//7,15,1,292,1,1,1,2,1,3,1,14,2,1,1,2,2,2,2,1,84,2,1,1,15,3,13,...//; (13) 2 + //1, 2, 1, 1, 4, 1, 1, б, 1, 1, 8, 1, 1, 10, 1, 1, 12, 1, 1, 14, 1, 1, 16, 1, 1, 18, 1,... //; //1, 1, 2, 1, 2, 1, 4, 3, 13, 5, 1, 1, 8, 1, 2, 4, 1, 1, 40, 1, 11, 3, 7, 1, 7, 1, 1, 5, 1, 49,...
//; 1 + //1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,... //. Ж= Числа Аы ° Аю ... называются часшичнььми ошношенилмп числа Х, Обратите внимание на закономерность поведения частичных отношений для чисел ~/8/29, йй и е; причины этой закономерности рассматриваются в упр. 12 и 18. Для чисел же зг- ~!2, х н 7 никакой видимой закономерности в поведении частичных отношений не наблюдается. Интересно отметить, что когда древние греки обнаружили существование иррациональных чисел, то, по существу, первое определение вещественных чисел они дали в термннах бесконечных цепных дробей. (Позже онн приняли предложение Евдокса вместо этого определить х = 9 следующим образом: "х < г для тех же рациональных чисел г, таких, что 9 < г".) (См.
О. Вес)сег, цие!!еп ппс! Яйи й)ел виг СеясЛйсЛйе МайЛ., Аз!гоп., Рйуяйй В2 (1933), зп-333.) Если Л" — рациональное число, то его разложение в правильную цепную дробь естественным образом соотносится с алгоритмом Евклида. Предположим, что Х = е/и для и > и > О. Процесс разложения в правильную цепную дробь начннаетсл с Хв = Х; обозначим (/в = и, )е = е. В предположении, что Х„= г;,/(/„~ О, уравнение (10) принимает вид А„+1 = (У„/3Г ), Хв ы — — У„/Ä— А„.ы = (У„шод $'„)/У'„. (14) Поэтому, если принять б'„„ь1 = \l„, 1l„+1 = У„шод Г„, (15) то условие Л„= Р„/Пв будет выполняться в течение всего процесса разложения дроби.
Далее, соотношение (15) — это в точности преобразование, выполняемое в алгоритме Евклида над переменными и и е (см. алгоритм 4,5.2А, шаг А2). Например, поскольку ээ = //3,1,1,1,2//, известно, что применение алгоритма Евклида к числам и = 29 и е = 8 потребует выполнения ровно пяти шагов деления и на шаге А2 частными (и/е) будут последовательно 3, 1, 1, 1 и 2. Если Х„= 0 и и > 1, то частичное отношение А„всегда должно равняться 2 или более, поскольку Л'„1 меньше единицы. Такое соответствие с алгоритмом Евклида означает, что правильная цепная дробь для числа Х заканчивается на некотором шаге со значением Л„= 0 тогда и только тогда, когда Х вЂ” рациональное число, ибо очевидно, что Л'„не может равняться нулю, если число Х иррационально, и, наоборот, известно, что алгоритм Евклида всегда заканчивается. Если частичные отношения, получаемые в ходе выполнения алгоритма Евклида, равны Аы Аз, ..., А„, то согласно (5) е К„,(Аэ,..., А„) ц К„(.4ы Ат,, Ае) (16) Эта формула справедлива также в случае и < е, когда А1 — — О.
Более того, соглас- но (8) К„1(Аз,..., А„) н К„(Аы Ам..., А„) будут взаимно просты и дробь в правой части выражения (16) является несократимой. Поэтому и = К„(А,,Аз,...,А„)Н, е = К„1(А„...,А„)И, (17) где И = 8сй(и,е). Наихудший случай. Теперь можно использовать сформулированные выше свойства для того, чтобы выяснить, как себя ведет алгоритм Евклида в наихудшем случае, или, другими словами, чтобы найти верхнюю гранину числа шагов деления. Наихудший случай имеет место, когда на входе задаются последовательные числа Фнбоначчи. Доказательство.
Согласно (17) должно быть и = К„(.4ы Ат,..., А„) А, где Ам Аэ,... ..., А„и г7 — положительные целые числа, а А„> 2. Поскольку ʄ— полипом с неотрицательными коэффициентами, включающий все переменные, минимальное значение достигается только тогда, когда А1 = 1, ..., А„ 1 = 1, А„ = 2, И = 1. Подставляя эти значения в (17), получаем искомый результат. 1 Теорема Г.
П>сть для и > 1 и н е — целые числа (и > и > 0), такие, что при применении к н и и алгоритма Евклида необходимо выполнить ровно п шагов деления, причем число и — -наименьшее возможное число, удовлетворяющее этим условиям. Тогда и = Е„.~э и е = Е .ьм Эта теорема явилась первым практическим применением последовательности чисел Фибаначчн. С тех пор числа Фнбоначчн нашли широкое применение при выполнении н исследовании алгоритмов.
Следующий результат получил Т. Ф. дс Ланьи (Т. Р, г!е1абпу) (Мйл. Асад. Яс!. Рапв 11 (1733), 363-364). Он составил таблицы нескольких первых К-палиномов и обнаружил, что числа Фнбоначчи дают для цепных дробей заданной длины наименьшие числитель и знаменатель. Однако он совсем не имел в виду вычисление наибольшего общего делителя. Первым на связь между числами Фибаначчи и алгоритмом Евклида указал Э.
Леже (Е. Ьебег) (Соггеэропс!алсе Масй. ес Рйувдие 9 (1837), 483-485]. Вскоре после этого П. Ж. Е. Финк (Р. 3. Е. Р!пс)с) [Тгайй Е!ешеагиге сГАг!йшебг!пе (8сгавЬоцгй, 1841), 44) другим методом доказал, чта если и > и > О, то 8с6(и, и) вычисляется не более чем за (2 !8 с+ 1) шагов, а Г. Ламе (О. Еаше) (Сошрссв Неправ Асад. Ясю. РаНв 19 (1844), 867-870( распространил полученный результат на 5(!ойш(с+1)). Полное изложение этих пеРвых Работ по анализУ алгоРитмов поЯвилось в интересном обзоре Дж. О. Шэллита (5. О. БЬа!!!1) НЫтоиа Майезпас!са 21 (1994), 401-419. Однако более точная оценка наихудшего случая является прямым следствием теоремы Р. Следствие 1. Если 0 < с < Н, то число шагав деления, необходимых алгоритму 4.5.2А для выполнения операций с числами и и и, не превышает(!о84 (3 — ф)Ю).
Доказательство. После выполнения шага А1 имеем с > и шой с. Поэтому согласно теореме Р максимальное число шагов и имеет место в том случае, когда с = Р„ьг н и шад с = Р„. Так как Р„+г < Х, то ф"+'/у/5 < Х (см. 1.2.8-(15)). Следовательно, ф" < (у/5/ф)Х = (3 — ф))У. 1 Величина !о84 (3 — ф)Аг приближенно равна 2 078 !и%+ .6723 ш 4 785 !обш Аг+.6723.
По поводу обобщений теоремы Р обратитесь к упр. 31, 36 и 38. Приближенная модель. Теперь, когда известно максимально возможное количество шагов деления, попытаемся найти их среднее число. Пусть Т(т,п) --число шагов деления в гшучае, когда алгоритм Евклида имеет на входе и = гп и с = и. Тогда Т(т,О) = 0; Т(т,п) = 1+ Т(п,тп1абп) прн и > 1. (18) Пусть ҄— среднее число шагов деления, когда и = п, а и выбирается случайным образом, Поскольку после выполнения первого шага деления на ход выполнения алгоритма влияет только значение и шой в, можно записать Т„= — ~ Т(й, ). (19) ояь< Например, Т(0, 5) = 1, Т(1,5) = 2, Т(2,5) = 3, Т(3,5) = 4, Т(4,5) = 3, так что Тз = ь(1+ 2+3+4+ 3) = 2г. Задача состоит в оценке Т„при больших значениях и. Попробуем сначала применить приближение, предложенное Р. У.
Флойдом (11. Ъг'. Р!оу6), Можно предположить, что для 0 < й < и значение п, па существу, "случайно" по модулю )с, так что можно записать 1 Т„1+ — (Т +Т +. +Т„). и Тогда Тп ш 5», где последовательность (5») есть решение рекуррентного соот- ношения 5о=О, 5»=1+ — (5о+51+" +5»-1) 1 (20) Это рскуррентное соотношение легко решить, если учесть, что 1 5п+! = 1+ — (50+51+". +5»-1+5») о+1 = 1+ — (п(5» — 1) + 5„) = 5»+ 1 1 и+1 и+1 1 1 — (и пю1! к) = — ~~1 (и — йй) [(и/(а + 1) ! < к < (и/о) ~ 1ййбп 1<яд<» ((1 М +1) (11»+1)1~1)) 1<1<» 1 Е (1 ь1+1) ! 515» »11 1 — — ) п + О(!ок а) 12) (21) (см.
упр. 4.5.2 — 10(с)). Это равно примерно .1775п, а не .25п. Поэтому значение и шо1! к меньше значений, предсказываемых моделью Флойда, а алгоритм Евклида выполнвется быстрее, чем предсказывает приближенная модель. Непрерывная модель. При» = Л поведение алгоритл1а Евклида, по существу., определяется поведением правилыюй цепной дроби для х = О/%, 1/й1 ...
..., (Ю вЂ” 1)/Н. Прн очень больших 11' естественно рассматривать разложение числа Х в правильную цепную дробь фактически как случайного вещественного числа, равномерно распределенного в интервале (0..1). Рассмотрим функцию рас- пределения (22) Р„(х) =Рг(Х» <х) приО<х < 1 Следовательно, 5» равно 1+ -' + + -„' = ̈́— гармоническому числу. Теперь приближение Тп ш 5» дает Тп !и и+ 0(1). Сравнение этого приближения с таблицами истинных значений Тп показыяает, однако, что !пп- — это слишком много.
(Тп возрастает не так быстра.) Предположение, что число п случайно по модулю Й, является по этой причине слишком пессимистическим. И в самом деле, более внимательный анализ показывает, что среднее значение числа и пюд Й меньше среднего значения числа -'Й при 1 < !с < и: равномерно распределенного числа К = Хв. По определению правильных цепных дробей получаем Ев(х) = х и Е„+г(х) = ~ Рг(Ь < 1/Хв < й + х) Рг(1/(й+ х) < Х„< 1//с) = ~ (5„(1/Ь) - Г„(1/(Ь+ х)) ). (23) Если распределения Еэ(х),Г~(х),..., определяемые этими формулами, сходятся к предельному распределению Р (х) = Г(х), то получаем Ь'(х) = ~~~ (Е(1/!») — Г(1/(/с+ х))).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
