Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 2) (1119371), страница 106
Текст из файла (страница 106)
Коды символов удовлетворяют соотношениям Л+ Т = 1+ й,  — Е = Π— В, а потому получим либо /(АТ) = /(18), либо /(ВЕ) = /(Ой). Обратите внимание на то, как команды 4 н 5 из табл. 1 разрешают зту дилемму, оставляя г11 в достаточно узком диапазоне. 4. Рассмотрим случай для й пар. Наимеяьшее я, такое, что тл "п(~ ( )( )2»с — притл=365, равно 88. Если вы пригласите 88 человек (включая себя), вероятность появления трио с одним днем рождении составит ООП1065; для 87 человек зта вероятность снижается до 0.499455.
См. С, Р. Ршхйа, АММ 67 (1960), 830. 6. Эта хеш-функция плоха, поскольку она принимает не бтшее 26 различных значений, причем некоторые из них будут встречаться явно чаще других. Даже при двойном хептировании (если предположить, например, что йт(К) = 1 + опюрой байта К и ЛХ = 101) низкая скорость поиска превысит выигрыш от высокой скорости вычисления хеш-функции. Кроме того, поскольку в программах на языке РОЕТЕАМ часто встречаетсл куда больше, чем 100 различных переменных, значение ЛХ = 100 явно малб, 6.
Не на 811-компьютере, поскольку почти всегда будет получаться арифметическое переполнение (слншком велико делимое). (Было бы неплохо иметь возмолтность вычислить (тоК) шот( М, в особенности для линейного исследования прн с = 1, яо, к сожалению, большинство компьютеров не предоставляют ее нз-за переполнения частного.) Т.
Если Е(х) кратен Р(х), то Н(ат) = О в СР(2 ) для всех у 6 Я. Пусть Е(х) = х" + +х»', где ат » . а, > 0 н о с к Выберем 1 — о значений а»+т,,от, таких, что ат,..., о, представляют собой различные неотрицательные числа, меньшие и. Матрица Вандермоцла сингулярнв, поскольку сумма ее первых в столбцов равна нулю, Однако зто противоречит тому факту, что и",..., и" — различные злементы СР(2 ) (см. упр.
1,2.3-37). (Первоначальяо идея полиномиального хеширования была предложена группой исследователей из 1ВМ (М. Напал, Я. Мвго8а, Р. Р. Ра1егпю, ЬЬ Ваоег, апт( С. Ясйау, 1ВМ Х Нсзеагсй Зо 1тете)ортелс 7 (1963), 121-129; см. также Г 5. Раселс 3311888 (1967)).) 8. По индукции. Сильная индуктивная гипотеза может быть дополнена тем фактом, что ((-1) "(г9» + 9»-т)д) = (-1)»(г(9»д — р») + (9» тд — р» т)) при 0 с г с а». "Рекордна низкие" значения (пд) достигаются для и = Ф, 9»+9», 29»+От,, а»9»+ От = 094+9», т?» + 9», ..., а»9» + Тз = От?» + То, ..., "РекоРдно высокие" — длЯ а = Тот Ф + То, ..., а»9т + Оо = Од» + От, ....
Это шши, на которых формируется интервал с номером 0 новой длины. (Дальнейшая структура может быть выведена обобщением системы счисления Фибоначчи из упр. 1.2.8-34; см. Ь. Н, Напмйаи, Х Хвшйег Тйеогу 13 (1981), 138-175.) 9. Имеем ф т ы //1,1,1,...// и б т = //2,1,1,...//.
Пусть д = //ат,аз,...//, 8» = //а»+ы о»+и . // и пусть Я» = 9»+ 9» тд»-т в обозначениях из упр, 8. Еслн от > 2, плохим являетсн самое первое разбиеяне. Три размера интервалов в упр. 8 равны (1 — гд» т)Я», Бь 1/йь и (1 — (г — 1)9ь ~)/(кь соответственно, так что отношение первых двух длин составляет (вь — г) + Бь. Эта величина меньше — при г = оь и аз+1 > 2; следовательно, чтобы не было плохих разбиений (вы аз, .) должны быть равны 1. (Другие связанные с данной темой теоремы можно найти в рабате Н.
Ь. СгаЬаш апд 1. Н. тап [.!пг, Саишйал 3. Маей. 20 (1968), 1020-1024, и в указанной в ней литературе.) 10. Вы найдете злегантное доказательство в работе г. М. ХАапК, [))зсгеге Мас)ь 28 (1979), 325-326. 11. Проблемы могут начаться при К = О. Если потребовать, чтобы все ключи были ненулевыми, как в программе 1., такое изменение может иметь смысл„при этом можно было бы помечать пустые позиции нулевым значением, 12. Можно хранить К в КЕТ [03, заменив при этом строки 14 — 19 следующими строками. БТА ТАБАК(КЕТ) А — $1 СНРА ТАВ|Е,2(КЕТ) С вЂ” 1 — Б2 СИРА ТАВЬЕ,2(ХЕТ) А — 51 ЛИЕ 2В С вЂ” 1 — $2 ЛЕ ЗР .4 — Б1 ЗН 322 БР А — Б1 2Н ЕИТ1 0.2 С вЂ” 1 — Б2 ЕИТ1 0,2 Б2 (3)2 ТАВ1,Е, 1(1.1ИК) С - 1 — 52 )НР БОСС ЕББ 52 $ "Сохраненное" время составляет С вЂ” 1 — 5А+ Б + 451 единиц, что в результате оборачивается попмреа, поскольку С очень редко превышает 5.
(Оказывается, ие всегда следует оптимизировать внутренние циклы!) 18. Пусть записи в таблице относятся к двум различным типам, как и в алгоритме С, с дополнительным однабитовым полем ТАСИ в каждой записи. В приведенном решении используются циклические списки, следуя предложению Аллена Ньювелла (АПеп Хепе)1), с установленным ТАСИ) = 1 в первом слове каждого списка. А1.
[Инициализация.) Установить ( +- 1 +- А(К) + 1, (4 +- С(К). А2. [Это список?) Если ТАБАК [(3 пуст, установить ТАС [(3 <- 1 и перейти к шагу А8. В противном случае, если ТАС [(3 = О, перейти к шагу А7. АЗ. [Сравнение.) Если (4 = КЕТ[П, алгоритм успешно завершается. А4. [Переход к следующему) Если ЫИКПЗ )А), установить(+- ЫИК[13 и вернуться к 1яагу АЗ. А5. [Поиск пустого узла.[ Уменыпить )1 один или несколько раз до тех пор, пока не будет найдено значение, такое, что ТАВАЕ[Н3 пуст.
Если Н = О, алгоритм завершается после переполяеиия; в противном случае установить 1.1ИК [(3 ь- )1. АО. [Подготовка к вставке.[ Устзиовить 1 <- Я, ТАС [)13 +- 0 и перейти к шагу А8. АТ. [Перемещение записи.[ Установить ( +- 1.1ИК [(3 одна нлн несколько раз, пока ие будет выполнено условие ПИК[(3 ш у.
Затем выполнить шаг А5 и установить ТАЗГ.Е[В) ь-ТАНИ[(3, 1+-3, ТАС[)"3 +- 1. АЗ. [Вставка ясного ключа.) Пометить ТАВ1Е[13 как занятый узел с НЕТ[(3 ь- (4, ЫИКЫ < ) (Заметьте, что, если ТАВ5Е[13 занят, можно определить соответствующий полный ключ К по данному значению 1. Имеем С(К) = КЕТ П3, а затем, несколько раз присвоив ( ь- ЫИК [(3 до тех пар, пока не выполнится равенспю ТАС [13 = 1, получим Ь(К) = 1 — 1.) 14. Согласно указанным соглашениям запись "Х ~ АРАП." нз 2.2.3-(6) теперь означает следующее. "Ус1иновить Х +- АТА11, присвоить Х +- ЫИК(Х) нуль или несколько раз до Х = А (ошибка переполнения) или до ТАС(Х) ш 0 и наконец )становнть АТАП. +- 11ИК(Х)." Для вставки нового ключа К: установить С ~ АЧАТА, ТАСЯ) е- 1 и сохранить К в этом слове.
(Мохсно также, если все ключи коротки, опустить этот шаг и заменить в дальнейших шагах О на К.) Затем усшиовить Е ~м АРАПь ТАС(Е) е- 1, АСХ(Е) +- С, 1.1НЕ(Е) +- Л. Присвоить Р +- А(К), а затем, если ТАС(Р) = О, установить ТАС(Р) г- 2, АСХ(Р) +- Е; если ТАС(Р) = 1, установить Б ~м АУАП., СОИТЕНТБ(Б) +- СОИТЕИТБ(Р), ТАС(Р) з- 2, АСХ(Р) Ф- Е, 11ИН(Р) +- Б; если ТАС(Р) = 2, установить 1.|ИК(Е) +- АСХ(Р), АОХ(Р) +- Е. Для получения ключа К; установить Р +- А(К) н, если ТАС(Р) -,4 2, К отсутствует; если ТАС(Р) = 2, установить Р +- АСХ(Р), а затем присвоить Р +- 1,1ИК(Р) нуль или несколько раз до тех пор, пока не выполнится либо Р = Л, либо ТАС(Р) = 1, тогда либо АОХ(Р) = К (если все ключи коротки), либо АОХ(Р) указывает на слово, содержащее К (возможно, косвенно через слово с ТАС = 2). В оригинальной схеме Элькока (Сошр.
Х 8 (1965), 242 — 243) в действительности исполь- зовазись ТАС = 2 и ТАС = 3 для того, чтобы различить списки единичной длины (когда можно сохранить одно слово памяти) и более длинные списки. Это улучшение заслуживает внимания, поскольку мы предположительно работаем с такой больпюй хеш-таблицей, что почти все списки имеют единичные длины. Другой путь размещении хеш-таблицы "наверху" большой связанной памяти с исполь- зованием срастающихся списков вместо раздельных цепочек был предложен Дж. С. Вит- тером (1. 3.
Ъ')жег) (Гзб Ргос. Гесгегв 13 (1981), 77-79). 16. Зная о том, что всегда имеется свободный узел, можно сделать внутренний цикл более быстрым, поскольку иет необходимости в счетчике для определения, сколько раз был выполнен швг Е2, Волее короткая программа компенсирует одну потерянную<b>Текст обрезан, так как является слишком большим</b>.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
