AOP_Tom3 (1021738), страница 162
Текст из файла (страница 162)
Точнее, заменилс каждое слово а парой (а', а), в которой а' формируется из а подстановкой А -> а,..., Е -+ с, затем рассортируем сформированные пары лексикографически. В резулшвте получим, например, сех ( Тех < ТеХ ( ТЕХ < сехс. В словарях также встречаются слова с диатоническими знаками, префиксами, суффиксами и аббревиатуры; например, а < А < А < а- < а, < -а < А- ( А. < аа < а.а. < аа< аа <АА < АА. < ААА « зе ( Ев.
(ЕЕ < все < ХХЕ. В таком более общем случае получим а' отображением а -> а, А -с а и т. д., отбрасывая знаки дефиса и точки. 5. Положим р(0) = 0 и р((1о)е) = 1р(!а!)а; здесь (1о)с является обычным двоичным представлением положительного целого числа, а !а! — длиной строки о.
Тогда р(1) = 10, р(2) = 1100, р(З) = 1101, р(4) = 1110000, , р(1009) = 111101001111110001, , р(65536) = 1~0~~,..., р(2ееезе) = 1 Оеееее и т. д, Длина р(п) равна /Р(п)! = Л(п) + Л(Л(п)) + Л(Л(Л(п))) + + 18 и+ 1, где Л(О) = О, Л(п) = ()8 и) для и > 1, а 1Я и есть наименьшее целое гп > О, такое, что Л~ 1(п) = О, [Эта конструкция предложена В. И. Певенштейном, Проблемы кибернетики 20 (1968), 173-1?9; см, также Д, Э.
Кнут в ТЬе 54анбетабса! Сагс1пег, есНСей Ьу П. А. К!агнес (Ве!псопс, Са1Ногща: Чгассеногссс 1псегпасюпа!, 1981), 310 — 325.] 6. Возможно переполнение, которое может исказить результаты сравнения. Следовало написать, например, чООА А: СИРА В" и проверить индикатор сравнении. (Невозможность сравнения чисел, занимающих целое слово, посредством вычитания — проблема, возникающая на многих моделях компьютеров; это основной довод в пользу включения операторов СИРА,..., СИРХ в систему команд компьютера И1Х.) 7. СОИРАВЕ 511 9Р ОЕС1 1Н 101 А,1 11Р СИРХ 8,1 9Н ЗИР ЗИЕ 9Р 8. Решение 1, основанное на тождестве ш 1 18 е я а = 2ас+ аз !ае! ( 1 6=26!+Ьс !Ьс! ( 1 ае — Ьс 5011 ЬОА А' ЯВАХ 5 019 2= БТА А1 5ТХ А2 СОА В ЯВАХ 5 017 -"2-" ЯТА 81 БТХ 82 10А А1 БОВ В1 ЯТА АВ1 ХОА А2 БОВ 82 ЯТА АВ2 Переполнение невозможно ас — 6~ сп(а,6) БВАХ АОО ЕИТХ ЯСАХ ИШ.
БТХ 1ОА АОО БОВ ЯВАХ 01Ч АОО АОО 508 БТА = с(а+ Ь вЂ” !а — Ь!): 1 АВ1 1 Б АВ2 АВЗ (ас — Ьс) яБп(а — Ь) А2 В2 АВЗ Б =2 А1 81 Переполнение невозможно АВ1(1:5) С 5 Решение Б, основанное на том, что индексирование может вызвать сложные взаимные обмены: 3012 ХОА А ЗТА С БТА ТА ЬРА В БТА ТВ Теперь включите в программу приведенную ниже последовательность операторов А раз подряд, где 2» > 10'е: ХОА ТА ЗВАХ 3 017 =2= ЗТХ ТЕМР 101 ТЕМР БТА ТА (Эта программа просматривает разряды в двоичном представлении а и Ь справа налево, сохраняя знаковые разряды.) В конец текста программы поместите следующую таблицу: 9. Вероятность равна сумме Х' ("~~ ')( — 1)1(„'~ )х'+', которую получим методом включения и исключения (упр. 1.3.3 — 26).
лто также можно записать в виде бета-распределении г(~) Г Г" '(1 — 1)к "Ж. 10. Рассортируйте содержимое ленты, а затем посчитайте. (Некоторые методы сортировки позволяют легко отбрасывать записи с повторяющимися ключами.) 11. Присвойте каждому человеку индивидуальный идентификационный номер, который даллсен быть указан на всех касающихся его карточках.
Рассортируйте отдельно информационные и налоговые карточки, использув в качестве ключа идентификационный номер. Обозначим рассортированные налоговые карточки через Кн, йп, а их ключи — через К1 « . Кн. (Не должно быть обнаружено ни одной пары карточек с повторяющимися ключами.) Добавьте новую (Ж+ 1)-ю запись с ключом оо и установите 1 ь- 1. Затем для каждой записи из информациониога файла проверьте, было ли о ней сообщено, следующим образом. Обозначим через К ключ обрабатываемой информационной карточки. а) Если К > К;, то увеличиты на 1 и повторить этот шаг. Ь) Если К < К; или К = К„а соответствующая информация не отображена в налоговой карточке Л„то сообщить об ошибке.
Постарайтесь проделать все это, не тратя впустую денег налогоплательщиков. 12. Один из способов состоит в том, чтобы присоединить к элементам матрицы а; ключи () 1), лексикографически рассортировать элементы по этим ключам, после чего ключи МСТ СОМ СОИ СОИ СОИ ТИХИ СОМ СОМ СОМ СОМ СОМ -1 -1 0 -1 +1 -1 -1 0 0 0 1 0 -1 1 0 1 1 1 з СОА ТВ БВАХ 5 ОХЧ "2 ЗТХ ТЕМР 102 ТЕМР БТА ТВ ХМС1 0,2 ХМС1 0.2 ХМС1 0,2 103 ТИХИ,1 СОА 0,3 ЗТА С отбросить.
(Подобная идея применима в любом случае, когда нужна переупорядочить информацию, если желаемый новый порядок выражается простой формулой.) В частном случае, рассмотренном в этой задаче, можно воспользоваться сбалансированной двухпутевой сортировкой методом слияния, при которой ключи обрабатываются нестолько просто, что их фактически не нужно явно записывать на ленту. Пусть задана матрица и х и, тогда можно действовать следующим образом.
Сначала запишем строки с нечетными номерами на ленту 1, а строки с четными номерами — на ленту 2: Лента 1: асс асг ., ас азс азг .. аз аы аьг... аь Лента 2 ам агг ..аз„аьс аю ..ас» аьс аьз ав» Затем перемотаем ленты в начюсо и будем считывать с них информацию синхронна, чтобы получить Лента 3: ап аы аы аю... ас» аз» аы аы аы авз .. аь ав Ленча 4: азс асс азг ась...аз аь»асс авс агг авг .. аг ав Перемотаем вторую пару лент в начало и вновь будем считывать с них данные синхронно: Лента 1: ан аы азс асс аы...аьг аь аэл.
Лента 2: аы аьс агс авс аьг... авз . ав асз,с И так до тех пор, пака после 1'13 и) просмотров ие получится требуемая транспонированная матрица. 13. Один из методов состоит в том чтобы добавить к записям различные случайные ключи, выполнить сортировку по этим ключам, а затем их убрать. (Ср.
с упр. 12; анююгичный метод получения случайной емборхн рассматривался в разделе 3.4.2.) Другой подход, требующий приблизительно столько же трудозатрат, но, по-видимому, в меньшей степени зависящий от качества генератора случайных чисел, состоит в том, чтобы присоединить к йс случайное целое число в диапазоне 0 < К, < ссс — с, а затем переупорядочигь записи, пользуясь методом из упр.
5.1.1 — 5. 14. Имея таблипу перекодировки, можно написать программу лексикографического сравнения, которая имитировала бы упорядочение, используемое на другом компьютере. Или же можно создать искусственные ключи, отличные от реальньсх литер, но дающие желаемое упорядочение. Последний метод имеет преимущество такую операцию достаточно проделать один раз, однако потребуется больше памяти и нужно будет преобразовать весь ключ целиком.
В первом методе результат сравнения часто можно определить, преобразовав всего одну-две буквы ключей; на последующих стадиях сортировки будут сравниваться почти равные ключи, поэтому в первом методе, видимо, выгоднее, прежде чем преобразовывать буквы, проверить, не равны ли они. 15. Заведите приблизительно 50 отдельных счетчиков и просмотрите весь файл один раз. Но есчи бы в условии задачи вместо слова "штат" стояло слово "город" и общее число городов было довольно велико, то следовала бы предпочесть сортировку по названиям городов. 16. Как и в упр. 15, решение зависит от объема задачи.
Если количество идентификаторов для перекрестных ссылок не очень велико и их можно разместить в оперативной памяти, то лучше всего, пожалуй, воспользоваться алгоритмом обработки таблицы символов (см. гл. 6), в котором с каждым идентификатором связывается голова связного списка ссылок. Если же задача большая, необходимо создать файл записей, по одной на каждую ссылку, которая вносится в указатель, а затем рассортировать этот файл. 1с. Присвойте всем карточкам "теневые ключи", чтобы требуемое упорядочение можно было выпщпшть с полсощью обычной лексикографической сортировки по этим ключам. Этот ключ дшгжен быть внесен персонююм библиотеки в каждую карточку, когда она впервые поступает в систему. Можно, например, использовать следующий двухбуквенный код для разделения слов: епй о( Ьеу; епй о( сгоаз-ге)егепсе; епй а( епгпаше; ЬурЬеп о) пш!Мр)е епгпате; епй о( ап)Ьог пате; епй о( р)асе пате; епй о(епЬ)есг Ьеай)пб; епй о1 Ьоо)г 61)е; красе Ьесиееп «огйе.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
