Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 2) (1119454), страница 91
Текст из файла (страница 91)
Если т»/и = //Ам..., А»// и гпэ/н = //А,,..., А»//, где т» и шэ взаимно просты с и, то т,шэ ш й1 (по модулю п), Это и есть условие, определяющее рассматриваемое соответствие. В случае, когда А» = 1, согласно (46) имеет место аналогичная симметрия.] 27. Сначала докажем результат для и ж р", а затем — для и = гэ, где числа г и э взаимно просты. Альтернативный путь — использовать формулу из следующего упражнения. 28. (а) Левая часть — мультипликатнвная функция (см.
упр. 1.2.4-31). Она легко вычисляется, когда и является степенью простого числа. (с) С учетом (а) имеем формулу обраэ»ения Мебиуса /МбМиэ/: есчи /(и) = ~„щ„д(И), то д(п) = 2 „!»(и/Ы)/(с!). 29. Сумма приблилсенно равна (((12!п2)/л ) !п)д!)/!у — Яэй»Л(б)/4~+ 1А7; здесь 2 „, Л(И)/оэ сходится к постоянному значению -~'(2)/Д(2), в то время как согласно приблюкению Стирлшпэ !и Ю! = /»с !и /»' — Х + О(!об Лг).
30, Предлагаемая модификация алгоритма влияет на вычисления только в том случае, когда при выполнении следующего шага деления немодифицированным алгоритмом получается частное, равное 1. В таком случае этот следующий шаг деления будет пропущен модифицированным алгоритмом, Вероятность того, что данный шаг деления будет пропущен, равна вероятности того, что А» = 1 и что этому частному предшествует четное число частных, равных 1. Учитывая условия симметрии, получаем, что зто есть вероатность того, что А» = 1 и что эа низ» слсдуеш четное число частных, равных 1.
Последнее имеет место тогда н тоны»о тогда, когда Х»» > 9 — 1 = 0.618..., где 9— отношение золотого сечения: действительно, А» = 1 и А»»с > 1 тогда и только тогда, когда 1 < Х»-с < 1; А» = А»+с = А»»т = 1 и А»»» > 1 тогда и только тогда, когда» < Л» с < 1», 7 » и т. д, Таким образом, экономится приблизительно Г» с(1) — Р» с(Ф вЂ” 1) щ 1 — )8 б ш 0.306 шагов деления.
Среднее число шагов деления в случае, когда с = и и и взаимно просто с и, приблизительно равно ((12!и С!)/х~) !и и. К. Вален (К. Уа!с!еп) в работе Сге!!е 115 (189о), 221-233, рассматривал все алгоритмы, которые при ашос)с ф 0 па каждой итерации заменяют значения (а,ь) значениями (щ (хи) щос)с). Для и з. с существует ровно с таких алгоритмов, н онн могут быть представлены в виде бинарного дерева с г ветвями. Самые мелкие ветви дерева будут формироваться, если на каждой итерации выбирать самые маленькие остатки — это соответствует наименьшему всиможному числу итераций выполнения всех таких алгоритмов определения наибольшего общего дели»тля.
В случае выбора нанбольших остатков будут формироваться самые глубокие ветви дерева. (Похожие идеи в Нйй Асж!. Ясй 23 (Вег!щ, 1768), 111-180, 358, рассматривал Лагранж,) Дальнейшие результаты, относящиеся к рассматриваемому вопросу, изложены в работе Н. Г. де Брейна (Н, С, ае Вгпбп) и Ъ'. М. Заринга (Ъ!с. М. 2вг!пб), опубликованной в Х!еисг Агой!ес" тоог Ис!з!спас(е (3) 1 (1953), 105-112, а также в рабате Г, И, Ригера (С. Ю, Н!сбег), опубликованной в Ма!5.
Хасйг, 82 (1978), 157-180. На многих компьютерах применение модифицированного алгоритма приводит к удлинению каждого шага деления. В таких случаях предпочтительнее воспользоваться идеей, изложенной в упр. 1. Применив ее, можно избежать выполнения всех шагов деления, когда частное равно единице. 31. Пусть ао = О, ас = 1, а»~.с = 2а„+ а„с; тогда ае ы ((1+ с/2)" — (1 — »/2)")/2»/2. Наихудший случай (в смысле теоремы Р) имеет место, когда и = а„+ а„с, в = а„, и > 2.
Этот результат получен А. Дюпре (А. ВирЫ) и опубликован в хсурналс Х с(е Масй. 11 (1846), 41-64. В этой работе А, Дюпре исследовал также более общие процедуры »с предварительным просмотром", предложенные Ж. Вине (Я, Вше»). (Ь) Член К -1(х»с ° ° ° 1х»с-1)К» — с(х»с»2,... сх»сс») соответствует тем словам длиной си+ и в азбуке Морзе, для которых тире находится в ни и (си+ 1)-й позициях; другой член соответствует противоположному слу*шю.
(Можно также воспользоваться упр. 2. Более общее тождество К +»(хс,...,х»„)К»(х +с,...,х +») = К»»(хс,...,х а»)К„(х, +с,...,х .с, ) 4-( — 1)»К,(х,,х,)К„» с(х»»»т,...,х + ) также опубликовано в работе Л. Эйлера.) 33. (а) Новыми представлениями'яахясотся х и си/с(, у = (и — ш)/с), х' = у' = с( = бес((т, и — си) для»и < т < и. (Ь) Отношение (и/х') — р < х < и/х' определяет х. (с) Подсчитаем все элементы х, которые удовлетворяют условиям (Ь). (с() Пару целых чисел х > у > 0 с х ' у можно записать единственным образом в аиде х = К,„(хс,..., х, ), у = К с(хм...,х~ с), где хс > 2 и ш > 1; здесь р/х = //х,...,хс//.
(е) Достаточно показать, что 2, <»<„с» Т(й, и) = 2(и/2) + Ь(и)-, это следует из упр, 26. 34. (а) Деление х и р на йсс((х,р) дает д(и) = 2 „Ь(и/с(). Применим результат упр. 28, (с) и используем условие симметрии между переменными со штрихом н без него. (Ь) Для фиксированных р и ! представления с хс! > х' обладают свойством х' < с/сю; следовательно, имеется О(с/йс!/у) таких представлений.
Суммируем теперь при условии 0 < ! < у < ° /и/с(, (с) Если»(р) есть даинан сумма, то, к примеру, 2 щ»з(с() = р(Н»„— Н„) = !с(у); отсюда»(у) ы 2" /с(у/с!). Далее !с(у) = р)п2 — -' + 0(1/у). (0) ~ „", З»(у)/у~ = 4т» г[6~9]П(6)/уеХ = ~ы( р(4)/со»». (Аналогично 2 „" с д(у)/уз = О(1) ) (е) 2 „", р(Ь)/Ь' ы 6/те+ О(1/и) (см. упр.
4 52-10(д)), а 2"„", р(Ь) (о8 Ь/йт = О(1). Следовательно, при И > 1 имеем Ьг(п) = п((3 !л 2)/з ~) !п(п/И) + О(п) для И > 1, В итоге Ь(п) = 2 ~ „щ» п(ь!)Ь,(в/Ы) = ((6!п2)/х~)п(!пп — ~ — ~ ') + О(пп ~(п)г), где остаточные сУммы Равны 2 = 2 „щ» п(И)!п(сИ)/сИ = 0 н 2 ' = 2, Р(И) !п~фх~ = ~,щ„Л(И)/Н. [Известно, что а ~(п) = О(!о3!о8п); см. работу Харди (Напру) и Райт (Ъгг!3!П) Ап 1пггодпсс!оп со гйе ТЬеогу оГ 7»пшЬегз, 522.9.] 35. См. Ргос. Г»аа Асаг!. 5сй 72 (1975), 4720-4722. М.
Л. В. Пайтвэй (М. Ь. У. Р!Ыеиау) и К. М. А. Кзстл (С. М. А. Сззг!е) [Вп!!. Гпзь Ма!5. апг! !сз Аррйсаг!опз 24 (1988), 17-20] нашли убедительное, но требующее больших усилий эмпирическое свидетельство того, что сумма частичных отношений равна 18 ! 2)2 — 2.542875+ О(п ггз). 36, Выполняя алгоритм в обратном порплке и полагая, что на шаге С2 для заданного значения Й выполняется !* — 1 делений, получаем минимальное число н», для которого йсг!(иь»»,..., и») = Рп, .. Ры и иь ш Рп Й», Б»-г (по модулю йсп(пь»»,..., и„)) ! здесь все 1; > 2, 1~ > 3 и Г~ + +Ф„~ = Ж+ и -1. При этих условиях можно минимизировать и» = Ри ...Ры„,, пРиняВ 11 = 3, Гз = " = 1»-з = 2, к» ы 2Рл-»ьз. Если условиться также, что п~ > кг > > и, решение п~ = 2Р»- +э+1, кз = .
= и»-~ = 2Рл-»ьз, и = 2Рл- ьз имеет минимум иь [См. САСМ 13 (1970), 433-436, 447-443.] 37. См. Ргос. Ашег. ЬГагЬ. Яос. 7 (1956), 1014-1021; см. также упр. 6.1-18. 38. Положим гл = [и/ф], так что гл/п = ф '+с = //ам аю .., //, где 0 < е < 1/и. Пусть й— минимальное значение, такое, что оь > 2; тогда (ф "+ (-1)" Рь ге)/(ф " - (-1)" Рье) > 2, отсюда Ь четно и ф ~ = 2 — ф < ф~Рь»те = (фы~~ — ф ~)с/Я.
[Алп. Ро!оп, Маей. 1 (1954), 203-206.] 39. Минимум 287; ни одна дробь со знаменателем < 287 не принадлежит //2,1,95// = 96/287 ш,33449477,как н интервалу [3335...3345] = [//2,1,666// .. //2,1,94,1,1,3//]. Чтобы решить основной вопрос для дроби с меныпим знаменателем в промежутке [а..Ь] в случае, когда 0 < а < Ь < 1, учтем, что з обозначениях, принятых дчя представления правильных лепных дробей, будет иметь место соответствие //хм хз,, // < //ш, ут,...// тогда и только тогда, когда (-Цэи < (-1)~р, для наименьших /, таких, что л ф рэ, причем символ»оо» помещается за последним частичным отношением рапионального числа.
Таким образом, если а = //хм хю, // и Ь = //уи уз,... // и если 7 минимально при х; ф р, в промежутке [а .. Ь] дробь принимает вид с = //хы...,, хэ из!,, .., з,//, где //з,...,з„// лежит между //х„х»м...// и //у,, у,»м...// включительно, Положим, что К-~ = О. Знаменатель ~з-'(х! . хг"г)йла-т»1(хг,,з»)+ Ьу-з(хм . яэ-г)Кт — !(зг»м...,х») числа с бУдет минимальным пРи ш = / и з, = (/ нечетно. » У! + [Р~».~ Рос], хэ + [х!+~ фоо]).
Другой способ вывода этого метода основан на теории, изложенной в следующем упражнении.! 40. Можно доказать по индукции, что в каждом узле выполняется р»у-рщ» = 1, т, е. числа р~ ид~ являются взаимно простыми. Поскольку р/д < р/д тор/д < (р+Р )Дд+д? < р/д. Кроме того, понятно, что метки на всех левых вершинах ветвей для чисел р/д меньше этих значений р/д, в то время как метки на всех правых вершинах больше этих значений.
Поэтому каждое рациональное число может появиться в качестве метки ие более одного раза, Теперь остается показать, что каждое ркциональное число должно обязательно появиться. Если р/д = //ам..., а„1//, где каждое из а, — положительное целое чисао, то по индукции можно показать, что узел с меткой р/д находится посредством перемещения аг раз влево, затем — перемещения аз раз вправо, аз раз влево н т. д. (Впервые последовательность меток на сформированных уровнях исследовалась М. А.
Штерном (М. А. Взегп) в Сге!!е 65 (1858), 193-220, хотя в этой работе связь с бинарными деревьями не прослеживается. На получение всех возможных дробей при помощи иктерполированнк дроби (р+ р')/( 7+ 7') между соседними элементами р/д и р'/д' обратили внимание позже. Относящиеся к решению этой задачи важные идеи были опубликованы Даниэлем Швентером (!уаа!е! БсЬмепзст) (!7е!!с!м РЬуясо-Магйетаз7сш (ХЬгпЬегб, 1636), Рагс 1, РгоЫеш 87; Сеошегг!а Ргасзкэ, Згг) еб!г!оп (1641), 68; см. М. Сап!от, Сезс!нейсе г(ег Мазй. 2 (1900), 763-765) и Джоном Уоллнсом (,!оЬп Жа!)В) в его книге 2)еаз!зе о/ А!6еЬга (1685), СЬаргегз 10-11.
К. Гюйгенс (С. Науйепз) использовал эти идеи при конструировании приводов для своего планетарии ?см. Оезспрйо А иготаВ Р!ааезапб (1703), опубликовано после его смерти). Лагранж в работе Нйз, АсЫ. Яс!. 23 (Вег!!и, 1767), 311-352, з24, и в дополнении к переводу на французский язык алгебры Эйлера (1774), $18-$20, привел полное описание втой идеи. См. также упр. 1.3.2-19; А. Вгосог, Ветае СЬгопошбгг!две 6 (1860), 186-194, П. Н. !.еЬшег, АММ 36 (1929), 59-67.] 41.
Действительно, правильные цепные дроби для чисел, записываемых в общем виде обладают интересной закономерностью, основанной на тождестве К~в+«е1 (хм, х «-м х» — 1, 1, у» — 1> у -1,..., уг ) х «К «-~ (хм ° °, х» -1) К Ау ° ~ уз) +(-1)"К +»(хм...,х мй,-у„,-у -м.,.,-у1). Наибольший интерес это тождество представляет для случая, когда у«ж х,«з м у«-~ = х,-з и т. д., так как К«ьз(зм ",зз,й,зз+м -,з«) = К«-з(зм..,,зз мзз+ззьг хз+з,,з ). В частности, если р„/д„м К з(хз,...,х„)/К„(хм...,х„) ж //хм .,х„//, то р»/д-+ (-1)"/д.'г = // „..., *., — 1, 1„х. — 1, *. м..., х //.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
