отбросить. (Подобная идея применима в любом случае, когда нужно переупорядочить информацию, если желаемый новый порядок выражается простой формулой.)

В частном случае, рассмотренном в этой задаче, можно воспользоваться сбалансированной двухпутевой сортировкой методом слияния, при которой ключи обрабатываются настолько просто, что их фактически не нужно явно записывать на ленту. Пусть задана матрица пхп; тогда можно действовать следующим образом. Сначала запишем строки с нечетными номерами на ленту 1, а строки с четными номерами - на ленту 2:

Лента 1: оп ai2 ... ащ аз1 аз2 ... азп 051 аъ2 аъп Лента 2: 021 022 ... а,2п 041 042 ... а4п aei аб2 . •. авп ..

Затем перемотаем ленты в начало и будем считывать с них информацию синхронно, чтобы получить

Лента 3: ац 021 012 022 ... аы агп аъ\ aei 052 аб2 .. • osn авп ... Лента 4: аз1 041 032 042 ... азп а4п 071 agi 072 а&2 ауп а&п Перемотаем вторую пару лент в начало и вновь будем считывать с них данные синхронно:

Лента 1: Он 021 аз1 041 ai2 ... 042 ... алп оэд •.. Лента 2: osi aei 071 O81 052 . •. 0,82 asn ai3,i ...

И так до тех пор, пока после fig п] просмотров не получится требуемая транспонированная матрица.

13. Один из методов состоит в том, чтобы добавить к записям различные случайные ключи, выполнить сортировку по этим ключам, а затем их убрать. (Ср. с упр. 12; аналогичный метод получения случайной выборки рассматривался в разделе 3.4.2.) Другой подход, требующий приблизительно столько же трудозатрат, но, по-видимому, в меньшей степени зависящий от качества генератора случайных чисел, состоит в том, чтобы присоединить к Ri случайное целое число в диапазоне О < Ki < N - i, а затем переупорядочить записи, пользуясь методом из упр. 5.1.1-5.

14. Имея таблицу перекодировки, можно написать программу лексикографического сравнения, которая имитировала бы упорядочение, используемое на другом компьютере. Или же можно создать искусственные ключи, отличные от реальных литер, но дающие желаемое упорядочение. Последний метод имеет преимущество: такую операцию достаточно проделать один раз, однако потребуется больше памяти и нужно будет преобразовать весь ключ целиком. В первом методе результат сравнения часто можно определить, преобразовав всего одну-две буквы ключей; на последующих стадиях сортировки будут сравниваться почти равные ключи, поэтому в первом методе, видимо, выгоднее, прежде чем преобразовывать буквы, проверить, не равны ли они.

15. Заведите приблизительно 50 отдельных счетчиков и просмотрите весь файл один раз. Но если бы в условии задачи вместо слова "штат" стояло слово "город" и общее число городов было довольно велико, то следовало бы предпочесть сортировку по названиям городов.

16. Как и в упр. 15, решение зависит от объема задачи. Если количество идентификаторов для перекрестных ссылок не очень велико и их можно разместить в оперативной памяти, то лучше всего, пожалуй, воспользоваться алгоритмом обработки таблицы символов (см. гл. 6), в котором с каждым идентификатором связывается голова связного списка ссылок. Если же задача большая, необходимо создать файл записей, по одной на каждую ссылку, которая вносится в указатель, а затем рассортировать этот файл.

17. Присвойте всем карточкам "теневые ключи" чтобы требуемое упорядочение можно было выполнить с помощью обычной лексикографической сортировки по этим ключам.

Этот ключ должен быть внесен персоналом библиотеки в каждую карточку, когда она впервые поступает в систему. Можно, например, использовать следующий двухбуквенный код для разделения слов:

Приведенный выше пример кодирования разделителей даст следующий результат (показаны только первые 25 литер):

АССADEMIAu8NAZI0NALEu8DEI

ACHTZEHNHUNDERTZWOLFuSEIN

BIBLI0THEQUEl,8Du8HIST0IRE

BIBLI0THEQUEu8DESu8CURI0S

BR0WNu2 Ju8CR0 SBYu4uO

BR0WNu2J0HNu4u0

BR0WNu2J0HNu4MATHEMATICIA

BR0WNu2J0HNu40Fu8B0ST0Nu0

BR0WNu2J0HNu41715u0

BR0WNu2J0HNu41715u6u0

BR0WNu2J0HNu41761u0

BR0WNu2J0HNu41810u0

BR0WNu3WILLIAMSu2REGINALD

BR0WNu8AMERICAu7u0

BR0WNu8ANDu8DALLIS0NSu8NE

BR0WNJ0HNu2ALANu4u0

DENu2VLADIMIRu8EDUARD0VIC

DENu7uO

DENu8LIEBENu8LANGENu8TAGu

DIXu2M0RGANu41827u0

DIXu8HUITu8CENTu8D0UZEu80

DIXu8NEUVIEMEu8SIECLEu8FR

EIGHTEENu8F0RTYu8SEVENu8I

EIGHTEENu8TWELVEu80VERnm

Iu8AMu8Au8MATHEMATICIANu7

Iu8Bu8Mu8J0URNALu80Fu8RES

Iu8HAu8EHADu7uO

IAu8Au8L0VEu8ST0RYu7u0

INTERNATI0NALu8BUSINESSu8

KHUWARIZMIu2MUHAMMADu8IBN

LAB0Ru7Au8MAGAZINEu8F0Ru8

