Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 2) (1119454), страница 106
Текст из файла (страница 106)
' ант1) для г+ х < у < п. Если 0 < а, < Ь и В = ]шах".,' ~,"„~~ ]ео]!1, имеем ]51(ам...,а 1)! < ЬВ. Таким образом, если выбрать Ь > (1бпВ)" ', должны существовать различные векторы (оо,,о„-з) и (ао,...,о'„1), такие, что (бп5!(ао»...,о„~)) = (бпБЯоо,...,а'„,)) для 1 < 1' < п, поскольку имеется Ь" векторов, но не более (16пЬВ)" < Ь" возможных (и-1)-злементнык наборов значений.
Пусть 1(х) = (оо — ао) + . + (а„1 — а'„1)х" и /г! = Ф(а!). Тогда "условие малости" удовлетворено. Кроме того, 6»;Ь О; в противном случае г(х) должно делить в(х), ]Х А!6опТйшв 3 (198Ц, 385-392.] 40. В данном множителе-кандидате «(х) = х~+ ах 1хх '+ + ао заменим каждмй а! рациональной дробью (по модулю р') с числителем и знаменателем < В. Затем выполним умножение на наименъшнй общий знаменатель и посмотрим, осуществляет ли полученный полином деление и(х) над кольцом целых чисел. Если нет, то не существует множителя о(х) с коэффициентами, ограниченными В, которые сравнимы по модулю р' с кратным «(х).
41. дэвид Бойд (Ва«Ы Воуб) заметил, что 4х~+4х~+х~+4х~+4 = (2х~+4х +Ьхз+4х+2) х (2х~ — 4хэ + 5х — 4х+ 2), и нашел пример более высокой степени для доказательства того, что с > 2, если оно существует. РАЗДЕЛ 4.0.3 1. з™, где пт = 20е "1 — наивысшая степень 2, меньшая или равная и. 2.
Положим, что входное значение к находится в регистре А, а и — в памяти по адресу ММ; выходное значение помещается в регистр Х. А1. Инициализация. У+-1. г- . 1Т Ф- и. Переход к шагу А2. В протявиом случае ответ равен 1. )т' <- 11'т'1'2). Аб. Возведение Я в к ат. Я+- Я х Яшобю. АЯ. Деление 1Т пополам. Переищ к шагу АЗ при четном ут", Переход, если Ф = 1, (м А . и еииеУ аЯ У+- Я х Ушодю. Переход к шагу Аб. Окоичательиае умножение, ! Время работы составляет 21Х + 16К+ 8, где Е = А(п) на единицу меньше количества битов в двоичном представлеиии п„а К = «(и) — количество единичных битов в таком представлении.
Для последовательной программы можно положить, что и достаточно малб для размещения в индексном регистре; в противном случае последовательное возведение в степпзь выходит за рамки лапкой задачи, Приведеипая ниже программа помещает выходное значение в регистр А. г11 4- и. Х+- х. 1 1 1 Ж вЂ” 1 1'т' - 1 Ф 01 31 501 МИ ОЯ 3 ТА Х ОУ ЗМР 2Р ОЯ 1Н Н01 Х 05 Я,АХ 5 ОО 2Н ОНС1 1 07 51Р 10 гА х Хшобю -ь гА, гП ь- гП вЂ” 1. Опять умножить при гП > О.
$ Время ее работы составляет 14)т' — 7; зтв программа работает быстрее предмдущей при и < 7 и медлениее--при и > 8. 3. Последовательвости показателей степени для этих методов следующие: (а) 1, 2, 3, б, 7, 14, 15, ЗО, 60, 120, 121, 242, 243, 486, 487, 974, 975 (16 умножений); (Ь) 1„2, 3, 4, 8, 12, 24, Зб, 72, 108, 216, 324, 325, 650, 975 [14 умножений); (с) 1, 2, 3, 6, 12, 15, ЗО, 60, 120, 240, 243, 486, 972, 975 (13 умножеиий); (6) 1, 2, 3, 6, 12, 15, 30, 60, 75, 150, 300, 600, 900, 975 (13 умножений).
Р(аименьшее возможное число умиажеиий равно 12; оио может 01 АХ НМТХ 1 ОЯ ЗТХ Т ОУ ЗТА Е 04 ЬОА ММ 05 ЗАР 2Р Об ЗМР ООМН 07 ЗН ЗНЗ 1 ОУ БТА И ОУ Аб ЬОА Е 10 Нй. Е 11 ЗТХ Е 18 А2 ЬОА И 18 ЗН ХАН 69 14 ЗНЗ 1 15 А4 ЗАЕ 4Р 16 БТА М 17 АЗ ЬРА Е 18 МК Т 1У ЗТХ Т ЯО ЗНР Аб 81 4Н ЕЗА Е ЯЯ ЮП. Т 1 1 1 1 1 О 5+1-К 5+1-К Ь Ь Е Ь Х+ 1 К К К-1 К-1 К-1 К-1 К вЂ” 1 1 1 быть получено путем комбинирования метода множителя с бинарным меттщом, поскольку 973 = 15 (2в + 1).] 4 (777777)в = 2тв — 1, б. Т1. [Инициализация.] Установить 1.1ИКО[Я +- О для 0 < у < 2' и установить тт +- О, ЫИКИ[0] Ф- 1, ЫИКИ[Ц +- О. ТЗ. (Изменение уровня.] (Теперь уровень тт дерева связан слева направо, начиная с ЫИКИ[0].) Если )т = т, алгоритм завершается.
В противном случае установить и +- 1.1ИКИ[0], ти +- О. ТЗ. [Подготовка и,] (Теперь и — узел уровня й и ит указывает на крайний справа в данный момент узел уровня (т + 1.) Установить д +- О, в +- и. Т4. (Уже в деревед] (Теперь в — узел на пути от корня дерева до и.) Если ЫИКО[и+ в] Р'. О, перейти к шагу Тб (значение и+ в уже имеется в дереве).
Тб. (Вставка под и.] Если д = О, установить ш' +- и + в. Затем установить ЫИКК[и+в]+-1,ЫИКО(и+в]+-и,дв-и+в. Тб. [Переметцение вверх.) Установить в +- ЫИКО(в]. Если в 14 О, вернуться к шагу Т4. Т7. [Присоединение группы.) Если д Ф О, установить ЫИКИ[ти] в- д, ти +- ш'. Т8. [Перемещение и.] Установить и+- 1.1ИКИ(и].
Если и ф О, вернуться к шагу ТЗ. Т9. [Конец уровни.! Установить ЫИКК(ти] в- О, л в- я+ 1 и вернуться к шагу Т2. $ 6. докажем по индукции, что путем к числу 2'в+2" + .+2" при ее > ет » ет > 0 является последовательность 1, 2, 2т, ... 2'в 2" +2" . 2" +2" + +2". Кроме того, последовательность показателей степеней на каждом уровне рассортирована в убывающем лексикографическом порядке. 7. Бинарный метод и метод множителя требуют при вычислении яв" на один шаг больше, чем при вычислении л"; метод дерева степеней требует не более одного дополнительного шага. Следовательно, (а) 1о 2в; (Ь) 33 2в; (с) 23 2"; » = О, 1, 2, 3, .... 8, Дерево степеней всегда включает узел 2ти на уровень ниже ш, кроме случаи, когда он уже встречалсв на том же нли на одном из предыдущих уровней; кроме того, дерево всегда включает узел 2ти + 1 на один уровень ниже узла 2ти, если только его нет яа том же уровне или на одном из предыдущих.
(Неверно, что 2ит является дочерним узлом ти в дереве степеней для всех ти; наименьший пример, когда это не так, — ит = 2138, который появляется на уровне 15, в то время как узел 4276 появляется на уровне 16 в другом месте. В действительности 2ти иногда встречается даже на том же уровне, что и ти; наименьший такой пример — ти = 6029.] 9. Начнем с установок тУ +- и, Я в- з и У с- 1 длв 1 < д < ш, где д — нечетно; в общем случае получим я" = УтУввУвв...
У,т Я» после выполнении алгоритма. Полагая, что Х > О, установим й +- тт' шоб ит, тт' т- [Х/из]. Затем, если й = О, установим Я +- Я~ и повторим шаг; в противном случае, если й = 2тд, где д — нечетно, установим Е +- Ет", Ут +- Ут Я и, если Кд > О, установим Е +- Ет' т и повторим шаг. И наконец установим 1в +- Ув Уввт для й = ти — 3, ти — $, ..., 1. Искомый ответ — Ут(УвУв...У -т)т. (Около ш/2 умножений представляют собой умншкения на 1.) 10.
Примените представление РаИКИТ, обсуждавшееся в разделе 2,3.3: используйте табли- цу р[У], 1 < У < 100, такую, что р(1] = 0 и р(у] является номером узла, расположенного непосредственно над У для т' > 2. (Тот факт, что калгдый узел этого дерева имеет степень, не превышающую двух, не влияет на эффективность представления. Это только улучшает внешний вид дерева, используемого в качестве иллюстрации,) 11. 1, 2, 3, 5, 10, 20, (23 или 40), 43; 1, 2, 4, 8, 9, 17, (2б или 34), 43; 1, 2, 4, 8, 9, 17, 34, (43 или 58), 77; 1, 2, 4, 5, 9, 18, Зб, (41 или 72), 77.
Если бы любой из двух последних путей имелся в дереве, и = 43 было бы невозможно, поскольку дерево должно содержать либо 1, 2, 3, 5, либо 1, 2, 4, 8, 9. 12, такое дерево невозможно, поскольку 1(п) з«Г(п) для некоторых п. 13. для случая 1 используйте цепочку типа 1, за которой следует 2л+с+2в+с+2л+ 2в, либо воспользуйтесь методом множителя. Для случая 2 испачъзуйте цепочку типа 2, за которой следует 2л+с+'+ 2 + + 2л+ 2 . Для случая 3 используйте либо цепочку типа 5, эа которой следует 2' + 2' ', либо метод множителя. Для случая 4 и ы 135 . 2о, так что можно использовать метод множителя. 14.
(а) Легко убедиться, что наги г — 1 и г — 2 не являются малыми. Это позволяет считать, что шаг г — 1 является малым, а шаг г — 2 — нет. Если с = 1, то Л(а з) = Л(а„«), так что Ь = 2: а поскольку 4 < м(а,) = и(а„-«)+о(а„-«)-1 < и(а„-,)+1, имеем и(а„-«) > 3„ делая шаг г — 1 звездным (чтобы цепочва ао, ац ..., а,-з, а„з не включала только один малый шаг). Тогда а, « = а,-з + а, з для некоторого д, и, если заменить а, з, а, м а„ на а„з, 2а, з, 2а„з + а, з = а„получится другая цепочка-контрпример, в которой шаг г является малым.
Однако это невозможно. С другой стороны, если с > 2, то 4 < и(а,) < и(а, з)+о(а, «) — 2 < и(а,-~); следовательно, о(а, ~) = 4, з(а -«) =-2 и с = 2. Это легко приводит к невозможной ситуации, возникающей в результате рассмотрения шести типов из доказательства теоремы В. (Ь) Если Л(а,-«) < гл — 1, имеем с > 3, так что з (а -«) + в (а„-ь) > 7 согласно (22); поэтому как а(а,-«), так н и(а з) оба > 3.
Все малые шаги должны быть < г — /с, а Л(а„«) = пз — Ь+ 1. Если Ь > 4, необходимо иметь с 4, й = 4, гг(а, «) = з (а, з) = 4. Таким образом, а, ч > 2 +2 '+2 зиа„~ должнобытьравно2 +2 '+2 з+2'" з, но из а -4 > -'а, ~ вытекает, что а,-з = 8а, з.
Знашт, 5 = 3 и а„-з > 2 + 2 Посколъку а„з < 2™ и а з < 2 ', шаг г — 1 должен быть удвоениелп однако шаг г — 2 не является удвоением, так как а, ~ з«4а, з. Кроме того, поскольку и(а, з) > 3, г — 3 является звездным шагом и из а,-з = а,-з + а -з должно следовать, что а, з = 2 Поэтому необходимо получить а, з = а -з+а -4. Как и в подобном случае, рассмотренном в тексте раздела, единспзенная возможность заключается в том, чтобы выполнялось а,-з = 2 "+2 з а «=2 з+2 +2+ +2 а, з =2 +2 '+2лт~+2«+',ноиэто невозможно.
15. Ахим Фламменкамп (Ас51ш р(азпшепЫыпр) (Ебр1ошагЬеы 1п Ма«Ьешабсз (В!е)е1е!д Шцтегз1«у, 1991), Разт 1] показал, что все числа п с Л(п) + 3 = 1(п) < Г(п) имеют вид 2л + 2в + 2 + 2 + 2в, где А > В > С > 11 > В и В+ Е = С+ Вт более того, они точно описываются как не соответствующие ни одному из восьми шаблонов (здесь ]е] < 1); 2л + 2л-з + 2с + 2с-з + 2зс+з-л 2л+2л-«+2с+2о+2с«о+~-л 2л+2в+2гв-л+з+2«в+з-л+2зв+з-зл 2л+2в+2зв-л+ +2о+2вео+ -л 2л + 2в + 2в-з + 2о + 2о-~ 2л+2в+2в-з+2о+2о-з (А > В+ц 2я + 2в + 2С + 2«в+ л + 2в+с+к-л 2л + 2В + 2с + 2В+с«е-л + 2«ст — л 16.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
