Программирование игр и головоломок
Шрифт:
Н(n– 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 строк с помощью последовательностей чисел, то, таким образом, достаточно снять крайнее правое число со строки н и присоединить его справа к строке к.
Если вы хотите представить стержни вертикально, создайте, кроме того, внутреннее представление с помощью трех цепочек символов и составьте процедуру вывода на экран. Это, как кажется, проще всего. Если вы не любите цепочек символов, используйте три таблицы, но вы не выиграете в легкости.
Игра 33.
Если ваш компьютер допускает рекурсию, заставьте работать рекурсивную процедуру и понаблюдайте за движением дисков. В противном случае выполните вручную рекурсивную процедуру для маленького n (например 4), что поможет вам наглядно увидеть то, что уже доказано: два диска одинаковой четности не могут оказаться друг на друге.
Вы должны заметить, что
— диск с номером 1 перемещается один раз за любые два хода,
— он перемещается циклически, причем всегда в одном направлении, а именно
либо 0 — 1 1 — 2 2 — 0…
либо 0 — 2 2 — 1 1 — 0…
Следующий ход, перемещающий диск с номером 1, полностью определен. Недостаточно проверить это, это нужно доказать. После этого итеративное решение тривиально. Можете ли вы априори определить перемещение диска с номером 1 в зависимости от четности числа дисков?
Можете ли вы сказать что-нибудь о движении остальных дисков?
Пронумеруйте ходы. Диск с номером 1 перемещается в ходах с нечетными номерами. Проверьте, а затем докажите, что диск с номером 2 перемещается в ходах с номерами 2, 6, 10, …, т. е. в ходах, номер которых кратен двум, но не кратен четырем. Обобщите. Исходя отсюда, вы можете сказать, зная номер хода, какой диск будет перемещаться, с какого стержня он уйдет и куда придет.
Красиво, не правда ли?
Игра 34.
Существование четвертого стержня не упрощает стратегию, даже наоборот. Одна из возможностей состоит в том, чтобы перемещать р верхних дисков, используя 4 стержня, затем оставшиеся диски — используя только 3 стержня (поскольку четвертый стержень блокирован башней самых маленьких дисков). Наконец, вы восстанавливаете р маленьких дисков над остальными, используя 4 стержня. Обозначим через
f4(р) — число ходов для перемещения р дисков, используя 4 стержня;
f3(р) — число ходов для перемещения р дисков, используя 3 стержня (известное число, см. игру 31).
Тогда наша стратегия дает
f4(n) = f4(р) + f3(n– p) + f4(р).