Игры с Чипом

— А как он это делает? Ведь алгоритм прогноза надо было написать заранее?

— Что-то, конечно, надо было написать заранее, в этом и состоит искусство программиста, но можно сделать так, чтобы программа сама себя исправляла.

— Ладно, хватит, Чип, я устал от разговоров. Давай все-таки поиграем.

— Хорошо, давай сыграем в машинную игру под названием «Жизнь». Условия игры такие. Колония бактерий живет на бескрайних просторах Фатландии. Предположим, что эта страна разбита на клетки, как листок из тетради. В каждой клетке только одна бактерия. Соседями одной клетки считаются все клетки, расположенные рядом по горизонтали, вертикали и диагонали. Мерой времени у нас служит смена поколений бактерий, и колония будет жить по таким законам:

1. Если у клетки меньше двух соседей, то бактерия в ней гибнет от скуки.

2. Если у клетки больше трех соседей, то бактерия в ней гибнет от тесноты.

3. Если у пустой клетки ровно три соседа, то в ней рождается новая жизнь.

Только не применяй эти правила поочередно к каждой клетке, бактерии рождаются и гибнут по общему сигналу.

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

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

— Чип, постой. Я не понимаю. Ведь та клетка, которая была сбоку, умерла, значит, у верхней средней клетки нет трех соседей.

— Я же сказал, они умирают и рождаются только по общему сигналу, в Фатландии жесткий порядок. Ты сначала найди все возможные изменения в своей колонии, а потом уж разом меняй.

— Понял, понял. Тогда в следующем поколении наша колония станет такой:

а потом опять

и так далее.

— Молодец! А колония

вообще никогда не меняется, но в Фатландии случаются и более невероятные приключения. Поиграй, например, с обыкновенным крестиком

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

— Чип! А давай напишем программу для «жизни»!

— Давай, только пусть это будет не простой подсчет соседей, а программа, которая ищет игровые ситуации. Например, если колония зациклится (повторит прошлое состояние), то пусть программа на это отреагирует.

Сережа подумал и написал программу. И машина выдала по этой программе вот такую серию картинок.

ОТ РЕДАКЦИИ:

Ребята! А вам такое задание: на листе бумаги в клеточку ноликами нарисуйте первую букву своего имени (такую форму будет иметь ваша колония бактерий) и продолжите историю развития этой колонии. Самую интересную историю мы напечатаем. На конверте поставьте девиз: «Жизнь».

Чип и Сережа читают ваши письма

— Чип! Посмотри, как много у нас новых друзей! — обрадовался Сережа, глядя на стол, заваленный письмами. Он взял наугад несколько конвертов: Мурманск, Одесса, Хабаровск, Ленинград, Киев... — Вот бы съездить ко всем этим ребятам в гости!

— На это тебе не хватило бы даже летних каникул, — засмеялся Чип. — Только на конкурс «Турнир »пришло 602 письма. Кстати, вот задача. Наверняка есть ребята, которые прислали нам по нескольку писем — ответы на различные конкурсы. Как нам найти их ответы в этой груде?

— Разве это задача, — сразу ответил Сережа. — надо рассортировать конверты с фамилиями авторов по алфавиту. А алгоритм быстрой сортировки мы уже знаем, помнишь историю про принца и Золушку?

— Помню, а вот какую программу ты бы написал для нашей задачи?

Сережа немного подумал и написал такую программу:

 1. Взять мешок, о котором М писем.
 2. Рассортировано 0 писем.
 3. Повторяй, пока рассортировано меньше, чем М писем.
 4. Возьми из мешка письмо.
 5. Вставь в список новое письмо.
 6. Конец.

 Подпрограмма: «Вставь в список »(новое письмо)
 1. Верхний = 0
 2. Если рассортировано 0 писем, перейди к строке 7.
 3. Нижний = длине списка.
 4. Средний = (Верхний + Нижний): 2
 5. Если фамилия > Среднего, то
  Нижний = Среднему,
  иначе
  Верхний = Среднему.
 6. Если Верхний > Нижнего + 1, переходи к 4-й строке.
 7. Вставить фамилию после Верхнего.
 8. Длина списка увеличилась на единицу.
 9. Возврат.

— Все правильно, — сказал Чип, проверив программу, — только ты ведь не знаешь, сколько в мешке писем. Поэтому лучше будет, если ты напишешь третью строчку программы так:

 3. Повторяй пока в мешке есть письма:

И еще хорошо бы вставить в блок между четвертой и пятой строчками строку: «Прочитать письмо ». Кстати, именно таким способом я и воспользовался, когда разбирал нашу почту.

Очень много откликов пришло на задание найти алгоритм Евклида. Правильные ответы прислали: Сергей АЛЕКСЕЕНКО из Хабаровска; Дима АПУХТИН, Челябинск; Люда БРЫНЬ, г Мена; Лена ГЕРАСИМОВА, Одесса; Саша ЗАВОРИН, п. Победа; Олеся КОСТЕНКО, Севастополь; Оля МАЗЕПА, Волжский; Лена МАЙОРОВА, Килок; Саша МАРТЫНЕНКО, Киев; Лена МОСТОЛЬСКАЯ, Москва; Наташа МУСИЕНКО, Похвистнев; Света НЕРЫДАЕВА, Ярославль; Туля ПУЗАТОВА, д. Б. Когульбаева; Таня РАМЕНСКАЯ, с. Рогачево; Аня САМАРОВА. Москва; Алена ТАРАСОВА, Ижевск; Оксана ТЮНИКОВА, Омск; Оля УСАЧЕВА, Донецк; Нина ШЕВЧЕНКО, Иркутск; Юра ЮРЬЕВ, Москва.

Гораздо сложнее оказалось помочь электронному мальчику с пальчик выйти из болота. С этой задачей из 90 претендентов лучше всех справились Алеша АЛЕКСЕЕВ, Уфа; Витя РЫЖАКОВ, Томск и Дима СОСУЛЯКИН, Новокузнецк. Программы которые они предложили, очень похожи и выглядят примерно так.

 1. Возьми три веревки, привяжи к колышку.
 2. Трем братьям отойти в разные стороны.
 3. Выбрать верхнего.
 4. Всем переместиться к выбранному брату и забить там колышек.