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

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.

41

American Standart Code for Information Interchange—американский стандартный 8-разрядный код для обмена информацией. — Прим. перев.

42

Признак косвенной адресации, — Прим. перев.

43

Аббревиатуры от Register-Register (регистр-регистр), Register-Storage (регистр-память), IMmediate (непосредственная), CHaracter (байтовая). — Прим. перев.

44

На языке ассемблера разряд косвенной адресации задается звездочкой перед полем адреса, как, например, LN,R1 * A,R.2.

45

Аббревиатуры от Overflow (переполнение), Less than (меньше, чем), Greater than (больше, чем), Equal (равно). — Прим, перев.

46

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

47

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

48

Мнемоническим обозначениям команд арифметических операций с вещественными числами предшествует буква «F» в силу исторически сложившегося названия представления вещественных чисел как чисел с плавающей точкой (floating point). Это отражается также в мнемонике кодов операций FLOATR, FLOAT и FLOATI.

49

Эти команды обозначены FIXR, FIX и FIXI, поскольку представление целых чисел исторически называется представлением с фиксированной точкой (fixed point).

50

Счетчик сдвига, по абсолютной величине больший 32, определяет те же действия, что и соответствующий счетчик, по модулю равный или меньший 32. При выполнении команды сдвига большие значения счетчика заменяются меньшими

51

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

52

Вообще, если A есть начальный адрес текущего загружаемого модуля, то всегда выполняется соотношение САР — А = СОР. То есть САР и СОР при всех обстоятельствах изменяются согласованно, образуя тандем.

53

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

54

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

55

В русском переводе приходится склонять нетерминальные символы грамматики. — Прим. перев.

56

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

57

Возможно, читателя заинтересуют следующие вопросы:

1. При какой точности выполнения операций с плавающей точкой можно гарантировать конечность первого цикла в функции integersqrt?

2. Не может ли получиться так, что после завершения этого цикла будет выполнено неравенство ?

3. Нельзя ли избавиться от второго цикла в функции integersqrt, выполнив все операции первого в целочисленной арифметике? Как следует выбрать начальное приближение и условие завершения цикла?

4. Действительно ли нужно прибавлять 1 при вычислении значения limit? 5. Можно ли в заголовке цикла маркировки составных чисел заменить 2*i на i*i?. — Прим. перев.

58

TRAC — это фирменный знак Rockford Research Institute, Cambridge,MA

59

Сейчас Муэрс использует холостую цепочку # (пц (CR LF)) # (пц, # (чц)), где CR — литера «возврат каретки», a LF — «перевод строки»

60

Позднее мы рассмотрим, каким образом цепочка может представлять число.

61

Для усиления аналогии между трудом писателя и программиста отметим, что данная глава переписывалась не раз и не два

62

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

63

Номера строк в этой процедуре те же, что и в полной программе, приведенной на стр. 265—275 (см.ниже)

64

Если переменная V — цепочка или выражение, тогда SUBSTR (V, S, L) есть подцепочка V, начинающаяся с S-й литеры (первая литера цепочки имеет номер нуль) и содержащая L байтов. Если аргумент L опущен, будет выдан весь остаток цепочки V, начиная с S-й позиции. Функция LENGTH выдает в качестве значения число литер в аргументе. В строке 332 процедуры BUILD.DICTIONARY используется SUBSTR вместе с LENGTH для того, чтобы исключить сличенную цепочку MATCH из начала INPUT.BUFFER (буфер ввода).