Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 2) (1119371), страница 91
Текст из файла (страница 91)
Это влечет за собой х(1) = Ип((1+ К1)/у), так что, когда х(Т) = 1., имеем КТ = (е — Цй Количество снега, упавшего с момента 1 = О, составляет, следовательно, (е — 1)Е1 = (е — 1)Р. 20. Как и в упр. 19, имеем (1+ Кг) ~(х = К(Ь вЂ” х) й; следовательно, х(1) = ЕК1/(1+ Кг). Количество записей в резервуаре равно гт Ы = Р = Р' = / х(1)КОЭ = У(КТ вЂ” 1 1п((1+ КТ)/1)); глеловатчльно, КТ = а1, где а — 2.14619 — корень уравнения 1+ а = е '. Длина серии есть суммарное количество снега за время О < 1 < Т, а именно — АКТ = оР. 21. Действуем, как описывалось в тексте раздела, но после каждой серии снегоочиститель, прежде чем вновь начать работу, ожидает, пока упадут Р— Р' снежинок.
Это означает, что Л(х(1),1) стало теперь ке КТ,, а КТ, где Т, — Т есть время дополнительного падения снега. Длинасерннравиа ЬКТм х(1) м Е(1-е ц~'), Р м АКТА е тгт' и Р' = / х(1)КО1 = Р+ 1 К(Т вЂ” Т~). Другими словами, длина серии е~Р получится, если Р' = (1 — (1 — В)г~) Р приО <9<1. 22. Прк О < 1 < (к — 1)Т имеем г1х л = Кг(1 (х(1+ Т) — х(1)), в при (л — 1)Т < 1 < Т имеем Ых й = К~й(1, — х(1)), где Л, как можно видеть, постоянно равна КТ в той точке, в которой находится снегоочиститель. Отсюда следует, что при О < У < й, О < и < 1 и 1 = (к — У вЂ” в)Т будем иметь х(1) = Х(1 — е" ~Р1(и)/Р(к)).
Длина серии есть ЕКТ количество снега, падающего мевьэу моментами, когда снегоочистители в установившемся режиме последовательно выходят из точки О; Р есть количество убранного снега в конце последнего участка каждого снегоочистителя, а именно — КТ(Ь вЂ” х(кТ)) = ЕКТе /Р(к); можно показать, что Р' = /е" х(1)К ~Ы и имеет требуемый вид. Замечания. Оказывается, что эта формула справедлива также и для й = О, При к > 1 число элементов каждой серии, попадающих в резервуар дваясдм, равно Р" /э' ~ х(1)КМ н можно легко показать, что (дэнни серии) — Р + Р = (е — 1)Р.
Это свойство отметили Фрейзер и Вонг. Является лн случайным совпадением то, что производящая функция для Еь(д) так похожа на функцию из упр. Ь.1.3-11? 23. Пусть Р = рР' и д = 1-р. В течение первых Т~ единиц времени падающий снег берется нз числа дР элементов, оставшихся в резервуаре после того, как вначале были удалены первые рР' элементов в случайном порядке. Когда старый резервуар станет пустым, снег снова начнет падать равномерно. Мы выбираем Ть так, чтобы Г.КТ~ = дР'. При О < 1 < Т~ имеем 6(х, 1) = (р+ да/Тъ )д(х), где д(х) — вес снега, ~омещаемого в рпэервуар из точки х; при Тг < 1 < Т имеем Ь(х,е) ы д(х) + (1 — 7~)К. При О < 1 < Т~ имеем, что д(х(1)) есть (9% — 1)/Т~)д(х(1)) + (Т вЂ” Ть)К, а прн Т~ < 1 < Т имеем д(х(1)) ы (Т вЂ” 1)К.
Таким образом, й(х(1)„1) = (Т вЂ” Ть)К при О < 1 < Т и х(1) = Ц1 — екр(-1/(Т вЂ” Т~))). Общая длина серии составляет ИС(Т вЂ” Т~); общее чясло элементов, повторно возвращающихся в резервуар, равно ЙКТ, (см. Упр, 22); общее количество снега, счищаемого после момента Т, РмКТ(У- (Т)) Таким образом, в условиях, заданных длв этого упражнении, получаются серии длиной (е'/э)Р, если размер резервуара — (1 + (е — 1)е'/з)Р, Это значительно хуже результатов упр. 22, поскольку там содержимое резервуара используется рациональнее, (Тот факт, что !)(х(!), !) есть величина постоянная в тисом большом числе задач, не удивителен, ведь он эквивалентен утверждению, что элементы каждой серии, получаемой в установившемся режиме системы, рвспрещлены равномерно.) 24.
(а) Работает, по существу, то же доказательство; в каждой последовательности имеются серии того же направления, что и выводные серии. (Ь) Вероятность, о которой ) озарится в указании, есть вероятиасть того, Чта серия имеЕт дииНУ и+ 1 и за ней слеэует йэ она равна (1 — х)"/н), если х > р, и (1 — х)"/н! — (9 — х)"/н!, если х < р, (с) Докезывается по ицлукции. Например, если и-я серия — восходящая, то (и — 1)-я бь)ла нисходящей с вероятностью р, так что применяется первый интеграл.
()!) Находим, что/ (х) = /(х)-с — р/(1-х) д/(х)! тогда /" (х) = -2рс, что, в конце концов, приводит к /(х) = с(1 — дх — рх ), с = 6Д3+ р). (е) Если р > ед, то ре + де' ~ монотонно возрастает при 0 < х < 1 и / ]ре* + де' епэ] Вх = (р — д)(еьы — 1)з < 043. Если д < р < ед, то ре* + де' *.лежит между 2 /рде и р+дс, так что 1е ]ре*+де' *-1)(р+де+2)/рде)])!х < -'( /р-,/де) < 04, несли р < д, можно использовать "симметричное" рассуждение.
Таким образом, для всех р и д суи)ествует константа С, такая, что /е ]ре" + де' ' — С]4х < 0.43. Пусть 5„(х) = / (х) — /(х). Тогда 5 +)(9) = (1 — е" ')Д'(ре*+де' ' — С)4 (х))!х+РЯ "е" )т"бв(х))(х+д/'е" д„(х))!х. Следовательно, еслибы„(9) <а, ]б +)(9)] < (1 — е" ').143а < 091а . (!) Привсех н > 0 величина (1 — х)"/и! есть вероятность того, что длина серий превьппает и, (8) 1е (ре' + де' *)/(х))(х = 6/(3 + р). 26. (а) Рассмотрите число перестановок из и + г + 1 элементов с и левосторонними минимумами, причем крайний справа элемент не является наименьшим, (Ь) Используйте свойство по определению чисел Стнрлингв в приложении Б. (с) Добавьте к средней длине ).
+ 1, используя для получения равенства ):"„>о[ "~'](и + г)/(и + г + 1)! = 1 тот факт, что ["+"]/(н+ ) — 1)). Формула в (Ь) получена в работе Р. Арре!1, АгсИгк бег Маей. ипс! Рйуэ)7) 65 (1880), 171-175. Соответственно имеем [[„"]] = (г+ 5)! !х" х"]с*) а), где /(х) = х/2+ хт/3+ -х ' 1н(1 — х) — 1; следовательно, с = [х" ] (г + 1 + /(х)) е) !" !. Число неупорядоченностей и объектов, которые имеют й циклов, иногда обозначаемое как ["„], равно [[", ~]]; см. Я. В!огбап, Ап !л)годисйоп !о Сотб!насос!и! Алв(уз!з (%)!!еу, 1958), 54.4.
(Имеется русский перевод: Риордан Дж. Введение в комбинаторный анализ. — Мл Иэд-во иностр. лиг., 1963.) 27. Если при 0 < В < 1 Р /Р = 2(е е — 1+В)Д1 — 2В+ 8~+ 2Ве ), то средняя длина серии в установившемся режиме будет равна 2Р/(! — 2В+В~+2Ве е). [См. 1!)гогшас!ол Ргосеш!л8 Ъег!егз 21 (1985), 239-243.] Добосевич обратил также внимание на то, что можно продолжать использование ыехавнзма выбора с замещением, поскольку можно вводить данные нз начала очереди во вспомогательном буфере н одновременно выводить их с конца этой очереди.
Например, если Р' = .5Р и продолжается выбор с замещением до тех пор, пока текущая серия не будет содержать .209Р записей, средняя длина серии при такой модификации возрастает от примерно 2.55Р до примерно 2,61Р. Если же Р' = Р и продолжается выполнение выбора с замещением до тех пор, пока в текущей серии не останется только .314Р записей, то средняя длина серии возрастает от еР до примерно 3.034Р. [См. Сошр. Х 27 (1934), 334 — 339, где представлен даже более эффективный метод, названный "слиянием с замещеннем".) 23. Для многопутевого слияния эта проблема относительна проста, поскольку Р остается постоянным и записи обрабатываютсл последовательно в каждом файле.
Однако при формировании начальных серий предпочтительнее изменять число записей в памяти в зависимости от их длин. Можно было бы прпменить пирамиду из такого числа записей, которые помещаются в памяти, используя динамическое распределение памяти, как описано в разделе 2.5. В работе М. А.
Свесе, Ргос. АР(РЯ Зошг СолзрпГег Солй 25 (1964), 602-604, предложен другой подход: разбить каждую запись на части фиксированного размера, которые связаны между собой (они располагаются в листьях деревьев, и только "головная" часть участвует в турнире).
29. Верхние 2~ узлов проигравших переходят на соответствующие позиции основных узлов. Оставшиеся узлы проигравших образуют 2" поддеревьев с 2" — 1 узлами в каждом; они подключаются к основным узлам в симметричном порядке: крайнее слева додерево --. к крайнему слева основному узлу и т. д, [См. К. Е(е, Х. Е1еэег, Асса |вйишабса 34 (1997), 429-447,) 30.
Предположим, что к 1 основным узлам подключен 2"-узловой подграф полного 2"+"- узлового дерева проигравших. В этом дереве имеется один узел на уровне 0 и 2' ' узлов на уровне 1 при 1 < 1 < и + Е Поддерево с корнем на уровне 1 > 1 имеет 2"+~~' ~ — 1 узлов, Таким образом, все корни Г несвязанных 2"-узловых деревьев должны находиться на уровнях < к. Каждое из этих поддеревьев должно содержать минимум один узел на уровне й, поскольку существует только 2" ' < 2" узлов нв уровнях < й. Отсюда следует, что 1 < 2" '.
Но количество ребер основного графа равно, по меньшей мере, 1+ 2(2* — 1) — 1, как следует из (0) и (1п), поскольку существует не меньше этого холичества узлов проигравв~их, родитель которых имеет отличную картину в основном графе. (Необходимо предполагать, что и > Рл егли и = й — 1, то существует соответствующий основной граф с 2ь + 2~ ' — 2 ребрами.) РАЗДЕЛ $.4.2 1.
3. Папке первой фазы слияния все оставшиеся фиктивные серии будут находиться на ленте Х и их будет самое большее а„— а„~ < а„ь Следовательно, все они исчезнут в течение второй фазы слияния. 3. Имеем (0Ш,0[2),...,0(Т)) ш (а -а р,а„-а„реп.,,,а„-а ), так что выполнение интересующего нас условпя следует из того, что последовательность о неубывающая. Это уьловие важно для правильной работы алгоритма, так как на шагах !72 н !13 никовда 0(у + !! не уменыпается чаще, чем О(/), 4. (1 — л — .. — лл)а(л) = 1 в силу (3).
Велес, г(л) = 2 „>,(а„+Ь„+с +4 +е„)л" = (л+ + ль)а(л) + (л+ + э~)а(л) + + ла(л) = (Ьл+4лз+ Зла+ 2ль+ лл)а(л). 5. Пусть др(л) = (л — 1)/р(л) = лр+ — 2лр+ 1 и Ьр(л) = лр+' — 2л". Теорема Руше (ВонсЬ4) [Х Есо!е Ро!угесйпк!пе 21,37 (1858), 1-34] утверждает: Ь„(л) и др(л) имеют равное число корней внутри окружности ]л] = 1+ е при условии, что [Ь (л)] > ]Ь (л) — др(л)] = 1 на Если ф ' > е > О и~сом ]Ьр(л)] > (1 + е) (1 — е) > (1+ ьЬ ') (1 — 4ь ') = 1, Следовательно, др имеет р коряей с абсолютной величиной < 1.
Они различны, так юьк боб(др(л),д'„(л)) = бсь!(др(л), (Р+ 1)л — 2Р) = 1. [АММ 67 (1960), 745-752.] 6. Положим се = — пр(а ~)/д (а '). Тогда р(л)/д(л) — со/(1 — пл) аналитична в круге ]л] < В для некоторого В > ]и] ', следовательно, коэффициенты [л"]р(л)/д(л) = соа + О(В "). Значит, 1пЯ = и1пп+ !пса+ О((аВ) "); а из и = (!вЗ/!пп) + 0(1) следует, что О[(аВ) ") = О(Я '). Аналогично положим сь = а'р(п ь)/д'(а-ь)л, сл = -ар'(а-')/ д'(и-ь)л+ пр(п-ьда(гл-ь)/д'(а-ь)ли рассмотрим р(л)/д(л)л — сь/(! — ал)л — сл/(1 — ал) 7. Пусть ар ьр 2л и л = — 1/2р+'.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