UB0Ru8RESEARCHu8ASS0CIAT

LABOURuluO

MACCALLSu8C00KB00Ku7u0

MACCARTHYu 2 J0HNu41927u0

MACHINEu8INDEPENDENTu8C0M

MACMAH0Nu2PERCYu8ALEXANDE

MISTRESSu8DALL0WAYu7u0

MISTRESSu80Fu8MISTRESSESu

R0YALu8S0CIETYu80Fu8L0ND0

SAINTu8PETERSBURGERu8ZEIT

SAINTu8SAENSu2CAMILLEu418

SAINTEu8MARIEu2GAST0Nu8Pu

SEMINUMERICALu8ALG0RITHMS

UNCLEu8T0MSu8CABINu7u0

UNITEDu8STATESu8BUREAUu80

VAm)ERM0NDEu2ALEXANDERu8T

VANVALKENBURGu2MACu8ELWYN

V0NNEUMANNu2 J0HNu41903u0

WHOLEuS ARTu80Fu8LEGERDEMA

WH0Su8AFRAIDu80Fu8VIRGINI

WIJNGAARDENu2ADRIAANu8VAN

3a таким вспомогательным ключом должны следовать данные из соответствующей карточки, чтобы можно было различать неодинаковые карточки с одинаковыми ключами (т. е. "Sir John" означает "John"). Обратите внимание, что "Saint-Saens" - это имя с дефисом, а не составное имя. Год рождения al-Khuwarizmi* должен быть представлен в виде u40779 с ведущим нулем. (Данная схема будет хорошо работать до 9999 года, после чего мир окажется перед лицом очередного информационного кризиса.)

* Имя арабского ученого Аль-Хорезми в английской транскрипции. - Прим. перев.

Внимательно изучив этот пример, вы сможете решать аналогичные задачи с другими необычными типами упорядочения, которые требуют совместных усилий человека и компьютера.

18. Подготовьте два файла, из которых один содержит числа (и* + + w) mod тп, а второй - числа (г* - - у) mod т, и < v < w, х < у < z, где т - длина слова в используемом компьютере. Рассортируйте оба файла и найдите в них общие элементы, которые нужно будет подвергнуть дальнейшему анализу. (Можно наложить дальнейшие ограничения на и, v, w, х, у, z с учетом того, что малые простые числа можно также сравнить по модулю.)

19. В общем случае для нахождения всех пар чисел {xi,Xj}, таких, что xt+Xj = с, при заданном с достаточно рассортировать файл так, чтобы xi < Х2 < < xn- Присвоить г <- 1, j <- N и затем повторять следуюшую процедуру до тех пор, пока не будет удовлетворено условие j < i:

если Xi + Xj = с, то вывести {xi,Xj}, установить г <- г + 1, j j - 1; если х, + Xj < с, то установить г <- г + 1; если Ж; -t- Ж; > с, то установить j j - I-

И наконец, если j = j и 2xi = с, вывести {xi,Xi}. Этот процесс аналогичен методу, описанному в упр. 18; по существу, мы подготовили два рассортированных файла, в одном из которых записаны xi,... ,xn , а в другом - c-XN,---,c-xi,ii отыскали в них дублирующиеся элементы. Но в данном случае второй файл не обязательно должен присутствовать в явном виде. При нечетном с возможен и другой подход - рассортировать файл по ключу (ж нечетное = х, х четное => с - ж).

Аналогичный алгоритм можно использовать и для поиска тах{ж; + Xj ж; -Ь Ж; < с} или, скажем, для поиска при заданном t mm{xi +yj ж,- + yj > i} в двух рассортированных файлах - Ж1 < • • < Жт и J/1 < • < j/n.

20. Вот некоторые из возможных решений, (а) Для каждой из 499 500 пар г, j, таких, что 1 < г < j < 1000, установить yi Xi® Xj, j/2 !/i Л (j/i - 1), г/з !/2 Л (j/2 - 1), после чего вывести (ж;,Ж;) в том и только в том случае, если уз = 0. Здесь символом "ф" обозначена операция "исключающее или" а символом "Л" - операция "поразрядное и" (б) Создать файл из 31 ООО элементов, образовав для каждого исходного слова Х( по 31 элементу, а именно - само х, и еще 30 слов, отличающихся от него значением в одном из разрядов. Затем рассортировать этот файл и найти повторяющиеся элементы, (в) Выполнить анализ, аналогично варианту (а), для

i) всех пар слов, старшие 10 разрядов которых совпадают;

ii) всех пар слов, средние 10 разрядов которых совпадают (но старшие 10 разрядов различаются);

iii) всех пар слов, младшие 10 разрядов которых совпадают (но ни старшие, ни средние не совпадают).

Этот метод предполагает выполнение трех процедур сортировки (каждая из которых - по одному из описанных 10-разрядных ключей). Если исходные слова представляют собой случайный набор, то ожидаемое число пар в каждом из трех случаев будет, по крайней мере, 499500/2°, что не превышает 500.

21. Прежде всего подготовьте файл из всех пятибуквенных английских слов. (Не забудьте о том, что такие слова могут образовываться и путем добавления суффиксов наподобие -ED, -ER, -ERS, -S к более коротким словам.) Затем рассортируйте буквы каждого слова а по возрастанию и обозначьте этот упорядоченный набор через а. Наконец, рассортируйте множество пар (а,а), собрав таким образом вместе все анаграммы.