Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 2) (1119371), страница 60
Текст из файла (страница 60)
Рассортируйте отдельно информационные и налоговые карточки, используя в качестве ключа идентификационный номер. Обозначим рассортированные налоговые карточки через Км..., Кл, а их ключи — через К~ С . С Кл. (Не должно быть обнаружено ни одной пары карточек с повторяющимися ключами.) Добавьте новую (М + 1)-ю запись с ключом оо и установите 1+- 1. Затем для каждой записи из информационного файла проверьте, было ли о ней сообщено, следующим образом. Обозначим через К ключ обрабатываемой информационной карточки, а) Если К > Кп то увеличить 1 на 1 и повторить этот шаг. Ь) Если К < К, или К = Кп а соответствующая информация пе отображена в налоговой карте ~ке Кп то сообщить об ошибке. Постарайтесь проделать все это, не тратя впустую денег налогоплательщиков.
12. Один из способов состоит э том, чтобы присоединить к элементам матрицы ост ключи (~,1), лексикографнчески рассортировать элементы по этим ключам, после чего ключи В1.Т СОИ СОИ СОИ СОИ ТИХИ СОИ СОИ СОИ СОИ СОИ "1 -1 0 "1 +1 "1 "1 0 О О 1 О -1 1 0 1 1 $ отбросить. (Подобная идеи применима в любом случае, когда нужно переупорядочить информацию, если желаемый новый порядок выражается простой формулой.) В частном случае, рассмотренном в этой задаче, можио воспользоваться сбаланси- рованной двухпутевой сортировкой методом слияния, при которой ключи обрабатыва- ются настолько просто, что их фактически ие иужио явно записывать иа ленту.
Пусть задана матрица и х и; тогда можно действовать следующим образом. Сначала запи- шем строки с нечетными номерами иа лепту 1, а строки с четными номерами — иа ленту 2: Лента 1: о~ ~ аш... а~» аэ~ азэ... оз» аы аээ... аэ Лепта 2: оз1 оээ ° . ° оэ» Оы я»2 ° ° и»» ое1 обэ ° Ое» Затем перемотаем лепты в начало и будем считывать с иих информацию синхронно, чтобы получить Лента 3: аи аэ~ а~эаээ... аг» аэ» аы ае~ ею а»э .,оь» ое Лента 4: аэ~ аыоээою...аэ» ое»ам аз~ огэоээ . аг»аэ» Перемотаем вторую цару лент в начало и вновь будем считывать с иих данные синхронна: Лента 1: ам аэ~ ам вы ош... аю...о»» аел...
Лепта 2: аы ее~ аи аы аш... аээ... аэ» а~э,~ И так до тех пор, пока после ~15 и) просмотров не получится требуемая траиспоиированная матрица. 13. Один из методов состоит в том, чтобы добавить к записям различные случайные клю- чи, выполнить сортировку по этим ключам, а затем их убрать. (Ср. с упр. 12; эиалогичиый метод получения случайной выборки рассматривался в разделе 3.4.2.) Другой подход, требуэиций приблизительно столько же трудозатрат, ио, по-видимому, в меньшей степени зависящий от качества генератора случайных чисел, состоит в том, чтобы присоединить к В, случайное целое число в диапазоне 0 < К; ( М вЂ” г, а затем переупорядочить записи, пользуясь методом из упр. 5.1.1-5.
14. Имея таблицу перекодировки, можно написать программу лексикографического срав- нения, которая имитировала бы упорядочение, используемое на другом компьютере. Или же можно создать искусствеииые ключи, отличные от реальиых литер, но дающие жела- емое упорядочение. Последний метод имеет преимущество: такую операцию достаточно проделать один раз, однако потребуется больше памяти и нужно будет преобразовать весь ключ целиком. В первом методе результат сравнении часто можно определить, преобразо- вав всего одиу-две буквы ключей; иа последующих стцциях сортировки будут сравниваться почти равные ключи, поэтому в первом методе, видимо, выгоднее, прежде чем преобразо- вывать буквы, проверить, не равны ли они.
15. Заведите приблизительно 50 отдельных счетчиков и просмотрите весь файл один раз. Но если бы в условии задачи вместо слова "штат" стояло слово '"город" и общее число городов было довольно велико, то следовало бы предпочесть сортировку по названиям городов, 16. Как и в упр. 15, решение зависит от объема задачи. Если количество идентификаторов для перекрестных ссылок не очень велико и их можно разместить в оперативной памяти, то лучше всего, пожалуй, воспользоваться алгоритмом обработки таблицы символов (см. гл. 5), в котором с каждым идентификатором связывается голова связного списка ссылок. Если же задача большая, необходимо создать файл записей, по одной на каждую ссылку, которая виосится в указатель, а затем рассортировать этот файл.
17. Присвойте всем карточкам "теневые ключи", чтобы требуемое упорядочение можно было выполнить с помощью обычной лексикографической сортировки по этим ключам. Этот ключ должен быть внесен персоналом библиотеки в каждую карточку, когда она впервые поступает в систему. Можно, например, использовать следующий двухбуквенный код дая разделения слов: епй о1 1сеу; епй о1 огоев-ге1»зевсе; епй о1 впгпаше; ЬурЬеп о1 пш111р!е вшгпаш; епй о( апсЬог пыое; епй о1 р1асе паше; епй о( ввЬЛесс Ьеай(пб; епй о1 ЬооЬ с(г)е; врасе Ьеснееп иогйв. цО н1 н2 цз ц4 цБ цб цу „3 Приведенный выше пример кодирования разделителей даст следующий результат (показаны только первые 25 литер): АССАОЕНХЬ ЗИАЕХОНАЬЕ ЮОЕХ АСНТХЕНИНОНОЕВТЕНОЬР~ЮЕХИ ВХБЬХОТНЕООЕи80иЗНХБТОХЙЕ ВХВЫОТНЕЦОЕнЮОЕБнЗСОВХОБ ВМИИн2ЛнЗСВОБВТи4цо ВМЧИн2 10НИцацо ВМИИн2ЛОНИцАНАТНЕНАТХСХА ВМИИн2ЛОНИн40рцЮВОБТОИно ВМИНн2ЛОННн41716цо ВМИИц2ЛОБИн41716цбнО ВМгюц2ЛОВИц41761цО ВВОИИн2ЛОЕИи41810 О ВМИИ~ЗНХХЛ.ХАН3~2НЕСХИЫЛ ВИСНИ ЮАНЕВХСА 7 О ВМИИнЮАИОиЗРАЬЬХБОИБнЗИЕ ВМИИЛОННн241АИн4цо ОЕИн2ТХАРХИХЗ ~ЗЕООАВООТХС ОЕИн7 О ОЕИн81 1ЕВЕИц81 АИСЕИцВТАСн 011ц2НОВСАИц41827цо ОХХцЮНОХТцЗСЕИТц8001гсЕц80 011рЮИЕОТХЕНЕнЗБХЕСЬЕиВРВ ЕХСНТЕЕИцЮРОВТТцЗБЕУЕИн81 Е1СНТЕЕНцВТНЕХЛЕцЗОТЕВТОН 1нВАНцВАнЗНАТНЕНАТХС1АИц7 1нЗВнЗНнВЛООБИА1 нВОРнВЕЕБ » Имя арабского ученого Аль-Хорезми е английской транскрипции.
— ХХрц»г. верее. За таким вспомогательным ключом должны следовать данные из соответствующей карточки, чтобы можно было различать неодинаковые карточки с одинаковыми ключами (т, е. "31г ЛоЬл» означает»ЛоЬп" ). Обратите внимание, что»Еа(ас-Яаеп⻠— зто имя с дефисом, а не составное имя. Год рождения а1-К1шъйпвпй» должен быть представлен в виде 40779 с ведущим нулем. (Данная схема будет хорошо работать до 9999 года, после чего мир окажется перед лицом очередного информационного кризиса.) Внимательно изучив этот пример, вы сможете решать аналогичные задачи с другимн необычными типами упорядочения, которые требуют совместных усилий человека и компьютера. 18. Подготовьте два файла, из которых один содержит числа (ве + в + ш~) шоб гл, а второй — чнсла (хе — хе — уе) шобтп, и < а < ы, х < у < х, где т — длина слова в используемом компьютере.
Рассортируйте оба файла и найдите в них общие элементы, которые нужно будет подвергнуть дальнейшему анализу. (в(ожив наложить дальнейшие ограничения на в, а, ы, х, у, х с учетом того, что малые простые числа можно также сравнить по модулю,) 19. В общем случае для нахождения всех пар чисел (х,, х ), таких, что х;+ хз = с, при заданном с достаточно рассортировать файл так, чтобы хэ < хз « . хл. Присвоить(+- 1, У +- )т' и затем повторять следующую процедуру до тех пор, пока не будет удовлетворено условие 2 < 1: если х; + хз = с, то вывести (х,, х;), устеловиты е- 1+ 1, у е- у — 1; если х; + хз < с, то установить 1 е- 1+ 1; если х; + хз > с, то установить у е- у — 1.
И наконец, если у = 1 и 2х; = с, вывести (хпх,). Этот процесс аналогичен методу, описанному в упр. 18; по существу, мы подготовили два рассортированных файла, в одном из которых записаны хм..., хл, а в другом — с-хи,..., с — хм н отыскали в инх дублирующиеся элементы. Но в данном случае второй файл не обязательно должен присутствовать в явном виде.
При нечетном с возможен и другой подход — рассортировать файл по ключу (х нечетное =ь х, х четное ~ с — х). Аналогичный алгоритм мохсно использовать и для поиска шах(х, + хэ ( х; + х; < с) или, скажем, для поиска при заданном 1 ппп(х; + уз ) х;+ у. > 1) в двух рассортированных файлах — х~ < < х и р < ° . < у . 20. Вот некоторые из возможных решений. (а) Для каждой из 499 500 пар 1, у, таких, что 1 < 1 < 1 < 1000, установить у~ < — хэ Юх;, уэ е- у~ Л (у~ — 1), уз е-уз Л (уз — 1), после чего вывести (ха ху) в том и только в том случае, если уэ = О. Здесь символом "Ю" обозначена операция "исключающее или", а символом "Л" — операция "поразрядное и1 (б) Создать файл из 31 ООО зяементов, образовав для каждого исходного слова х; по 31 элементу, а именно — само х, и еще 30 слов, отличающихся ат него значением в одном иэ разрядов.
Затем рассортировать этот файл и найти повторяющиеся элементы. (в) Выполнить анализ, аналогично варианту (а), для 1) всех пар слов, старшие 10 разрядов которых совпадают; й) всех пар слов, средние 10 разрядов которых совпадают (но старшие 10 разрядов различаются); Й) всех пар слов, младшие 10 разридов которых совпадают (но ни старшие, ни средние не совпадаот).
Этот метод предполагает выполнение трех процедур сортировки (каждая из которых— по одному из описанных 10-разрядных ключей). Если исходные слова представляют собой случайный набор, то ожидаемое число пар в каждом из трех случаев будет, по крайней мере, 499500г'2'", что не превышает 500. 21.
Прежде всего подготовьте файл нз всех пятибуквенных английских слов. (Не забуш»те о том, что такие слова могут образовываться и путем добавления суффиксов наподобие -ЕО, -ЕЕ, -ЕЕВ, -$ к более коротким словам,) Затем рассортируйте буквы каждого слова а по возрастанию и обозначьте этот упорядоченный набор через о( Наконец, рассортируйте множество пар (а', а), собрав таким образом вместе все анаграммы. Эксперименты Кима Д.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
