Этюды для программистов

1

Семь лет — традиционный срок ученичества в средневековых ремесленных мастерских Англии. — Прим. перев.

2

Чиппендейл (Chippendale) Томас (1718–1779) — английский мебельный мастер. Сочетал функциональную целесообразность форм с изяществом линий. — Прим. перев.

3

Мы называем нашего читателя «студентом». Это, однако, не должно отпугнуть тех, кто не учится в соответствующем учебном заведении. Научиться программировать можно и в одиночку; желая вдохновить тех, кто вынужден осваивать предмет самостоятельно, мы предлагаем им для решения набор задач, достаточно близких к реальным. Учтите, однако, что осваивать предмет под руководством преподавателя все же неизмеримо легче.

4

Предлагаются такие общедоступные языки, как Фортран, Кобол, Алгол, язык ассемблера, APL, XPL, PL/I, Бейсик, Паскаль, Лисп, Снобол и др. Это не означает, что не подходит какой-нибудь менее известный или менее распространенный язык, тем более что в наших рекомендациях мы руководствовались собственными вкусами. В любом случае приветствуется использование языков и трансляторов более высокого уровня, типа WATFIV, PL/C или SPITBOL, требующих и более серьезного к себе отношения. Можно также использовать задачу для изучения нового языка («полное погружение» — метод тяжелый, но эффективный).

5

На русском языке вышли 3 тома (как, впрочем, и на английском). — Прим. перев.

6

Один из способов сокращения памяти, требуемой для запоминания позиций, состоит в том, чтобы хранить позицию в виде массива битов, отводя для каждой клетки один бит (а не слово памяти). Как это ни странно, такой способ позволяет также получить выигрыш во времени, если воспользоваться командами поразрядных логических операций над векторами битов, имеющихся в системах команд почти всех ЭВМ и в некоторых языках программирования высокого уровня (например, в PL/I). Если обозначить через р исходную позицию, через p₁, p₂, …, p₈ — позиции, сдвинутые на одну клетку в направлении всех соседей клетки, и через r — новую позицию, то каждый бит r будет однозначно определяться битами с тем же номером в позициях p₁, p₂, …, p₈, т. е. будет логической функцией от них. Всякую логическую функцию можно, как известно, записать с помощью элементарных логических операций: ∧ (логическое И), ∨ (логическое ИЛИ), ⊕ (сложение по модулю два) и ¬ (логическое отрицание). Задача состоит в том, чтобы выразить r через p₁, p₂, …, p₈ экономно, с использованием возможно меньшего числа операций. Необходимое число операций удается уменьшить до 29 (и это, вероятно, не предел), что при размере машинного слова в 48 битов (над всеми битами слова логические операции выполняются параллельно) составляет чуть более половины логической операции на обработку одной ячейки. — Прим. перев.

7

Теперь это замечание имеет лишь исторический интерес. Разъяснение вы найдете в литературе к гл. 29.

8

Английское существительное format (формат) служит для обозначения размера, формы и общего оформления публикации. Фортран присвоил это слово для описания формы и структуры записей данных. Но для обозначения того процесса, которым управляет фортранная инструкция FORMAT, удобного глагола не существует. Поэтому, говоря о процессе оформления текста по заданному образцу или схеме, наряду с глаголом to edit (редактировать) в этой главе будем использовать глагол to format (форматировать). Следует ли это считать жаргоном или нормальным развитием английского языка — дело вкуса читателя. (Примерно так же обстоит дело с терминологией в русском языке. В скобках указаны термины, которые используются в переводе этого этюда. Спорным, конечно, является и слово «форматор» (formattor). — Перев.)

9

Выпускающий редактор этой книги утверждает, что процесс подготовки большинства изданий проходит отнюдь не так идиллически, как это здесь обрисовано. Хотя в издательстве «Прентис Холл» набор текста производится при помощи ЭВМ, все же большая часть работы по оформлению, размещению и расклейке материала еще делается вручную. В частности, наборщики требуют дополнительного вознаграждения за исправления вкравшихся в текст ошибок. Тем не менее ручной труд в печатном деле отходит в прошлое, а для полной победы автоматизации недостает, пожалуй, только устройства непосредственного ввода рукописного текста.

10

i — первая буква английского слова italics (курсив). — Прим. перев.

11

Тут автор неточен. Статистика М показывает, сколько соперников, считавшихся до турниров сильнейшими (имеющих меньшие номера), заняло в обеих классификациях одинаковые места (возможно, и не самые высокие). — Прим. перев.

12

Все права на изобретение деловой игры менеджмент принадлежат фирме Avalon Hill Company, 4517 Harford Road, Baltimore, MD, 21214, которая ее опубликовала. Мы слегка изменяли правила, чтобы этюд легче было программировать.

13

Профсоюз водителей грузовиков. — Прим. перев.

14

Инвестиционный фонд — тип финансового института — вкладывает в ценные бумаги денежный капитал, аккумулированный путем эмиссии собственных ценных бумаг. Прибыли фонда обусловлены разницей между полученными и выплаченными дивидендами и процентами. — Прим. перев.

15

Читатели, знакомые с вычислительными методами, должны были заметить, что приведенная формула соответствует решению уравнения относительно дохода методом Ньютона.

16

Журнал деловых кругов США — Прим. перев.

17

В лингвистике диграф — комбинация из двух букв, обозначающая один звук; аналогично, триграф — из трех букв, квадриграф — из четырех и т. д. — Прим. перев.

