Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 2) (1119371), страница 92
Текст из файла (страница 92)
Тогда лр+' = л"'+ л и в результате получается сходив!яйся ряд ар = 2 х ~ь>е [' ь Р) ль/(1 — Ьр) = 2 — 2 " — р2 ле ' + 0(!Р2 лР), кэк следует из формулы 1.2.6-(25). Замечание. Отсюда следует, что величина р в упр. 6 становится примерно равной !о84 3 с ростом р, Аналогично для табл, 5 и б коэффициент с приближается к 1/((6+2) 1п Ф) при большом числе лент. 8. Очевидно, Агар~ = 1, Аг'р~ ы 0 для гл < О. Рассматривая все варианты для первого слагаемого, получаем №~~! = Аь!Р! ь+ +Ар„э~ р прн иь > О.
Следовательно, Л;!Щ = Р!Р+! [йейгбпсЬ ь(ег СотЫпагоп!г (Ье1ржб. "ТевЬпег, 1901), 136-137.] 9. Рассмотрим положение крайнего слева нуля, если таковой имеется; находим, что К1 ~ = Р~~„' . Замечание. Существует простое взаимно однозначное соответствие между такими последовательностями нулей и единиц и изображениями гл + 1, рассмотренными в упр. 8: добавьте О к правому концу последовательности и посмотрите на положение всех нулей. 10. Лемма. Если и = Р)р! + .. + Р)р~ является таким представлением, гд» уь > .
> у > р, то и < Р,р+ . Докаларлельсиьао. Этот результат очевиден, если иь < р. В противном аяучае пусть Ь есть минимальное число, такое, что /ь > дал ь +1; имеем й < р и по индукции Рно + . + РЬО < Р!р1; следовательно, и < Р!р!+. + Р)р! < Роб ьь+~ ''' л »ь ь' ьь ' ' ' !ь -ь-1 — ььль. Искомое теперь может быть доказано инлукцней по и. Если и > О, то пусть,!' будер максимальным числом, таким, что Р' Р < и. Лемма показывает, что любое представление и должно состоять из Р!Ю плюс представление и — Р!'( По индукции и — Р!Р~ имеет ! ! р единственное представление нужного вида, и это представление не содержит всех чисел Р Р~ьь...,Р!"р „так каку максимально. Замечания.
Случай, когда р = 2, упомянутый в работе Е. Еес)ьепь!ог(, ЬОтол Згеу!и 29 (1952, 190-195, был рассмотрен в упр. 1.2.8-34. Имеется простой алгоритм перехода от представления и к представлению и+1, работающий с последовательностью нулей и единиц с,,сьсе, чикой, что и = 2 с Р',ьр.
Например, если р = 3, мы смотрим на правые цифры и 04 заменяем... О на .. 1,, 01 на... 10,... 011 на... 100; затем осуществляем "перенос" влево, если это необходимо, заменяя ... 0111... на ... 1000.... (См. последовательности нулей и единиц в упр. 9 в том порядке, в котором они записаны.) Подобная система счисления была исследована в работе %. С. 1.упсЬ, Р2Ьопаса с)пал!ел!у 8 (1970), 6-22. Автор приводит очень интересный способ ее применения дли управления и фазой распределения, и фазой слияния многофазной со1зтнровхи. 12. й-я степень содержит точные распределения для уровней с й — 4 до к-го в последова- тельных строках с наибольшими элементами справа. 13. Доказывается индукпней по уровню.
15. Эта теорема была доказана Д. Э. Зэйвом (П. А. Каче), статья которого упоминается в тексте раздела. 16. Д. Э. Зэйв показал, что число вводимых (и выводимых) записей равно 31обг, Я+ з В )об — )оа — В+ С(В) 17. Пусть Т = 3; Лп(х) = бхе + 35х~ + 5бхе +, Вц(х) = хе + 15х~ + 35х» + .
-, Тц(х) = 7ке + 50х~ + 91хз + 64хэ + 1дх'о+ 2к". Оптимальное распределение для я = 144 требует 55 серий на Т2. Это обязательно приводит к неоптимальному распределению для Я = 145. Д, Э. Зэйв изучил процедуры такого вида, близкие к оптвмальным. 16. Пусть Я = 9, Т = 3. Рассмотрим гледуюн»ие две схемы. Альтернатива Т1 Т2 ТЗ Стоимость Оптимальное мномфазное слняние Т1 Т2 ТЗ Стоимость О'1е 0'1 1 3 — 1'3» 3' 3' — 3 1 9 1 01 01 1 з 1~3 3' 3' 3' д! 0»2» 6 2» 7 3 6 б 9 31 0»23 22 (Еще един способ улучшения "оптимального" многофазного метода состоит в пересмотре того, в каких местах выводной ленты появляются фиктивные серии на каждой фазе слняняя.
Например, результат слияния 0»1» с 0»1» можно было бы рассматривать как 2'0'2 О'2' вместо О 2". Таким образом, остается много нерешенных вопросов, связанных с оптимальностью.) 14. (а) п(1) ж 1, поэтому будем считать, что )» > 1. Закон Т» = Т1»Н»-ц + + 21„гд» ц показывает, что Т„» < Тшчц» тогда и только тогда, когда 7~„рй» ц < т„ы ц, Пусть г — произвазьное положительное целое и пусть п' — минимальное число, такое, что Тш Н» ц > Т„ч»-ц; тогда Тш,н» ц > Тщ» ц для всех и > и', поскольку это тривнальпо длв и > п(й — 1) + г а иначе Ты,п» ц > Т1 и» ц > Т, ц > Т„р, ц. (Ь) То же рассуждение при г = и — и' показывает, что Т„» < 2'„» влечет за собой Кы ю» < Тш й» для всех 1 > О.
Значит, из рекуррентного соотно»пения следует, что Т1„11» < Ты ц» для всех з > 0 и й > й', (с) Пусть 1(8) — наименьшее и, такое, что Е„(Ю) принимает свое минимальное значение, Требуемая погледовательность М„существует тогда н только тогда, когда 8(Я) < 1(Я+!) для всех Ю. Предположим, что и = 1(8) > 1(В + 1) = и', так что Е„(Я) < Е„(8) и Е (л + 1) > Е„(Я+ 1). Существует наименьшее 5', такое, что Е„(5') < Е„.(У); имеем и» = Е„(У) — Е (У— 1) < Е„(В') — Е„(У вЂ” 1) = и»', Тогда Я»,Т„» < У < К,Т»; следовательно, существует некоторое к' < гл, такое, что Т„» < Т„» . Аналогично имеем 1 = Е,„(Я+ 1) — Е»(Я) > Е„(Ю + 1) — Е„(Я) = 1', значит, 2"», Т„» > Я+ 1 > 2,»д, Т„».
Поскольку 1' > т' > ш, существует некоторое к > и», такое, что Т„» > Т». Но это противоречит п. (Ь). 10. Окончательный Уровень Т1 Т2 ТЗ Т4 Сумма результат на а+1 т(ц а„ 1 + 2а„ Т(л — Ц аи ь„ 20. а(з) =1/(1 — хз-хз-хв),1(х) =(Зх+Зх~+22'+х"))(1 — хз-хз-хв), ~ „ивт (х)х" = х(зз+Зз +22 +х )/(1 — х(» +х +х')).;Р~ = А~-4+1 С» = Ап-зА 2+1, Вп Аи-2А -2Ап-3+ 1, Аи =.4п-24 -ЗАп-4+ 1 21. 333343333332322 3333433333323 33334333333 3333433 333323 То 22.
1„— 1„2 — 1„2 = -1+ 3(пщо63=1). (Это соотношение, подобное соотношению Фибоначчи, следует нз того, что 1 — зв — 2зз — х = (1 — фз)(1 — фх)(1 — ых)(1 — й22), где з 23. Вместо (25) длины серий в течение первой половины и-й фазы слияния будут з„, а в течение второй половины — З„, где з = Зи-2+ 1 -з+ з -з+ з -и, Зп = З -2+ з„-2+ з -з + з -4. Здесь мы полагаем з„= 1п ии 1 при н < О, (В общем случае, если еп+з яепявтоя СуММОй ПЕРВЫХ 2Г ЧЛЕНОВ ИЗ Н„в+ ° + Е„Р, ИМЕЕМ В„= З„= Зи 2+ °" + Фи-, + 21п-,-з +1п- -2+ . + Фи Р.
Если епиз ыть сумма первых 2г — 1 членов, то Зи =си-2+ '''+си — и — З+ Зп-и-1+' '+хи-Р Зи = си-2+ '''+Зп — +З -«+'''+хи-Р) Вместо (27) и (28) (У вЂ” 11 п-1Уп-2~ п-2пГп-21 и-Зии-4 ип-4) + 1~ ((г 4)' в)+1, (К 21 — Ю 3)+ 11 (и' — 1К 2пги 2) + 1 (1 -Ю -Зии' -217 -4(Г -«) + 1. Е, 1п+2 К, — 1" В 124 В 25. 1И 14 1 в 26. Если сортируются 2" начальных серий, то во время слияния обрабатываются и . 2"-е серии. Кавкдая половина фазы (за немногими исключениями) сливает 2" 2 и перематывает 2" '. Если сортнруются 2" + 2" 2 начальных серий, то обрабатываются во время слияния 0 1 2 з 4 5 6 В 8 16' 84 16 В 8~ 16' 16' 8" В 16' 16' 16' В 16е 16е 322 Зе В 24е 24е32о (В) 0 1 1 1 2 3 4 6 0 1 0 1 1 2 2 4 1 3 3 5 7 11 15 23 т1 тб т5 Т4 тз Т2 т1 тб и 2" +(и — 1) .2" '. Каждая половииа фазы (за немногими исключениями) сливает 2" з или 2" ' и перематывает 2" ' + 2" з начальных серяй.
27. Стратегия работает тогда и только тогда, когда наиболыпий общий делитель чисел распределения равен 1. Например, пусть имеется шесть лент; если мы распределим (а, Ь,с,б,е) на лепты Т1-ТЬ, где а > Ь > с > Ы > е > О, то после первой фазы получится распределен ие (а — е, Ь -с, с — с, 4-«, с) и Всб(а — е, Ь вЂ” е, с-с, б — с, е) = Всб(а, Ь, с, 4, е) . (Любой общий делитель одного из зтих множеств чисел делит также числа друтого миожества.) Рассматриваемый процесс уменьшает количество серий на каждой 4зазе до тех пор, пока иа одной ленте не остапется Всб(а,Ь,с,б,е) серий.
[Заметим, что эти пе миогофазпые распределения иногда оказываются лучше многофазпого при определенном расположении фиктивных серий, как показано в упр. !8. Это свойство впервые было замечено Б, Сзкмаиом примерно в 1963 году.] 28. Мы получаем любую такую пятерку (а,б,с,д,е), начав с (1,0,0,0,0) и выполнив равно и раз следующую операцию: выбрать г из (а, Ь, с, 4, г) и добавить х к каждому из остальяых четырех элементов (а, Ь, с, 4, с). Чтобы доказать, что а + Ь + с + д + е < 1„, докажем по индукции, что если а > Ь > с > 4 > е, то всстда имеем а < а„, Ь < Ь„, с < с„, д < д, е < е . В предположении, что сказанное справедливо для уровня и, зто также должна быть сцраведлиао для уровня и+ 1, поскольку распределения (и+ 1)-го уровия суть (Ь+а, с+а,4+а, е+а, а), (а+Ь, с+Ь 4+Ь, е+Ь, Ь), (а+с Ь+с,4+с, с+с, с), (а+4 Ь+Ю с+4 е+б, д), (а+с, Ь+с, с+с, Ы+е, е).
30. Дж. А. Мортенсоп (2. А. Могзепзоп) свел результаты вычисаеиий в следующую таблицу. Уровень Т=5 Т=б Т=7 Т=В Т=9 Т=-10 1 2 2 2 2 2 2 М~ 2 5 б 7 8 9 Мз 3 5 б 7 8 9 Мз 4 В 8 10 12 14 16 Мь 5 10 14 18 17 20 23 Мз 6 18 20 26 27 32 31 Мз 7 26 32 46 47 56 42 Мг В 44 53 74 82 92 92 Мз 9 68 83 122 111 138 139 Ма 10 112 134 206 !40 177 196 М!« 11 178 197 317 324 208 241 Мп 12 290 350 401 488 595 288 Мш 13 466 566 933 640 838 860 Мзз 14 756 917 1371 769 1064 1177 Мы 15 1220 1481 1762 2078 1258 1520 ЬХм 16 1976 2313 4060 2907 3839 1821 Мш 31.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
