Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 2) (1119371), страница 15
Текст из файла (страница 15)
Отдельные списки, датируемые примерно 300 г. до н. з., которые были найдены на островах Эгейского моря, содержат имена членов некоторых религиозных общин, упорядоченные только по первой букве (представляя, таким образом, результат одного прохода поразрядной сортировки слева направо). Некоторые греческие папирусы, датируемые 134-135 г. н. э., содержат списки налогоплательщиков, упорядоченных по первым двум буквам. Аполлоний Софист«* (Аро11опшз БорЫзса) использовал алфавитный порядок по первым двум буквам (а иногда н по последующим) в своем словаре поэзии Гомера (1 в. н. э.).
Известны примеры более совершенного упорядочения, например Н!рросгайс С!оазез Галена«*е (ок, ЮО г.), но это было крайне редким явлением. По первым буквам были упорядочены слова и в Егуто!ой!агпш Св. Исидора (ЯФ. 1зЫогпз)вв«е (ок. 630 г., книга Х), а в Согрнз 6!оззагу (ок. 725 г.) использовались только две первые буквы каждого слова. Эти две работы были, пожалуй, крупнейшими нечисловыми файламн данных, скомпилированными в средние века. Впервые описание алфавитного порядка появилось в Сазьойсоп Джованни Генуэзского (С(оуапш 61 Оепоа'з) в 1286 году. В предисловии поясняется, что ьзьо аФео ашот зпзрибепз сиз!из ро!мзепиз предшествует предшествует предшествует предшествует предшествует предшествует ашо аЬео ага а!из !таргзм(епз сиз!заза ро!мзпгйегоп (т. е.
приводятся примеры ситуаций, в которых порядок следования слов определяется первой, второй, ..., шестой буквами)»и далее точно так же". Он отмечает, что для изобретения подобного способа упорядочения слов потребовались значительные усилия. »Я прошу тебя, читатель, не презирать мой огромный труд н этот порядок, как нечто ничего не стоящее." Подробным изучением развития алфавитного порядка до начала книгопечатания занимался Ллойд В. Дейли (1,1оуб %. Па1у) (Со!!есбоп Еагошиз 90 (1967), 100 р.], «такая же система была принята в Древней Руси: применялись алфавит и специальный символ ("титло"), а также некоторые дополнительные обозначения для тысяч, миллионов и т.
д. — Прим. нерее. ««Одни из грамматиков древности; выкодец из Александрии. ««* Римский врач и естествоиспытатель, классяк античной медицины. *«««Исидор Севильский — испанский епископ, выдаюпгийся ученый и писатель. Им найдено несколько интереснейших старинных рукописей, которые, несомненно, использовались в качестве черновых записей при сортировке слов по первой букве (см, с. 89-90 его монографии). В первом словаре английского языка Роберта Коудри (НоЬегь Савч(геу) 2ЪЫе А!рЬаЬег!са)! (Ьопбоп, 1604) содержатся следующие инструкции.
Если слово, которое ты ищешь, начинается с "а", то ищи его в начале, а если оно начинается с "г", то ищи его в конце книги. Опять-таки, если слово начинается с "са", то искать его следует в начале буквы "с", а если с "сн", то смотреть надлежит в конце этой буквы. И так поступай до конца слова. Создается впечатление, что Коудри сам учился своему методу расставления слов в алфавитном порядке в процессе работы — на первых страницах словаря многие слова находятся не на своих местах, в то время как остальная часть словаря содержит гораздо меньше ошибок.
Бинарный поиск был впервые упомянут Джоном Мочли (ЗоЬп МансЫу) в, пожалуй, первой опубликованной дискуссии о нечисленных методах программирования (ТЬеогу апс! 2ЬсЬпк!иев гог гЛе Овэ!бп о! Е!ее!гоп!с О!8!Фа! Сотригегэ, ео1гео Ьу О. Ж. Раыьтвоп, 1 (1946), 9.7-9.8; 3 (1946), 22.8 — 22.9].
Метод становится хорошо известным программистам, однако ни у кого не возник вопрос, как работать с Ь!, не равным 2" — 1. (См. А. О. ВоотЬ, г!агиге 176 (1955), 565; А. 1, Ошпеу, Сошригегэ апд А иготайоп 5 (ОесешЪег, 1956), 7 (здесь бинарный поиск назван так: "Двадцать вопросов"); Оаше1 О. МсСгасйеп, О!8!Ге! СотриГег Ргойгагпш!п8 (%!1еу, 1957), 201-203; М. На!реги, САСМ 1,1 (РеЬгцагу, 1958), 1-3.] Д.
Г. Лехмер (О. Н. ЬеЬшег), пожалуй, был первым, кто опубликовал алгоритм бинарного поиска, работающий при любьгх Х ]Ргоа сутр. Арр!. МаВь 10 (1960), 180-181]. Следующий шаг был сделан Г. Боттенбруком (Н. ВогсепЬгцсЬ), который представил интересный вариант алгоритма В, в котором отдельные проверки равенства отодвигаются в конец алгоритма (Х4СМ 9 (1962), 214], Используя ! ~- !'(!+и)/2] вместо ! ~- '1(! + и)/2] на шаге В2„он устанавливает ! г — ! при К > К;; тогда и — ! уменьшается на каждом шаге. В конце, когда ! = в, мы имеем К! ( К < К~~~ н можем проверить, является ли поиск успешным, при помощи еще одного сравнения (Боттенбрук полагал, что изначально К > К~).
Данная идея позволяет несколько ускорить внутренний цикл на многих компьютерах; этот же принцип может быть применен и к другим алгоритмам поиска, обсуждавшимся в этом разделе, Впрочем, успешный поиск потребует в среднем около одной дополнительной итерации в соответствии с (2). Так как внутренний цикл выполняется примерно около 18 Ф раз, более быстрый цикл сможет компенсировать дополнительную итерацию только при очень больших Ф (см.
упр. 23). С другой стороны, алгоритм Боттенбрука будет находить крайнее справа вхождение ключа в таблицу, имеющую дубликаты; а это свойство алгоритма может оказаться важным для определенного класса задач. К. Ю. Айверсон (К. Е. 1гегэоп) (А Ргойгаглт!п8 Ьапхпабе (%!!еу, 1962), 14Ц привел описание алгоритма В, однако не рассмотрел случай неудачного поиска. Д. Э. Кнут (О. Е. КпнгЬ) (САСМ 6 (1963), 556-558] представил алгоритм В в качестве примера, использованного автоматической системой построения блок-схем. Однородный бинарный поиск (алгорнтм С) был предложен автору А. К. Чандрой (А. К.
СЬаш(га) из Станфордского университета в 1971 году. Поиск Фибоначчи изобретен Дэвидом Э. Ферпосоном (ПагЫ Е. Регбцвоп) [САСМ 3 (1960), 648]. Бинарные деревья, подобные деревьям Фибоначчи, появились в "пионерской" работе норвежского математика Акселя Тью (Ахе1 ТЬце) еще в 1910 году (см. упр. 28). Деревья Фибоначчи без меток появились также в качестве курьеза в популярной книге Хьюго Штейнгауза (Нцбо БсеьпЬацв) Маьйешайса) БпарвЬосз (Ыев Уогй: БгесЬег1, 1938, с. 28).
Они изображались корнем вниз и выглядели почти как настоящие деревья, с правыми ветвями, которые были в два раза длиннее левых (так что все листья находились на одном уровне). Ннтерполяционный поиск был предложен В. В, Петерсоном (%. 'гг'.
Ресегвоп) [1ВМ Х Нгн. 3г Веге). 1 (1957), 131-132], однако корректный анализ этого метода был сделан значительно позже (см. упр. 22), УПРАЖНЕНИЯ 1. [31] Докажите, чта если на шаге В2 бинарнага поиска и с Ь та в =1 — 1 и К, < К < Кь (Полагаем, что Ка = — оа и Кл+~ = +со, хотя зти искусственна введенные ключи в действительности алгоритмом не испальзуютсл и не обязаны находиться в таблице.) ° 2. [26] Будет ли алгоритм В прсдалжать корректно работать при наличии К в таблице, ели мы: (а) установим на шаге Вб "1 +- г" вместо сй < — 4+ 1"; (Ь) установим на шахе В4 "в +- Р вместо "и г- 1 — 1"; (с) внесем аба зти изменения? 3.
[46] Какой метод поиска соответствует дереву Каково среднее число сравнений выполняется при успешном и неудачном поиске? 4. [лд] Если поиск с использованием программы 6.13 (последовательный поиск) выпалняетсв ровно 636 единиц времени, та как долго будет работать программа В (бинарный поиск)? б. [Мй(] Для каких значений г? программа В в среднем въшалняется медленнее последавагельнага поиска (праграмма 6.1()') в случае успешного поиска? 6. [28] (К. Ю. Айеерсон (К. Е. 1тегвап).) Упр. 5 принадит нас к мысли, что стбит иметь некий гибридный метод, переходящий ат бинарного поиска к последовательному при лостата'шам уменьшении интервала поиска.
Напишите соответствующую программу для Н1Х-кампьютера н определите наилучший момент перемены метода поиска. 7. [МЗЗ] Будет ли алгоритм (5 корректно работать, если мы изменим шаг Б1 так, чта а) и Ь и гп установятся равными [г?/21; Ь) и Ь и ш установятся равными [К/2]? ]Уюиаяие. Предположите, чта первый шаг был "Установить 1 +- О, т <- К (или Ж+ 1), перейти к шагу С4".] 6. [М20] Пусть д, = вйьта (?3 является у-и приращением в алгоритме С, как определена в (6). а) Чему рвана сумма 2 1вл1.~-24 т Ь) Чему равны минимальное и максимальное значения в, которые могут паявитьсв на шаге С2? й.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
