Программирование игр и головоломок

4		9	1	4	6
5		13	1	4	7
6	3	17	3	8	9
7		25	3	8	10
8		33	4	8	11
9		41	5	8	12
10	4	49	6	16	14
11		65	6	16	15

Мы добавили в таблицу переменное q, связанное с «треугольными» числами. Для n = q(q + 1)/2 действительно убеждаемся, что

h(р) = h (р ? 1) + 2

в то время как для других n

h(p) = h (p ? 1) + 1.

Исходя из n, можно вычислить q:

q = целая_часть (( ? 1)/2).

Имеем

h(n) = n + целая_часть (( ? 1)/2).

Покажите это по индукции. Исходя отсюда, вычисляется все. Таким образом, если n дано, то р — наименьшее целое, большее или равное

(2n ? 1 ? )/2.

Игра 35.

Возьмем, например, игру с 50 дисками. Она реализуется переносом сначала 40 дисков на запасной стержень, а затем 10 последних дисков со стержня 0 на стержень 1, с использованием при этом только трех свободных стержней. Наконец, остается перенести начальные 40 самых маленьких дисков с запасного стержня на первый стержень, используя все 4 стержня.

Чтобы переместить 40 дисков с 4 стержнями, сводим задачу к перемещению 31 диска с 4 стержнями, а затем 9 с 3 стержнями…

Таким образом, дело сводится к разбиению 50 дисков на 8 сегментов:

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

Договоримся работать с тремя стержнями 0, 1, 2, так что стержень 3 остается пустым и служит запасным стержнем при любом перемещении какого-либо сегмента. Более точно, перемещение сегмента р со стержня d на стержень а осуществляется с помощью изученной выше процедуры Н, в которой запасным стержнем является стержень 3.

Сегмент 1 перемещается в каждый из двух ходов подряд (под ходом я понимаю последовательность операций, реализующих процедуру Н), всегда в одном и том же направлении.