Жак Арсак - Программирование игр и головоломок

Когда мы оказываемся заблокированными, нужно возвращаться назад. Нетрудно скорректировать число появлений рассматриваемых цветов. Нужно переоценить уже полученные числа белых и черных шашек. Вы действуете при этом путем пересчитывания вклада данного цвета в рассматриваемую позицию.

Игра 27.

Рассмотрим игру НАДЕВАТЬ. В начале на игровом поле ничего нет. Можно играть только на поле, которое следует эа первым занятым полем, а такого поля нет. Играем на поле 1.

На следующем ходе было бы глупо снимать только что выставленную шашку. Первое занятое поле — первое. Ставим шашку на поле 2. Первое занятое поле — это снова первое поле. Было бы глупо снимать только что выставленную шашку, и поэтому нужно играть на первом поле, т. е. освобождать его. Теперь первое свободное поле — это поле 2. Было бы глупо возвращать на поле 1 только что снятую шашку. Следовательно, поставим шашку на поле 3. Никакого выбора…

Чтобы освободить игру на одно поле, очищаем поле 1.

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

Для игры с 3 полями, мы очищаем 1, эатем ставим 3, ставим снова 1, очищаем 2, а затем 1.

Если n четно, то мы начинаем с удаления шашки 2, в противном случае мы удаляем шашку 1.

Теперь вам не составит ни малейшего труда написать итеративную программу:

место := 0; игра : = пусто

ВЫПОЛНЯТЬ

ЕСЛИ поле (1) = пусто ТО поставить (1);

место := место + 1

ИНАЧЕ удалить (1);

место := место − 1

КОНЕЦ_ЕСЛИ

ЕСЛИ место = n ТО КОНЧЕНО КОНЕЦ_ЕСЛИ

искать первое занятое поле, номер которого дает число i ;

ЕСЛИ поле ( i + 1) = пусто ТО поставить ( i + 1);

место := место + 1

ИНАЧЕ удалить ( i + 1);

место := место − 1

КОНЕЦ_ЕСЛИ

ЕСЛИ место = n ТО КОНЧЕНО КОНЕЦ_ЕСЛИ

ВЕРНУТЬСЯ

Для игры СНИМАТЬ вы действуете аналогично.

В том, что касается последовательностей чисел, порожденных игрой СНИМАТЬ, начнем с рассмотрения конкретного примера. Вот игра СНИМАТЬ для n = 4.

Использованы все числа, меньшие 8, а из больших или равных 8 участвуют только 12, 13 и 15. Для обобщения действуйте по индукции.

Игра 29.

Вот решение для 8 букв и 10 полей.

..абабабаб

баабаба..б

бааб..аабб

б..баааабб

ббббаааа..

Присутствие куска X не меняет последовательности изменений.

..абабХабаб

баабабХа..б

бааб..Хаабб

б..бааХаабб

ббббааХаа..

Последний перенос пары букв аа слева от X в свободные пары справа дает

бббб..Хаааа

Теперь вы можете заняться X (если для этой комбинации вам решение уже известно) и получить

ббббY ..аааа

Таким образом, остается переместить два а с крайних полей справа на свободные поля, и все закончено. Следовательно, если вы умеете исследовать комбинацию Х с р парами букв а , б , то вы умеете исследовать и комбинацию с р + 4 парами.

Я уже предложил вам решение для четырех пар. Таким образом вы получаете решение для 8, 12,…

Главные решения — это решения для 4, 5, 6, 7 пар. Вот одно из решений для строчки из 5 пар

..абабабабаб

Искомое расположение имеет вид

бббббааааа..

Можно задаться целью удалить все буквы а (особенную трудность при перемещениях вызывает то, что их число нечетно) из первой половины (первых 5 позиций, в которых букв а в исходном положении не столько же, сколько букв б ).

..абабабабаб

баабабаба..б

бааб..абаабб

бааббаа..абб

б..ббааааабб

бббббааааа..

Предлагаю вам разыграть 6 и 7 пар. Совершенно бесполезно подключать к этому делу компьютер. А где же программирование, спросите вы? Я отвечу, что это упражнение вводит вас в рекурсивные или индуктивные рассуждения. Это оздоровляет Наши способы рассуждать…

Игра 30.

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

Игра имеет ту же конфигурацию, что и для лис и кур. Поле обозначается своим положением в цепочке. Перемещение в данном направлении реализуется добавлением некоторой константы к данному положению. Таблица из четырех элементов дает эти константы для всех четырех направлений. Свободное поле представляется точкой, занятое поле — крестиком ×.

Вы ищете первый крестик в цепочке и вы начинаете с первого возможного перемещения i = 1. Если есть возможность взятия в этом направлении, то вы регистрируете данные ×, i в цепочке или таблице (во втором случае вы симулируете кучу). Вы выполняете взятие и начинаете сначала. Если же возможности взятия в данном направлении нет, то вы переходите к следующему i . Если вы достигаете четырех, то с этим крестиком все кончено, и вы переходите к следующему. Если их больше нет, то вы возвращаетесь к последней зарегистрированной в куче паре данных ×, i , отменяете соответствующее взятие (изменение состояния игры) и продолжаете переходом к следующему i .

Вы уже проделали более трудную работу для самого длинного взятия в игре с курами и лисами.

Игра 31.

Число ходов f ( р ) для переноса р дисков получается переносом сначала p − 1 дисков со стержня d на стержень 3 − а − d за f ( р − 1) ход, затем из перемещения диска р , что требует в точности одного хода, а затем возвращения р − 1 дисков из запаса на стержень прибытия за f ( р − 1) ход, откуда получаем:

f ( р ) = 2 * f ( р − 1) + 1,

g ( p ) = f ( p ) + 1 = 2 * f ( р − 1) + 2 = 2 * ( f ( p − 1) + 1) − 2 * g ( р − 1).

По индукции g (р) = 2 pg (0).

Так как f (0) = 0, g (0) = f (0) + 1 = 1, g ( р ) = 2 p , то, наконец

f (р) = 2 p − 1.

Для игры с 50 дисками нужно 2 50− 1 ходов. Но 2 10равно 1024, или порядка 10 3. Следовательно, 2 50порядка 10 15.

В часе 3600 секунд, в сутках 3600 × 24 = 86400 секунд, за год получаем 86400 × 365 — или порядка 3 × 10 7секунд, откуда, наконец, 3 × 10 9секунд за столетие. Поэтому нужно порядка 10 15/3 × 10 9, или порядка 3 × 10 5веков для игры с 50 дисками, которая, таким образом, требует около 300000 веков…