18

Попав в калах, камень уже никогда не покинет его: Кроме того, не существует циклических последовательностей ходов, приводящих к исходной позиции, поскольку любом ход либо помещает в калах хотя бы один камень, либо перемещает некоторые камки ближе к калаху. Если реализовать изменение, упомянутое в следующем абзаце, то любая игра должна заканчиваться в состоянии, когда все камни лежат в одном из двух калахов.

19

Перебор в ширину называют также полным перебором. — Прим. перев.

20

Достаточно проверить только непосредственный предшественник, при этом будут найдены все отсечения. — Прим. перев.

21

Это не совсем так. Число простых чисел среди первых n (при n → ∞) примерно равно n/ln n. Таким образом, отношение числа простых и составных чисел есть

— Прим. перев.

22

Напомним, что книга издана в 1978 г. — Прим. перев.

23

Дата в журнале представлена в последовательности месяц, число, год. — Прим. перев.

24

Дополнительную трудность вызывает использование традиционных английских мер. Однако сделано это умышленно, и вы должны выдавать результаты в тех же единицах. Если бы скорость измерялась в д/д, т. е. в дюймах в день, было бы еще хуже…

25

Напомним, что натуральное число — это неотрицательное целое число.

26

Файл ввода/вывода состоит из записей, которые могут быть разной длины. Каждое физическое устройство может накладывать свои ограничения на длину записи. Предполагается, что перед первой операцией ввода/вывода с данным файлом указатель текущей позиции в нем установлен на конец воображаемой нулевой записи. При выводе по мере надобности создаются новые записи.

27

−q нулей и d+q цифр по стандарту Фортрана и Фортрана-77. — Прим. перев.

28

Английское словосочетание to lose patience имеет два значения — «потерять терпение» и «проиграть пасьянс». — Прим. перев.

29

Эта грустная шутка основана на созвучии Las Vegas (Лас Вегас) и lost wages (потерянные зарплаты). — Прим. перев.

30

Фактически поиск максимального в столбце элемента М на шаге 3 алгоритма обращения есть одно из таких изменений. М называется ведущим элементом, а сама операция — выбором ведущего элемента; на самом деле необходимо лишь, чтобы М был ненулевым. Максимальный элемент используется, чтобы уменьшить арифметическую погрешность ЭВМ. При обращении матрицы Гильберта ведущим элементом всегда должен оказываться ; если же алгоритм выбирает в качестве ведущего элемент, лежащий ниже, то это означает, что погрешность уже очень велика.

31

Как здесь не отметить, что самую плодотворную идею по части быстрого умножения вы можете позаимствовать у кроликов. Их многочисленное потомство — тому порука.

32

Дадим небольшое пояснение к рисунку: long — длинный, stack — стек, control — управляющий pop … into — удалить вершину … и поместить в, abort — аварийное окончание. Остальные ключевые слова имеют тот же смысл, что в яэыке Паскаль. — Прим. перев.

33

В алгоритм, вероятно, необходимо внести следующие изменения:

a) на шаге 1 заменить max (m, 2n) на max (2m − 2n, 2n);

b) на шаге 4 заменить 2^3·2i на 2^3·2i−1.

Прежде чем приступать к программированию алгоритма Тоома—Кука или алгоритма деления, рекомендуем тщательно разобраться в них, ознакомившись с теорией, например по книге Кнута, неоднократно цитируемой здесь — Прим. перев.

34

На самом деле a_i+1 = (a_i/5²) · (2i − 1)/(2i + 1)). Чтобы не выполнять умножение, можно хранить кроме a_i еще одно число b_i, равное (2¹⁰⁰⁰ × 16)/5²ⁱ⁻¹. Тогда переход к следующему члену осуществляется по формулам: b_i+1 = b_i/5², a_i+1 = b_i+1/(2i + 1). — Прим. перев.

35

Эти алгоритмы для очень длинных чисел работают еще быстрее алгоритма Тоома—Кука, затрачивая на умножение n-разрядных чисел время, пропорциональное n log n log log n — Прим. перев.

36

В § 4.4 этой книги приведены алгоритмы перевода чисел в десятичную систему. — Прим. перев.

37

В журнале «Наука и жизнь» № 2, 1978, с. 150–151; № 8, 1978, с. 142—143, опубликован вариант этой игры под названием «Быки и коровы». — Прим. перев.

38

Здесь автор имеет в виду вариант той же игры, в котором вместо цифр используются фишки, окрашенные в шесть цветов. — Прим. перев.

39

В оригинале, разумеется, все рассуждения проводятся для английского текста. — Прим. перев.

40

В криптографии используются некоторые слова, которые люди непосвященные часто употребляют не совсем правильно. Шифрование — это способ засекречивания сообщения путем замены или перемешивания букв, кодирование же подразумевает замену целых слов или фраз, а не отдельных букв. Лица, владеющие шифром или кодом, шифруют или кодируют свои сообщения, а получатели сообщений дешифруют или декодируют их. Лица, пытающиеся узнать чужой секрет, расшифровывают сообщения; различие между этими глаголами соответствует различию между знанием секрета шифра и попыткой разгадать его. Тот, кто составляет секретные сообщения, занимается криптографией, или тайнописью, а тот, кто стремится прочитать чужое секретное сообщение, занимается анализом криптограмм (cryptanalysis). Применяемые для этого методы составляют предмет науки, которая по-английски называется cryptology.