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