Грисуолд, Поудж, Полонски (Griswold R. E., Poage J. E., Polonsky I. P.). The SNOBOL4 Programming Language, 2nd ed. Prentice-Hall; Englewood Cliffs, NJ, 1971. [Имеется перевод: Грисуолд Р., Поудж Дж., Полонски И. Язык программирования Снобол-4. — М.: Мир, 1980.]
Имеется множество книг по таким языкам, как Фортран, Кобол, Бейсик, Алгол, языки ассемблера и PL/I. Айверсон разработал язык APL как алгоритмический; перед тем как приступить к работе с его конкретной реализацией, ознакомьтесь с соответствующим руководством. Книга Мак-Кимана и др. — эталонное описание языка XPL. Перед тем как работать с языками Лисп или Снобол, очень желательно ознакомиться с особенностями конкретной реализации.
Айверсон (Iverson К. Е.). A Programming Language. Wiley, New York, 1962.
*Гилман, Роуз. Курс АПЛ: диалоговый подход. Пер. с англ. — М.: Мир, 1979.
Йенсен, Вирт (Jensen К., Wirt N.) PASCAL User Manual and Report. Lecture Notes in Computer Science, 18, Springer-Verlag, Berlin, 1974.
*Грогоно. Программирование на языке Паскаль. Пер. с англ. — М.: Мир, 1982.
Кнут (Knuth D. E.). The Art of Computer Programming/Fundamental Algorithms. Addison-Wesley, Reading, MA, 1968. [Имеется перевод: Кнут Д. Искусство программирования для ЭВМ. Т. 1. Основные алгоритмы. — М.: Мир, 1976.]
Серия книг Кнута[5], если он когда-нибудь ее закончит, имеет все шансы стать библией программистов. Конечно же, первый том содержит наиболее элементарные сведения о структурах данных и алгоритмах работы с ними. Если вы не понимаете, как воспользоваться предложенной в настоящей книге структурой данных, — справьтесь у Кнута. Мы, однако, не предлагаем стиль программирования Кнута как образец структурирования программ.
Люка (Lucas F. L.). Style. Collier, New York, 1962.
Эта книга вовсе не о программировании. Вам со временем понадобится писать обширную документацию — тут-то и может помочь эта книга. Более того, многие наблюдения автора применимы также и к написанию программ. Люка сосредоточивает внимание на способах убеждения, а программисту приходится убеждать и машину, и человека.
Мак-Карти и др. (McCarthy J. et al.). LISP 1.5 Programmer's Manual. MIT Press, Cambridge, MA, 1972.
Мак-Киман, Хорнинг, Уортмен (McKeeman W. M., Horning J. J. Wortman D. B.)s A Compiler Generator. Prentice-Hall; Englewood Cliffs, NJ, 1970.
Вегнер (Wegner P.). Programming Languages, Information Structures, and Machine Organization. McGraw-Hill, New York, 1968.
Если у вас возникнут какие-либо вопросы об архитектуре ЭВМ, языках, структурах данных, а также их взаимосвязях, книга Вегнера, возможно, даст ключ к ответу. В книге собрано и увязано воедино исключительное количество распространенных терминов. Приводится краткий обзор информатики и ценный список литературы.
2.
Жизнь диктует свои законы,
или Клеточные автоматы и машинная графика
Жизнь — это многоклеточное сообщество, населяющее пустыни Флатландии. Пустыня представляет собой квадратную решетку, каждая ячейка которой вмещает одну клетку Жизни. Мерой течения времени служит смена поколений Жизни, приносящая в колонию клеток смерть и рождение.
Чтобы проследить за историей развития колонии, разместим в пустыне клетки Жизни в их начальном положении. Смена поколений будет происходить по следующим правилам.
1. Соседями клетки считаются все клетки, находящиеся в восьми ячейках, расположенных рядом с данной по горизонтали, вертикали или диагонали.
2. Если у некоторой клетки меньше двух соседей, она погибает от одиночества. Если клетка имеет больше трех соседей, она погибает от тесноты.
3. Если рядом с пустой ячейкой окажется ровно три соседние клетки Жизни, то в этой ячейке рождается новая клетка.
4. Гибель и рождение происходят в момент смены поколений. Таким образом, гибнущая клетка может способствовать рождению новой, но рождающаяся клетка не может воскресить гибнущую, и гибель одной клетки, уменьшив локальную плотность населения, не может предотвратить гибель другой.
На рис. 2.1 показана история еще одной колонии клеток Жизни.
Тема. Напишите программу, моделирующую колонию Жизни. Исходными данными служит начальное расположение клеток, а в качестве результата нужно получить вид сверху всех поколений колонии. Для вывода истории можно воспользоваться обычным устройством построчной печати (АЦПУ), но такой способ дает весьма неприглядные изображения. Если в вашем распоряжении имеется графопостроитель или графический терминал, воспользуйтесь их возможностями для получения более изящной картинки.
Рекомендации исполнителю. Хотя этого и не видно из примеров, некоторые колонии разрастаются невероятным образом при весьма скромных начальных размерах. Есть другие колонии, которые медленно перемещаются по пустыне, переходя на все новые и новые территории. Ваша программа должна обрабатывать большие колонии без чрезмерной траты памяти или времени. Многократный просмотр большого массива для построения следующих поколений — это банальный подход; здесь программистская задача состоит в выборе более экономичных структур данных и алгоритмов. Вам, возможно, захочется испытать какой-либо метод, отслеживающий только занятые квадраты. Растущая или движущаяся колония может выйти из поля зрения, если его положение и границы зафиксированы, поэтому, вероятно, понадобится еще и метод вывода, перемещающий нашу точку зрения вслед за изменениями колонии[6].
6
Один из способов сокращения памяти, требуемой для запоминания позиций, состоит в том, чтобы хранить позицию в виде массива битов, отводя для каждой клетки один бит (а не слово памяти). Как это ни странно, такой способ позволяет также получить выигрыш во времени, если воспользоваться командами поразрядных логических операций над векторами битов, имеющихся в системах команд почти всех ЭВМ и в некоторых языках программирования высокого уровня (например, в PL/I). Если обозначить через р исходную позицию, через p1, p2, …, p8 — позиции, сдвинутые на одну клетку в направлении всех соседей клетки, и через r — новую позицию, то каждый бит r будет однозначно определяться битами с тем же номером в позициях p1, p2, …, p8, т. е. будет логической функцией от них. Всякую логическую функцию можно, как известно, записать с помощью элементарных логических операций: ∧ (логическое И), ∨ (логическое ИЛИ), ⊕ (сложение по модулю два) и ¬ (логическое отрицание). Задача состоит в том, чтобы выразить r через p1, p2, …, p8 экономно, с использованием возможно меньшего числа операций. Необходимое число операций удается уменьшить до 29 (и это, вероятно, не предел), что при размере машинного слова в 48 битов (над всеми битами слова логические операции выполняются параллельно) составляет чуть более половины логической операции на обработку одной ячейки. —