AOP_Tom3 (1021738), страница 113
Текст из файла (страница 113)
813 †8 ЬаЬопг. А шабаг!пе Гог аИ иог1гегя ЬаЬог геяеагсЬ аявос1айоп 1 аЪопг, яее 1 аЬог МсСа!Ря сооЬЬооЬ МсСаггЬу, 2оЛп, 1927- Мас2бпе-!пберепгГепг сошрп!ег ргобгаппшпб. МасМаЬоп, Маз. Регсу А!ехаш1ег, 1854-1929 Мгя. Вайоиау М!яггеяя оГ гпонгеяяея Науа! яос!е!у оГ Ьопг!оп Яг. РегетвЬпгбег Ее!гппб Яашг-Язепа, Саппйе, 1835-1921 Бге-Маг!е, Оая!оп Р Беш!пагпейса! а18оПГ1нпя 1)пс!е Тош'я саЬгп (1.
Я. Ьпгеап оГ гЬе сепяпя Эамечаная Указание положении (Вг.) игнорируется Дефис рассматринается как пробел Названия книг указываются после составных фамилий 8г в английском тексте превращается в "ап<Г Апостроф в именах игнорируется Артикль в начале текста игнорируется ..., если существительное стоит в именительном падеже Фаягилии идут раньвге других слов Г)!х-Ьп!г сепг Иопге (числительное 1812 на французском языке) Рйх-пепюепге (числительное Х1Х-й на французском языке) Е!8ЛГееп Гогсу-яегел (числительное 1847 на английском языке) Е!8Ьгееп Гие!ге (числительное 1812 иа английском языке) (а Ьоой Ьу НогЬегг 'г!г!епег) (книга Норберта Винера) Аббревиатуры рассматриваются как ряд однобуквенных слов Артикль в начале текста игнорируется Знаки препинания в названиях игнорируются Начальное "а1-" в арабских именах игнорируется Заменяется словом ийаЬого Ссылка на другую карточку в картотеке Апостроф в английском тексте игнорируется Мс = Мас Дефис рассматривается как пробел Указание положения (Ма).) игнорируется "Мгя." заменяется словом «М!ясгеяяь В названиях британских учреждений слово "гоуа!гу" (королевский) учитывается "Бк" заменяется словом аБМпг", даже в немецком тексте Дефис рассматривается как пробел Ба!пге (а Ьоой Ьу ВопаЫ Егг!п Кпп!Ь) (а Ьоой Ьу Ншйег ВеесЬег Ясоне) 'Ч).Я." заменяется словами аНп!гег! Я!а!ее" Замечания Текст карточки Ъапдегшаллг!е, А!ехапбге Т!леорйб!е, 1735-1796 5галл 1га!Ьепйиг8, Мас Е!еуп, 1921- Чоп Хеигпапп, ЗоЬп, 1903-1957 ТЬе лкЬо!е ахб о( !еЕегбеша!п 55'Ьо'б а?ган3 о( Ъ'!гЕ!и!а %ос!1? Пробел после префикса в фамилиях игнорируется Артикль в начале текста игнорируется Апостроф в текстах на английском языке игнори- руется Фамилия никогда не начинается со строчной литеры Ч'!)пЕаагаеп, Абг!аап кап, 1916- (У большинства из этих правия есть исключения; кроме того, существует много других правил, которые здесь не упомянуты.) Предположим, вам поручено рассортировать большое количество таких карточек с помощью компьютера, а затем обслуживать огромную картотеку, причем у вас нет возможности изменить уже сложившийся порядок заполнения карточек.
Как бы вы организовали инфармацию, чтобы упростить операции сортировки и включения новых карточек? 18. [М25) (Э. Т. Паркер (Е Т. Рвг1гег).) Леонард Эйлер высказал предположение [Р?оба Асса Асад. Ясй Реггоро!йвлш 13 (1795), 45 — 63, 53; написана в 1778[, что уравнение и +с +лв +х +у б,б б б б б не имеет нетривиальных решений среди целых неотрицательных чисел и, в, ш, х, у, х.
Одновременно он предположил, что уравнение хл + + х„л — — х„" АРЕВБ, АБРЕВ, РАВЕБ, РАББЕ, РЕАВБ, РВАБЕ, РЕЕВА, ВАРЕВ, ВЕАРБ, БРАЕВ, БРАВЕ, БРЕАВ, к которой можно еще добавить французское слово АРВЙБ.[ не имеет решения в положительных целых числах при и > 3, но зто предположение было опровергнута уже в наше время, когда с помощью компьютера было найдено тождество 27 +84 +110 +133 = 144л [см. 1. 3. Ьаглг!ег, Т.
Н. Рагйбп, апб 3. 1.. Яе!Гг!г!Ее, МайЛ. СотР. 21 (1967), 446 — 459[. Множество аналогичных примеров было обнаружено и при п = 4 Н. Д. Элкисом (ЬЬ П. Е1йбеб) [Маей. Соплр. 51 (1988), 825-835[. Подумайте, как можно было бы использовать сортировку для поиска примеров, опровергающих предположение Эйлера при п = 6.
ь 19. [24[ Файл содержи~ большое количество 30-разрядных двоичных глав: хл,..., хя, Придумайте хороший способ нахождения в нем всех пар с взаимно дополняющими элементами (хн х;). (Два слова называются взаимно дополняющими, если второе содержит нули во всех разрядах, в которых были единицы в первом слове, и наоборот; таким обраэолй они взаимно дополняющие тогда и только тогда, когда их сумма равна (11... 1)э, если они рассматриваются как двоичные числа.) ь 20. [25] Имеется файл, содержащий тысячу 30-разрядных двоичных слов хн...,хлебе. Как бы вы стали составлять список всех пар (х„х,), таких, что х; отличается от х, не более чем в двух разрядах? 21. [22[ Как бы вы поступили, если бы вам нужно быяо найти все пятибуквенные шгаграммы, такие как САВЕТ, САВТЕ, СЯТЕВ, СВАТЕ, ВЕАСТ, ВЕСТА, ТВАСЕ! СЮЖЕ, ЬОСВЕ, ОЬСЕВ; ОДВТ, ВОВОТ, ВОВОТ? [Или если бы вы, допустим, захотели узнать, существуют ли в английском языке наборы из десяти или более анаграмм, кроме замечательной серии 22.
[М28) Пусть даны аписы~ив весьма большого числа ориентированных графов. Как можно струппировать озомо?гриме графы? (Два ориентированных графа называются изоморфными, если существует взаимно однозначное соответствие между их вершинами и взаимно однозначное соответствие между их лугами, причем эти соответствия сохраняют инцидентность вершин и дуг.) 23. [ЯО) В некоторой группе из 4 090 человек каждый имеет около 100 знакомых. Был составлен список всех пар людей, знакомых друг с другом (Это отношение симметрично, т. е. если х знаком с у, то и у знаком с х.
Поэтому в списке содержится примерно 200 000 пар.) Придумайте алгоритм, который по заданному?г выдавал бы все клики из 6 человек. (Клоки — это группа людей, в которой все знают друг друга.) Предполагается, что не бывает слишком больших хлик (размером более 2о). ь 24. [90) Три миллиона человек с различными именами были уложены рядом непрерывной цепочкой от Нью-Йорка до Калифорнии Каждому из них дали листок бумаги, на которол~ он написал свое пмя и имя своего ближайшего западного соседа.
Человек, находившийся в крайней западной точке цепи, не понял, что ему делать, и выбросил свой листок. Остальные 2 999 999 листков собрали в болыпую корзину н отправили в Национальный архив, в Вашингтон, округ Колумбия. Тал~ содержимое корзины тщательно перетасовали и записалп на магнитные ленты.
Специалист по теории информации определил, что имеется достаточно сведений дчя восстановления списка людей в исходном порядке. Программист нашел способ сделать зто менее чем за 1 000 просмотров лент с данными, используя лишь последовательный доступ к файлам на лентах н небольшой объем оперативной памнти.
Как ему это удалось? [Другимн словами, как, имея расположенные произвольным образом пары (х„х, ~), 1 < 1 < Ж, где все х, различны, получить последовательность я~ хе... хл, применяя лишь методы последовательной обработки данных, которые пригодны для работы с магнитными лентами? Это сортировка в случае, когда трудно определить, какой из двух ключей предшествует другому; мы уже поднимали этот вопрос в упр. 2 2.3 25,[ 2б. [Мй?) (Дисхреглнис легари|мы.) Пусть известно, что р — простое число (довольно большое), а а — первообразный корень по модулю р, Следовательно, для любого 6 в диапазоне 1 < Ь < р существует единственное и, такое, что а" глоб р = Ь, 1 < и < р.
(Это и называется индексом Ь по модулю р па отношению к о.) Как по заданному Ь найти и менее чем за (?(и) шагов. [Указание. Пусть т = [э/р~(. Попытайтесь решить уравнение а "' = Ьа " (по модулю р) при 0 < ям из < т.[ б.2. ПОИСК ПУТЕМ СРАВНЕНИЯ КЛЮЧЕЙ В ЭТОМ РАЗДЕЛЕ мы обсудим методы поиска, основанные на линейном упорядочении ключей (таком, как числовое или алфавитное). После сравнения данного аргумента К с ключом К, из таблицы поиск продолжается одним из трех путей, в зависимости от того, какое из условий — К < Кп К = К, или К > К! истинно.
Последовательные методы поиска, рассмотренные в разделе 6.1, по сути, имели только два варианта ветвления поиска — в зависимости от выполнения или не выполнения утловия К = Кц прн отказе от исключительно последовательного доступа к таблице можно организовать более эффективный поиск с использованием отношения порядка. К! < Кз « ' ' ' КФ и в которой мы имеем простой и быстрый доступ к ключу в любой заданной позиции. После сравнения в такой таблице Л и К, мы получим один из трех результатов: ]Лп Л; !,..., Лк исключаются из рассмотрения); ]поиск завершен]; ]Л!, Лю..., Л, исключаются из рассмотрения]. ° К < К! ° К=К, ° К>К, В каждом из них в процессе поиска достигается существенный прогресс — за исключением тех случаев, когда ! близко к одному из концов таблицы (более корректно было бы сказать "к одному из концов рассх!атрнваел!ой части таблицы".
— Прим. перев.). Таким образом, с помощью упорядочения можно построить эффективные алгоритмы поиска. Бинарный поиск. Вероятно, первым методом, который приходит в голову, является следующий: сравнить К со средним ключом в таблице, в результате этого сравнения определить, в какой половине таблицы находится искомый ключ, и снова 6.2.1. Поиск в упорядоченной таблице Что вы станете делать, если вам вручат большой телефонный справочник и попросят найти владельца телефояа 444-3522? Вряд ли вы сможете предложить чтото лучшее, чем метод пег"!едовательного поиска нз раздела 6.1 (методы наподобие "позвонить и спроситсз кто это" и "купить компакт-диск с телефонной базой данных службы '09"' не рассматриваются).
Беда в том, что, хотя в справочнике и содержится вся необходимая информация для поиска как по имени абонента, так и по его номеру, поиск по имени владельца гораздо проще именно благодаря упорядочению записей в телефонном справочнике. Последовательный поиск в огромном файле— это почти всегда безумие н пустая трата времени, но если файл упорядочен, решить задачу намного проще. Вопросы сортировки рассматривались в главе 5, а потому нам не сложно выбрать подходящий метод сортировки, упорядочить данные и тем самым существенно облегчить задачу поиска. Само собой, выполнить однократный поиск в некоторой таблице проще последовательным методом, безо всякой сортировки; однако, если необходим многократный поиск, затраты на сортировку окупятся очень быстро.
Таким образом, в этом разделе мы рассмотрим методы, обеспечивающие эффективный поиск в таблице, в которой ключи удовле!воряют условию чиоа аааериаииа Уоиеииое аааариеиие Рис. 3. Бинарный поиск, применить ту же процедуру к половине таблицы. Максимум за величину порядка 15 1о' сравнений мы найдем искомый ключ [либо установим, что его нет в таблице). Эта процедура известна как 'логарифмический поиск" или "метод деления пополамо но чаще всего употребляется термин бинарный поиск. Хотя основная идея бинарного поиска сравнительна проста, детали его реализации нетривиальны и много неплохих программистов ошибались при первых попытках написать соответствующую программу. В одной вз наиболее популярных форм реализации метода используются два указателя, 1 и и, которые указывают верхнюю и нижнюю границы поиска.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
