Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 2), страница 5

с) Покажите, что Ь(и) = 2 Ии/(р+ Ф) - Е) /р) -' [(и — 1)/2), где сумма берется по всем положительным целым числам р, Г, г', таким, что г 1 р, е < р, Е < р, йб ш и (по модулю 9). 4)) Покажите, что каждое из таких представлений Ь(и) можно выразить единственным способом в аиде х = К„(хн...,х, ), р = К 4(Х4,...,х -4), х' = Кь(х,„+и...,х„,+ь)4(, р' = Ко 4(х .„з,...,х„,+ь)4(, где т, Ь, а' и все хз — положительные целые числа, для которых Х4 > 2, х ль > 2, а 41 — делитель числа и. Теперь из тождества, приведенного в упр. 32, следует, что и/4( = К ~,ь (хм, х е ь) . Обратно, любой заданной последовательности целых чисел Хи ..., Х ЕЕ, таКОй, Чта Х4 > 2, Х 4 Ь > 2, И дпя КОтОрОй К,„4.4(ХМ..., Х пе) дспнт и, соответствует, таким образом, т + Ь вЂ” 1 представлений чнела п, е) Покажите, что иУп = [(Зи — 3)/2) + 2Ь(и).

34. [НМ40) (Г. Хейльброин (Н. НеИЬгопп).) Пусть Ье(и) — - количество представлений чис- ла и, описанных в упр. ЗЗ, для которых Х41 < х', плкк половина количества представлений, для которых хе( = х'. а) Пусть д(и) — количество представлений, на которые не накладывается ограничение х л р. Докажите„что Ь(и) = ЕРИ)дв), д(и) =2ЕЬе(-„") Е1л 41п Ь) Обобщите результат упр. 33, (Ъ), показав, чтодля В > 1 выполияется равеиство Ье(п) = 2"(и/(р(у+ !))) + 0(п), где сумма берется по всем целым числам р и 1, для которых !.~ряб<с<р<,/-/В.

с) Покажите, что ~„",(р/(р + !)) = Р(р) !и 2+ 0(о,(р)), где сумма берется по ! из интервала 0 < ! < р, причем Ф .Ь р и с ~(р) = 2т" Ар(1/В) б) Пока иге, что~„„", Р(р)/р' = 2 ~, д(г()Н!ь?е!/В~ е) Отсюда получаем асимптотическую формулу Т„= ((12!п2)/я~)(!пп — ~в А(В)/о)+О(п-~(п) ). Зб. [БМ41] (Э. Ч. Яо (А.

С. Уао) и Д. Э. Кнут (П. Е. Кпатй).) Докажите, что при 1 < ш < и сумма по всем частичиым частимм для дробей т/и равна 2(2,'[к/р]+ [и/2]), где суммирование берется по всем предсгавлеияям и ж зз'+ рр', удовлетворяющим условиям упр. 33, (а), Покажите, что 2 [л/р] ы Зь" зп(!пп)е + 0(п!обп(!ой!обп)~), и примените полученный результат к "античному" виду алгоритма Евклида, в котором вместо операции деления используется только операция вычитакия. 36. [М35] (Г. Х. Брздли (О. Н.

Втаб!еу).) Каково иаимеиьшее значение я„, при котором для вычисления бсб(ам..., и„) по алгоритму 4.3.2С требуется Аг делений, если в процессе вычислений постоянно используется елгоритм Евклида? Предполагается, что АГ > и > 3. 3'г. [МВВ) (Т. С. Моцкии (Т.

