условие важно для правильной работы алгоритма, так как на шагах D2 и D3 никогда bij + 1] не уменьшается чаш;е, чем D[j] .

4. (1-г-----г)а(г) = 1 в силу (3). Далее, «(г) = „Дап + Ь„ + Сп + dn + вп)г" =

(г +----h z)a{z) + {z +----h z)a{z) +----h za{z) = {5z + 4г + Зг + 2z* + z)a(z).

5. Пусть gp{z) = (г- 1)/р(г) = 2+ -2гР+1 и hp{z) = z+-lz. Теорема Руше (Rouche) [J. Ecote Poiyteciinique 21,37 (1858), 1-34] утверждает: hp{z) и gp{z) имеют равное число корней внутри окружности г = 1 + б при условии, что /гр(г) > \hp{z) - gp{z)\ = 1 на окружности. Если > е > О имеем \hp{z)\ > (1 + 6)(1 - е) > (1 + <~)(1 - ф~) = 1. Следовательно, др имеет р корней с абсолютной величиной < 1. Они различны, так как gcdigpiz),gpiz)) = gcd(зp(г), (р+ 1)г - 2р) - 1. [АММ 67 (1960), 745-752.]

6. Положим Со = -ар(а"")/д(а~). Тогда p{z)lq{z) - со/(1 - az) аналитична в круге \z\ < R для некоторого R > следовательно, коэффициенты [г"]р(г)/д(г) = соа" + 0(Я-"). Значит, 1п5 = nlna + In со + 0((аЛ)-"); а из п = (1п5/1па) + 0(1) следует, что 0((аЯ)"") = 0(5"). Аналогично положим ci = a2p(a-i)/g(a-i)2, сг = -ap{a-) g(a-i)2 + ар(а-1д"(а-1)/д(а-1)Зи рассмотрим p{z)/q{z) -ci/(l - az) -С2/(1 - аг).

7. Пусть ар = 2х и г = -1/2*". Тогда х"" = х** + г и в результате получается сходящийся ряд ар = 2 ,к>о ("/)«V(1 -кр) = 2- 2" - р2-- +0{р2-), как следует из формулы 1.2.6-(25).

Замечание. Отсюда следует, что величина р в упр. 6 становится примерно равной log4 5 с ростом р. Аналогично для табл. 5 и 6 коэффициент с приближается к 1/([ф+2) In ф) при большом числе лент.

8. Очевидно, n" = 1, n} = О для т < 0. Рассматривая все варианты для первого

слагаемого, получаем TVm = Am-i -----•m-p при т > 0. Следовательно, TV = Flp-i

[Lehrbuch der Combinatorilc (Leipzig: Teubner, 1901), 136-137.]

9. Рассмотрим положение крайнего слева нуля, если таковой имеется; находим, что АГт = Fm+p- Замечание. Существует простое взаимно однозначное соответствие между такими последовательностями нулей и единиц и изображениями т + 1, рассмотренными в упр. 8: добавьте О к правому концу последовательности и посмотрите на положение всех нулей.

jm > р, то п < FJ. Доказательство. Этот результат очевиден, если m < р. В противном случае пусть к есть минимальное число, такое, что jk > jk+i +1; имеем fc < р и по индукции tl ++ it! < следовательно, п< FJ + + Flf , , < РД.

P/f + • • + FJ является таким представлением, где ji >

Искомое теперь может быть доказано индукцией по п. Если п > О, то пусть j будет максимальным числом, таким, что FJ < п. Лемма показывает, что любое представление п должно состоять из FJ плюс представление п - F-\ По индукции п - Fj имеет единственное представление нужного вида, и это представление не содержит всех чисел FJZ\,..., P/p+i, так как j максимально.

Замечания. Случай, когда р = 2, упомянутый в работе Е. Zeckendorf, Simon Stevin 29 (1952), 190-195, был рассмотрен в упр. 1.2.8-34. Имеется простой алгоритм перехода от представления п к представлению п+1, работающий с последовательностью нулей и единиц Cj ... cico, такой, что п = j-j+p- Например, если р = 3, мы смотрим на правые цифры и заменяем ... О на ... 1, ... 01 на ... 10, ... 011 на ... 100; затем осуществляем "перенос" влево, если это необходимо, заменяя ... 0111... на ... 1000 .... (См. последовательности нулей и единиц в упр. 9 в том порядке, в котором они записаны.) Подобная система счисления была исследована в работе W. С. Lynch, Fibonacci Quarterly 8 (1970), 6-22. Автор приводит

очень интересный способ ее применения для управления и фазой распределения, и фазой слияния многофазной сортировки.

12. fc-я степень содержит точные распределения для уровней с fc - 4 до fc-ro в последовательных строках с наибольшими элементами справа.

13. Доказывается индукцией по уровню.

14. (а) п(1) = 1, поэтому будем считать, что fc > 1. Закон Тпк - T(„ i)(a, i) + • • -f T(„-P)(k-i) показывает, что Тпк < Tn+l)k тогда и только тогда, когда Г(„ я)(д, 1) < Тп(к-1)- Пусть г - произвольное положительное целое и пусть п - минимальное число, такое, что Tn-r)(k-l) > Тцк-ху, тогда Tn-r)k-l) > Tn(k-i) Для всех п > п, поскольку это тривиально для п > п{к - 1) + г, а иначе T(n-r)(k-i) > T(n-r)k-i) > ТпЦк-i) > Tn(k-i)- (b) To же рассуждение при г = п - п показывает, что T„t < Тпк влечет за собой Tni j)ki < Tn-i)k для всех j > 0. Значит, из рекуррентного соотношения следует, что Tn-j)k < Tn-j)k Для всех j > О и fc > fc. (с) Пусть i{S) - наименьшее п, такое, что En (5) принимает свое минимальное значение. Требуемая последовательность Мп суш;ествует тогда и только тогда, когда (.{S) < £{S + 1) для всех 5. Предположим, что п = e{S) > e{S -fl) = п, так что En(S) < Е„/(5) и Еп(5 -Ы) > En(5 + 1). Суш;ествует наименьшее 5, такое, что Еп(5) < Е„(5); имеем т = Еп(5) - Еп(5 - 1) < EniS) - En,(5 - 1) = т. Тогда ЕГ=1пк < 5 < ZTink; следовательно, существует некоторое fc < т, такое, что Тпк < Тпк- Аналогично имеем I = Еп(5--1) - En (5) > En (5 -fl) - En (5) = I; значит, ELi Tn > 5 -Ь 1 > ELi nk- Поскольку I > m > m, существует некоторое fc > m, такое, что Гпа, > Тпк- Но это противоречит п. (Ь).

