32. (а) На самом деле к - 1<тгк<к + 2, если к - четное, и к - 2 < тгк < к + 1, если к - нечетное. (Ь) Выбирайте Экспоненты слева направо, полагая вк = 1 тогда и только тогда, когда к и к + 1 пока еще находятся в разных циклах перестановки. [Steven Alpern, J. Combinatonai Theory B25 (1978), 62-73.]

33. Для I - 0 положим (Qoi,ao2;/3oi,/9o2) = (7г,р;б,б) и (qii,Qi2;/3ii,/3i2) = (€,€;7г,р), где = (14)(23),р=(15)(24)ие=().

Предположим, мы построили такую конструкцию для некоторого I > О, где ajk = 0jk = О для 0<j<mHl <к<п. Тогда перестановки

(Аут+>)1 • • i0m+j)(4n); Bjm+ji)l,- , B(jm+j)(4n)) =

(ff-Qjiff,.. .,(T~ajn(T, tOjit, .. .,T~djinT,

(T~0jl(T, . . . ,ff"/3j„ff, T~Pj,iT, . . .,t~0j,r,t,

a~ajncr,ffajia, т~ау„т,... ,т~ ajnr)

обладают свойством

ff~(12 34 5)ffT"(123 45)Tff"(543 21)ffT~(543 21)T,

если i = j и i = j, в противном случае произведение равно (). Выбирая а = (2 3)(4 5) и т = (3 4 5), получим искомое произведение (12 3 4 5) при im + i = jm + j.

Метод построения от I к 1 + 1 предложен Дэвидом А. Бэррингтоном (David А. Barrington) [J. Сотр. Syst. Sci. 38 (1989), 150-164], который доказал общую теорему о том, что любую булеву функцию можно представить в виде произведения перестановок множества {1,2,3,4,5}. С помощью аналогичной конструкции можно, например, найти последовательности перестановок (aji,..., Qj„; /3,1,...,/Зп), такие, что

an/3jiai2/3j-2 ... ai„/3j„ = q

2 34 5), если<;;

если t > j;

для О < i, j < m = 2, где n = 6+ - 4+.

34. Пусть N - т + п. Если m ± п, существует только один цикл, так как каждый элемент можно записать в виде am mod Л для некоторого целого а. В общем случае, если d - gcd(m, тг), то существует ровно d циклов Со, Ci, ..., C-i, где Cj содержит элементы {h 3 д,..., j + N - d), расположенные в некотором порядке. Тогда, чтобы выполнить перестановку, необходимо действовать следующим образом для Q < j < d (параллельно, если это удобно). Присвоить t Ь- Xj тл к +- j. Затем, до тех пор, пока {к + тп) mod Л / j, присваивать Хк ч- Х(к+т) mod n и к +- {к + т) mod Л. И наконец присвоить Хк t. В этом алгоритме неравенство {к + тп) mod N ф j будет выполняться тогда и только тогда, когда [к + тп) mod N > d, поэтому можно использовать любой тест, который является более эффективным. [W. Fletcher, R. Silver, САСМ 9 (1966), 326.]

35. Положим М = / + тп + пиЛ = ; + 2тп + п. Циклы искомой перестановки получены из циклов такой перестановки на множестве {0,1,..., Л - 1}, которая переводит к в (к + I + тп) mod Л, просто исключая все элементы каждого цикла, которые > М. (Сравните это с аналогичной ситуацией в упр. 29.) Доказательство. Когда в результате предложенного в указании взаимного обмена будет выполнено присвоение Хк Хк и Хк Ч- Хк» для некоторого к, где к = {к + I + т) mod Л, к" = (к + I + т) mod N и к > М, получим, что Хк = Хк"- Отсюда переход afif -> 7/Зо; заменяет Хк на Хк".

Следовательно, существует ровно d = gcd(Z + т,т + п) цдклов и можно использовать алгоритм, аналогичный тому, который рассматривался в предыдущем упражнении.

Заслуживает также внииания несколько более простой способ сведения этой задачи к частному случаю из упр. 34, хотя он подразумевает больше случаев обращения к памяти. Предположим, 7 = 77", где 7" = q. Тогда можно заменить a0ff" на а и выполнить взаимный обмен 7" с /з7. Аналогичный подход можно использовать и при \а\ > 7(. [См. J. L. Mohammed, С. S. Subi, J. Algorithms 8 (1987), 113-121.]

РАЗДЕЛ 1.4.1

1. Последовательность вызова: JMP MAXN; или JMP МАХ100, если п = 100. Состояния при входе: Для входа MAXN г13 = тг; предполагается, что тг > 1. Состояние при выходе: Такие же, как в (4).

2. МАХ50 STJ EXIT

ENT3 50 JMP 2F

3. Состояние при входе: тг = гИ, если гП > 0; в противном случае тг = 1. Состояние при выходе: гА и г12 такие же, как в (4); гП не изменился; г13 = min(0, гП);

rJ = EXIT + 1; CI не меняется, если п = 1, в противном случае CI будет больше, равен или меньше прежнего значения, в зависимости от того, будет ли максимум больше А[1], равен А[1] при г12 > 1 или равен Х[1] при г12 = 1. (Аналогичное упражнение для (9), конечно, было бы немного более сложным.)

4. SHAX1 ENT1 I г = 1

SMAX STJ EXIT Произвольное г.

JMP 2F Далее, как в прежней программе.

DEC3 0,1 Уменьшить на г. J3P IB EXIT JMP ♦ Выход.

Последовательность вызова: JMP SMAX; или JMP SMAX1, если г = 1.

Состояние при входе: г13 = п, предположительно положительному; для входа SMAX

rll = г, предположительно положительному.

Состояние при выходе: гА = тахо<к<„/г CONTENTSCX + п-кг) = CONTENTSCX + г12);

и г13 = (тг - 1) mod г + 1 - г = -((-п) mod г).

5. Можно использовать любой другой регистр, например:

Последовательность вызова: ENTA +2.

JMP MAXIOO.

Состояние при входе: Нет.

Состояние при выходе: Такие же, как в (4).

Код аналогичен (1), но первая команда имеет вид "МАХ100 STA ЕХ1Т(0:2)".

6. (Решение предложено Джоэлом Голдбергом (Joel Goldberg) и Роджером М. Аароисом (Roger М. Aarons).)

MOVE STJ 3F

STA 4F Сохранить гА и rI2.

ST2 5F(0:2)

LD2 3F(0:2) rI2 ч-адрес "NOP A, 1(F)".

LDA 0,2(0:3) rA "A.I".

STA *+2(0:3)

7. (1) Операционная система распределяет высокоскоростную память (кэш-память) более эффективно, если программные блоки предназначены только для чтения. (2) Аппаратная кэш-память команды будет более быстрой и менее дорогой в случае, если команды не смогут измениться. (3) Рассмотрим (2), только с "каналом" вместо "кэш-памяти". Если команда модифицируется после входа в канал, то канал нужно очистить; схема проверки этого условия очень сложна, а ее использование отнимет много времени. (4) Самомодифицирующийся код может использоваться только одним процессом за один раз. (5) Самомодифицирующийся код может повредить программу отслеживания переходов (упр. 1.4.3.2-7), которая является важным инструментом диагностики, выполняющим "профилирование" (т. р. определяющим, сколько раз выполняется каждая команда).

РАЗДЕЛ 1.4.2

1. Если одна сопрограмма вызывает другую только один раз, то это всего лишь подпрограмма. Поэтому нужен такой пример, в котором каждая сопрограмма вызывает другую по меньшей мере в двух различных местах. Но даже в таком случае иногда можно установить что-то наподобие переключателя или воспользоваться каким-либо свойством данных, чтобы, входя в фиксированную точку внутри одной сопрограммы, можно было направляться к одному из двух нужных мест. И для этого опять-таки достаточно подпрограммы. А польза от применения сопрограмм становится все более очевидной по мере роста числа их обращений друг к другу.

2. Первый символ, найденный IN, будет потерян. [Сопрограмма OUT запускается первой, потому что в строках 58 и 59 вьшолняется необходимая инициализация IN. Чтобы первой запустить IN, нужно инициализировать OUT с помощью команды "ENT4 -16" и очистить буфер вьшода, если неизвестно, пуст ли он. Затем можно из строки 62 перейти сначала в строку 39.]

3. Утверждение почти истинно, так как команда "СМРА =10=" внутри IN будет тогда единственным оператором сравнения в программе, а кодом "." является 40. (!) Но если бы перед завершающей точкой стояло число повторений, то тест прошел бы, как по маслу. [Замечание. Если задаться целью создать эффективную программу и подойти к этому с максимальной педантичностью, то, вероятно, нужно будет удалить строки 40, 44 и 48 и вставить команду "СМРА PERIOD" между строками 26 и 27. Но если в сопрограммах используется флаг сравнения, то его необходимо занести в список характеристик сопрограммы в документации к программе.]