Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 2) (1119371), страница 61
Текст из файла (страница 61)
Гибсона (К. О. С!Ьэоп), проведенные в 1967 году, показали, что вторая по величине группа пятибуквенных аиаграмм из общеупотребительных слов — зто ЬЕАБТ, 81дТЕ, ЗТА1.Е, ЯТЕА1., ТАЮ.З, ТАЬЕБ, ТЕАЙЗ, Но если воспользоватьсл более обшириым словарем, то в иее можно добавить слова А1.ЕТБ (стальные наплечники), АЗТН. (осколок), АТ1.ЕЯ (намереиия), 1.АЕТБ (люди, занимающие промежуточное положеиие между рабами и свободными гражданами), 1.АБЕТ (горностай), 1,АТЕЯ (иильский окунь), ЬЕАТЗ (каиавы), ЬИ.ЕТ (средневековый шлем), ЯЕТА1. (относящийся к остюкам), Я.ЕАТ (подстрекать), БТЕЬА (колоина, стела) и тез1.А (единица измерения магнитной индукции).
если добавить сюда еще и устаревшие написания слов "эещ!е" и "Севке!" (БАТЕ., ТАБЕ1. и ТАБ1.8), то получим в результате 22 слова из тех же букв, ни одно из которых не представляется в орфографическом словаре прописными литерами. Потратив еще немного времени, можио добавить в набор и слово "!сиГ' из староа~глийского языка, "айез' — из немецкого и "Маг!агпе де Затее!" — из французского! Набор (ьАРЗЕ, ЬЕАРЗ, РА1.ЕЗ, РЕАЬЯ, Р!.ЕАБ, БК.ЕР, ЯЕРАЦ также можно расширить, по крайней мере, до 14 слов, если всерьез взяться за специальные словари.
(См. Н. Е. Пвг(епеу, 300 Вш! 1уогс( г.ияя!аэ, еб!тес! Ьу Маг0п Сагбпег (Хек УогЬ: СЬал. ЗгНЬпег'з Яопэ, 1968), Рпзз!ез 190 апг! 194; Ноэз ЕсМег, Ма(сшЕ гйе А!рйаЬес Оапсе (Х.У.. 'Ба Магйп'з Ст!(Еп, 1997), г !Е. 46с.) Первой и последней анаграммами среди найденных наборов из пятибуквенных анаграмм в английском языке длиной не менее трех элементов являются (АЛВАЗ, ВА1.АБ, ВА1.БА, ВАБЩ и (БТВОТ, ЗТВВТ, ТЕВЗТ), если не принимать во внимание подходящих имея собственных. Если же сиять зто ограничение, то имена А!Ьал, Ва1ап, ЬаЬап и ХаЬа! образуют набор, занявший теперь первое место (АЬВАИ„ВАЬАИ,ВАИА1.,1.АВАИ,ИАВАЬ,БАВА). Самый впечатляющий пример двиииых анаграмм в английском языке дают математические термины: (И.ЕВТ1ИБ,АЬТЕЕ1И6,1ИТЕСВАЬ,ВИ.АТ1ИБ,ТВ1АИСЩ, Сюда можно добавить и австралийскую рыбу ТЕВА61.1И.
Можно ускорить процесс, вычисляя У(о) = (Л(о~) + Л(ат) + + Л(аэ)) шод ш, где ам..., аз — числовые коды букв слова а, а (Л(1), Л(2),... ) представляют собой 26 случайно выбранных констант; здесь т — длииа машинного слова, В результате сортировки файла (7(п),п) все аиаграммы будут собраны вместе; после этого для всех случаев 7(о) = 7(,:3) иужно убедиться в том, что найдена действительно анаграмма, т. е.
а' = 0'. Зиачеиие г(п) вычисляется существенно быстрее, чем о', и этот метод позволяет избежать вычисления о' для большинства слов о из файла. Замечание, Аншюгичиым методом можно воспользоваться, если нужно собрать все множества записей, имеющих равные многословные ключи (ап, .., а ). Предположим, что иам безразличен поридок записей, важно только, чтобы записи с равными ключами располагались псщряд. В этом случае иногда удобно выполнить сортировку по однословному ключу (а~з" '+азх" ~+ +а ) шобзп, где х — любая фиксированная величина, вместо того чтобы сортировать по исходному многословному ключу.
22. Найдите инварианты графов (т. е. функции, прииимшощие равные значения иа изоморфных ориентированных графах) и выполните сортировку по этим инвариаитам, чтобы отделить одну от другой группы "явио иеизоморфиых" графов. Далее приводятся примеры иивариантов. (а) Представьте вершину о, в виде пары (а„Ь,), где а; — полустепеиь захода, а Ь, — полустепень исхода вершины, после чего рассортируйте пары (а„Ь;) в лексикографическом порядке. Полученный файл представляет собой иивариант изоморфных графов. (6) представьте дугу из е, к ег в виде совокупности (а„ь„а, ьз) и рассортируйте эти тетрады в лексикографическом порядке. (с) Разделите ориентированный граф иа связанные компоневты (см.
алгоритм 2.3.3Е), определите инварианты каждой компоненты и любым способом рассортируйте эти компоненты в порядке инвариаитов. (См. также ответ к упр. 21.) В общем случае после сортировки ориентированных графов по инвариантам необходимо дополнительно проанализировать, являются лн графы с равными инвариантами в самом деле изоморфными. При выполнении этого анализа могут пригодиться и сформированные инварианты. В случае свободных деревьев можно найти "характеристические" или "канонические" инварианты, которые полностью характеризуют дерево, так что необходимость в дополнительном анализе исчезнет. [См.
Л. Норсгой, В. Е. Твгзап, Согпр!ехйу оГ Сошрисег Сошрпсаг!опв (Нем Ъ'огй; Р!епшп, 1972), 140-142,] 23. Один из способов выполнения этого упражнения — сформировать файл, содержащий все клики из трех человек, преобразовать его в файл, содержащий все клики из четырех человек, и т. дд если клики не слишком велики, этот метод вполне подойдет.
(С другой стороны, если есть клика размером и, то найдется, по крайней мере, ("„) клик размером Й; так что этим методом не удастся получить требуемый результат, даже если и приблизительно равно 2о или более того.) Если имеется файл, в котором перечислены все клики размером (Й вЂ” !) в виде (ом..., аь 1), где а1 « аь ц то клики размером Й можно отыскать следующим образом: (!) сформировать новый файл, в который включить элементы (Ь с ам, .. „аь-з) для каждой пары клик размером (Й вЂ” 1) в виде (оп...,аь з, Ь), (ам...,оь з,с), где 6 < с; (й) рассортировать этот файл по первым двум компонентам; (ш) для каждого элемента (Ь,с,ом...,аь-з) этого нового файла (при том что пара (Ь,с) принадлежит исходному файлу знакомств) вывести в качестве результата клику (ап..., аь-з, Ь, с) размером Й.
24. (Это решение предложено Норманом Харди (М, Нап!у) (1987).) Скопируем исходный файл, рассортируем одну копию по первым компонентам, а другую — яо вторым. Теперь можно, просмотрев последовательно эти два файла, создать новый, в который включить все пары (х„х; х), 1 < ! < !т' — 2, и найти (хл-и ел). Пары (У-1, хя-1) и (Н,хя) следует записать в еще один файл. Далее процесс продолжается по индукции. Предположим, файл Г содержит все пары (х„хс ы), 1 < ! < Н вЂ” 1, в произвольном порядке, а файл С содержит все пары (Г,х;), Н вЂ” ! < ! < !т', упорядоченные по вторым компонентам. Пусть Н -- копии файла Р', рассортируем Н по первому компоненту, а à — по второму, Просмотрим теперь Г, С, и Н и сформируем два новых файта Г' и С' следующим образом. Если текущие записи файлов Г, С, Н равны соответственно (х,х'), (у,у'), (х, х'), то: !) если х = х, выведем (х, х ) в Г' и перейдем дальше в файлах Г н Н; й) если х' = у', выведем (у-з, х) в С' и перейдем дальше в файлах Г и С; ш) есви х' > у', перейдем дальше в файле С; ге) если х' > -, перейдем дальше в файле Н.
Когда дойдем до конца файла Г, рассортируем С' по вторым компонентам и сольем с ним С; затем заменим ! на 21, Г на Г~, С на С'. Таким образом, ! принимает значения 2, 4, 8,...; при фиксированном Г для сортировки необходимо выполнить О(!ой%) проходов. Следовательно, общее число проходов будет О((!ой Н) ). В конце концов выполнится ! > У и файл Г опустеет; тогда останется только рассортировать С по первым компонентам. 28. (Идея решении принадлежит Д.
Шанксу (П. БЬапйз).) Подготовьте два файла, один из которых содержит числа а " шоб р, а другой — Ьа " шог! р, О < и < пз. Рассортируйте оба файла и найдите общий элемент. Эамечанпе. В результате врелэя выполнения б!(р) в худшем случае сократится до 4!(ьГр!ойр). Возможно и дальнейшее повышение производительности: например, несложно за )ойр шагов проанализировать, является ли и четным, проверив, какое из равенств 6!™з шос! р = 1 и (р — 1) имеет место, В общем случае, если Г' является любым делителем р — 1, а р! — любым делителем 8сб(7', и), можно аналогичным образом найти (и/р!) шор! р, отыскав значение Ь!Х П! ! в таблице длиной 7/р!.
Если простыми делителями р — 1 являются Ор < Оэ « . Ои причем, если Ор — мал6, можно быстро вычислить и, выполняя поиск разрядов справа налево в предстэалеиии со смешанными осиоваииями йм ..., Оь (Эта идея принадлежит Р. Л. Сильверу (В. 1,. Бйаег), 1964; см. также 8. С. РоЫ!8, М. Не19пап, 1ЕЕЕ ТгшкмсВолв ГГ-24 (1978), 106-110.) Джон М.
Поллард (уо!рв М. Ро!!агр!) иашел довольно элегантный способ вычислении дискретных логарифмов, требующий порядка 0(за) операций шор! р при малых затратах памяти. Способ основан иатеории случайныхотображений (гапбош шарр!вйэ). См. Магй, Сошр. 32 (1978), 918-924, где он предложил еще один метод, базирующийся иа числах ир = гр шог! р, которые имеют только малые простые делители. Асимптотически более быстрые методы обсуждаются в ответе к упр. 4.5.4-46. РАЗДЕЛ 5.1.1 1. 205223000; 27354186.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