15. Эта теорема была доказана Д. Э. Зэйвом (D. А. Zave), статья которого упоминается в тексте раздела.

16. Д. Э. Зэйв показал, что число вводимых (и выводимых) записей равно 51ogy j S -Ь ISlogr.logr-i S + 0{S).

17. Пусть Г = 3; Аи{х) = 6х« + 35х + 56х* + --, Bii(x) = + 15х + 35х* + Tii{x) = 7х -Ь бОх -f 91х* -f 64х® -Ь 19х° -f 2х\ Оптимальное распределение для 5 = 144 требует 55 серий на Т2, Это обязательно приводит к неоптимальному распределению для 5 = 145. Д. Э. Зэйв изучил процедуры такого вида, близкие к оптимальным.

18. Пусть 5 = 9, Г = 3. Рассмотрим следующие две схемы.

(Еще один способ улучшения "оптимального" многофазного метода состоит в пересмотре того, в каких местах выводной ленты появляются фиктивные серии на каждой фазе слияния. Например, результат слияния 01 с 01 можно было бы рассматривать как 2о202 вместо 02. Таким образом, остается много нерешенных вопросов, связанных с оптимальностью.)

20. а(г) = 1/(1 -z-z- г"), t{z) = {3z + 3z + 2z + z*)/{l - z- z- г"), En>i Гп(х)г" =

x{3Z + 3z + 2z + z)/il - x{z + z + z)). Dn = An-l + 1, Cn = An-lAn-2 + 1, Bn = An-lAn-2An-3 + 1, An = Ап-2Ап-зАп-4 + 1-

21. 333343333332322 3333433333323 33334333333 3333433 333323 T5

22. tn - tn-i - tn-2 = -1 + 3[nmod3 = l]. (Это соотношение, подобное соотношению Фибоначчи, следует из того, что 1 - - 2z - г"* = (1 - фг){1 - $z){l - loz){1 - ujz), где

lj = 1.)

23. Вместо (25) длины серий в течение первой половины п-й фазы слияния будут s„, а в

течение второй половины - tn, где S„ = tn-2 + tn-З + «п-З + «п-4, tn = tn-2 + Sn-2 +

Sn-3 + Sn-4- Здесь мы полагаем = <п = 1 при п < 0. [В общем случае, если Vn+i является суммой первых 2г членов из Un-i + • • • + Vn-p, имеем = tn = tn-2 + • • • + tn-г + 2tn-r-i + tn-r-2 + • • • + tn-p. Если Vn+l есть сумма первых 2г - 1 членов, то

Sn = tn-2 Н-----h tn-r-1 + Sn-r-l Н-----h Sn-P, tn = tn-2 H-----h tn-r + Sn-r H-----h Sn-P-]

Вместо (27) и (28)

An = iUn~lVn-lUn-2Vn-2Un-3Vn-3Un-4Vn-4) + 1, . . . ,

Dn = {Un-iVn-i) + l,

En={Un-2Vn-2Un-3) + l, Vn+l=iUn-lVn-lUn-2) + l,

Un = iVn-2Un-3Vn-3Un-4Vn-4) + 1.

25. 1 1* - 1* 1" 1" R 1*2" 1-2 R

R 816 8 8°

16° R 8 -

16 16 8° R

R 16 - 24°

16 16 R 24°32°

16° 16° 32 (R)

26. Если сортируются 2" начальных серий, то во время слияния обрабатываются п 2"-е серии. Каждая половина фазы (за немногими исключениями) сливает 2"" и перематывает 2"~. Если сортируются 2" + 2"~ начальных серий, то обрабатываются во время слияния