Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 2) (1119454), страница 38
Текст из файла (страница 38)
УПРАЖНЕНИЯ 1. [15[ Чему равно значение л при завершении работы алгоритма Ау 2. [24[ Напишите йХХ-программу лля алгоритма А, вычисляющую х" шобш лля данных истых и и х, где ш — размер машинного слова. Считается. что й12 имеет бинарные операции БВЗ, Лаа и др., описашпяе в разделе 4.5,2. Напиюите еще одну программу, вычисляющую х" шос1 ш последовательно (посредством многократного умножения на я), и сравните время работы этих программ.
3. [22[ Как вычисляется хэм при помощи (а) бинарного метода, (а) гернарного метода, (с) кватернарного (чегверичного) метана и (д) метода множитачяу 4. (ЛИд[ Найдите число и, ддя которого восьмеричный (2э-арный) метод дает на десять умножений меньше, чем бинарный метод. 5. [24) На рис. 14 показаны первые восемь уровней дерева степеней. В предположении, что к-й уровень дерева построен, его (я + 1)-й уровень определяется счелуюн1им образом: берем каждый узел и иа 1-м уровне слева направо и присоединяем к нему снизу узлы и+1, и+ам и+а, ..., ич-аь ~.=2п (именно н таком порюзке), где 1, ам аэ, ..., аь, представляет собой путь от корня дерева да узла и.
При этом, однако, устранякггся все узлы, которые уже пояктялись в дереве. Разработайте аффективный алгоритм, хотарый строит первые г + 1 уровней дерева степеней. [Указаиое. используйте два массива переменных, ьтйкц[у[ и 1.1нкв[1[, лля О <З < 2':, эти переменные указывают соответственно вверх и вправо лля числа у в дереве) 6. [М26] Коли ввести незначительные изменения в определение дерева степеней, данное в упр. 5, чтобы узлы, расположенные ниже и, присоединялись я порядке нбмеаиал и+аз-м ..., и+ам и+ам и+1, а не возрастания, получится дерево, первые пять уровней которого выглядят как Покажите, что это дерево дает метод вмчисления х", который требует столько же умиожеиий, сколько при двоячяом методе.
Поэтому молифицироваияое дерево, несмотря на то что оно строится почти так же, как и дерево степеней, дает более плохой гаетод вычисления стапеней. 7, [М61] Докажитс, что имеется бесконечно много зиачеиий и, для которых а) метод множителя лучше бинарного метода; Ъ) бинарный метод лучше метода множителя: с) метод дерева степеней лучше как бинарного метода, так и метода множителей.
(В данном случае пояятие "лучше" означает вычисление х" с использованием меньшего количества умножений.) 8. [Мй!] Докажите, что дерево степеней (упр. 5) никогда ие дает для вычисления г" большего количества умножений, чем бинарный метод. 9. [85] Разработайте процедуру возведения в степень, аналогичную алгоритму А, но базирующуюся на го = 2'. Ваш метод должен выполнять примерно!8 я+г +п«умножений, где и — казачество ненулевых цифр в т-эрном представления числа я. 10. [10[ На рис.
15 показано дерево, которое указывает для каждого и < !00 единственный путь вычисления х" с минимально возможным количеством умножений. Каким образом это дерево можно расположить в памяти компьютера, используя «ольке 100 ячеек памяти? ь 11. [МЯ6] Дерево иа ри». 15 изображает аддитивные цепочки ас, ам , а„ у которых ((а,) = ! для всех ! в цепочке. Найдите все адцитивяые цепочки для и =- 43 и и, — — 77, имеющих зто свойство.
Покажите, что любое дерево, подобное изображенному па рис. 15, должна включать в себя либо путь 1, 2, 4, 8, 9, 17, 34„ 43, 77,либо путь 1, 2, 4, 8, 9, 17, 34, 68, 77, 12. [М!О] Нельзя ли расширить показанное на рис. 15 дерево до бесконечного дерева, которое давало бы правило выч«ишения я" с наименьшим количеством умяожений для всех положительиых целых чясел и'! 13.
[М8!] Найлите звездную цепочку длиной 4+ 2 для каждого из четырех случаев, перечиглениых в теореме С (следовательио, теорема С остается справедливой и при замене ! яа Г.) 14. [М89]' Завершите доказательство теоремы С, показав, что (а) шаг г — 1 не является малым шагом; (Ь) Л(а, «) ие может быть меньше, чем и« вЂ” 1.
15, [М43] Напашите компьютерную программу для расширения 'теоремы С, определяющую все и, такие, что !(и) = Л(п) + 3, и все и, для которых Г(п) = Л(п) + 3. 16. [НМ15] Покажите, что теорему 0 трудно получить, используя бинарный метод; если ! (и) обозначает ддииу адпитианой цепочки лля и, построенной бинарным ЯХ-методом, отношение ! (и)!'Л(п) ие стремится к определенному пределу при и -«оо.
17. [М25] Объясните, как найти интервалы Ум ...,,7«, требующиеся в доказательстве леммы Р. 18. [ЮИ4] Пусть (! — положительная константа, Покажите, что существует константа а < 2, такая, что (т+э)(г+э) э,((п«+э) ) для всех больших т, где сумма берется по всем э, г, и, удовлетворяющим (30). 19.
[МЯЯ] "Мультимножество" подобно множеству, ио ано мажет содержать один и тот же элемент конечное число раз. Если А и  — мультимиожества, то мультимножества А В! В, А О В и А г! В определяются следующим образом: элемент, встречающийся а рвз в А и 6 раз в В, встречается в А !з В а+ 5 раз, в А Π — шах(об) и в А г!  — ш!п(а 5) раз. (" Множество" явлются мультимиожесгвом, в котором нет мементов, встречающихся более одного раза; если А и  — множества, то множествами являютгл и А О В, и А !З В и данные здесь определения в этом случае согласуются с определениями объединения и пересечения множеств.) а) Разложение натурального числа и на простые множители представляет собой мульти- множество Ю, элементами которого являются простые числа, причем Д л = и.
Тот факт, что каждое натуральное число может быть единственным образом разложено иа простые множители, дает взаимно однозначное соответствие между множеством натуральных чисел и конечными мультимножествамя простых чисел, например если и = 2 . 3 17, соответствующим мультимножесгвом является !»' = (2,2,3,3,3,17). Если М и М--мультимиожества, соответствующие гл и и, то какие мультимиожества соответствуют йсс((т, и), !сш(ш, и) и шп? Ь) Каждый нормированный полинам 7(з) над полем комплексных чисел естественным образом соответствует мультимножеству его "корней"; имеем 7(») = Дсег(з — ь).
Если г(з) и д(з) — полиномы, соответствующие конечным мультимножествам г' и С комплексных чисел, то какие полиномы соответствуют Р Ге»», Р О 17 и Г й С7 с) Найдите как можно больше интересных соотношений, выполняющихся при приложении к мультимиожествам операций В1, О, !1. 20. [МЯО) Какие последовательности Я, и М; (О < 1 < г, 0 < з' < 1) появляются при структурной декомпозиции Хансена звездных цепочек (а) типа 3 и (Ь) типа 57 (Шесть "типов" цепочек определены в доказательстве теоремы В.) ь 21. [МО6] (В. Хансен (%.
Наивен).) Пусть Π— некоторое натуральное число. Найдите значение и, такое, что !(и) < ("(и) — Ф 22. [МОО] Докажите, что аддитивная цепочка, построенная в доказательстве теоремы Г, является ! -цепочкой. 23. [МЗО] Докажите неравенство Браузра (50). ь 24. [МОО) Обобщите доказательство теоремы О, чтобы поююать, что !'(( — 1)~( — 1)) < (и — 1) !'(В) + !'(и) для любого целого В > 1; докажите также, что !(2 " — 1) < !(2 — 1) + глп — та + !о(п).
25. [20] Пусть у является дробью 0 < у < 1, выраженной в двоичной системе счисления как у = (.И~ . О»)ь Разработайте алгоритм для вычисления к" с использованием операций умножения и извлечения квадратного корня. э 26. [МО5] Разработайте эффективный алгоритм, вычисляющий и-е число Фибоиаччи Р„ по модулю из по данным большим целым числам и и ш, 27.
(МО)] (А. Флал»менкаьш (А. Р!ашшец1ашр).) Чему равно наименьшее и, для которого каждая аддитивная цепочка содержит как минимум шесть малмх шагов? 28. [ВМУО) (А. Шеихаге (А. БсЬопЬабе).) Назначение данного упражнения — дать ясное и короткое доказательс»во того, что !(и) > Л(п) + 18 и(п) — 0(!об !об(и(п) + 1)). а) Если г = (г»... хо.х»... )» и у = (у» .. уо.у-1 .. )з представляют собой действительные числа в двоичной записи, то введем обозначение з С у, если х! < уз для всех .1. Приведите простое правило для построения наименьшего числа з, обладающего тем свойством, что из х' С х и у' С у вытекает, что к'+ у' С ю Обозначив такое число как я!7 у, до ж~е, ч о г(к~Ъ) < (х) + ю (у).
Ь) Дана произвольная аддитивная цепочка (11) с г = 1(и) н последовательность Ас, А,... ..., А„определенная, как в (55). Определим последовательность Ас, Ам ..., А, таким образом: Ас = 1; если а, = 2а, м то А, = 2А, и в противном случае, если а« = а, + а«для некоторых О < й < у < «, А; = А, 117(А, ~/2"~ "'). Докажите, что зта последовательность "покрывает«данную цепочку в том смысле, что а; С А, для О < «< г.
с) Пусть 5 — натуральное число (которое будет выбрано позже). Назовем неудваявающий шаг а, = а, + а«небольшим шагом, если 4, — 4«> б, в противном случае назовем его близким шагом, Пусть Вс = 1; В, = 2В, м если а, = 2о, и В, = В, 1«у(В«-ь/2~г е'), если а; = а, +ૠ— небольшой шаг; В, = р(2В«1) — в противном случае, где с(х) — наименьшее число у, такое, что х/2' С у для О < е < 5, Покажите, что А, С В, и и(В«) < (1+ 5с,)2М для О < «< г, где Ь; и с, означают соответственно число иебольшях шагов и число близких шагов < «. [Указание.
Покажите, что единицы в В, появляются в последовательных блоках размером > 1+ 5сн] «() Теперь((п) = г = Ь, + с„+ Ы и и(п) < и(В,) < (1+5с„)2«', Объясните, как выбрать 5, чтобы получить неравенство, упомянутое в начале этого упралсиеиия. [Указание. См. (16); обратите внимание иа то, что и < 2" а"" для некоторого а < 1, зависящего от 5.] 29.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
