AOP_Tom3 (1021738), страница 163
Текст из файла (страница 163)
О н1 н2 нв и4 иб иб и7 и8 Приведенный выше пример кодирования разделителей даст следующий результат (пока- заны только первые 25 литер): За таким вспомогательным ключом должны следовать данные из соответствующей карточки, чтобы можно было различать неодинаковые карточки с одинаковыми ключами (т. е. кБ)г ЗоЬок означает гйоЬпк ). Обратите внимание, что кЯашг-Баепях — зто пмя г дефисом, а не составное имя. Год рождения а)-КЬпиапзпй* должен быть представлен в виде и40779 с ведущим нулем. (Данная схема будет хорошо работать до 9999 года, после чего мир окажется перед лицом очередного информационного кризиса.) к Имя арабского ученого Аль-Хорезми в английской транскрипции.
— Прим. верее. АССАОЕМ1АибМА210ЫАСЕобОЕ1 АСНТЕЕНЫНОЫОЕВТЕЧОЬРибЕ1Ы 81ВХТОТНЕЦОЕивОи881БТОТВЕ В18110ТНЕЦОЕи80ЕБи8СОВ108 ВВОУМи21ивСВОБВЧнбио ВВОУЫо210НМобно ВВОЧМн210НЫи4МАТНЕМАТ101А ВВОЧМи210НМи40рнвВОБТОМоо ВВОУЫо21ОНМи4171биО ВВОЫМи21ОНМи4171бибио ВВОУМи210НМи41781иО ВВОУМн210НЫи41810иО ВВОЧМнЗЫ1111АМБн2ВЕСХМАЬО ВВОЫЫ„БАМЕВТСА~7 О ВВОЫМ~БАМО~БОАШБОЫБ~БЫЕ ВВОНЫООНМи2АЬАМнбиО ОЕМн2ЧСА01Н1йиВЕООАНООЧХС ОЕМи7но ОЕМо811ЕВЕМибЬАМСЕЫобТАСи 01Хи2МОКСАЫн41827иО 01ХиВН01Т БСЕМТ ВОООЕЕ 80 011ивЫЕОУ1ЕНЕи881ЕСХЕовРК Е1СНТЕЕМивРОВТТиВБЕЧЕМи81 ЕХСНТЕЕМиВТУЕЕУЕиВОУЕВТОВ 1иВАМиВАн8МАТНЕМАТТС1АМи7 1,ВВ,ВМ,ВОООВЫАЬиВОР БНЕБ 1и8НАи8ЕНАОи7иО 1АибАнбСОЧЕибБТОВУи7ио 1ЫТЕВЫАТ1ОЫАС~ВВОБ1МЕББ~Б КНОНАВ12М1о2МОНАММАОн81ВЫ САНОВ 7А БНАСА21МЕ 8РОВ 8 САВОНнвВЕБЕАВСНн8АББОС1АТ ЬАВООВн1ио МАССА11бивСООКВООКиуио МАССАВТНТи210НЫи41927иб МАСН1ЫЕи81МОЕРЕМОЕМТнбСОМ МАСМАНОМи2РЕВСУивАСЕХАМОЕ М1БТВЕББиВОАХЬОЧАУи7иО МТБТВЕББнвОРиВМ1БТВЕББЕБи ВОУАСн8БОС1ЕТУн80рн8ЬОЫОО БА1МТибРЕТЕВБВОВСЕВнвЕЕ1Т БА1МТибБАЕМБи2САМ111Еи418 БАХМТЕн8МАВ1Еи2САБТОМи8Ри БЕМТМОМЕВ1САЬибАССОВ1ТНМБ ОЫСХЕибТОМБиВСАВХМн7ио ОМХТЕОибБТАТЕБивВОВЕАОо80 УАМОЕНМОМОЕи2АСЕХАМОЕВибТ УАМЧАСКЕМВОВСн2МАСн8ЕЬНУМ УОММЕОМАЫМи230НМи41903оо УНОХЕнВАВТн80рнВЬЕСЕВЭЕМА ЫНОБ~ВАРКА10„80Р~БЧТВС1М1 Ч11МСААВЛЕМн2АОН1ААЫи8ЧАМ Внимательно изучив этот пример, вы сможете решать аналогичные задачи с другими необычными типами упорядочения, которые требуют совместных усилий человека и компьютера.
18. Подготовьте два файла, из которых адин содержит числа (ие + ие + ив) шоб гн, а второй — числа (з~ — хе — ув) шоб т, и < и < ш, х < у < х, где т — длина слова в используемом компьютере. Рассортируйте оба файла и найдите в них общие элементы, которые нужна будет подвергнуть дальнейшему анализу. (Можно наложить дальнейшие ограничения на и, и, ш, х, у, х с учетом того, что малые простые числа можно также сравнить по модулю.) 19. В общем случае для нахождения всех пар чисел (хи х,), таких, что х, +х = с, при заданном с достаточно рассортировать файл так, чтобы х~ < хэ < < хл.
Присвоиты е- 1, ,1 +- Ж и затем повторять следующую процедуру до тех пор,пока не будет удовлетворено условие 1 < 0 если х, + х = с, то вывести (хих,), установиты е- г р 1, г'+- г' — 1; если х; 4- х, < с, то установить 1+- 1+ 1; если х, + хз > с, то установить г' е-2 — 1. И наконец, если з = 1 и 2х, = с, вывести (хах,). Этот процесс аналогичен методу, описанному в упр. 18; по существу, мы подготовили два рассортированных файла, в одном из которых записаны хм..., хл, а в другом — с — хл,..., с — хц и отыскали в них лублирующиеся элементы. Но в данном случае второй файл не обязательно должен присутствовать в явном виде.
При нечетном с возможен и другой подход — рассортировать файл по ключу (х нечетное ~ х, х четное ~ с — х). Аналогичный алгоритм можно использовать и для поиска шах(х; + х, ( х, + хз < с] или, скажем, для поиска при заданном Г ~п! в(х, + у, ! х, + у~ > С) в двух рассортированных файлах --х~< <х ну~< .<у. 20. Вот некоторые из возможных решений. (а) Для каждой из 499 500 пар 1, г', таких, что 1 < ю' < 1 < 1000, установить у~ +- х, Ю хз, уз +- у~ Л (у~ — 1), уз +- уз Л (уз — 1), после чего вывести (хи хе) в том и только в том случае, если уз = О. Здесь символом "йг» обозначена операция "исключающее или", а символом "Л" — операция "поразрядное и5 (6) Создать файл из 31 000 элементов, образовав для каждого исходного шюва х, по 31 элементу, а именно — само х, и еще 30 слов, отличающихся от него значением в одном иэ разрядов.
Затем рассортировать этот файл и найти повторяющиеся элементы. (в) Выполнить анализ, аналогично варианту (а), для 1) всех пар слов, старшие 10 разрядов которых совпадают; й) всех пар слов, средние 10 разрядов которых совпадают (но старшие 10 разрядов различаются); ий) всех пар слов, младшие 10 разрядов которых совпадают (но нн старшие, ни средние не совпадают).
Этот метод предполагает выполнение трех процедур сортировки (каждая из которых— по одному из описанных 10-разрядных ключей). Если исходные щюва представляют собой случайный набор, то ожидаемое число пар в каждом из трех случаев будет, по крайней мере, 499500/2'~, что не превышает 500. 21. Прежде всего подготовьте файл из всех пятибуквенных английских слов. (Не забудьте о том, что такие слава могут образовываться и путем добавления суффиксов наподобие -ЕО, -ЕБ, -ЕББ, -Б к более коротким словам.) Затем рассортируйте буквы каждого слова о по возрастанию и обозначьте этот упорядоченный набор через а'.
Наконец, рассортируйте множество пар (а', о), собрав таким образом вместе все анаграммы. Эксперименты Кима Д. Гибсона (К. Р. С)Ьэоп), проведенные в 1967 году, показали, что вторая по величине группа пятибуквенных анаграмм из обпсеупотребнтельных слов — зто ЬЕАЗТ, ЗЬАТЕ, ЗТАЬЕ, ЗТЕАЬ, ТАЕЬЗ, ТАЬЕБ, ТЕАЬБ. Но если воспользоватьсн более обширным словарем, то в нее можно добавить слова АЬЕТ5 (стальные наплечники), АЗТЕЬ (осколок), АТЬЕБ (намерения), ЬАЕТЗ (люди, занимающие промежуточное положение между рабами и свободными гражданами), ЬАБЕТ (горностай), ЬАТЕЗ (нильский окунь), ЬЕАТЗ (канавы), БАЬЕТ (средневековый шлем), БЕТАЬ (относящийся к остюкам), БЬЕАТ (подстрекать), БТЕЬА (колонна, стела) н ТЕЗЬА (единица измерения магнитной индукции).
Если добавить сюда еще и устаревшие написания слов "зем1е" н 'Сеазе1" (ЗАТЕЕ, ТАБЕЬ и ТАБЬЕ), то получим в результате 22 слова из тех же букв, ни одно из которых не представляется в орфографическом словаре прописными литерами. Потратив еще немного времени, можно добавить в набор и слово "Ск р из староангляйского языка, "айес" — из немецкого н "Мадаше йе БСаеГ' — из французского! Набор (ьАРБЕ, ЬЕАРБ.
РАЬЕБ, РЕАЬБ, РЕВАЗ, БАЬЕР, БЕРАЦ также можно расширять, по крайней мере, до 14 слов, если всерьез взяться за специальные словари. [См. Н. Е. Побепеу, 300 Вез! И'ог0 Ризе!ез, еб)Сед Ьу Магбп Сагбаег ()Мея 'г'огЬ. СЬаз. Ясг!Ьпег'э Зопз, 1968), Раке!ел 190 апд 194; Нош ЕсЫег, Ма)апИ сЛе А)РЬаЬес Рапса (ХХ.: Бс Ъ!агсш'э Сг!%л, 1997), Р)6. 46с.] Первой и последней анаграммами среди найденных наборов из пятибуквенных анаграмм в английском языке длиной не менее трех элементов являются (АЬВАБ, ВАЬАБ, ВАЬБА, ВАБАЦ н (ЗТВВТ, ЗТСВТ, ТВЗБТ). если не принимать во внимание подходящих имшс собственных.
Ешси же снять это огршгичение, то имена А)Ьап, Ва!ап, ЬаЬап и НаЬа1 образуют набор, занявший теперь первое лчесто (АЬВАИ, ВАЬАМ, ВАМАЬ, ЬАВАМ, МАВАЬ, ИАВЬА). Самый впечатляющий пример длинных анагралсм в английском языке дают математические термины. (АЬЕВТ1ИС,АЬТЕВ1МС,1ИТЕСВАЦ ВЕьАТ1МС,ТВ1АИСьЕ). Сюда можно добавить и австралийскую рыбу ТЕВАСЬХМ. Можно ускорить процесс, вычисляя )'(а) = (Ь(ас) + Ь(аз) + .. + Й(аз)) пюб ш, где ам, .., аз — числовые коды букв слова а, а (Ь (1), Ь(2),... ) представляют собой 26 случайно выбранных констант; здесь пс — длина машинного слова В результате сортировки файла (1'(а), а) все анаграммы будут собраны вместе; после этого для всех шсучаев у'(а) = )"()3) нужно убедиться в том, что найдена действительно анаграмма, т. е. а' = 0'. Значение )'(а) вычисляется существенно быстрее, чем аа, и этот метод позволяет избежать вычисления а' для большинства слов а из файла.
Замечание. Аначогичным методом можно воспользоваться, если нужно собрать все множества записей, имеющих равные многословные ключи (ам..., а ). Предположим, что нам безразличен порядок записей, важно только, чтобы записи с раепыми ключами располагались подряд. В этом случае иногда удобно выполнить сортировку по однословному ключу (асх" '+атал з+ +а„) шоб т, где х — любая фиксированная величина, вместо того чтобы сортировать по исходному многословному ключу. 22. Найдите инварианты графов (т е. функции, принимающие равные значения на нзоморфных ориентированных графах) н выполните сортировку по этим инвариантам, чтобы отделить одну от другой группы "явно нензоморфных" графов Далее приводятся примеры инвариантов. (а) Представьте вершину о, е виде пары (а„Ь,), где а, — полустепень захода, а Ь, — полустепень исхода вершины, после чего рассортируйте пары (а„Ь,) в лексикографическом порядке.
Полученный файл представляет собой нниариант изолюрфных графов. (6) Представьте дугу нз е, к ос в виде совокупности (ац Ьь а,, Ь,) и рассортируйте эти тетрады в лексикографическом порядке. (с) Разделите ориентированный граф на связанные компоненты (см. алгоритм 2 З.ЗЕ), определите инварианты каждой компоненты и любым способом рассортируйте эти компоненты в порядке инварнантов. (См.
также ответ к упр. 21.) В общем случае после сортировки ориентированных графов по инвариантам необходимо дополнительно проанализировать, являются ли графы с равными инвариантами в самом деле изоморфными. При выполнении этого анализа могут пригодиться и сформированные инварианты. В случае свободных деревьев можно найти "характеристические" или "канонические" инварианты, которые полностью характеризуют дерево, так что необходимость в дополнительном анализе исчезнет.
(См. Л. Норсго11, В.. Е. Твг!ап, Сошр!сайгу ну Сошрисег Сотригагюпэ (уееи Уогй: Р1егппп, 1972), 140 — 142.) 23. Один из способов выполнении этого упражнения — сформировать файл, содержащий все клики из трех человек, преобразовать его в файл, содержащий все клики из четырех человек, и т. дд если клики не слишком велики, этот метод вполне подойдет. (С другой стороны, если есть клика размером и, то найдется, по крайней мере, (") клик размером й; так что этим методом не удастся получить требуемый результат, даже если и приблизительно равно 25 или более того.) Если имеется файл, в котором перечислены все клики размером (к — 1) в виде (ам, .,, аь-1), где а1 « аь ц то клики размером Ь можно отыскать следующим образом: (!) сформировать новый файл, в который иключить элементы (Ь,с,ам...,аь э) для каждой пары клик размером (й — 1) в виде (оц, аь ш 6), (ам, аь-и с), где 6 < с; (й) рассортировать этот файл по первым двум компонентам; (!В) для каждого элемента (6, с, ам..., аь э) этого нового файла (при том что пара (Ь, с) принадлежит исходному файлу знакомств) вывести в качестве результата клику (ам..., оь м 6, с) размером /с.
24. (Это решение предложено Норманом Харди (М Нагбу) (1967).) Скопируем исходный файл; рассортируем одну копию по первым компонентам, а другую — по вторым. Теперь можно, просмотрев погледовательно эти два файла, создать новый, в который включить все пары (амхээ), 1 < 1 < Х вЂ” 2, и найти (х г-и хл). Пары (Х-1, хл 1) и ()э', кл) следует записать в еще один файл. Далее процесс продолжается по индукции.
Предположим, файл Г содержит все пары (кот, ~), 1 < г < Х вЂ” Г, в произвольном порядке, а файл С содержит все пары (й к,), )х' — 1 < 1 < Х, упорядоченные по вторым компонентам. Пусть Н вЂ” копия файла Г, рассортируем Н по первому компоненту, а à — по второму.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
