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

НАДЕВАТЬ( n ) = НАДЕВАТЬ( n − 1);

СНИМАТЬ( n − 2); поместить( n ); НАДЕВАТЬ( n − 2)

То же самое вы должны проделать и для СНИМАТЬ. Эта запись не учитывает простых частных случаев, позволяющих избежать в этом рекурсивном определении порочного круга: оно должно содержать не рекурсивные случаи, Определение должно включать n − 1 и n − 2, Вы можете либо определить игру НАДЕВАТЬ для n = 0 (ничего не делать) и n = 1 (поставить первую шашку, что всегда возможно), либо для n = 1 и n = 2. Вы сами решите, как лучше сделать.

Но еще более удивительно изучение «итеративной» стратегии для этой игры, т, е. последовательности ходов, приводящих к выигрышу. Рассмотрим игру НАДЕВАТЬ. Вы увидите, что первый ход предопределен. Используйте тот факт, что ход не должен разрушать то, что было сделано на предыдущем ходе. Вы установите, что

— вы делаете первой шашкой один ход из двух,

— остальные ходы полностью определены,

так что в игре НАДЕВАТЬ нет никакого выбора. Она полностью определена на каждом ходе: делайте единственно возможный не глупый ход…

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

— удалить сначала шашку 1 (это возможно всегда),

— удалить сначала шашку 2 (это шашка, которая следует за первой шашкой, расположенной на игровом поле).

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

Игра 28.

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

Игра 29.

Используйте индукцию или ее двоюродную сестру рекурсию. Если у вас на вашем компьютере рекурсивных возможностей нет (бедные владельцы Бейсика…), используйте ее по крайней мере в вашем черновике: хорошая рекурсивная процедура — лучшее из описаний решаемой задачи.

Решите сначала задачу с 8 буквами и 10 полями.

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

..абабХабаб

к ситуации

бббб..Хаааа

затем решите задачу для X и отправьте два последних а на их место.

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

Игра 30.

Это — типичная игра, которая анализируется методом систематического перебора всех возможных решений. Их гораздо меньше, чем может показаться, до такой степени, что в наиболее простых случаях все это выполнимо вручную. Так, для креста на рис. 23 есть (с точностью до симметрий) только три игровых хода.

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

Тогда без колебаний составляйте:

— либо рекурсивное решение. У меня есть процедура, которая решает задачу с n шашками. Какова бы ни была начальная конфигурация, для любого возможного хода вы этот ход осуществляете и решаете задачу с n − 1 шашками;

— либо итеративное решение. Оно отличается от предыдущего только необходимостью восстанавливать игру при возвращении назад. Это приводит вас к вопросу о представлении игры. Возможностей много…

Игра 31.

Поскольку рекурсивное решение тащится по всем книгам, я его вам здесь и предлагаю: это избавит вас от поисков…

Нужно перенести диски со стержня номер н (начального) на конечный стержень номер к . Номер запасного стержня x (хранилища) таков, что н , к , x есть перестановка чисел 0, 1, 2, поэтому н + к + x = 3. Номер запасного стержня равен 3 − н − к . Чтобы решить задачу, перенесем n − 1 первых дисков со стержня н на стержень x с помощью Н ( n − 1, к , 3 − к − н ).

Затем мы переносим последний диск n с н на к , что обозначается