Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 2) (1119454), страница 4
Текст из файла (страница 4)
9. (МИ) Покажите, что цепные дроби удовлетворяют следующим тождествам: а) //х„...,х„//=//хм...,хз+//хззл,...,х„////, 1< й < и; Ь) //О,хнхз,,х //ыхз+//хг,...,хо//, и>1,. с) //х ь...;ха ь ха, 0 ха+ н х о+г, ° .. х„// = //хи..., ха н хо + х ьз ь х а+г,..., х„//, 1 < К < и; н) 1 //хз хг, ° °,хо// //1,х! 1,хз . °,х //. и > 1 ° 10. (МЯО) Из результата упр. б следует, что любое иррациональное число Х единственным образом разложимо в правильную цепную дробь вида Х = Ао+//АпАн.4з,...//, где Ао — целое число и Ам Аг, Аз, ... — положительные целые числа. Покажите, что если Х имеет такое представление, то разложение числа 1/Х в правильную цепную дробь имеет внд 1/Х = Во + //Вп, В „Аз, Аз, . // для соответствующих целых чисел Во, Вь ..., В .
(Наиболее интересен, безусловно, случай, когда Ао < О.) Объясните, как можно выразить все В через Ао, Ан Аг, Аз и Аз 11. [МЗО) (Ж.-А. Серре (Л.-А. Беггес), 1850.) Пусть Х = Ае+//АнАз,.4з,А4,...// и У = Во+//Вн Вг, Вз, Вз,... // — представления в аиде правя~нных цеп~ы~ дробей двух в»- щественных чисел Х и У в смысле упр. 10. Покажите, что зти представления "звентуально согласованы" в том смысле, что А„,+з = В„+з для некоторых гл и и и для всех й > О тогда н только тогда, когда для некоторых целых чисел в, г, з, Г выполняется Х = (ОН+ г)/(ау+ Г) при (Ог — гв) = 1. (Зта теорема является аналогом представлений цепными дробями простого результата, заключающегося в том, что представления целых чисел Х и У в десятичной системе счисления в конечном счете совпадают тогда и только тогда, когда для некоторых целых чисел о, г и з выполняется равенство Х = (10оУ + г)/10*,) ь 12.
(МЯО) Квадращнчноя иррациональностью называют число вида (з/Р— (у)/У, где Р, (/ и 1' — целые числа, удовлетворяющие условиям Р > О, У Ф О, н Р не есть полный квадрат. Без потери общности можно предшиожить, что У является делителем числа Р— (У~, в противном случае зто число можно переписать в виде (з/РУг — ЦУ~)/(У)У|). а) Докажите„что разложение в правильную цепную дробь (в смысле упр. 10) квадратичной иррациональности Х = (з/Р— сУ)/У получается по следующим формулам: Уо ж У, (Р Пг)/У Ао = 1Х), 6'о — — (/+ АОУ; А +з = ((з/Р+П )/У„+з), К,оз =А +зУьз — П .
Ь) Докажите, что для всех и > Х, где М вЂ” некоторое целое число, зависящее от Х, выполняются неравенства 0 < б'„<»/»», 0 < 1'„< 2»/»з. Следовательно, представление квадратичной иррапиональности правильной цепной дробью в конечном счете периоднчно. (Указание. Покажите, что (-»Я — П)/1' = Ао + //Ам .. А, — У /(»/12 + С )//, и, используя равенство (5), докажите, что при большик значениях и веднчииа (»/ь" + П )/Ъ'„положительна.) с) Положим р„= Кьы(4о,.4м.,.,.4„) и 9„= К„(А„...,А„). Докажите тождество 1'р' + 2(7р 9~ + ((П» — П)/Ъ')9~ = (-1)" ~' У,+ь и) Докажите, что представление иррационального числа Х правильной цепной дробью в конечном счете периодично тогда и только тогда, когда число Х есть квадратичная иррациональность.
(Это утверждение относительно цепной дроби является аналогом утверждения о том, что разложение вещественного числа Х в десятичную дробь в конечном счете периодично тогда и только тогда, когда Х рационально.) 13. (М40) (Ж. Лагранж, 1767.) Пусть /(х) = а„х" + - + ао, а > Π— полипом с целочисленными коэффициентами, у которого нет рациональных корней и имеет»ж точно один вещественный корень 5 > 1. Разработайте компьютерную программу для нахождения примерно первой тысячи частичных отношений числа 5 с помощью следующего алгоритма (который включает в себя только сложение). Ы. Присвоить А» — 1.
ЕЗ. Для Ь = О, 1, ..., и — 1 (в таком порвдке) и у = и — 1, ..., Ь (в таком порядке) присвоить а, »- а,»~ + а„. (На этом шаге функция /(х) заменяется функцией д(х) = /(х + 1), полнномом, корни которого на единицу меньше корней цолянома /.) ЕЗ.
Если а~+а»+ . +ае < О, то присвоить А А+1 и возвратиться к шагу 1.2. Ь4. Вывести А (которое является значением следу1ощего частичного отношения). Заменить коэффициенты (а„,а м,ао) на ( — ар,-ам...,-а,,) и возвратиться к шагу Е1. (На этом шаге выполняется замена /(х) полиномом, корни которого обратны корням полинома /.) Например, начав с /(х) = х» — 2, алгоритм выведет сначала "1" (заменив /(х) на х — Зх~- Зх — 1), затем — "3" (заменив /(х) на 10х — бх~ — бх — 1) и т.
д, 14. (МЯУ) (А. Гурвиц (А. Нпгэч»э), 1391.) Покажите, что при помощи следующих правил можно найти разложение в цепную дробь числа 2Х, если известны частичные отношения числа Х: 2// 2а, Ь, с,... // = // а, 2Ь+ 2//с, ... //7)'; 2// 2а + 1, Ь, с,... // ы // а, 1, 1 + 2//Ь вЂ” 1, с,, ////. Используйте этот метод для нахождения разложения в цепную дробь числа 1е, если известно разложение в цепную дробь числа е (зто разложение дается формулой (13)). ь 15.
(МЯ] (Р. У. Госпер (В, ЪЧ. Соэрег),) Обобщая упр. 14, разработайте алгоритм, который вычисляет цепную дробь Х„+ //Хм Хэ,... // для (ах + Ь)/(сх + З) по заданному разложению числа х в цепную дробь хо+//хм хе,... // и заданным целым числам а, Ь, с, 3, таким, что аЗ 14 Ьс.
Сделайте свой алгоритм таким, чтобы он выполнялся как "оперативная сопрограмма", которая перед вводом каждого из х выводит как можно болыпе значений Х». Продемонстрируйте, как эаш алгоритм вычисляет (97х + 39)/( — 62х — 25), когда х = -1+//5,1,1,1,2,1,2//. 16. [НМЯО) (Л. Эйлер, 1731.) Пусть /о(з) = (е' — е ')/(е'+е ') = сап!гг и /+~(») ы 1//»(») — (2ц+1)/». Докажите, что для всех н функция /„(з) есть аналитическая функция комплексной переменной з в окрестности начала координат, которая удовлетворяет дифференциальному уравнению /„'(») = 1-/„(») -2п/„(г)/г.
Используя этот факт, докажите, что СапЬ» = //» ',Зз ',5» ',7» ',...//. Затем докажите, используя правило Гурвица, что е ь» = // 1, (2ш + 1) и — 1, 1//, т > О, (Это общепринятое обозначение бесконечной цепной дроби //1, п-1, 1, 1, Зп-1, 1, 1, бп-1, 1, ...//.) найдите также разложение в цепную дробь числа е ш", где н > О нечетно. ° 17. [МЯЯ) (а) Докажите, что //хц -хз// = //хг — 1,1,хг — 1//. (Ь) Обобщите это тождество, получив формулу для //хм -хг хз, -х» хэ, — хе,..., хг„м -х ь //, в которой все частичные отношения являются положительными целыми числами при условии, что все х — большие положительные целые числа. (с) Из результата упр. 16 следует, что сап! = //1, -3, 5, -7,... //, Найдите разложение Сап 1 в правильную пенную дробь.
18. [МЯЯ[ Покажите, что //ац аз,,, а, хц ац аз,..., а, хг, ам аз,,, аы, хз„..//- //а,..., аг, ам хм а„„..., аг, ац хз, а,..., аз, ац хз,... // не зависит от хц хз, хз, .... Указание. Умножьте обе цепные дробя на К,(ацаг,,а ) 19. [МЯО[ Докажите, что Е(х) ы !о8»(1 + х) удовлетворяет уравнению (24). 26. [НМЯО[ Выведите (38) из (37). 21. [НМЯЯ) (Э. Вирсинг (Е.
%!гэ!а8).) Ограничения (39) были получены для функции р, соответствующей функции Я, с помощью оператора ТЯ(х) = 1/(х+ 1). Покажите, что функция, соответствующая ТЯ(х) = 1/(х+с), при подходящей константе с > О обеспечивает лучшие оценки. 22. [НМ16[ (К.
И. Бабенка.) Разработайте эффективный способ вычисления точных прнближений для величин Л» и Ф, (х) в (44) при малых,! > 3 и О < х < 1. 23. [НМЯЯ) Докажите (53), используя результаты, полученные при доказательстве теоремы Ж. 24. [МЯЯ) Каково среднее значение частичного отношения А„в разложении в цепную дробь случайного вещественного числау 25. [НМЯЯ) Найдите пРимеР множества Х = 1~ О1» О1зш С [0..1[, где все 1 — непеРесеквющиеся интервалы, для которых (45) не выполняется. 26. [МЯЯ) Покажите, что если числа (1/н, 2/и,..., [и/2)/н) выражены в виде правильных цепных дробей, то полученные результаты обнаружившот лево-правую симметрию в том смысле, что всякий раз одновременно с //А,,., Аз, Аг// появляегся //Ам Аг,..., А~//. 27, [МЯ1[ Выведите (55) из (49) и (54).
28. [Мяя[ докажите следующие тождества, в которые входят трн теоРетико-числовые функции !е(н), д(гз), Л(п). а) ~ р(8) =Ям. щ» с) Л(п) = ~~> р Я !пЫ, щ» 29. [МЯЯ) Полагая, что Т„задается формулой (55), покажите, что (57) равно (о8). ь 30. [НМЗЗ) Часто предлагается следующий вариант алгоритма Евклида: при выполнении шага деления вместо замены с величиной и азад е заменить его величиной [(и що41 е)-е[, если и шо4) и > -'е. Так, например, если и = 26 и а = 7, то бее((26, 7) = Зсд(-2, 7) = бс41(7, 2); когда кратные 7 вычитаются из 26, наименьшим ло абсолютлой величине остатком будет -2.
Сравните зту процедуру с алгоритмом Евклида; оцените число шагов деления, сзкономленных в результате применения етого метода. ь 31. [МЮЗ[ Найдите наихудший случай для модифицированного алгоритма Евклида, предложенного в упр. ЗО. Каковы наименьшие исходные числа и > е > О, для обработки которых необходимо затратить и шагов деления? 32. [Яд) (а) Словом длиной и в азбуке Морзе называется цепочка из г точек и е тире, для которой г + 2е = и.
Например, словами длиной 4 в азбуке Морзе являются Учитывая чта кл(х! хн хе хл) полинам равный х4хехехе + х4хз + х!хл + хзхп + 11 найдите и докажите простую связь между полиномом Кп(хи..., х ) и словами двиной и в азбуке Морзе. (Ь) (Л. Эйлер, )44ог( Сошш. Асае(. Еа. Рес. 9 (1762), 53-69.) Докажите, что Кп 4 л(хм ° ° °,х 44 ) — К (хи . ~хм)Кп(х~ .4 ы ° ° °,ел+ ) + Км-4(ХП...,Хп,-4)Кл-4(хм+а, °,Хм+и) 33. [МЯЯ) Пусть Ь(и) — количество различных представлений числа и в виде и = хх'+ рр', х > р > О, х' > р' > О, х 1. р, где х, х', р, р' целые. а) Покажите, что если ослабить зги условия, допустив выполнение равенства х' = р', то количество возможных представлений числа и будет равняться Ь(и) + [(и — 1)/2) . Ь) Покажите, что для фиксированных р > О и О < е < р, где Е л р, и для любых фиксированных х, принедлекщщих интервалу О < х < и/(р+ 4) и таких, чта хч щ в (по модулю р), существует точно одно представление числа и, удовлетворяющее ограничениям в (а) и условию х щ Е (по модулю 9).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