3. Мосек!и) к Е. Г. Штраус (Е. С. Есгаве).) Пусть ап., ., а— положительные целые числа. Покажите, что найдется щахК„(е„ц1,...,ащ„!) по всем перестановкам р(1)... р(п) для всех (1, 2,..., и), когда ощц > а„ш! > ащм > ам„-ц > и минимум будет приамы < ам„! < ащз! < ам„е! < аыз! « ° аме! < аж -з! < арса> < ежа-И < ар(з!.

36. [МВВ] (Я, ь!икусииский(Л. М!квж!йз)г!).) Пусть й(п) = юзах,йеТ(т,п). ИзтеоремыР следует что Цп) < !обе(Лп+ 1) — 2. Докажите, что 2Х(п) > !обе(Ми+ 1) — 2. ° 39. [МВВ] (Р. У. Госпер.) Среднее количество ударов, которые выполяяет бейсболист, равно .334. Каково минимально возможное число ударов, которое он выполняет? [Напомним читателям, не являющимся приверженцами бейсбола, что среднее количество ударов = (количество бросков) Дчисло битов), округленное до трех десятичных знаков.] ь 40. [М2В] (Дерево Штерна-Бреке ($!егп-Бгосо!/.) Рассмотрим бесконечное бинарное дерево, в котором каждый узел связан с дробью (р~ + р,)/(и + 4„), где р~/6 — метка узла, блюкайшего к левому прешиественнику, и р,/4„— метка узла, ближайшего к правому предшественнику.

(Левый предшественник расположен перед узлом в симметричном порядке, в то время как правый предшественник расположен за узлом. Определение симметричного порядка приведено в разделе 2.3.1.) Если для узла левые предшественники отсутствуют, то р~/6 = О/1; при отсутстяни правых предшественников р„/д„= 1/О. Таким обрезом, метка кориевого узла есть 1/1; метками узлов, порожденных корневым узлом, будут 1/2 и 2/1; метками четырех узлов второго уровня слева направо будут 1/3, 2/3, 3/2 и 3/1; метками восьми узлов третьего уровня будут 1/4, 2/5, 3/б, 3/4, 4/3, 5/3, 5/2, 4/1 и т.д. Докажите, что для каждой метки р/д число р является взаимно простым с д; более того, узлы с метками р/4 предшествуют узлам с метками р'/4 в симметричном порядке тогда и только тогда, когда метки удовлетворяют иеравеяству р/4 < р'/4 .

Нейдите связь между цепной дробью для метки узла и пути к узлу, показав таким образом, что любое положительное рационвльиое число появляется как метка точно одного узла дерева. 41. (М40) (Дж. Шэллит (1. ЯЬо!!В), 1979.) Покажите, что разложение в правильную цепную дробь выражения 1 1 1 ч 1 — + — + — + 2' 2о 2г д 2ш ~31 содержит только единицы и двойки и представляется в исключительно простом |щде.

Докажите, что в случае, когда ! — любое целое число > 2, частичные отношения чисел Лнувилля 2 „>, Г ' имеют регулярный внд. (Эти числа, введенные Ж. Лиувиллем (3. !лоцгй!!е) в Г с(е МаоЬ. Рпгее ес Арр!. 16 (18о1), 133-142, впервые были строго определены как шронсценденшнме. Первым доказал трансцендентность такой формы числа и подобных констант О. Дж, Кемпнер (А.

1, Кешрпег) в Тгело, Ашег. МаГЬ. 5ос, 17 (1916), 476-482.) 42. [М30) (Ж. Лагранж, 1798.) Предположим, что разложение числа Х в правильную цепную дробь имеет внд //АмАо,...//, н пусть 9 = А (Ам,А ). Обозначим через ))х!) расстсшние от х до ближайшего целого числа пппр (х — р). Покажите, что !)дХ)) > !(9 1Х!) для 1 < 4 < д„. (Таким образом, знаменатели 9 так называемых сходящихся дробей р /9 = //Ам, ..,А„// представляют собой целые числа, "обрывающие ряд", что приводит к приобретению ))ОХ)) новых свойств.) 43. )МЯ0) (Д. В. Ыатула (Р, %.

МаМа).) Покажите, что описываемое уравнением 4,5.1-(1) правило "медианного округления" для чисел, представленных в формате с фиксированной и плавающей дробнымн чертами, в случае, если число х > 0 не представимо, может быть введено следующим простым образом. Пусть разложение числа х в правильную цепкую дробь имеет вид ао + //ам ом... // и пусть р = К о~(ао, -, ао), д = К (ац...,а„).

