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

Конвей, Грис (Conway R., Gries D.). An Introduction to Programming, 2nd ed. Winthrop, Cambridge, MA, 1975.

Строго говоря, это — введение в программирование (а заодно и хорошее руководство по PL/I). Но, кроме того, это прекрасный учебник по надежности и методам доказательства правильности программ. Перед тем как приступить к вашему первому этюду, имеет смысл повторить материал по построению программ, приведенный в этой книге.

Вирт (Wirth N.). Algorithms + Data Structures = Programs, Prentice-Hall, Englewood Cliffs, NJ, 1976.

Дейкстра (Dijkstra E. W.). A Discipline of Programming, Prentice-Hall, Englewood Cliffs, NJ, 1976. [Имеется перевод: Дейкстра Э. Дисциплина программирования.— М.: Мир, 1978.]

Работы Дейкстры и Вирта перекликаются друг с другом, хотя и написаны независимо. Примерный курс мог бы выглядеть так: прочитайте Конвея и Гриса; попробуйте несколько несложных задач; прочитайте Вирта; попробуйте несколько более трудных задач; прочитайте Дейкстру и снова решите уже пройденные задачи. Вирт, по существу, приводит примеры программ и методы их построения для некоторых задач среднего размера. Дейкстра обсуждает в целом только критические циклы, а также структуры данных, но приводит больше формальных доказательств. В книге Дейкстры также содержатся размышления о программировании как творческой деятельности, и эти мысли, может быть, самая ценная часть книги (но для того, чтобы их оценить, требуется некоторый опыт).

Грисуолд, Поудж, Полонски (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. Если рядом с пустой ячейкой окажется ровно три соседние клетки Жизни, то в этой ячейке рождается новая клетка.