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

Р ( 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 строк с помощью последовательностей чисел, то, таким образом, достаточно снять крайнее правое число со строки н и присоединить его справа к строке к .

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

Игра 33.

Если ваш компьютер допускает рекурсию, заставьте работать рекурсивную процедуру и понаблюдайте за движением дисков. В противном случае выполните вручную рекурсивную процедуру для маленького n (например 4), что поможет вам наглядно увидеть то, что уже доказано: два диска одинаковой четности не могут оказаться друг на друге.