Тогда гоппб(х) = (р,/йз), где дробь (р,/йз) представима, а,зробь (рьы/Ог ы) — нет. (Указание, См. упр. 40.) 44. (М85) Предположим, что выпшпгяются арифметические операции в формате с фиксированной дробной чертой с меднанным округлением, а которых дроби (и/и') представимы тогда и только тогда, когда )и) < М, О < и' < А! и и Х и'. Докажите нли опровергните тождество ((в/и') Ю (о/о')) 6З (о/о') = (и/в') для всех представимых дробей (и/и') и (о/о'), обеспечивающих выполнение условия и' < ~/Х и отсутствие переполнения.

45. (М85] Покажите, что алгоритм Евклида (алгоритм 4.5.2А) в случае применения к двум двоичным числам при и -+ со требует для выполнения 0(п ) единиц времени. (Такая же верхняя оценка справедлива и доя выполнения алгоритма 4.5.2В.) 46. (М43) Можно ли уменьшить верхнюю границу О(п~) в упр. 43, если для вычисления наибольшего общего делителя иаюльзовать другой алгоритм? 47. (М40) Разработайте компьютерную программу нахождения как можно большего числа частичных отношений для вещественного числа х, задаваемого с высокой точностью.

Примените ее для вычисления первых нескольких тысяч частичных отношений для постоянной Эйлера 7, которые можно вычислить по алгоритму, описанному Д. В. Суини (Р, %. Явеепеу) в МагЬ. Сошр. 17 (1963), 170-178. (Если 7 есть рациональное число, то можно найти числитель и знаменатель этой константы, решив таким образом знаменитую математическую проблему.

Согласно теории, изложенной в разделе, если рассматривать исходное число как случайное, следует ожидать получения около 0.97 частичных отношений на каждый десятичный разряд. При этом не возникает необходимости в операциях деления с многократной точностью. (См. алгоритм 4.5.21. и статью Дж. У. Ренча (1. %. %гепсЬ) и Д. Шэнкса (Р. БЬапйо), МаСЬ. Сошр.

20 (1966), 444-447.) 48. (Мйу) Пусть То = (1, О, к), Т1 = (О, 1, о), ..., Т„+1 — — ((-1)" +'о/0, (-1)" и/И, О) представляют последовательности векторов, вычисляемых по алгоритму 4,3.2Х (расширенный алгоритм Евклида), и пусть //ам..., а„// — правильная цепная дробь для о/и. Выразите То через континувнты, включающие ам ..., а„, где 1 < З < и. 49. [МЯУ) Откорректируйте последнюю итерацшо алгоритма 4.5.2Х так, чтобы можно было заменить элемент а„двумя частичными отношениями (а„— 1, 1).

Подразумевается, что число итераций в подчиняется заданной закономерности. Продолжая предыдущее упражнение, положим, что Л н р — произвольные положительиьщ вещественные числа, и пусть И Ь/Лрю/И, где И = йсб(и,и). Докажите, что если число и четко и если 21 = (кнуз,хз), то ш!и"+,'[Лху+ ух, — [уеэев) И[ < У. ь $0. [М23) Для данного иррационального числа о 6 (О .. 1) и вещественных чисел 5 и т, таких, что 0 < д < у < 1, положим, что /(а,/1,т) — наименьшее неотрицательное целое число и, такое, что !3 < оп пина 1 < Т.

(Такое целое число всегда существует в силу теоремы Вейля (ууеу!), упр. 3.5-22.) Разработайте алгоритм для вычисления /(а, ~У, у). ь 51. [Муу) (Рациокальнал рекоксшрукцил,) Число 28481 превращается в число 41/316 (по модулю 199999) в том смысле, что 316 28481 н 41. Как это можно обнаружить'? Объясните„ как для заданных целых чисел а и т при ш > а > 1 найти целые числа к и у, такие, что ах н у (по модулю т)„х Л у, 0 < х < ~/ш/2 и [у[ < ~/ш/2, или определить, что таких чисел х н у нет.