AOP_Tom3 (1021738), страница 201
Текст из файла (страница 201)
Нш»ример, прн !»' = 12 расположение ключей должно быть с»»едующим. Кэ<К»<Ко<К»<К»о<К»<Кп <К» <Кы<Ке<К» <К» Врел»я работы такой программы на 811-компьютере примерно равно 6 !8»»» единицам Таким образом, зта программа работает быстрее программы С, однако для начальной установки таблицы требуется известная доли труда и сообразительности. 25. (а) Поскольку ае = 1 — Ье, а» = 2аа — Ь», ае = 2໠— Ь» и т. д., имеем А(х) + В(я) = 1 -»- 2сА(з).
Несколько формул, приведенных в разделе 2.3 4.5, л»ожно вь»вести из э»ого соотношения, рассматривая А(1), В(1), В(-'), А'(1) и В'(1) Прн использовании двух переменных для того, чтобы отл»»чита»лаги влево от шагов вправо, получим более общий результат А(х,р) + В(х,у) = 1 + (х + р)А(х, 9), представляющий собой частный случай формулы, справедливой дла »-арных деревьев (см. Н. М. Каср, 7ЯЕ Тгап»осман» 1Т-7 (1961). 27 — 38). (Ь) тш(д) = ((7»»+ 1)/К)гас(Ь) — ((7»'+ 1)/Ж~) п»еал(Ь) + 2.
26. Дерево для трехленточного многофазного слиянии, соответствующее распределению с заполненным уровнем Ь, есть дерево Фибоначчи порядка Ь + 1; надо только поменять правую и левую ветви. (Перерисуйте дерево на рис. 76 нз раздела 5.4.4, поменяв местами левые и правые поддеревья А и С. При этом должен получиться аналог рис. 8). 27. Поскольку можно упорядочить индексы таким образом, что КП < Км « К,„, возможно максимум Ь + 1 исходов из 2". Таким образом, поиск может быть описан с помощью дерева с узлами, из которых выходит не более (8+ 1) ветвей. Количество записей, которые могут быть найдены на ш-м шаге, — не более Ь(Ь+1)м '.
Следовательно, среднее количество сравнений, как минимум, равно сумме Ж наименьших элементов мультимножества (Й 1, Й(Й -!- 1) 2, Й(Й+ 1)з.3,...), умноженной на )з' '. При )г' > (Й+ 1) — 1 среднее количество сравнений > ((Й+ 1)" — 1)"' 2 ", Й(Й+ 1) 'т > и — 1/Й. 28. (БЙгййег ас(8!ггзе а/ Ъ'МелзйаЬзч8е!в1гаЬез 1 СЬг(яс!ал(а, МасЬепзас!зЙдКагпгг!о)епзйаЬе!18 К!ааэе (1910), )йа. 8; перепечатано в Т1ше'з Ее1есгег) Ма(Ьелзабга! Рарегз (Оз!о: (7л!гегз)сезз(ог!аКец 1977), 273 — 310). (а) Т„имеет Х' эз + Р -з = Ез /Е листьев.
(Это так называемое число Лукаса Е = й" + Ю~.) (Ь) Лксиома гласит, что То(Тз(х)) = Тз(х), и получается Т„,(Т„(х)) = Т т, з(х) при т = 1 или и = 1. По индукции па зз результат справедлив при т = 0; например, То(Тз(х)) = То(Тз(х)*Тз(х)) = То(Тз(Тз(х))*То(Тз(х))) = То(Тз(Тз(х))) = Тз(х). И на последнем шаге следует использовать индукцию по т. 29. Пусть Ко —— — ао и Клез = Клтз — — са. Сначала проведем бинарный поиск на множестве Кз < Кз < .; это потребует максимум (!8 М) сравнений. Если поиск неудачен, при этом определяется интервал Кз, з < К < Кз„К отсутствует, если 21 = Х+ 2. В противном случае бинарный поиск для Кз, .
з определит з, такое, что Кз; з < Кз, з < Кз,. Теперь может быть два исхода — либо К = Лз.-м либо К отсутствует. (См. ТЬеог. Сошр. Яс1 68 (1988) 67 ) 30. Пусть и = ()г/4). Начиная с Кз < Кз « ... Кн, можно расположить Кц Кз, ..., Кз„з в любом требуемом порядке, поменяв их местами с любой перестановкой из Кз„ац Кз„ез,,, .. Кз ц такое расположение удовлетворяет условиям предыдущего упражнения. Теперь пусть Кз < Кз « . Кх м з — границы между всеми возможными Ь битовыми числами.
Нставим Кз~.н,, Кз~эзэп..., Кз ~-1ез 3 между этим "частоколом" в соответствии со значениями хм хз, ..., хм. Например, если т = 4, 1 = 3, хз = (001)з, хз = (111)з и хз = хз = (100)з, требуемый порядок таков: Кз < Кзз < Кз < Кз < Кг < «зо < Км < Ко < Кп < Кзз < Км. (/(опускается также, чтобы Кзз предшествовала Кш.) Бинарный поиск «зою з, з в подмножестве Кз < Кз « Кз ~ з будет эквивалентен поиску битов числа х, слева направо.
(См. Г!ац Мшпо, Ь)аог, ЯсЬа)Тег, ЯсЬшздз, апб 8!еКе!, Х Сашр. Яузе. Яс1 43 (199Ц, 406-424.) РАЗДЕЛ 6.2.2 1. Используйте головной узел, скажем, с НООТ г— в НПИК(ИКАО); начните выполнять алгоритм с шага Т4 с Р е- ИЕАО. Шаг Т5 должен выполняться так, как будто К > КЕТ(НЕАО) . (Соответственно в программе Т счедует заменить команды строк 04 и 05 комацзамн "ЕИТ1 НООТ; СИРА К"). 2. На шаге Т5 установите НТАС(Ц) з- 1. Кроме того, при вставке влево установите нй1ик(ц) +- Р, при вставке вправо установите 81.1ик(Ц) з — 81.1ик(Р) и нтАс(Р) +- О.
На шаге Т4 измените проверку оЫ.1ИК(Р) ~ Л" на "НТАС(Р) ~ 0". (Если узлы вставляются в последовательные ячейки памяти Ц и если все удаления осуществляются по принципу ЫЕО (" последним вошел - первым вышел" ), поля НТАС могут быть удалены, поскольку НТАС(Р) будет равно 1 тогда и только тогда, когда НЙ1ИК(Р) < Р.
Подобное примечание справедливо и для левой, и для правой прошивок.) 3. Можно заменить Л корректным адресам и установить КЕТ(Л) е- К в начале работы алгоритма. В таком случае проверки 11188 и 81188 = Л могут быть удалены из внутреннего цикла. Однако для корректного выполнения вставки необходимо ввести другой указатель, следующий за Р. Это можно сделать, дублирован кад твк же, как и в программе 6.2.1Е. Работа программы при этом не замедляется. Бремя работы такой моднфицировшзной программы уменьшается до 5 5С единиц. 4.
Сн = 1+ (О 1+1 2+ +(и — 1)2' '+Сг 1+ +Ся 1)/гУ = (1+1/г»7)Сй — 1 при Н > 2" — 1. Решением этих уравнений является С~я = 2(На+1 — Нг ) +п, 141 > 2" — 1. При этомэкономится 2Нг — и — 2 п(1п4-1) сравнений. Улучшениедляп = 1,2,3,4 составляет соответственно О, е 42 2 для малых п выигрыш, как видите, невелик. (См, статью 1 41 274222 Ргагег апо МсКе!!аг, 1АСМ 17 (1970), 502, в которой подробно описана эквивалентная задача сортировки ) 5.
(а) Первым должен быть элемент САР810088; затем умножаем количество способов построения левого поддерева на количество способов построения правого поддерева и на (2) 1О1 2), количество совместных перестановок этих двух последовательностей. Таким образом, искомый ответ равен (3) (о)(о) Со) Сз)(о)(о)(о)(1) Со)( ) =48оо, (В общем случае ответ представляет собой произведение ('т") по всем узлам, где ! и г означают размеры левого и правого поддеревьев этого узла. Данное произведение равно дг!, деленному на произведение размеров поддеревьев. В результате получилась та же формула, что и в упр. 5.1.4 — 20; в самом деле, существует очевидное однозначное соответствие между перестановками, позволяющими получить некоторое дерево поиска, и итопологическими» перестановками, подсчитанными в указанном упражнении — при замене аь в дереве поиска на !4 (с использованием формы записи из упр.
6).) (Ь) 2н 1024; на каждом шаге, кроме последнего, должен вставляться либо наименьший, либо наибольший из оставшихся ключей. 6. (а) Для каждой из Р„ь перестановок аг... а„га„, стоимость которых равна Я, построим и+ 1 перестановку а',... а'„,гп а~„, где а' = а или а + 1 в зависимости от выполнения условия аг ( т или а; > т (см.
раздел 1.2,5, метод 2). Если т = а» или а, + 1, такая перестановка имеет цену !4 + 1; в противном случае ее цена равна 14. (Ъ) С (2) = (22+ и — 2)(22+ и — 3)... (22). Поэтому Риь=~ ]2. Эта производящая функция была получена, в сущности, В. Ч. Линчем (!Ч. С. ЬупсЬ) ]Сотр. 4. 7 (1965), 299-302]. (с) Производящая функция для вероятностей есть д (2) = с (2)ггп!. Она ЯвлЯетсЯ пРоизведением пРостых пРоизводЯщих фУнкций веРонтностей, а потому П-2 г» «-2 ~ +1) - ~ +2-(.+ ) )- (С помощью упр.
6.2.1-25, (Ь) можно вычислить среднее значение и дисперсию С,', чтобы вычислить дисперсию с„, которая равна (2 + 10]п) и„— 4(1 + 1гп)(н„+ н„(н) + 4; эта формула выведена Г. Д. Кноттом (С. П. Кпост).) 7. Сравнение с я-м наибольшим элементом будет выполнено тогда и только тогда, когда этот элемент появится до гп-го и до всех элементов между (г- и т-м; вероятность этого равна 1/(]т — 14]+ 1). Суммируя по !4, получим искомый ответ: Н + Н„ег — 1 [САСМ 12 (1969), 77-80; см. также К СшЬав, Асса 1аагтаггса 4 (1975), 293-298]. 8.
(а) д (2) = 2" '2 „",дь-1(2)д -2(2)/и, де(2) =1, (Ь) 7п — 4(п+ 1)~Н! ! — 2(п+ 1)Н„+ 13п. (В статье Р. Р. Ъ7!пг!!еу„Сотр. Х 3 (1960), 86, приведены рекуррентные соотношения, по которым можно найти дисперсию численно, однако в ней не содержится решение проблемы. Обратите внимание на оглсдтстепе простой связи с дисперсией С„, найденной в ответе к упр. 6,) 10. Например, каждое слово к ключа можно заменить словом ах шоб т, где т — размер машинного слова, а а — случайный множитель, взаимно простой с т. Можно также порекомендовать величину, близкую к ((э — 1)т (см. раздел 6.4) Гибкое распределение памяти при работе с деревьями может сделать такие методы более притягательнымн, чем схемы с хешированием. 11.
Лà — 2; однако это происходит с вероятностью 1/(Ж Н!) только при удалении О1 Лг Н-1 ... 2. 12. 1(п + 1)(п + 2) удалений в доказательстве теоремы Н относятся к случаю 1, так что ответ — ()У + 1)/2а(. 13. Да. Доказательство теоремы Н показывает, что если удалить й-й вставленный элемент, то для любого фиксированного к результат будет случайным. (Г. Д. Кнотт (Р)ь )).
(бее)э, Есап(огб, 1975) показал, что результат остается случайным после любой фиксированной последовательности вставок н удалений элементов (йц ,94),) 14. ПустьИОВЕ(Т) находится на уровне 1 и пусть ШИК(Т) = Л, КПИК(Т) = Кп ььТМК(К~) = Кж ..., КОТИК(йа) = Л, где Ка Ф Л и 4 > 1. Допустим, что в правам поддереве узла МООЕ(К,) находится п„1 < ( < Ы, внутренних узлов. При наличии шага П1-' длина внутреннего пути уменьшается на к+ 4+ а~ + + пю без этого шага она уменьшается на )с+ г(+ пю 13. 11, 13, 25, 11, 12. (Если а, является наименьшим, средним, наибольшим из (ам аз, аз), после удаления дерево Х, будет получено (4,2,3)х 4 раз.) 16.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
