Инструментовка. Для этой задачи подойдет язык APL благодаря наличию в нем операций над векторами и матрицами, однако можно использовать почти любой язык высокого уровня, если в нем предусмотрена работа с массивами. На примере этой задачи хорошо изучать, как сказывается использование языка ассемблера: насколько замедляется программирование и каков выигрыш в эффективности внутреннего цикла. Наконец, для тех, кто имеет доступ к оборудованию ЭВМ, интересным экспериментом могла бы быть микропрограммная реализация; машина при этом превращается в колонию Жизни.
Длительность исполнения. Одному исполнителю на 3 недели.
Развитие темы. Колония может все время расти, непрерывно меняя свое расположение, форму или число клеток. Однако чаще колония становится в конце концов стационарной, начиная циклически повторять один и тот же конечный набор состояний. Длина цикла называется периодом колонии. (По этому определению период мертвой и пустой колонии равен единице.) Измените вашу программу так, чтобы она выявляла стационарные колонии и сообщала о них. Можете ли вы придумать хоть какой-нибудь алгоритм, не использующий запоминания всех предыдущих поколений, который мог бы распознать любую стационарную колонию?
История колонии Жизнь зачаровывает, если ее просматривать как фильм (это одно из соображений в пользу графического терминала), но она будет еще увлекательней, если предстанет в цвете. Каждой клетке при рождении может быть приписан некоторый цвет, определяемый, возможно, ее поколением или генами, переданными ей родителями. Циклические, но при этом движущиеся колонии (а таких немало) великолепны в своем сверкающем многоцветном наряде.
Любая колония имеет преемника, но не у каждой есть предшественник. Такие изолированные колонии называются садами Эдема. Сад Эдема можно увидеть, только если поместить его на плоскость в качестве начальной конфигурации. Подумайте, как использовать вашу программу для нахождения сада Эдема.
Беркс (ред.) (Burks A. W. (Ed.)). Essays on Cellular Automata. University of Illinois Press, Urbana, IL, 1970.
Кодд (Codd E. F.). Cellular Automata. Academic Press, New York, NY, 1968.
Обе эти книги значительно серьезнее статей Гарднера в Scientific American. Вторая из названных книг познакомит вас с основами предмета, а книга Беркса представляет собой сборник разнородных статей, охватывающих всю область клеточных автоматов. После изучения этих книг читателю будет доступен практически весь математический материал.
Гарднер (Gardner Martin). Mathematical Games. Scientific American, 223, 10, pp. 120–123, October 1970, and 224, 2, pp. 112–117, February 1971. [Имеется перевод: Гарднер М. Математические досуги. — Мл Мир, 1972, с. 458.]
Мартин Гарднер описал игру Жизнь в своей колонке журнала, и это вызвало такой отклик читателей, что он вынужден был немедленно (по меркам ежемесячного журнала) посвятить ей еще одну колонку. Игра Жизнь, несомненно, принесла славу Джону Хортону Конвею, ее талантливому и продуктивному изобретателю. В более поздних статьях содержится много дополнительного материала об игре Жизнь, а также о других работах Конвея.
Уэйнрайт (ред.) (Wainwright R. Т. (Ed.)). Lifeline. 1280 Edcris Road, Yorktown Heights, NY 10598.
Lifeline — ежеквартальный журнал, посвященный Жизни и родственным темам. Ориентированный на фанатиков этой игры, журнал содержит всевозможную информацию о Жизни, и его чтение может оказаться захватывающим занятием.
3.
Папочка, а почему море синее?
или Раскрашивание карты методом исчерпывающего поиска
Чтобы на географической карте было удобно различать регионы, ее раскрашивают по следующему правилу: два региона должны быть окрашены в разные цвета, если их границы имеют более чем конечное число общих точек. (Обычно составители карт не страдают топологическими патологиями и не ищут вырожденных примеров, противоречащих здравому смыслу.) С другой стороны, картографам предстоит оплачивать типографские счета, поэтому, чем меньше цветов будет использовано, тем лучше. В частности, картографы, расписывающие карту как попало, распишутся лишь в своем легкомыслии: им придется использовать больше красок, чем это необходимо. Свои действия нужно планировать заранее. Итак, задача о раскрашивании карты сводится, в сущности, к определению минимального числа красок.