ОТВЕТЫ К УПРАЖНЕНИЯМ

"Нет, довольно! - сказал возмущенный отец.

- Есть граница любому терпенью. Если пятый вопрос ты задашь наконец, Сосчитаешь ступень за ступенью!"* ЛЬЮИС КЭРРОЛ (LEWIS CARROLL), Алиса в стране чудес, гл. 5. (1862)

ПРИМЕЧАНИЯ К УПРАЖНЕНИЯМ

1. Задача средней сложности для читателей с математическим уклоном.

3. См. W. J. LeVeque, Topics in Number Theory 2 (Reading, Mass.: Addison-Wesley, 1956), Chapter 3; P. Ribenboim, 13 Lectures on Fermats Last Theorem (New York: Springer-Verlag, 1979); A. Wiles, Annals of Mathematics 141 (1995), 443-551.

РАЗДЕЛ 5

1. Пусть p(l).. .p(n) и q{l)...q{n) - две ргьзличные перестановки, удовлетворяющие этим условиям, и пусть г - минимальный индекс, при котором p{i) ф q{i). Тогда p{i) = q(j) при некоторых j > г, а (г) = р{к) при некоторых к > i. Поскольку АГр() < Кк) = Kq{.i) < яИ) - P<.i)> имеем АГр(() = Kfiy, атак как сортировка устойчива, то p{i) < р{к) = q{i) < q{j) = p{i), чего быть не может.

2. Да, если все операции сортировки были устойчивыми. (В противном случае этого утверждать нельзя.) Ясно, что Алиса и Крис получили одинаковые результаты; то же самое получил и Билл, так как вследствие устойчивости при равных больших ключах малые ключи расположились в порядке неубывания.

Формальное доказательство: пусть после сортировки по малым ключам Билл получил Др(1)... Др(л-) = Ri...Rn, а после второй сортировки по большим ключам - • К(.Ю - p(4W) RpMN))- Нужно показать, что при 1 <i< N

ip(4(i))K(Q(i))) (p(9(i+l)),=p(<7(i+l)))-

Если ATpffi)) ф А:р(,(,+1)), то A:p(,(i)) < A:p(,(i+i)); если же А:р(,(;)) = ATpffi+i)), то ATj;) = Kii+i), и тогда (г) < q{i + 1). Следовательно, fcj) < т. е. fcp(,(i)) < fcp(,(i+i)).

3. Всегда можно собрать вместе записи с одинаковыми ключами, сохранив при этом их относительное расположение; тогда в последующих операциях каждая такая группа рассматривается как неделимое целое. Следовательно, можно считать, что все ключи различны. Пусть а < Ь < с < а; эти три ключа можно упорядочить так: аЬс, Ьса или cab. Далее, если упорядочены N - 1 различных ключей тремя способами, можно это сделать и для N ключей, поскольку при Ki < ••• < Kn-i > Kn либо Ki~\ < Kn < Ki для некоторого г, либо Kn < К\.

* Перевод С. Я. Маршака.

4. Сначала сравним слова, не обращая внимания на регистр символов, затем воспользуемся регистром символов для уточнения порядка. Точнее, заменим каждое слово а парой (а, а), в которой а формируется из Q подстановкой А а, ..., Z z; затем рассортируем сформированные пары лексикографически. В результате получим, например, tex < Тех < ТеХ < ТЕХ < text.

В словарях также встречаются слова с диатоническими знаками, префиксами, суффиксами и аббревиатуры; например,

а < А < А < а- < а. < -а < А- < А. < аа < а.а.

< аа < аа < АА < А.А. < AAA < • < zz < Zz. < ZZ < zzz < ZZZ.

В таком более общем случае получим а отображением а а, А а и т. д., отбрасывая знаки дефиса и точки.

5. Положим р{0) = О и р{{1а)2) = 1р{\а\)а; здесь (1а)2 является обычным двоичным представлением положительного целого числа, а а - длиной строки а. Тогда р{1) = 10, р{2) = 1100, р{3) = 1101, р{4) = 1110000, ..., /j(1009) = 111101001111110001, ..., /j(65536) =

\р{п)\ = Л(п) + Л(Л(п)) + Л(Л(Л(п))) + • • • + Ig* п + 1,

где Л(0) = О, Л(п) = [IgnJ для п > 1, а lg*n есть наименьшее целое m > О, такое, что Л"1(п) = 0. [Эта конструкция предложена В. И. Левенштейном, Проблемы кибернетики 20 (1968), 173-179; см. также Д. Э. Кнут в The Mathematical Gardner, edited by D. A. Klarner (Belmont, California: Wadsworth International, 1981), 310-325.]

6. Возможно переполнение, которое может исказить результаты сравнения. Следовало написать, например, "LDA А; СМРА В" и проверить индикатор сравнения. (Невозможность сравнения чисел, занимающих целое слово, посредством вычитания - проблема, возникающая на многих моделях компьютеров; это основной довод в пользу включения операторов СМРА,..., СМРХ в систему команд компьютера MIX.)

7. COMPARE STJ 9F DECl 1 IH LDX A,l JIP IB

CMPX B.l 9H JMP * I

JNE 9F

8. Решение 1, основанное на тождестве min(a,b) = (а -Ь 6 - а - 6):

(02 - 62) sign(a - 6)

Переполнение невозможно

Решение 2, основанное на том, что индексирование может вызвать сложные взаимные обмены:

S0L2 LDA А STA С STA ТА LDA В STA ТВ

Теперь включите в программу приведенную ниже последовательность операторов к раз подряд, где 2* > 10°:

LDA ТА LDA ТВ INC1 0,2

SRAX 5 SRAX 5 INC1 0,2

DIV =2= DIV =2= INC1 0.2

STX TEMP STX TEMP LD3 TMIN.l

LDl TEMP LD2 TEMP LDA 0.3

STA ТА STA ТВ STA С

(Эта программа просматривает разряды в двоичном представлении а и 6 справа налево, сохраняя знаковые разряды.) В конец текста программы поместите следующую таблицу:

9. Вероятность равна сумме С"*! )(-1)(r+j)"") которую получим методом включения и исключения (упр. 1.3.3-26). Это также можно записать в виде бета-распределения

10. Рассортируйте содержимое ленты, а затем посчитайте. (Некоторые методы сортировки позволяют легко отбрасывать записи с повторяющимися ключами.)

11. Присвойте каждому человеку индивидуальный идентификационный номер, который должен быть указан на всех касающихся его карточках. Рассортируйте отдельно информационные и налоговые карточки, используя в качестве ключа идентификационный номер. Обозначим рассортированные налоговые карточки через i?i,..., Rn, а их ключи - через Ki < < Kn- (Не должно быть обнаружено ни одной пары карточек с повторяющимися ключами.) Добавьте новую {N -t- 1)-ю запись с ключом оо и установите г <- 1. Затем для каждой записи из информационного файла проверьте, было ли о ней сообщено, следующим образом. Обозначим через К ключ обрабатываемой информационной карточки.

a) Если К > Ki, то увеличить г на 1 и повторить этот шаг.

b) Если К < Ki или К = Ki, & соответствующая информация не отображена в налоговой карточке Ri, то сообщить об ошибке.

Постарайтесь проделать все это, не тратя впустую денег налогоплательщиков.

12. Один из способов состоит в том, чтобы присоединить к элементам матрицы Oij ключи (j, г), лексикографически рассортировать элементы по этим ключам, после чего ключи