Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 2) (1119454), страница 34
Текст из файла (страница 34)
Большинство рассмотренных здесь аддитивных цепочек являются звездными. Минимальная длина звездной цепочки для и запи- сывается как 1 "(и); понятно, что (13) 1(п) < 1"(и). Теперь можно вывести несколько нетривиальных фактов об аддитивных цепочках. Сначала покажем, что в цепочке должно быть весьма много удвоений, если г не слишком сильно отличается от Л(п). Теорема А. Если здлнгнвнал цепочка (11) включает Ы удвоений л / = з' — с( неудвоенлй, то п < 2 Ру+з. (14) Использованный нами метод доказательства показьвает, что неравенство (14) является "наилучшим возможным" при указанных предположениях; адднтивная цепочка 1,2,,2 ',2 Рз,2 Рз, ",2" 'Ру+3 (И) имеет 4 удвоений и / неудвоений.
Следствие. Если аддя тинная цепочка (11) включает / неудвоеннй и з малых шагов, з < / < 3.271з. (16) Доказательство. Очевидно, что з < /. Имеем 2М"1 < и < 2~ ~Руане < 2~ФУ = 2 ~"1~'(Ф/2)У~ посколькУ 4+ / = Л(п) + з и Ру+з < АУ пРи /'> О, Значит, 0 < з 1п 2+ /1п(Ф/2) и (16) следует из того факта, что 1п 2/!п(2/ф) зз 3.2706, $ Значения 1(п) дли специальных зз. Легко показать при помощи индукции, что а; < 2', и, таким образом, 1я и < г в любой аддитивной цепочке (11). Следовательно, !(п) > ~)йп1. (17) Эта нижняя граница вместе с верхней границей (10), полученной при помощи бинарного метода, дают значения Х(2 )=А; 1(2 + 2в) = А+ 1, если А > В.
(18) (19) Доказапзельсшео. Используя индукцию по г = 4+ /, находим, что (14) истинно при г = 1. При г > 1 имеется три случая. Если шаг г — удвоение, то ~1п = а, з < 24 "Руез, следовательно, (14) выполняется. Если шаги г и г — 1 не являются удвоениями, то а„, < 2~ 'Ру+з н а, з < 2~ 'Ру+з," следовательно, и = а, < а -з + а -з < 2~ '(Ру+г + Ру+з) = 2~ 'Ру+з по определению последовательности Фибоначчи. И наконец, если шаг г — неудвоенне, а шаг г -1 — удвоение, то а, з < 24 зРуез и и = а„< а„г + а, з = За, з.
Теперь 2Ру+з — ЗРу+з = Ру+з — Ру > 0; следовательно, п < 2" 'Ру+з для всех случаев. $ Другими словами, бинарный метод является оптимальным при и(п) < 2. При помощи некоторых вычислений можно расширить зти формулы для случая, когда и(п) = 3. Теорема В. 1(2А + 2в + 2с) = А + 2, если А > В > С. (гО) Доказательсшво. В действительности можно доказать более строгий результат, который будет использован позже в этом разделе. Все аддптналые цепочки с ровно одним малым шагом принадлежат одному из следующих шести типов (здесь все шаги, указанные как "...", являются удвоениями).
2А 2А+2Н 2А+С+2В+С. А > В > О Тнп 2. 1,..., 2А 2А+2я 2А+~+2н 2"+с+'+2л+с; А > В >О, С>О. Тнп 3 1 2А 2А+2А-~ 2А+1+2А-~ 2Ает 2А+с. 4> О С > 2 Тии 4 1 2А 2А+ 2А-! 2А+1 + 2А 2А+т 2А+с. 1 > О Тнп 5 1 2А 2А+2А-1 2А+с+2А~.с-~ 2А+с+1+ 2А+с-з ..., 2 + + +'+2" + -', А > О, С1 О, В > О. Тип 6. 1,...,2А,2А+2в,2А+1,, 2А+с.А>В>О,С>1. Непосредственные вычисления покэзывают, что этн шесть типов исчерпывают все возможности.
Согласно следствию из теоремы А имеется не более трех неудвоений при наличии одного малого шага; этот максимум встречается только в последовательности третьего типа. Все приведенные выше цепочки — звездные, за исключением типа 6, когда В с А — 1, Теперь теорема следует из того факта, что 1(2А+ 2в +2с) с А+ 2 и 1(2А + 2н + 2с) должно быть больше, чем А + 1, поскольку ни один из шести возможных типов не имеет и(п) > 2, ! (Э. де Жонкиэрес (Е.
сне Лопчшйгеэ) в 1894 году без доказательства указал, что 1(п) > Л(п) + 2, когда и(п) > 2. Впервые теорема В появилась в работе А. А. Сю!а, М. Ъ'. ЯпЬЬагао влб М. 9цйппапапа, Вийе Масй. Х 29 (1962), 431-437.) Вычислить 1(2А + 2н + 2с + 2Р) при А > В > С > В более сложно. По бинарному методу эта величина не превышает А + 3, а в соответствии с доказательством теоремы В она не меньше, чем А+ 2.
Величина А+ 2 является допустимой, так как известно, что бинарный метод не оптимален при п = 15 илн и = 23. Как мы сейчас увидим, при и(п) = 4 можно дать полное определение поведения этой величины. Теорема С. Если и(п) > 4, то((п) > Л(п) +3 за лсключенпем следующих случаев, когда А > В > С > В и 1(2А + 2в + 2 + 2 ) равно А + 2.
Случай 1. А — В = С вЂ” В. (Пример: и = 15.) Случай 2. А — В = С вЂ” В+1, (Пример: и = 23.) Случай 3. А-В = 3, С вЂ” В = 1. (Пример: и = 39.) Случай 4. А — В ж 5,  — Сы С вЂ” В = 1. (Пример: и = 135,) Доказательсрлво. Когда 1(п) = Л(п) + 2, существует аддитивная цепочка для и, имеющая только два малых шага. Она состоит из одного из шести типов, перечисленных в доказательстве теоремы В, малого шага н последовательности немалых шагов. Будем говорить, что и "специально", если и = 2л + 2в + 2С + 2~ для одного из четырех случаев, перечисленных в теореме.
Можно получить адаптивные цепочки требуемого вида для каждого специального и, как показано в упр. 13, поэтому остается доказать, что не существует цепочек с точно двумя малыми шагами, содержащих любые элементы с и(а;) > 4, за исключение»» специального аи Назовем цепочкой-контрпримером аддитивную цепочку с двумя малыми шагами, такую, что и(а„) > 4. но а„не является специальным. Если цепочка-контрпример существует, то рассмотрим цепочку 1 = ао < а» « ° . а, = п наименьшей возможной длины.
Тогда шаг г не является малым шагом, поскольку ни один из типов цепочек из доказательства теоремы В не может предшествовать малому шагу с и(п) > 4, за исключением специального и. Кроме того, шаг г не является удвоением, так как более коротким контрпримером была бы цепочка ао,..., а, м Наконец, шаг г является звездным, так как иначе цепочка ао, ..., а„г, а„представляла бы собой более короткую цепочку-контрпример. Таким образом, а„ = а, » + аг ы й > 2, и Л(а„) = Л(а„ ») + 1. (21) Обозначим число переносов, встречающихся при сложении а„-» и а„-» в двоичной системе счисления по алгоритму 4.3.1А, как с. Используя фундаментальное соотношение и(а ) = и(а„, ) + и(а„») — с, (22) можно доказать, что шаг г — 1 не являегсл малым (см.
упр. 14). Пусть т = Л(а„-г), Поскольку ни г, ни г — 1 не является малым шагом, с > 2; равенство с = 2 может быть справедливо только тогда, когда а„» > 2 + 2™ 1. Теперь предположим, что г — 1 — не звездный шаг. Тогда г — 2 — малый шаг и ао, ..., а,-г, а, » представляет собой цепочку с только одним малым шагом. Следовательно, и(а„») < 2 и и(а, г) < 4.
Соотношение (22) может выполняться, только если и(а„) = 4, и(а, ») = 2, 1» = 2, с = 2, и(а„г) = 4. Из с = 2 можно заключить, что а„г = 2"'+ 2~ ', следователыю, ао, аы ..., а, г = 2 ' + 2~ г является аддятив»»ой цепочкой с только одним малым шагом и эта цепочка должна быть первого типа, так что а„относится к случаю 3. Таким образом, г — 1 является звездным шагом.
Теперь предположим, что а„» — — 2'а„» для некоторого г. Если и(а„») < 3, то в соответствии с (22) с = 2, (р = 2 и а„должно относиться к случаю 3. С другой стороны, если и(а„») = 4, то а„г будет специальным, и при рассмотрении каждого случая легко видеть, что а„также относится к одному из четырех случаев.
(Случай 4 возникает, например, когда а, » = 90, а„» —— 45 или когда а„, = 120, а„» = 15.) Поэтому можно заключить, что а, » ф 2'а, » для любого б Мы доказали, что а„ » = а„ г + а„ для некоторого а > 2. Если 1р = 2, то д > 2 и ао а» ° , а„ г, 2а„ г, 2а„-г + аь р = а, представляет контрпример последовательности, у которой й > 2. Поэтому можно считать, что к > 2. Теперь предположим, что Л(а„») = т — 1. Случай, когда Л(а„») < т — 1, может быть исключен в результате подобного рассмотрения, квк показано в упр, 14. Если й = 4, то и г -2, и г — 3 являются малыми шагами; следовательно, а„р — — 2 и (22) невозможно.
Поэтому й = 3; щаг г — 2 является малым, и(а„э) = 2, с = 2, а, ~ > 2™ + 2 ~ и и(а„~) = 4. Должно существовать как минимум два переноса при сложении чисел а„э и а„~ — а„э. Значит, и(а, з) = 4 н аг а (будучи специальными > -'а, г) имеетвид2 '+2 э+2е ~+2кдлянекоторогод, Теперь а„~ равно либо 2'"+2 ~+2"+'+24, либо 2 +2 '+2"+з+2а ы и в обоих случаях а„з должно бьггь равно 2 '+ 2 з, так что а, относится к случаю 3. $ Э. Г. Тюрбер (Рас!бс Х Май, 49 (1973), 229-242) расширил теорему С для показа того, что 1(п) > Л(п) + 4 при и(п) > 8. Представляется обоснованным предположение, что 1(и) > Л(п) + (8и(п) в общем случае, поскольку А.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
