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

Арсак Жак

Простое итеративное решение имеет следующий вид: исходя ив четности n определите направление перемещения диска 1. Начните с 2ⁿ– 1 число ходов, которые осталось сделать:

s := ЕСЛИ четно (n) ТО 2 ИНАЧЕ 1 КОНЕЦ_ЕСЛИ

d := 0; k:= 2ⁿ– 1

ВЫПОЛНЯТЬ

а := d + s; ЕСЛИ a > 2 ТО а := а– 8

КОНЕЦ_ЕСЛИ

переместить диск 1 с d на а;

d : = a; k := k– 1

ЕСЛИ k = 0 TO КОНЧЕНО КОНЕЦ_ЕСЛИ

переместить единственный диск, который можно переместить, кроме диска 1

k := k– 1

ВЕРНУТЬСЯ

Все диски имеют общее свойство: нечетные диски перемещаются в том же направлении, что и диск 1, а четные диски — в другом направлении.

В вышеприведенной программе стратегия совершенна с точки зрения исполнения вручную, потому что в каждый данный момент сразу видно, какой диск нужно переместить, если это не самый маленький диск (меньший из двух остальных дисков перемещается на больший). В нашей программе вам нужно вычислить это движение. Один из наиболее простых способов состоит в том, чтобы представить игру с помощью вектора, дающего для диска i номер стержня, на котором он находится. Диск, подлежащий перемещению — это наименьший Диск, который находится не на том же стержне, что и диск 1, следовательно, номер стержня которого отличается от d. Этот самый диск перемещается со стержня, на котором он находится — с номером x — на стержень 3 - x– d.

Обозначим первое перемещение через 1. Поскольку диск 1 перемещается один раз в каждой паре ходов (точнее, перемещается через ход), то он перемещается в каждый нечетный ход. По индукции покажите, что диск p перемещается в ходы с номерами, которые делятся на 2^{р– 1}, но не делятся на 2^p (т. е. являются нечетными кратными числа 2^{p– 1}).

Номер k любого хода может быть единственным способом представлен в виде

k = (2r + 1)2^{р– 1}.

Перемещаемый на этом ходе диск есть диск с номером p, и это — его (r + 1)-е перемещение. Так как он начинает движение со стержня 0 и перемещается в направлении s_p (1, если р нечетно, и 2 в противном случае), то на этом ходе диск перемещается с rs_p– го на (r + 1)s_р– й стержень, где эти числа берутся по модулю 3.

Игра 34.

Попытаемся охарактеризовать значение р, дающее игре оптимум для данного n. Нам известно, что f₃(n– p)= 2^{n– p}– 1.

Должно выполняться

2f₄(p– 1) + 2^{n– p+1}– 1 >= 2f₄(р) + 2^{n– p}– 1,

2f₄(p + 1) + 2^{n– p-1}– 1 >= 2f₄(р) + 2^{n– p}– 1.

Удобно пользоваться первыми

разностями для функции f₄:

d(р) = f₄(p + 1) - f₄(p).

Два приведенных выше соотношения могут быть переписаны следующим образом:

d(p– 1) < 2^{n– p– 1}, d(р) >= 2^{n– p-2}.

Интересно рассматривать даже не d(р), а скорее 2^pd(р) = g(р):

g(р– 1) ~ 2^{n– 2} <= g(р).

Можно еще упростить запись, беря не g(р), а величину

h(р) = log₂(g(р)) = р + Iog₂(d(р)).

Тогда получаем

h(р– 1) < n– 1 <= h(р).

При данном n величина р — наименьшее целое, для которого h больше или равно n– 2.

Приведем здесь первые из полученных таким образом значений:

n	q	f 4	p	d	h
0	0	0		1	0
1	1	1		2	2
2		3		2	3
3	2	5	1	4	5
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