Ю.А.Соколинский
Введение
Популярная игра "Жизнь" является, с одной стороны, увлекательным развлечением, а с другой — моделью биологической эволюции. Для учащихся классов с углубленным изучением информатики предлагается проект: разработка программы игры "Жизнь" и на этой основе знакомство с указанной игрой. Составление такой программы вполне по силам достаточно подготовленным учащимся. В основном требуется умение работать с циклами, массивами строк и символами. Отметим, что в тех случаях, когда требуется формализованная запись алгоритма, используется нотация, близкая к школьному алгоритмическому языку.
1. Игра "Жизнь" — развлечение и средство моделирования биологической эволюции
Игру "Жизнь" придумал в конце 60-х годов американский математик Конуэй (Conway), и она сразу же оказалась весьма популярной, поскольку позволяет выполнять интересные исследования и получать удивительные, неожиданные результаты. Для этой игры не требуется партнер — в нее можно играть и одному. Возникающие в процессе игры ситуации очень похожи на реальные процессы, происходящие при зарождении, развитии и гибели колоний (популяций) живых организмов. По этой причине "Жизнь" можно отнести к категории моделирующих игр, которые в той или иной степени имитируют процессы, происходящие в реальной жизни.
Для игры "Жизнь", если не пользоваться компьютером, понадобятся большая (строго говоря, бесконечная) доска, разбитая на клетки, и много фишек двух цветов. Основная идея игры состоит в том, чтобы, начав с какого-нибудь простого расположения фишек (организмов, особей), расставленных по различным клеткам доски, проследить за эволюцией исходной позиции под действием "генетических законов" Конуэя, которые управляют рождением, гибелью и выживанием фишек. Конуэй тщательно подбирал свои правила и долго проверял их на практике, добиваясь, чтобы они удовлетворяли ряду условий, главные из которых:
1. Не должно быть ни одной исходной конфигурации, для которой существовало бы простое доказательство возможности неограниченного роста популяции.
2. Должны существовать простые начальные конфигурации, которые в течение значительного промежутка растут, претерпевают разнообразные изменения и заканчивают свою эволюцию одним из трех способов:
• полностью исчезают либо из-за
перенаселенности, либо, наоборот, из-за
разреженности жизненного пространства, т.е.
популяция вырождается;
• переходят в устойчивую конфигурацию и перестают изменяться вообще — эволюция вышла на стационарный режим;
• выходят на колебательный режим, при котором совершают некий бесконечный цикл превращений с определенным периодом.
Короче говоря, правила игры должны быть такими, чтобы поведение популяции было интересным, а главное, непредсказуемым.
Прежде чем сформулировать законы жизни популяции, обратим внимание на то, что каждую клетку бесконечной доски окружают восемь соседних клеток: четыре имеют с ней общие стороны, а четыре другие — общие вершины.
Теперь приведем указанные законы (правила игры). Они довольно просты.
1. Правило выживания. Каждая фишка, у которой имеются две или три соседних, выживает и переходит в следующее поколение.
2. Правило рождения. Если число фишек, с которыми граничит какая-либо пустая клетка, равно трем, то на ней происходит рождение нового организма, т.е. следующим ходом на нее ставится одна фишка.
3. Правило гибели. Каждая фишка, у которой оказывается более трех соседних, погибает от перенаселения. Каждая фишка, вокруг которой свободны все клетки или занята только одна, погибает от одиночества.
Гибель и рождение всех организмов происходит одновременно. Выжившие и вновь рожденные организмы образуют одно поколение, или ход (шаг), эволюции начальной конфигурации.
При игре "вручную" (без использования компьютера) полезно использовать следующие рекомендации:
1) начать с конфигурации из черных
фишек;
2) положить на каждую обреченную фишку по одной
черной фишке;
3) найти все свободные клетки, на которых должен
произойти акт рождения, и поставить на них белую
фишку;
4) снять погибшие (столбики из двух фишек), а
новорожденные белые заменить черными фишками.
Пора привести примеры.
ПРИМЕР 1
|
||||
Рис. 1а. Мигалка
Рис. 1б
Рис. 1 в
Начальная конфигурация состоит из трех фишек, расположенных подряд, горизонтально, см. рис. 1а. Ясно, что крайние фишки погибают, так как у них только один сосед. Зато в свободных клетках, находящихся выше и ниже средней фишки, происходит рождение новых фишек, поэтому следующее поколение состоит из трех фишек, расположенных подряд, но уже вертикально. Начальная конфигурация повернулась на 90°, см. рис. 16. По аналогичным причинам следующее, второе, поколение опять повернется на 90° и совпадет с исходным, см. рис. 1 в. Мы получили пульсирующий, периодический режим эволюции с периодом, составляющим два поколения. Данная начальная конфигурация имеет название "мигалка". (Среди любителей игры "Жизнь" принято давать характерным конфигурациям не слишком научные, но зато выразительные названия.)
А если взять начальную конфигурацию из трех вертикальных фишек, как на рис. 1б? Ясно, что она ведет себя аналогичным образом, и ее мы также будем называть "мигалкой".
ПРИМЕР 2
В начальной конфигурации, изображенной на рис. 2а, выживает лишь верхняя фишка, а рождение происходит в клетке, расположенной ниже, — она окружена тремя фишками. Следующее поколение (см. рис. 2б) состоит из двух фишек, из которых одна находится выше другой. Каждая из них имеет лишь одного соседа и, следовательно, погибает. Это пример вырождения популяции.
Рис. 2а Вырождение популяции
Рис. 2б. Вырождение популяции
ПРИМЕР 3
На рис. 3а изображена начальная конфигурация, состоящая из семи горизонтальных фишек, а на рис. 3б — ее 14-е поколение. Оно имеет название "улей", поскольку состоит из четырех "пасек". Попробуйте самостоятельно получить пропущенные 13 поколений, а также 14-е и 15-е. Если вы не запутаетесь, то убедитесь, что 15-е поколение ничем не отличается от предыдущего и является таким же "ульем". Значит, в данном случае эволюция на 14-м ходу вышла на стационарный режим. Сам "улей" и образующие его "пасеки" — это примеры устойчивых, самовоспроизводящихся конфигураций.
Рис. 3а. "Пасека" (пример стационарного режима)
Рис. 3б. "Пасека" (пример стационарного режима)
Последний пример говорит о том, что, как правило, играть в "Жизнь" "вручную" — это занятие, требующее времени и внимания. Ясно, что для получения удовольствия от игры и возможности изучать сложные ситуации требуется компьютер. И автор игры, Конуэй, и его многочисленные последователи разработали целый ряд вариантов программ игры "Жизнь", с помощью которых было получено множество интересных результатов. Давайте и мы прежде всего разработаем свою версию этой программы. Этой задаче посвящены следующие разделы.
2. Организация программы игры "Жизнь"
Прежде всего остановимся на вопросах сценария программы, структуры основных данных, этапах разработки программы.
Ясно, что реализация концепции бесконечной доски (другими словами, бесконечного жизненного пространства) весьма затруднительна. Более того, от нее следует отказаться не только по техническим причинам, но и по соображениям принципиального характера. Пространство, которое занимает биологическая популяция, как правило, ограничено, и его нехватка — это одна из важнейших причин, препятствующих развитию популяции.
Отметим, что если фишки находятся на краю доски, то нельзя гарантировать корректность процесса эволюции. Приведем соответствующий пример. Возьмем в качестве начальной конфигурации три горизонтальные фишки ("мигалку"), но расположим их на верхнем краю доски, см. рис. 4а. На следующем шаге останется средняя фишка, а под ней окажется новорожденная, см. рис. 46. Как и в примере 2, обе фишки погибают, т.е. получилось вырождение популяц, а вовсе не колебательный режим.
Рис. 4а. "Мигалка" на краю доски
Рис. 4б. "Мигалка" на краю доски
Поэтому при формировании начальной конфигурации запретим ставить фишки на край доски. Каждую новую конфигурацию будем располагать по центру доски. Если же это не поможет избежать появления фишек на граничных строках и/или столбцах доски, то, значит, достигнуты предельные размеры жизненного пространства — процесс эволюции завершен.
Доску конечных размеров можно моделировать либо двухмерным символьным массивом, либо одномерным массивом строк. Последний подход оказывается более удобным, и именно его мы будем придерживаться. Каковы размеры этого массива, т.е. длина строк и их количество? Будем исходить из следующего соображения: когда мы просматриваем эволюцию популяции, то каждое поколение должно целиком умещаться на экране монитора.
Изображением фишки ( "организма" ) будет служить звездочка, т.е. символ "*". Конечно, можно выбрать любой другой символ, который кажется подходящим.
Видимо, представленные выше рисунки свидетельствуют, что нет необходимости рисовать сетку, разбивающую доску на клетки. Вместо этого пустые клетки будем помечать точкой, что повышает наглядность изображения доски с фишками (т.е. очередного поколения).
Запоминать образы поколений будем в текстовом файле. При этом первые и последние "свободные" строки(они содержат только точки) в файл не выводим. Поколения в файле отделяются друг от друга строкой, которая содержит слово "Поколение" и его порядковый номер. Номер начального поколения — нулевой. Естественно дать указанному файлу имя LIFE (без расширения).
Работу программы следует прекратить в следующих случаях:
- Популяция выродилась, т.е. очередное поколение оказалось пустым.
- Достигнуты предельные размеры (ширина или высота) жизненного пространства.
- Обнаружена периодичность эволюции, т.е. очередное поколение совпало с одним из предшествующих. При этом если период оказался равным единице, то популяция вышла на стационарный режим: все поколения, начиная с некоторого, совпадают.
Перед прекращением работы программы желательно вывести на экран соответствующее сообщение. Просмотр файла можно выполнить после завершения программы с помощью любого текстового редактора. Например, подойдет редактор Edit входящий в состав DOS б.х, или редактор файловой системы Norton, который вызывается клавишей <F4>.
Разработку программы выполним в два этапа, т.е. составим две версии: 1 и 2. Отличаться они будут лишь одной процедурой: генератором начального поколения (начальной конфигурации) и параметрами экрана (об этом см. ниже).
На первом этапе генератор будет выполнен предельно просто. После инициализации массива строк нового поколения установка фишек (организмов) производится с помощью операторов присваивания. Каждой фишке соответствует свой оператор. Конечно, такой вариант генератора начального поколения является лишь отладочным. Он позволит проверить работоспособность всех компонент программы и получить первые впечатления о самой игре "Жизнь".
На втором этапе мы разработаем усовершенствованный, наглядный генератор. Он позволит вывести на экране доску и расставлять на ней фишки с помощью соответствующих клавиш.
Теперь обсудим вопрос о структуре основных данных программы. Начнем с размеров доски, а точнее, с параметров массива строк, который ее моделирует. Обозначим через NSscr, NCscr число строк и столбцов (колонок) экрана. Конечно, длина строки должна быть максимально возможной, т.е. равной NCscr. Введем тип строки, на языке Паскаль он записывается как
type tStr = string[NCscr]
и аналогично на других алгоритмических языках.
Количество строк массива обозначим через NSmax. Как мы условились, поколение должно целиком поместиться на экране. Кроме того, на экране должна находиться разделительная строка, а также служебные строки редактора, который используется для просмотра (они содержат меню и подсказки). Пусть Nhelp — количество служебных строк. Можно принять Nhelp=3. Следовательно,
NSmax = NSscr - 1 - Nhelp
Создаем тип поколение, который на Паскале имеет вид:
type tGen = array[1..NSmax] of tStr
Основными переменными программы будут Geni и Gen2 — старое и новое поколения, они имеют тип tGen. Кроме того, используются следующие глобальные переменные:
Count — счетчик поколений;
CountP — номер поколения, начиная с которого эволюция носит периодический характер;
SO — строка, состоящая из точек ("свободная" строка);
Fout — логический текстовый файл, в котором хранятся образы поколений.
В Паскале эта переменная объявляется как Fout: text, в Си — как FILE *Fout.B Бейсике роль такой переменной играет порядковый номер файла, который указывается при его открытии.
Выше мы использовали параметры текстового экрана NSscr, NCscr, но не указали их значений. Восполним этот пробел. Обычные значения указанных параметров составляют: NSscr = 25, NCscr = 80. Это означает, что по умолчанию текстовый экран состоит из 25 строк и 80 колонок. Чтобы изменить эти характеристики, надо предпринять специальные усилия. Спрашивается, а зачем их изменять? Попробуйте с помощью какого-либо текстового редактора изобразить квадрат из символов типа звездочек, точек и т.п. На экране этот квадрат будет выглядеть как вытянутый по вертикали прямоугольник. Объясняется такое явление тем, что высота области символа вдвое больше ширины. Для нас этот эффект нежелателен, поскольку он затрудняет зрительное восприятие конфигураций, особенно сложных, см., например, рис. 10 .
Рис. 10. "Вертушка"
Как сделать размеры символа одинаковыми? Надо либо удвоить число строк экрана, либо уменьшить вдвое число его колонок. Первый способ удобен, когда мы пользуемся текстовым редактором для просмотра файла поколений. Обычно такие редакторы имеют средства переключения в режим " 50 строк": для редактора Edit надо при его вызове указать опцию / Н, а для редактора Norton Commander, вызываемого клавишей <F4>, можно воспользоваться меню команд или нажать клаиши <ALT>+<F9>.
При разработке программы, в которой изображения выводятся на текстовый экран, удобнее второй способ: перейти в режим "40 колонок". Мы воспользуемся им на втором этапе, чтобы обеспечить наглядность генератора начального поколения. Как перейти в режим "40 колонок" ? В Паскале для этого надо выполнить команду TextMode (С040) , в Си — textmode (C40) , в Бейсике (версия QBasic) — SCREEN 1.
Итак, на первом этапе (программа 1) параметры экрана составляют NSsc г = 25, NCscr = 8 0, а на втором (программа 2) число строк не меняется, а число колонок уменьшается вдвое: NCsсг = 40. Обратите внимание: после выхода из программы 2 восстанавливается текстовый режим 80 х 25, поэтому и здесь редактор, с помощью которого просматривается файл поколений, надо перевести в режим "50 строк". Однако длина строки, равная 40, разумеется, не изменится и на экране поколения будут занимать половину его ширины.
3. Вспомогательные функции
Разделим процедуры и функции на два класса: основные и вспомогательные. Основные процедуры и функции — это те, которые вызываются из основного алгоритма, остальные — вспомогательные. Как мы увидим ниже, основными являются только процедуры, а вспомогательными — функции. С них и начнем.
3.1. Функция Near(i,j,Gen) выдает число соседних фишек. Входы функции:
— индексы клетки i, j , для которой
находится число соседних фишек, т.е. i — номер
строки, j — номер столбца, в которых находится
заданная клетка;
— текущее поколение Gen типа tGen (в дальнейшем мы не будем оговаривать тип
поколения).
Алгоритм заключается в следующем.
Вводится счетчик п, вначале равный нулю. Просматривается по очереди каждая соседняя клетка, и если она содержит фишку, то наращивается значение счетчика. Его последнее значение и выдает функция Near. Запишем этот алгоритм подробнее и более формально:
n:=0
нц для ii от i-1 до i+1
нц для jj от j-1 до j+1
если
(ii>0) и (ii<-NSmax)
и (jj>0)
и (jj<=NCscr) и ((ii<>i)
или (jj<>j)) и
(Gen[ii] [jj]='*')
то n:=n+l
кон если
кц
кц
Near :==n
3.2. Функция EmptyLine (i, Gen) логического типа выдает значение истина, если i-я строка текущего поколения "свободная", т.е. не содержит фишек, а иначе ложь. Входные переменные: номер строки i и текущее поколение Gen.
Алгоритм достаточно прост.
Полагаем EmptyLine: =истина. Затем в цикле просматриваем заданную строку от начала до конца, т.е. от 1 до NCscr. Если очередная позиция j-и строки содержит звездочку (Gen [ i ] [ j ]='*'), то полагаем EmptyLine : = ложь и выходим из функции.
3.3. Функция EmptyCol (j, Gen) логического типа выдает значение истина, если j-я колонка текущего поколения "свободная", т.е. не содержит фишек, а иначе ложь. Входные переменные: номер колонки j и текущее поколение
Алгоритм аналогичен предыдущему. Полагаем EmptyLine : =истина. Затем в цикле просматриваем заданную колонку от начала до конца, т.е. от 1 до NSmax. Если очередная позиция i-й колонки содержит звездочку (Gen [ i ] [ j ]='*'), то полагаем EmptyLine : = ложь и выходим из функции.
4. Основные процедуры
Здесь мы рассмотрим основные процедуры, за исключением генератора начального поколения.
4.1. Процедура NewGen (Gen I, Gen2) осуществляет переход к новому поколению. Ее вход — старое поколение Geni, выход — новое поколение Gen2.
Алгоритм реализует "законы жизни популяции" Конуэя. Сначала происходит инициализация нового поколения:
нц для i от 1 до NSmax Gen2[i]:=SO кц
Как мы помним, SO — строка, состоящая из точек ("свободная" строка).
Затем отслеживаются фишки, которые выживают и переходят в новое поколение. Это те фишки, для которых число соседних фишек составляет два или три. Формальная запись этого правила:
нц для i от 1 до NSma
нц для j от 1 до NCscr
если
(Genl[i][j]='*') и
((Near(i, j, Geni) =2) или
(Near(i, j, Geni) =3))
то Gen2[i]
[j] := '*'
кц
кц
4.2. Процедура
Transform(Gen2,Geni,I1,H,SignEnd)
преобразует новое поколение Gen 2 в старое Geni.
Вход процедуры — новое поколение Gen2.
Выходные параметры:
Geni — старое
поколение;
II — номер первой строки Geni, содержащей фишки;
Н — "высота" Geni, т.е. число строк, начиная с II
и кончая 12, где 12 — номер первой снизу строки Geni,
содержащей фишки.
Выходной параметр SignEnd — признак конца. Он имеет значения:
1 — при
вырождении нового поколения Gen2,
2 — при достижении предельной высоты,
3 — при достижении предельной ширины. В остальных
случаях его значение — ноль. Идея преобразования
заключается в том, что новая конфигурация (если
она не вырождена) переносится в Geni таким образом,
чтобы она расположилась по центру. Если
конфигурация не достигла своих предельных
размеров, то это обеспечит "свободу"
граничных строк и столбцов, т.е. они не будут
содержать фишек.
Изложим сущность преобразования более подробно. Находятся номера "окаймляющих" строк Imin, Imax и столбцов Jmin, Jmax. Это означает, что Imin — номер первой сверху строки Gen2, содержащей фишки, а Imax — номер первой снизу такой же строки. Аналогично, Jmin, Jmax — номера первой слева и справа колонки Gen2, содержащей фишки. Если поиск Imin оказался безрезультатным, то это означает вырожденность Gen2. Иначе прямоугольник, окаймленный указанными строками и столбцами, переносится в Geni так, чтобы он расположился по центру, насколько это возможно. Если окажется, что высота этого прямоугольника Н > NSmax—1, то это означает существование фишек в граничных строках (в первой и/или последней). Аналогично, если ширина прямоугольника больше либо равна NCscr—1, то существуют фишки в граничных столбцах. В первом случае признак конца SignEnd получает значение 2, во втором — 3. Теперь приведем формальное описание алгоритма.
SignEnd:=0; Imin:=l
нц пока (EmptyLine(Imin,Gen2)) и (Imin<NSmax)
Imin:=Imin+l
кц
если (Imin=NSmax) и (EmptyLine(Imin,Gen2))
то
SignEnd:=1 |Вырождение популяции
выход из процедуры
кон если
Imax:=NSmax
нц пока EmptyLine(Imax,Gen2)
Imax:=Imax-l
кц
Jmin:=l
нц пока EmptyCol(Jmin,Gen2)
Jmin:=Jmin+l
кц
Jmax:=NCscr;
нц пока EmptyCol(Jmax,Gen2)
Jmax:=Jmax-1
кц
H:=Imax-Imin+l;
W:=Jmax-Jmin+1
если H>=NSmax-1 то SignEnd: =2 кон если
если
W>=NCscr-l то SignEnd:=3 кон если
нц для i от 1 до NSmax Gen1[i]:=SO кц
Чистка Gen1
| I1, J1 — номер строки и столбца
левого j верхнего угла центрированной
конфигурации
I1:= (NSmax-H) div 2+1
Jl:= (NCscr-W) div 2+1
| Копируем Gen2 в Gen1, центрируя
новую конфигурацию
нц для i от Imin до Imax
нц для j от Jmin до
Jmax
| Gen1 [Il+i-Imin][Jl+j-Jmin]:=Gen2[i][j]
кц
кц
4.3. Процедура Out (Gen, II, H, Count) выводит очередное поколение Gen в файл поколений Fout. Как уже говорилось, первые и последние "свободные" строки в файл не выводятся. Входные параметры процедуры:
Gen — очередное
поколение;
II — номер первой строки
Gen, содержащей фишки;
Н — число строк Gen, содержащих фишки;
Count — номер
поколения.
Алгоритм работы процедуры довольно прост:
вывод нс (Fout,'Поколение', Count)
нц для i от I1 до I1+H-1
вывод не (Fout,
Gen[i])
кц
4.4. Процедура Period (Gen, II, Н, CountP) ищет в файле поколений "близнеца" очередного поколения
Входные параметры процедуры:
Gen — очередное
поколение;
I1 — номер первой строки Gen, содержащей
фишки;
Н — число строк Gen, содержащих фишки.
Выходной параметр:
CountP
— номер поколения-"близнеца".
Если "близнец" не нашелся, то
CountP = -1
Нахождение "близнеца" означает, что, начиная с поколения CountP, режим эволюции — периодический.
Алгоритм поиска "близнеца":
Закрываем файл поколений Fout и открываем его на чтение. Читаем первую строку файла, содержащую заголовок начального поколения. Полагаем:
Count=0; CountP= -1.
( Здесь Count не глобальная, а локальная переменная данной процедуры.)
Начинаем цикл анализа поколений:
Полагаем счетчик строк поколения i=0.
Выполняем цикл чтения очередного поколения. Он заканчивается, когда прочитанная строка является заголовком следующего поколения либо последней строкой файла. Поколение записывается в массив GenO, число записанных строк хранит счетчик i.
Если i=H, то проверяем совпадение массивов GenO и Gen. В случае совпадения полагаем CountP=Count.
Закрываем файл Fout и открываем его на дозапись (append).
Выходим из процедуры.
Если i<>H или GenO>Gen, то наращиваем счетчик поколений Count. Конец цикла анализа поколений, когда прочитана последняя строка файла. Закрываем файл Fout и открываем его на дозапись.
Конец алгоритма.
Запишем его подробнее и более формально:
закрыть файл(Fout)
открыть файл(Fout, 'г')
| файл открывается на чтение
ввод нс (Fout); Count:=0;
CountP-:=-l
нц
i:=0
нц
ввод нс (Fout. S)
|S хранит очередную строку
если S[1]='П'
|
заголовок поколения имеет вид "Поколение
<номер>"
то NewGen:=истина
иначе
NewGen:=ложь
i:=i+l
Gen0[i]:=S
кон если
кц при (конец Файла (Fout)) или (NewGen)
если i=H
то
j:=1
нц пока (j<i) и
(Gen0[j]=Gen[I]+j-1])
j:=j+1
кц
если (j=i) и (Gen0[j]=Gen[I]+j-1])
то
закрыть Файл(Fout)
открыть файл(Fout, 'а')
| файл открывается на дозапись
CountP:=Count
выход из процедуры
кон если
кон если
Count:=Count+l
кц при конец Файла(Fout)
закрыть файл(Fout)
открыть файл(Fout, 'а')
Здесь функция конец файла (F) выдает значение истина, когда прочитана последняя строка файла F, а иначе ложь
5. Этап 1. Генератор начальной конфигурации и основной алгоритм
Все приведенные выше процедуры и функции будут использоваться как в первом, так и во втором варианте программы. Сейчас мы составим вариант генератора начальной конфигурации, который предназначен для первого этапа, т.е. для программы 1. Как уже указывалось, он весьма прост и, можно даже сказать, примитивен. Естественно, при этом пользователь имеет минимум удобств, а главное, он должен ориентироваться в данной программе, так что этот вариант надо рассматривать как отладочный.
Процедура StartGenI (Gen) создает первоначальное новое поколение (начальную конфигурацию) Gen. Конфигурация фишек, рассматриваемая как единое целое, может располагаться внутри массива произвольно. Ведь процедура Transform, которая будет вызвана вслед за StartGen1, преобразуя первоначальное новое поколение в старое, расположит его по центру массива.
Алгоритм процедуры заключается в том, что сначала массив Gen чистится:
нц для i от 1 до NSmax Gen2[i]:=S0 кц,
— а затем расстановка фишек производится соответствующими операторами присваивания, количество которых определяется числом фишек. Разумеется, предыдущие операторы присваивания надо стереть или превратить в комментарий. Как мы помним, фишки не желательно ставить на край доски, однако в процедуре это не контролируется.
Например, возьмем в качестве начальной конфигурации "мигалку", т.е. три фишки, расположенные подряд горизонтально.
Надо написать три оператора присваивания, которые могут иметь вид:
Gen[2][2]:='*';
Gen[2][3]:='*';
Gen[2][4]:='*';
С таким же успехом их можно записать и так:
Gen[5][10]:='*';
Gen[5][11]:='*';
Gen[5][12]:='*';
и т.д.
Теперь мы в состоянии сформулировать основной алгоритм программы 1.
• Присваиваем значения параметрам экрана:
NSscr:=25; NCscr:=40;
Nhelp:=3; NSmax:=NSscr-(NHelp+1)
• Присваиваем начальное значение счетчику поколений Count<>:=0
• Формируем "чистую" строку S0:
S0 := ' ';
нц для i от 1 до NCscr
S0:=S0+ '.'
кц.
• Связываем логический файл поколений Fout с физическим файлом Life и открываем файл Fout на запись.
• Вызываем генератор начальной конфигурации StartGenI (Gen2)
• Начало основного цикла
•
Вызываем процедуру преобразования новой
конфигурации Gen2 в старую Gen1:
Transform(Gen2,Gen1,I1,Н,SignEnd).
• Напомним, что
I1 —
номер первой строки Gen, содержащей фишки,
Н — число строк Gen, содержащих фишки,
SignEnd — признак
конца.
| если поколение не начальное и не
вырожденное
если (Count>0) и (SignEnd<>1)
то
Period(Gen1,I1,Н,CountP)
| вызов процедуры
поиска "двойника"
| если нашелся "двойник" (режим
стал
| периодическим), то признаку конца
| даем значение 4
если CountP>=0 то SignEnd:=4 кон если
кон если
• Если очередное поколение не вырожденное (SignEnd <>1), то вызываем процедуру записи очередного поколения в файл поколений Out(Gen1,I1,Н,Count) и наращиваем счетчик поколений Count.
• Если достигнут конец процесса эволюции (SignEnd > 0), то выводим на экран соответствующее сообщение и приостанавливаем работу программы до нажатия любой клавиши (либо клавиши <Enter>) , а иначе вызываем процедуру создания нового поколения NewGen(Gen1,Gen2).
• Конец основного цикла при SignEnd>0.
• Закрываем файл поколений Fout.
Конец основного алгоритма программы 1.
Составив программу 1, можно проверить работоспособность всех ее компонент и убедиться, что для простых начальных конфигураций (можно использовать примеры раздела 1 и, в частности, пример 3) программа действительно порождает новые поколения в соответствии с законами Конуэя.
6. Этап 2. Наглядный генератор начальной конфигурации и уточнение основного алгоритма
Переходим ко второму, основному, этапу. Здесь нам надо разработать усовершенствованный, наглядный генератор, позволяющий вывести на экран доску и расставлять на ней фишки с помощью соответствующих клавиш, а также уточнить основной алгоритм.
Начнем с наглядного генератора
начальной конфигурагщи.
Естественно использовать привычные управляющие клавиши: стрелки для сдвига курсора по горизонтали и вертикали, клавиши <END> и <HOME> для установки курсора в конец и начало строки, клавиши <PAGE DOWN> и <PAGE UP> для установки курсора в конец и начало массива. Устанавливать фишку будем нажатием клавиши <ENTER>. Если она уже установлена, то нажатие клавиши <Enter> наоборот, снимает фишку. Для выхода из генератора используем клавишу <ESC>.
Доску расположим в верхней части экрана. Внизу останутся Nhelp+1 (т.е. 4) не использованные строки. В трех нижних строках можно разместить подсказку, например, такую:
"стрелки —
управление курсором"
"Enter - уст/снять фишку Esc - выход"
"Home,End,PgUp,PgDn - нач/кон строки/поля"
Мы знаем, как в программу ввести с клавиатуры тот или иной символ. Для этого в Паскале используется функция ReadKey, в Си — getch ( ) , в Бейсике — INKEY$. А как передать в программу сообщение о том, что нажата какая-то специальная клавиша? Прежде всего клавиши <Enter> и <Esc> не отличаются в этом отношении от обычных. Для них в таблице символов предусмотрены индексы: 13 для <Enter> и 27 для <Esc>, и, следовательно, указанные функции позволят узнать, что нажата какая-то из этих клавиш. Для остальных специальных клавиш их нажатие моделируется последовательным нажатием двух клавиш. Первой из них соответствует нулевой индекс, а так как ни один символ клавиатуры не имеет такого индекса, то нулевой индекс служит признаком нажатия какой-то специальной клавиши. Индекс второго "прочтенного" символа (так называемый скан-код) и говорит, какая специальная клавиша нажата. Приведем таблицу скан-кодов тех специальных клавиш, которые нам понадобятся:
| <End> | <Home> | <Page Up> | <Page Down> | ||||
| 72 | 80 | 77 | 75 | 79 | 71 | 81 | 73 |
Запретим ставить фишки в граничные строки и столбцы. Это гарантирует, что начальная конфигурация не будет занимать все жизненное пространство.
Нам понадобится вспомогательная процедура Star(Xc,Yc,Gen), которая устанавливает или сниает фишку. Алгоритм этой процедуры:
Устанавливаются черный (Black) цвет текста и светло-серый (LightGray) цвет фона.
Курсор устанавливается в позицию Xc,Yc. (В Паскале для этого используется команда gotoXY. в Си — gotoxy, в Бейсике — LOCATE.)
Если символ Gen[Yc] [Xc] — это звездочка, то в позицию Xc.Yc массива Gen и экрана заносится точка, и наоборот. Точнее:
еcли Gen[Yc][Xc]='*'
то
Gen[Yc][Xc]:='.'
вывод ('*')
иначе
Gen[Yc][Xc]:='*'
вывод ('*')
кон еслиКурсор снова устанавливается в позицию Xc.Yc (поскольку он сдвинулся на одну позицию вправо).
Конец алгоритма
Теперь мы можем составить наглядный генератор начальной конфигурации, т.е. процедуру StartGen2 (Gen) . Изложим алгоритм работы этого генератора.
Выполняем чистку экрана.
Устанавливаем светло-серый цвет фона и черный цвет текста.
Производим чистку массива Gen и первых NSmax строк экрана:
нц для i от 1 до NSmax
Gen[i]:=S0 | Чистка Gen
вывод (S0) | Чистка экрана
кцВыводим подсказку в нижние три строки.
Даем координатам курсора начальные значения: Хс=2; Yc=2 — и устанавливаем курсор в начальную позицию.
Выполняется цикл клавиатуры, который запишем в формальном стиле: '
нц
Ich:= индекс (ввод символа)
| Ich — индекс символа, введенного с клавиатуры
выбор Ich
27: | Esq
чистка экрана
выход
из процедуры
13: | Enter
Star (Xc,Yc,Gen)
|
установка/снятие фишки
0: | специальная клавиша
SC:=индекс(ввод
символа)
| SC —
скан-код специальной клавиши
выбор SC
72 | Курсор вверх
если Yc>2 то Yc:=Yc-l кон если
75 | Курсор влево
если Хс>2 то
Хс:=Хс-1 кон если
77 | Курсор вправо
nbsp; если Xc<NCscr-l то Xc:=Xc+1 кон если
80 | Курсор вниз
если Yc<NSmax-l то Yc:=Yc+l кон если
71 | Home Курсор к началу строки
Xc =2
79 | End Курсор к концу строки
Xc =NCscr-l
73 | PgUp Курсор к началу
поля
Xc =2; Yc:=2
81 | PgDn Курсор к концу поля
Xc =NCscr-l; Yc:=NSmax-l
кон выбор
Установка курсора в позицию Xc.Yc
кон выбор
кц
Конец алгоритма наглядного генератора.
Нам осталось сформулировать основной алгоритм программы 2. Но поскольку он мало отличается от своего предшественника — основного алгоритма программы 1, то мы укажем лишь, в чем заключаются эти различия. Их всего два.
1. Число колонок экрана теперь не 80, а 40, т.е. параметр NCscr-имеет значение NCscr=40.
2. В начале основного алгоритма надо поместить команду перехода в режим "40 колонок". Как уже указывалось, в Паскале она имеет вид TextMode (C040) , в Си — textmode (С40) , в Бейсике (версия QBasic) — SCREEN 1.
7. Играем в "Жизнь"
Итак, мы составили и отладили программу 2, позволяющую удобным способом формировать начальную конфигурацию и следить за ее эволюцией. Давайте воспользуемся этой программой и посмотрим, на что способна игра "Жизнь".
Сейчас мы приведем несколько задач, выполнив которые, вы познакомитесь с некоторыми достижениями в этой области и интересными конфигурациями. Сначала о терминологии: триплетами называют конфигурации из трех фишек, каждая из которых имеет хотя бы одного соседа. Тетрамино и пентамино — это аналогичные конфигурации из четырех или пяти фишек, связанных между собой "ходом ладьи".
ЗАДАЧА 1
Исследуйте эволюцию всех возможных триплетов. (В их число входят начальные конфигурации примеров 1 и 2 раздела 1.) Покажите, что эволюция триплетов, симметричных относительно вертикальной или горизонтальной оси, протекает одинаково.
ЗАДАЧА 2
Исследуйте эволюцию пяти тетрамино, изображенных на рис. 5. (Если не учитывать симметричные конфигурации, то это все возможные тетрамино.)
| б | |||||||||
| а | |||||||||
| в | г | ||||||||
| д | |||||||||
Рис. 5. Пять вариантов тетрамино
Покажите, что:
• Первая из них, имеющая название "блок", является устойчивой конфигурацией.
• Следующие три на некотором шаге (каком именно?) переходят в уже знакомую нам устойчивую конфигурацию "пасеку" (пример 3 раздела 1).
• Пятая на каком-то шаге (опять-таки, каком?) переходит в конфигурацию, изображенную на рис. 6а. Она называется "навигационные огни" и состоит из четырех "мигалок". На следующем шаге "мигалки" поворачиваются на 90°, см. рис. 66, далее они опять поворачиваются на тот же угол, т.е. восстанавливаются "навигационные огни", рис. 66. Эволюция стала периодической с периодом два.
а
б
в
Рис.6. "Навигационные огни"
ЗАДАЧА 3
Исследуйте эволюцию 12 пентамино, изображенных на рис.7.
| а | ||||||||||||||||
| б | в |
|||||||||||||||
| г | е |
|||||||||||||||
| д | ||||||||||||||||
| ж | и | |||||||||||||||
| з | ||||||||||||||||
| к | м | |||||||||||||||
| л | ||||||||||||||||
Рис. 7. 12 вариантов пентамино
Покажите, что:
• Первые четыре варианта дают "навигационные огни".
• Варианты 5—10 приводят к вырождению.
• Вариант 11 приводит к устойчивой конфигурации "каравай", изображенной на рис. 8.
• Для последнего варианта, известного как r-пентамино, на 70-м ходу достигается предельная ширина жизненного пространства.
Рис. 8. "Каравай"
ЗАДАЧА 4
Покажите, что конфигурации, показанные на рис. 9:
"бакен" (рис. 9д), "часы" (рис. 96), "жаба" (рис. 96), "палка" (рис. 9г), — являются "флип-флопами", т.е. повторяются через каждые два шага.
| а | б | |||||||||
| в | ||||||||||
| г | ||||||||||||||||
Рис. 9. "Флип-флопы"
ЗАДАЧА 5
Покажите, что внутренняя часть конфигурации "вертушка", изображенной на рис. 10, поворачивается на 90° по часовой стрелке на каждом ходу, а все блоки остаются на месте, т.е. эволюция этой конфигурации периодическая с периодом 4.
Рис. 10. "Вертушка"
ЗАДАЧА 6
Покажите, что конфигурация "восьмерка" (см. рис. 11), не только внешне напоминает эту цифру, но и повторяется циклически через каждые 8 шагов.
Рис. 11. "Восьмерка"
ЗАДАЧА 7
Исследуйте эволюцию "глайдера", см. рис. 12. Покажите, что он воспроизводится через каждые 4 хода (английское слово glider означает планер).
Рис. 12. "Глайдер"
ЗАДАЧА 8
Проверьте, что П-гептамино (рис. 13) на некотором шаге (определите его номер) превращается в "пульсар СР 48-56-72", т.е. конфигурацию, изображенную на рис. 14, который, в свою очередь, повторяется после следующих трех шагов. Другими словами, эволюция П-гептамино на некотором шаге выходит на пульсирующий режим с шагом 3.
Откуда взялись такое название и обозначение? Пульсары — это космические объекты, обладающие строго периодическими характеристиками. Их открытие в 60-х годах было настоящей научной сенсацией. В названии обыгрывается не только тема пульсаров, но и способ их обозначения. Число 48 — это количество фишек пульсара, а 56 и 72 — числа фишек следующих двух поколений (проверьте!).
Рис. 13. П-гептамино
Рис. 14. "Пульсар СР 48-56-72"
ЗАДАЧА 9
Проследите за судьбой "Чеширского кота", рис. 15. Убедитесь, что на шестом ходу от него остается только улыбка (рис. 16), которая затем пропадает, и остается лишь след лапы (блок из четырех фишек). (Напомним, что Чеширский кот — это персонаж сказки Л.Кэрролла "Алиса в стране чудес". Он обладает чудесной способностью исчезать, оставляя свою улыбку.)
Рис. 15. "Чеширский кот"
Рис. 16. "Улыбка Чеширского кота"
Мы рассказали лишь малую часть того, что удалось открыть и исследовать любителям игры "Жизнь". Еще много интересного об этой игре можно найти в прекрасных книгах М.Гарднера {1, 2], рекомендуем ознакомиться с ними.
Но самый главный совет: самим попробовать эту игру, отыскать интересные, неожиданные конфигурации, проследить за их превращениями. Без сомнения, вы получите много удовольствия, погрузившись в "Жизнь".
Литература
1. Гарднер М.
Крестики-нолики. М.: Мир, 1988.
2. Гарднер М. Математические новеллы. М.: Мир, 1974.
3. Фаронов В.В. Программирование на персональных ЭВМ в среде Турбо Паскаль. М.: изд-во МГТУ, 1991.
4. Каспер Е. Освоим QBasic играючи! М.: Горячая линия — телеком, Радио и связь, 1999.
5. Болски МИ. Язык программирования Си. М.: Радио и связь, 1988.