Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 1) (1119456), страница 5
Текст из файла (страница 5)
р(еУ), если сортировка устойчива. 2. [21] Пусть каждая запись Йе некоторого файла имеет два ключа: "большой ключ" К к "малый ключ" я, причем аба множества ключей лшеейна упорядочены. Тогда можно обычным способом иввспю леиеииварафичеекия яарядви иа множестве пар ключей (К, л): (Киее,) <(Ке,(еэ), если К; < Ку или К; = К; н (е, < й . Алиса рассортировала этот файл сначала па большим ключам, получив и групп записей с адинакавымн большими ключами в каждой группе: К„„= " = К„и, < Кжи,м — " — К„<,,> « " К,н„гем — — " - -К,П„Ь ГДЕ Е = Х.
ЗатЕМ аиа РаССОРтИРОВаЛа КажДУЮ Иэ П ГРУПП Вьи.. +и,..., Л и,! Па Собственным малым ключам. Билл взял тиг же исходный файл и сначала рассортировал ега па малым ключам, а затем получившийся файл рассортировал па большим ключам. Взяв тат же исходный файл, Крис рассортировал ега адин раэ в лексикаграфнческам порядке, пользуясь парами ключей (кз, /се). Получилось ли у всех троих одно и та жеу 3. [Млл] Пусть на мналеестве Км, Кл определено отношение '<", для которого закон трнхатамии выполняется, а закан траиэитивиастя — нет.
Докажите, чэа я в этом случае ваэлюжна устойчивая сортировка записей, т, е. сортировка, при натирай выполняются условия (1) и (2). (На самом деле существует, па крайней мере, три распалаженяя записей, удовлетворяющих этим условиям!) 4. ]В?] Составители словарей фактически не следуют жестко лексикографическому порядку, так как прописные н стра псые буквы у них перемежакпся, В частности, ггспшгьзуется такой порядок; а < Агав < АА < ААА с Ааслен с ааЬ « . зяз < ЕЕЕ. Поясните, как реализовать подобный словарный порядок сортнровки.
б. ]МВ8] Разработайте дяоичнмй код для всех неотрнцателыгых целых чисел, такой, что, если и закодировано в виде строки р(п), то пг < и тогда н только тогда, когда р(т) меньше в лексикографвческом смысле, чем р(п). Более того, р(т) не должно быть префиксом р(н) для любого т ~ и. По возможности длина р(п) должна быть по крайней мере !Е и + О(!об!об и) для всех больших и.
(Такой способ кодирования очень удобен, если приходится сортировать текст, состоящий из чисел и слов, или если желательно отобразить довольна большие текстовые последовательности на двоичные коды.) 6. [18! Программисту на И11 Б. С. Даллу потребоваяось выяснить, находится ли в ячейке А число, большее числа из ячейки В, меныпее или же равное ему. (ггг написал в программе "1Лй А. 505 В? а полол» проверил, какой результат получился в регистре А: положительный, отрицательный нли нуль, Какую серьезную ошибку он допустил и как должен был поступить? 7. (17] Напишите подпрограмму для компьютерай11длясравнения ключейсувеличенной точностью, исходя из следующих условий.
Вызов: 1ИР СОИРАВЕ Состояние при входе г11 = и; СОИТЕИТВ (А + й) = а» и СОИТЕИТ5 (В + Ь) = Ь» лля 1 < й < и; полагается, что и > 1. Состояние при выходе: С1 = ОВЕАТЕВ, если (а„г..., аг) > (Ь„,..., Ьг),. С1 ю ЕОШП., если (а г,..., аг) = (Ья,, Ьг); С1 = ЬЕ55, если (а„,...,аг) < (Ь„,...,Ьг); гХ и гП, возможна, нзмеиилигь. Здесь отношение (а„,, аг) с (Ь„,..., Ьг) обозначает лексикографическое упорядочение слева направо, т. е.
существует индекс г, такой, что а» = Ь» для п > Ь > 8, но аг < Ьр ° В. ]?О] В ячейках А и В содержатся соответственно чясла а н Ь. Покажите, что можно написать программу дая и11, которая вычисляла бы пнп(а, Ь) и записывала результат в ячейку С„не пользуясь командами перехода. (Предостережение. Поскольку арифметическое переполнегшб невозлюжно обнаружить беэ операторов перехода, разумно так построить программу, чтобы переполнеяие не могло возникнуть ни при каких зншгениях а и Ь.) 9. ]МВ?! Какова вероятность того, что после сортировки в порядке неубывания и независимых равномерно распределенных на отрезке ]О, 1] случайных величин г-е от начала число окажется < х? УПРАЖНЕНИЯ (часть 2) В каждом иэ этих упражнений поставлена задача, с которой может столкнуться программист.
Предложите хорошее решение задачи, ареднолагал, чта ан имев»не дела с "музейннм" компьютером, у которого имеепгсл сраанигяельно небольшая анерапгианал намять, порядка наскальная тысяч слов и около полудюжины накопителей на магнитной ленте (НЫЛ) — этого каэичества вполне достаточно дчя выполнения сортировки. Алгоритм, ко~орый сможет эффективно работать в таких "спартанских" условиях, тем более будет прекрасно выполнять задачу на современных компьютерах. 10.
]18] Имеется лента, на которой записан миллион слов данных. Как определить, сколько иа этой ленте различных слов? 11. [12) Вообразите себя в роли Управления внутренних доходов Министерства финансов США. Вы получаете миллионы информационных карточек от организаций о том, сколько денег онн выплатили различным лицам, и миллионы налоговых деклараций (карточек) о доходах от налогоплателыциков. Как бы вы стали отыскивать людей, которые сообщили не обо всех своих доходах? 12. [М25[ (Трансаонироеание матрицм.) Имеется магнитная лента, содержащая миллион слов, которые представляют собой элементы матрицы 1000 х 1000, записанные по строкам: агл аьг,,.аглаю ах~ ...аглеоа агооолооо Ваша задача — получитьленту, на которой элементы этой матрицы были бы записаны по столбцам: ацг агл... агахгл аьг...
аьюр г . агюо,гахг. (Постарайтесь сделать ие более десяти просмотров данных.) 13. [Мйб) В вынем распоряжении есть довольно большой файл из А! слов. Как бы вы его "перетасовали" случайным образом? 14. [20[ Вы работаете с двумя вычислительнымн системамн, в которых по-разному упорядочены литеры (буквы и цифры). Как заставить первую систему сортировать файлы с буквенно-пифровой информацией, предназначенные для использования во второй системе? 16.
[12) Имеется довольно большой список лкщей, родившихся в США, с указанием штата, в котором онн родились. Как подсчитать тех, кто родился в каждом штате? (Предполагается, что ни один человек не указал в списке более одного раза.) 16. [20) Чтобы облегчить внесение изменений в большие программы, написанные иа языке ЕОВТВА?ч, желательно написать программу, которая формирует таблицу перекрестных ссилок. Входными данными для нее служит программа на РОВТВА?ч, а в результате получается листинг исходной программы.
снабженный указателем всех случаев употребления каждого идентификатора (т е. имени) в программе. Как написать такую программу? ° 17. [22] (Сортировка библиографических карточек каталога.) Ло появления компьютерных баз данных в каждой библиотеке существовал каталог библиографических карточек, с помощью которого читатели могли отыскать интересующие нх издания. Но сортировка карточек в порядке, удобном для читателей, усложняется по мере увеличения библиотечного фонда.
В следующем "алфавитном" списке содержатся рекомендации, взятые из правил регистрации н хранения каталожных карточек Американской библиотечной ассоциации (Чикаго, 1942). Текст ка?тгочки В. Ассаг!еш!а пахюпа)е с(е! Ь!псе!, Ноше 1812; ещ Ь!выг!зсЬег Вовгап ВгЬйогЬЬгрге гРЬ!в!о!ге гав!ос!оппапе В!Ь!!огЬецпе без сит!ов!гбв Вгони, Мгв.
3. СговЬу Вго» и, уоЬп Вговчг, ЛоЬп, гааеЬепгас)с(ап Вговп, ЗоЬп, о( Возпгп Вговчг, ЗоЬп, 1715-1766 ВВО%л. 1ОН?ч, 1715-1766 Вговп, Зойп, б. 1811 Замечания В названиях иностранных (кроме британских) учреждений слово "гоуа(гу' (королевский) игнорируется АсЬГхеЬпЬппг)ег!хгго!1 (числительное 1812 на немецком языке) В французском тексте апостроф рассматривается как пробел Днатонические знаки игнорируются Указание положения (Мп.) игнорируетсн Фамилии с датами следуют за фамилиями без дат ..., которые упорядочиваются по описательным словам Одинаковые фамилии упорядочиваются по датам ровсдения Работы о нем идут после его работ Иногда год рождения определяется приблизи- тельно Теясш карточки Вгони, Рг. 2оЬп, 1810-1882 Вго» п-%!!!!шпв, ВейшаЫ Майереасе Вгони Ашепса Вго»ш Вг Ра(Ьвоп'в 1Четада ейгесгогу Вго»чцойп, А!ап Реп', Ч!абпп!г Ебиагбот!сЬ, 1387- ТЬе деп Реп !!еЬеп 1апВеп Таб Р!х, Могйик 1827-1908 1812 оитехгиге 1,е Х1Хе в!Ьс!е 1гап9а!в ТЬе 1847 !ввие о( С.
Б. агашрв 1812 озеггиге 1 аш а шатЬешагю!ав 1ВМ )оигпа! оу геаеаггЬ апб г(ете!оршепг Ьа-1 Ьа-еЬаг! 1а; а 1оте аготу 1пгетпабопа! Вивпеза МасЫпев Согреты!оп в)-КЬиийг!хпй, МиЬшппшс1 !Ьп Мбва, 71, 813-346 1 аЬош. А шайаппе (ог а1! иогйегв (.аЬог гшеагсЬ аыос!айоп 1,аЬоиг, аее ЬаЬог МсСа1!'в сооЬЬооЬ МсСаггЬу, доЬп, 1927- МасЫпе-!пг!ерепг(еп! сошрисег ргойгаппп! иВ, МасМаЬоп, Ма1. Регсу А!ехапбег, 1854-1929 Мш. Райочау Мййгеэе о( ш!вгпыже Впуа! шов!у оГ Ьопбоп Бь РегегаЬигйег Ее!гипй БшпыБаепв, СаппНе, 1835-1921 Бге-Мане, Оавгоп Р Беш!пишейса! в!ВопгЬшв Впс!е Тош'в саЫп 11.$. Ьигеаи о1 гЬе сепвив Замечания Указание положения (Рг.) игнорируется Дефис рассматривается как пробел Названии книг указываются после составных Фамилий Вг в английском тексте превращается в "апб» Апостроф в именах игнорируется Артикль в начале текста игнорируется ..., если существительное стоит в именительном падеже Фаыилии идут раньше других слов Ебх-Ьий сепг баеве (числительное 1812 на французском языке) Р!х-пеит!Ьше (числительное Х1Х-й на франпузском языке) ЕЬТЫееп Еогсу-везен (числительное 1847 на английском языке) Е)ВЬгееп Г»»4»е (числительное 1812 на английском языке) (а Ьоой Ьу НогЬегг 1У!епег) (книга Норберта Винера) Аббревиатуры рассматриваются как ряд однобуквеинмх слов Артикль в начале текста игнорируется Знаки препинания в названиях ипюрируются Начальное "а1-" в арабских именах игнорируется Заменяется словом 'Ч аЬог" Ссылка на другую карточку в картотеке Апостроф в английском тексте игнорируется Мс = Мас Дефис рассматривается кшс пробел Указание положения (Маз.) игнорируется "Мга." заменяется словом "М!в!сева" В названиях британских учреждений слово "гоуз!Гу" (королевский) учитывается "Бь" заменяется гловоы "Ба!пг"', даже в немецком Дефис рассматривается как пробел Бшпге (а Ьоой Ъу Ропе!б Егт!п КпигЬ) (а Ьоой Ьу Нагг!еФ ВеесЬег Бсоже) "Р, $." заменяется словами "1)п!Ыг) Бакеев" Замечания Текста карточки Ъанбегшоибе, Л!ехапбге ТЬеорЫ1е, 1735-1796 Чаи Уа)Ьеибиг6, Вбас Е!иуп, 1921— Чоп 24еипгапп, 1оЬп, 1903-1957 ТЬе и Ьо!е агг оГ !е8етг)ешшп %Ъо'з а?ган1 о? у'!г8!и!а %ос!1? Пробел после префикса в фамилиях игнорируется Лртикль в начале текста игнорируется Апостроф в текстах на английском языке игнори- р ется Фамилия никогда не начинается со строчной литеры %!)пЕаагг!еп, Абг!ааи тап, 1916- (У большинства из этих правил есть исключения; кроме того, существует много других правил, которые здесь не уиомянуты.) Предположим, вам поручено рассортировать большое количество таких карточек с помощью компьютера, а затем обглуживать огромную картотеку, причем у вас нет возможныти изменить уже сложившийся порядок заполнения карточек, Как бы кы организовали информацию, чтобы упростить операции сортировки и включения новых карточек? 16.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
