Программирование игр и головоломок - [49]

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

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

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

— либо вы определяете его с помощью программы,

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

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

Остается способ вычисления состояния отрезка. Я принял следующее соглашение:

— поле, ход на которое невозможен, обозначается 0 (нулем);

— поле, ход на которое возможен, обозначается 1.

Так как нужно изучить отрезки, проходящие через игровое поле, то их наименьшее число 1, но может доходить и до 4. Поэтому нужно быть в состоянии выделять среди них сегмент, содержащий игровое поле и шашку +. Следовательно, придадим такой шашке значение 4. Может появиться отрезок, содержащий ·+++ со значением 13, отличающийся от сегмента с игровым полем и шашкой 0.

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

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

5. Стратегия без игры (выигрывающие стратегии)

Игра 27.

Чтобы найти рекурсивное решение в игре НАДЕВАТЬ, нужно действовать по индукции. Назовем НАДЕВАТЬ(n) решение, которое помещает n шашек на первоначально пустое игровое поле. Предположим, что мы умеем выполнять задание игры НАДЕВАТЬ для p, меньших n.

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

НАДЕВАТЬ(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 обозначает некоторую последовательность пар аб без пустых полей. Используя предыдущий метод (та же последовательность ходов плюс один), перейдите от ситуации