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

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

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

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

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

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

— удалить сначала шашку 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 с н на к, что обозначается

Р(n, н, к).

Эта процедура, которая реализует, например, сообщение

n ИДЕТ С н НА к

Наконец, мы переносим n − 1 первых дисков с запасного стержня на стержень к:

Н(n −1, 3 − н − к, к).

Нужен частный случай, не являющийся рекурсивным. Если диск всего один, то можно сразу перенести его от н к к:

Н(р, н, к) = ЕСЛИ р = 1 ТО Р(1, н, к) ИНАЧЕ Н(р − 1, н, 3 − н − к)

Р(р, н, к)

Н(р − 1, 3 − н − к, к)

КОНЕЦ_ЕСЛИ

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

Число ходов игры легко выводится из этой процедуры. Обозначим через f(p) число ходов, необходимых для игры с p дисками. Из рекурсивной процедуры следует, что

f(1) = 1,

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

(Почему?) Исходя из этого, вы можете вычислить f(p) (на самом деле g(p) = f(p) + 1 имеет более простой закон построения, чем f(p). Образуйте сначала этот закон, найдите решение, а затем выведите закон для f(p)).

Чтобы доказать свойство, касающееся четности дисков, действуйте по индукции подходу вычислений. Предположите, что это свойство выполняется для Н(р − 1, …). Покажите, что от сюда следует его справедливость и для Н(р, …).

У вас не получается? Вот дополнительная помощь. Начнем с переноса р − 1 дисков на запасной стержень. Пока не передвинут (р − 1)-й диск, нп один диск не кладется непосредственно на диск с номером р, и требуемое свойство выполняется. Рассмотрим момент, когда р − 2 дисков находятся на одном стержне, диски с номерами р − 1 и р — на другом стержне, а третий стержень пуст, Вы перемещаете диск с номером р − 1. Теперь, поскольку нужно переместить первые р − 2 дисков на диск с номером р − 1, то диски будут оказываться на диске с номером р. Если мы помещаем диск с номером q на диск с номером р, то для того, чтобы образовать пирамиду дисков с номерами от q до 1 и иметь возможность переместить диск с номером q + 1, который отправится на диск с номером р − 1. Но требуемое свойство выполняется для р − 1 дисков, и поэтому четность диска q + 1 не может совпадать с четностью р − 1. Следовательно, она совпадает с четностью р. Следовательно, р и q имеют разные четности.

Потренируйтесь в доказательствах такого рода…

Игра 32.

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

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

Операция Р(р, н, к) на самом деле следующая: снять диск с вершины стержня н и поместить его на вершину стержня к.

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

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