Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 2) (1119371), страница 48
Текст из файла (страница 48)
Пусть де = О, ро = 1, 9» = 1. р» = О и В»+1 = а»й» + В»-м р»»» = а»р» + р»» при А > 1. Пусть (х) означает х шос(1 = х - (х), а (х)+ — х— (х) + 1. Перенумеруем отрезки, получающиеся в результате последовательной вставки точек (В), (2В), (ЗВ),...
в интервал (О .. Ц, в порядке их появления, причем первому отрезку присваивается номер О. Докажите справедливость следующих утверждений. Интервал номер э длиной ((В), где 1 = гд» + д»эм О < г < а», (с четно и 0 < э < о», имеет левую границу (эВ) и правую границу ((э + 1)В)+. Интервал номер э длиной 1 — ((В), где 1 = язгляките с этой точка зрения ка коликами х~е» х»э+х»+ 1 к хээ 4 хэе 4хээ 4хээ+ х~е.»х»э.~- х" +х»о+ хе+ х" + х»+ х»+ хе+ х' + 1, определяющие СС1ТТ СКС-16 к СКС 32 соответствекко, к рассмотрите возможкость ксиользовэнкя СКС в качестве хеш-фукалка, — Прим.
перев. го» + С»» и О < г < о», Ь нечетно и 0 < в < Сы имеет левую гранину ((в+ 1)д) и правую границу (вд)+. Любое положительное питое число и может быть единственным образом представлено в виде и = го» + о» 1 + в при А > 1, 1 < г < а» и 0 < в < С». В зтнх обозначениях перед вставкой точки (пд) имеется и интервалов: первые в интервалов (с номерами О, ..., в — 1) длиной ((-1) (гд» + С»-»)б)' первые и — о» интервалов (с номерами О... и — С» — 1) длиной ((-1) С»Ь); последние о» -в интервалов (с номерами в,..., о» вЂ” 1) длиной ((-1) ((г-1)д»+С»-1)()) . Операция вставки (пд) приводит к удалению интервала номер в третьего типа и его преобразованию в интервал номер в первого типа и номер и — С» второго типа.
9. [Муй) Прн последовательной во~алке точек (д), (29), ... в отрезок [О .. 1[ теорема Я утверждает, что каждая новая точка всегда разбивает один из наибольших имеющихся интервалов. Если интервал [а..с[ разбит так»ьи образом на две части, [а..Ь] и [Ь..с), назовем разбиение плохим, если одна из частей более чем в два раза больше другой, т. е. если Ь вЂ” а > 2(с — Ь) нли с — Ь > 2(Ь вЂ” а), Докажите, что при некотором и точка (пб) дает плохое разбиение, за исключением случаев () шод1 = 4 ' и 9 пюд1 = й в, прн которых никогда не бывает плохих разбиений. 10. [М33[ (Р. Л. Грэхем (К. 1.. Сгаба»п).) Докажите, что если О.пп,,пв — действи- тельные числа, причем о~ = О, если пп,пв — положительные целые числа и если точки (од+ о,) вставлены в интервал [0..1[ при 0 < и < гб и 1 <,у < д, то и» + + пв получающихся интервалов (возможно, пустых) имеют не более Зд различных длин.
11. [16[ Как правило, поиск чаще завершается успешно, чем неудачно. Исходя из этого, насколько разумно заменить строки 12-13 программы С строками 10-112 ь 12. [31[ Покажите, что программа С может быть переписана так, что во внутреннем ци- кле останется только олин условный переход. Сравните время работы модифицированной и исходной программ. ь 13. [34) (Сокращенные ключи.) Пусть Ь(К) представляет собой хеш-функцию, а д(К)— функцию от К, такую, что К можно определить по данным И(К) и д(К). Например, в случае хеширования путем деления можно положить Ь(К) = К шод Ы, а д(К) = (К/Ав); при мультиплпкативном же хешировании в качестве Ь(К) можно взять старшие биты (АК~и) |под 1, а в качеств о(К) — осгальные биты.
Покажите. что при использовании цепочек без списков перекрытий достаточно хра- нить значение о(К) вместо К для каждой записи. (Это позволяет сэкономить простран- гтво, необходимое для полей ссылок,) Измените алгоритм С, чтобы он позволял работать с такими сокращено.лми ключами н можно было избежать использования списков пере- крытий и вспомогательной памяти для хранения переполняющих записей. 14.
[34[ (Э. В. Элькок (Е. %. Е1сос)»).) Покажите, что большая хеш-таблица может Раздавать на»пиль с другими связанными списками. Пусть каждое слово области списка имеет двухбитовое поло ТАС и два ссылочных поля (ЬХЯК и АОХ), имеющих следующий смысл. ТАС(Р) = 0 указывает на слово в списке свободного пространства, 1.13К(Р) указывает на следующий элемент в списке, а АОХ(Р) не используется. ТАС(Р) = 1 указывает на используе»юе слово, где Р ие является хеш-адресом никакого ключа из хеш-таблицы; другие поля слова в позиции Р могут иметь любой фо рмат. ТАС(Р) = 2 указывает, что Р представляет собой хеш-адрес, по меныпей мере„одного ключа, АОХ(Р) указывает на связанный список, определяемый всеми такими ключами, а ЫИК(Р) указывает на другое слово в памяти списка.
При каждом обращении к слову с ТАС(Р) = 2 во время обработки любого списка мы присваиваем Р +- 11)В(Р) несколько раз до достижения слова с 110(Р) < 1. (Для эффективности можно также изменить предшествующие ссылки так, что не нужно будет пропускать одни и те же элементы снова и снова.) Определите подходящий алгоритм для вставки и получения ключей из такой хеш-таблицы. 15. (16) Почему в алгоритмах 1. и 1) стбит сообщать о переполнении при Ь? = М вЂ” 1„а не при ?т' = М? 16. (10] В программе Ь говорится, что К не должно быть нулем.
А вдруг на гамом деле она работает при К = О? 17. [16) Почему бы просто не определить Ь»(К) = Ь~(К) в (25) при Ь~(К) эе О? ь 18. (31) Что лучше использовать для замены строк 10-13 программы 1) — (31) нли (30)? Дайте ответ на основании средних значений А, $1 и С. 19. (ХР) Проверьте эмпирически воздействие ограничения области значений Ьз(К) в алгоритме 1), так что; (а) 1 < Ьт(К) < г при г = 1,2,3,...,10; (Ь) 1 < Ьз(К) < рМ при ~о го го 20. (М33) (Р. Крутар (В.
Кгвгаг).) Измените алгоритм 1) следующим образом для удаления хеш-функции Ьз(К): на шаге 1)3 установите с г- О, а в начале шаха П4 установите с < — с+1. Докажите, что, если М = 2, соответствующая последовательность проб Ь|(К), (Ь~(К) — 1) шоб М, ..., (Ь|(К) — ( )) шоб ЛХ будет перестановкой (0,1,..., ЛХ-1». Если такой метод "квадратичных проб" запрограммировать для компьютера 811, как будет выглядеть полученная программа по сравнению с программами, показанными нв рис. 42, в предположении, что алгоритм ведет себя, как при случайном опробовании с вторичной кластеризацией? ь 21.
(36) Предположим, что необходиью удалить запись из таблицы, построенной согласно алгоритму 1), помечая ее как удаленную, как было предложено в тексте. Следует лн при этом уменьшать значение переменной Ж, используемой для управления алгоритмом 1)? 22. (37) Докажите, что алгоритм В оставляет таблицу в таком виде, квк будто 33?РД никогда ие был вставлен. ь 23. (38) Разработайте алгоритм, аналогичный алгоритму В., для удаления элементов из хепьтаблицы с цепочками, построенной по алгоритму С.
24. (МЯО) Предположим, что множество всех возможных ключей имеет ЛХР элементов, из которых ровно Р имеют некоторый данный хеш-адрес. (На практике Р очень велико; например, если ключи представляют собой произвольные десятизначные числа и если М = 10з, то Р = 10'.) Положим М > 7 и ЛХ = 7. Если из множества всех возможных ключей выбраны семь различных, то чему будет равна точная вероятность того, что будет получена хеш-последовательность 1 2 6 2 1 6 1 (т.
е. Ь(Кг ) = 1, Ь(Кз) = 2, ..., Ь(Кг) = 1)? Выразите ответ в виде функции от ЛХ и Р. 23. (М19) Объясните, почему верна формула (39). 26. (МЯО) Чему равно количество хеш-последовательностей а~ оз... аэ, дающих при использовании линейного исследования картину занятых ячеек, приведенную в (21)? 27, (ЛХ37) Завершите доказательство теоремы К. (Указание, Пусть лля доказательства того, что в(н,х, Р) = х(х + у)" + пв(п-1,х+1, Р-1), используйте биномивльную теорему Абеля (1.2.6-(! 6) ),) 28. [Муд] "В те времена укромные, теперь почти былинные'", когда компьютеры были очень медлительными, по скорости мигания лампочек иа панели можно было увидеть, иасколько быстро работает алгоритм 1..
Когда таблица заполнялась почти до конца, можио было заметить, что одни даииые обрабатыввлигь очень быстро, а друпге — очень медленно. Эти наблюдения наталкивают на мысль о большом значении стандартного отклоиеиия количества проб в случае неудачного поиска при использовании линейного исследования. Найдите формулу, выражающую дисперсию через функции О из теоремы К, и оцените ее зца юпие при М = аМ и М -+ оо. 29.
[М311 (Задача о паркоеке.) Предположим, существует некоторая улица с односторонним движением. имеющая т мест для парковки, пронумерованных от 1 до гп. В автомобиле рядом с водителем дремлет его жена, которая вдруг просыпается и требует немедленно остановиться. Муж послушио выполняет требование жены и остаиевливается на первом свободном месте для парковки. Однако, если "нет нигде стоянки, Брайтон весь забит", т. е. впереди иет ни одного свободиого места (жеиа просиулась в тот момент, когда автомобиль проезжал Ь-е место парковки, в все места Ь, Ь+ 1,..., т были заняты), законопослушность водителя перевешивает послугциость жене и ои, принеся свои извипеиия, едет дальше, Предположим.
что нв одной улице оказалось и автомобилей с дремлющими жеиами, причем У-я жена (имеется в виду, конечно же, жена У-го водителя. — Про»». нерее,) просыпается напротив а,-го места парковки. Сколько последовательностей ам .. а позволят всем автомобилям успешно припарковаться, если предположить, что первоначально улица была пуста и что ни один из припарковавшихся автомобилей ие уехав. Например, при т = и = 9 и а~...
а» = 3 1 4 1 5 9 2 б 5 автомобили будут припаркованы следующим образом. [Укозеиие. Воспользуйтесь анализом линейного исследования.] 30. [МЯ8] Покажите, что в задаче о парковке из упр. 29 при и = гп все машины припарковывшотся тогда и только тогда, когда существует перестановка р~ рз...р множества (1, 2,..., и), такая, что а„< р, для всех у', 31. [М40] При им ш в упр.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
