AOP_Tom2 (1021737), страница 142
Текст из файла (страница 142)
! /~ й /~ /~ /~ ! ! ! /~ 19 гв 21 гг гз 4о 27 зо гз 4в 26 з4 зб зз 64 ! Й /'1 ! ! /'1 /'1 /'1 ! /'1 /'1 /'1 /'1 /'1 3829 56 314244 46 41 ВО 395445 60 50 51 96 35 52 43 68 37 72 49 бб 65 ! ! /'1 ! ! ! /'1 ! /'1 ! ! ! /'1 ! ! /'1 ! ! /'1 ! ! ! ! ! ! 765857596284 68 47928283857855906375100 53 97 99 70 61 77 86 69 74 73 98 67 81 !!! !! ! 71 87 89 94 93 95 79 91 Рнс. 15. Дерево, минимизирующее число умножений для и < 100. Можно также сформулировать и1-арный метод в терминах аддитивных цепочек.
Рассмотрим случай, когда т = 2", изапип1ем и = 1(от'+4т1 '+ 4111 в тичной системе счисления. Соответствующая аддитивная цепочка принимает вид 1,2,3,...,ти — 2,т — 1, 24(о, 44(о,..., тоо, т4~о + с(1; 2(тб(о+А),4(т110+111),, т(т~10 + 111), т с(о + тА + А т'4(0 + т' '«1 + . + 4о (4) Ее длина равна т — 2+ ()4+ 1)1, и зачастую ее можно уменьшить, удалив некоторые элементы из первой строки (те, которые не встречаются среди коэффициентов 4(13 а также элементов из 21(о, 44(о, ..., которые уже имеются в первой строке).
Если какое-либо оу равно нулю, последний член в правой части соответствующей строки, конечно, может быть опущен, Кроме того, как обнаружил Э. Г. Тюрбер (Е. 6. Т11нгЬег) (1)о)4е Май. Х 40 (1973), 907-913], можно опустить все четные числа (за исключением 2) в первой строке, если привести значения вида 111/2' в вычислении е шагамн ранее. Простейший случай т-арного метода — двоичный (бинарный) метод (т = 2), когда общая схема (4) упрощается да правила «Я и Х", упоминавшегося в начале этого раздела: бинарная адцитивная цепочка для 2п представляет собой бинарную алдитивную цепочку для п с добавлением числа 2п; для 2и+1 она является бинарной аддитивной цепочкой для 2и с последующим числом 2п + 1.
Из бинарнага метода можно заключить, что 1(2" + 2" + . + 2" ) < ео + 4, если ео > е, » . е, > О. (3) Определим теперь две вспомогательные функции для удобства последующего обсу- ждения: (б) (7) Л(п) = ~18п); и(п) = количество единиц в двоичном представлении и. Таким образом, Л(17) = 4, и(17) = 2. Эти функции могут быть определены следую- щими рекуррентными соотношениями: (8) (9) Л(1) = О, и(1) = 1, Л(2п) = Л(2п + 1) = Л(п) + 1; и(2п) = и(п), и(2п+ 1) = и(п) + 1. С их помощью можно записать, что бинарные зддитивные цепочки для п требуют ровно Л(п) + и(п) — 1 шагов, а (5) принимает вид 1(п) < Л(п) + и(п) — 1.
(1О) Специальные классы цепочек. Не теряя общности, можно положить, что ад- дитивные цепочки вазрасшающое, т. е. 1 = ае < аг < аг « а,. = п. Если два числа из а одинаковы, то одно из них может быть опущено. Можно также переупорядочить последовательность (1) в порядке возрастания и удалить члены, ббльшие, чем и, не нарушая свойство аддитивной цепочки (2), В дальнейшем будем рассматривать только возрастающие цепочки, не оговаривая это соглашение явно.
Теперь удобно определить несколько специальных терминов, относящихся к аддитивным цепочкам. По определению для 1 < 1 < г (12) а, =а +аг для некоторых у и А, О < А < у' < ь Если это соотношение выполняется для более чем одной пары (у, А), полагаем, что у — наибольшее из возможных. Будем говорить, что шаг 1 цепочки (11) — удвоение, если у = й = 1 — 1. Тогда а; имеет максимально возможное значение 2а; ы которое может следовать эа возрастающей цепочкой 1, аы ..., а; и Если д (но не обязательно А) равно 1 — 1, будем говорить, что шаг 1— звездный шаг (ггаг г1ер).
Важность звездных шагов поясняется ниже. И наконец, будем говорить, что шаг 1 представляет собой малый шаг, если Л(а;) = Л(а, ~). Поскольку а; г < а; < 2а, ы величина Л(а;) всегда равна либо Л(а; г), либо Л(а; г) + 1; отсюда следует, что длина г любой цепочки (11) равна Л(п) плюс количество малых шагов. Эти типы шагов удовлетворяют ряду элементарных соотношений.
Шаг 1 всегда представляет собой удвоение. Ясно, что удвоение — звездный шаг, но никогда не малый шаг. За удвоением всегда следует звездный шаг. Кроме того, если шаг 1 иг малый, то шаг 1+ 1 является либо малым, либо звездным, либо и тем, и другим одновременно. Рассматривая данное утверждение с друтой стороны, получим, что если шаг 1+ 1 не является ни малым, ни звездным, то шаг 1 должен быть малым. Звездной цепочкой (з1аг сЬаш) является аддитивная цепочка, включающая только звездные шаги. Это означает, что каждый член а, представляет собой сумму а; ~ и предшествующего ему ам простой "компьютер", упоминавшийся ранее, после (2), в звездной цепочке использует только две операции, ЯТА и АРР (без РРА), поскольку каждый новый член последовательности использует предыдугций резуль- тат, находящийся в аккумуляторе.
Большинство рассмотренных здесь аддитивных цепочек являются звездными. Минимальная длина звездной цепочки для и запи- сывается как 1" (и); понятно, что (13) 1(п) < 1'(и). Теперь можно иывести несколько нетривиальных фактов об аддитивных цепочках. Сначала покажем, что в цепочке должно быть весьма много удвоений, если г не слишком сильно отличается от Л(п).
Теорема А. Если адднгивная цепочка (11) включает ат удвоений и т = г — а' неудяоеннй, то п < 2 г'7+з (14) Использованный нами метод доказательства показывает, что неравенство (14) является "наилучшим возможным" при указанных предположениях; аддитивная цепочка 1, 2,..., 2т-~, 2~-~Уз, 2'т-~Е»т..., 2»-~Е7».з (15) имеет г( удвоений и 7" иеудвоений.
Следствие. Если адднтияная цепочка (11) включает 7' неудвоеннй и з малых шагов, то з < 7' < 3. 271а (16) Двказатпельстпвв. Очевидно, что з < 7'. Имеем 2~т") < и < 2~ »Р7+з < 2 фт = 2Ц"т+'(фт2)т поскольку Н+ 7' = Л(п) + з и гу»з < 2фт при 7' > О. Значит, 0 < з!п2+ 7" 1п(ф/2) и (16) следует из того факта, что!п27'1п(2/ф) ж 3.2706. 1 Значения 1(и) для специальных и. Легко иоказать прн помощи индукции, что а» < 2', и, таким образом, 1и и < г в любой аддитивной цепочке (11).
Следовательно, (17) 1(и) > ((ба), Эта нижняя граница вместе с верхней границей (10), полученной при помощи би- нарного метода, дают значения 1(2 )=А; 1(2" + 2 ) = А + 1, если А > В. (18) (19) Двказатпельстпво. Используя индукцию по г = т1+ /, находим, что (14) истинно при г = 1.
При г > 1 имеется три случая. Если шаг г — удвоение, то -'и = а„г < 2" згу+з, следовательно, (14) выполняется. Если шаги г н г — 1 не нвляются удвоениями, то а„т < 2~ 'Гу+з и а„з < 2~ 'Гу+т, следовательно, п = а, < а -т + а -з < 2~ '(Гу+з + гу+т) = 2~ 'Гу+з по определению последовательности Фибоначчи. И наконец, если шаг г — неудвоение, а шаг г — 1 — удвоение, то а, з < 2 гудат и и = а„< а, т + а, з = За„з.
Теперь 2Еу+з — ЗГу+з —— Ру+т — гу > 0; з-3 следовательно,п < 2» »ЕГ+з для всех случаев. 1 ,вкругими словами, бинарный метод является оптимальным при и(п) < 2. При по- мощи некоторых вычислений можно расширить эти формулы для случая, когда о(и) = 3. Теорема В. Доказапгельспгво.
В действительности можно доказать более строгий результат, который будет использован позже в этом разделе. Все адднтивные цепочки с ровно одним малым шагом принадлежат одному яз следующих шести типов (здесь все шаги, указанные как "... ", являются удвоениями). Тнп 6. Непосредственные вычисления показывают, что эти шесть типов исчерпывают все возможности. Согласна следствию из теоремы А имеется не более трех неудвоений при наличии одного малого шага; этот максимум встречается талька в последовательности третьего типа. Все приведенные выше цепочки — звездные, за исключением типа 6, когда В < А — 1.
Теперь теорема следует из того факта, что 1(2л+2в 2с) < 4+2 и 1(2л + 2н + 2с) должно быть больше, чем А+ 1, поскольку ни один из шести возможных типов не имеет и(п) ) 2. ! (Э. де )Конкиэрес (Е. бе3опцшегеэ) в 1894 году без доказательства указал, что 1(п) > Л(п) + 2, когда о(п) > 2. Впервые теорема В появилась в работе А. А.
61о!а, М. У. БпЬЬагао апс1 М. Впйппапипа, Вийе Маг)г. Х 29 (1962), 481-487.) Вычислить 1(2" + 2н + 2с + 2с) при А ) В ) С > Р более сложно. По бинарному методу эта величина не превышает А + 3, а в соответствии с доказательством теоремы В ана не меньше, чем А+ 2. Величина А+ 2 является допустимой, так как известно, что бинарный метод не оптимален при п = 15 илн и = 23. Как мы сейчас увидим, при ы(п) = 4 можно дать полное определение поведения этой величины. Теорема С.
Если и(и) > 4, то1(п) > Л(п) +3 за исключением следующих случаев, когдаА>В)С>Рн1(2 +2 +2 +2 )равноА+2. Случай 1. А — В = С вЂ” Р. (Пример: п = 15.) Случай 2. А — В = С вЂ” Р + 1. (Пример: п = 23.) Случай 3. А — В = 3, С вЂ” Р = 1. (Пример: п = 39.) Случай 4. А — В = 5,  — С = С вЂ” Р = 1. (Пример: п = 135.) Тип 1. Тип 2. Тип 3. Тип 4.
Тнп 5. 1(2л+2н+2с) = А+2, если А > В > С. (20) 1 2л 2л+2в 2л+с+2н+с.А>В>О,С>О. 1 2л 2л+2н 2л+г+2в 2л~ьс+г+2втс. 4)В)0 С)0 1 2л 2л+2л — г 2л+г+ 2л-г 2л+г 2л+с. А > 0 С > 2 1 2л 2л+ 2л — г 2л+г+2л 2л+г 2л+с. А > 0 С > 2 2л 2л + 2л-г 2л+с + 2л+с-г 2л+с+г + 2л+с-г 2л+с+с+г+2л+с+с-г. А > 0 С > 0 Р > 0 1 2л 2лл 2в 2л+г 2л+с.А>В>0 С>1 Доказательствоо. Когда 1(п) = Л(п) -ь 2, существует авдитивная цепочка для и, имеющая только два малых шага.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
