было предоставлено О Коши (А. Cauchy) [Bull. Societe Philomathique de Paris (3) 3 (1816), 133-135], который дал этому ряду имя Фарея О других интересных свойствах данных рядов говорится в работе G. Н Hardy, Е. М Wright, Ал Introduction to the Theory of Numbers, Chapter 3.

20. * ЗАДАЧА 0 СИГНАЛАХ СВЕТОФОРА

AGREEN ALF САВА Зеленый свет для авеню.

AAMBER ALF СВВВ Желтый свет для авеню.

BGREEN ALF АСАВ Зеленый свет на проспекте.

BAMBER ALF ВСВВ Желтый свет на проспекте.

END BEGIN I

Последним остается человек в позиции 15. Общее время выполнения программы без печати результатов составляет (4(JV - l)(f + 75) + 16)u Программу можно несколько улучшить, например воспользоваться предложением Д. Инголза (D. Ingalls) и взять состоящие из трех слов пакеты кода "DEC2 1; J2P NEXT; JMP OUT", где команда OUT модифицирует поле NEXT таким образом, что удаляет пакет Асимптотически более быстрый метод приведен в упр. 5.1.1-5.

РАЗДЕЛ 1.3.3

1. (1 2 4)(3 6 5).

2. о <+ с, с <+ /; 6 <+ d. Совершенно очевидно, как это обобщить на случай произвольной перестановки.

abed Jb f с

4. (adcfe).

5. 12 (см упр 20).

а е)

6. Общее время увеличится на 4и для каждого пустого ввода, перед которым идет непустое слово "(", и еще на 5й для каждого пустого слова, перед которым идет непустое слово-имя Начальные пробелы и пробелы между циклами не оказывают влияния на время вьшолнения программе Положение пробелов никак не влияет на время выполнения программы В

7. X = 2, У = 29, М = 5, Л = 7, {/ = 3, V = 1 Общее время выполнения согласно (18) равно 2161it

8. Да В этом случае нужно использовать обратную перестановку, чтобы х, переходило в Xj тогда и только тогда, когда T[j] = г (Тогда окончательный вид циклической формы будет построен справа налево с помощью таблицы Г )

9. Нет Например, если вводом является (6), то программа А в качестве вывода даст "(ADG) (СЕВ)", а программа В - " (СЕВ) (DGA)" Эти ответы эквивалентны, но не идентичны, так как циклическая запись не единственна В программе А первым элементом цикла выбирается крайний слева, а в программе В - последний отличный от других при движении справа налево

10. (1) По закону Кирхгофа получаем A = l+C-D, B = A + J+P-l,C = B-{P-L), E = D-L, G = E,Q = Z,W = S (2) Объяснение В = число слов ввода = 16Х - 1, С = число непустых слов = Y, D = C - М, E = D - М, F = число сравнений при поиске по таблице имен, Н = N, К = М, Q = N, R = U, S = R - V,T = N - V, так как каждое из других имен помечено (3) В итоге получаем (4F + 16У + 80Л 4- 21Л - 19М + 9U- 16V)u Это несколько лучщий результат, чем дает программа А, поскольку, безусловно, F меньше, чем 16NX Общее время выполнения в данном случае равно 983и, так как F = 74

11. "Отразите" ее Например, обратной к перестановке {acf){bd) является {db){fca)

12. (а) Значение, которое находится в ячейке L + тп - 1, во время транспонирования остается на месте, поэтому ее можно исключить из рассмотрения А в остальном, если х - n{i - \) + {] - \) < тп - 1, значение из ячейки L + ж должно перейти в ячейку L + тх mod N = L + {mn{i - 1) + m{j - 1)) mod N = L + m{j - 1) + (г - 1), так как тп = 1 (по модулю Л) и о < m{j - 1) + (t - 1) < Л (b) Если в каждой ячейке памяти один бит свободен (например, бит знака), элементы можно "помечать" по мере их перемещения с помощью алгоритма, подобного алгоритму I [См М F Berman, JACM 5 (1958), 383-384 ] Если для битов пометки нет свободного места, то их можно сохранять во вспомогательной таблице или использовать список элементов, содержащихся во всех не единичных циклах Для каждого делителя d числа Л можно по отдельности транспонировать те элементы, которые кратны d, так как т взаимно просто с Л Длина цикла, содержащего х, где gcd{x,N) = d, - это наименьшее целое г > О, такое, что тп = 1 (по модулю N/d) Для каждого d нужно найти (p{N/d)/r элементов-представителей, по одному из каждого цикла Это можно сделать с помощью ряда теоретико-множественных методов, но они недостаточно просты для того, чтобы мы могли ими удовлетвориться Эффективный, но довольно сложный алгоритм можно получить, применяя теорию чисел, а также используя небольшую таблицу битов пометок [См N Brenner, САСМ 16 (1973), 692-694 ] И наконец, существует метод, который является аналогом алгоритма J Он работает медленнее, но зато не требует дополнительной памяти и любые нужные перестановки выполняет гп situ* [См Р F Wmdley, Comp J 2 (1959), 47-48, D E Knuth, Proc IFIP Congress (1971), 1, 19-27, E G Gate, D W Twigg, ACM Trans Math Software 3 (1977), 104-110, F E Fich, J I Munro, P V Poblete, SICOMP 24 (1995), 266-278]

13. Покажите no индукции, что в начале шага J2 X[i] = +j тогда и только тогда, когда J > ти J переходит в г в результате перестановки тг X[i] = -j тогда и только тогда, когда

* На месте" (лат ) - Прим перев