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

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

<i>d</i> := 0; <i>k</i>:= 2^<i>n</i> − 1

ВЫПОЛНЯТЬ

  <i>а</i> := <i>d</i> + <i>s</i>; ЕСЛИ <i>a</i> &gt; 2 ТО <i>а</i> := <i>а</i> − 8

  КОНЕЦ_ЕСЛИ

  переместить диск 1 с <i>d</i> на <i>а</i>;

  <i>d</i> : = <i>a</i>; <i>k</i> := <i>k</i> − 1

  ЕСЛИ <i>k</i> = 0 TO КОНЧЕНО КОНЕЦ_ЕСЛИ

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

<i> k</i> := <i>k</i> − 1

ВЕРНУТЬСЯ

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

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

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

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

k = (2r + 1)2р-1.

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

Игра 34.

Попытаемся охарактеризовать значение р, дающее игре оптимум для данного n. Нам известно, что f3(n − p)= 2n-p − 1.

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

2f4(p − 1) + 2n-p+1 − 1 ≥ 2f4(р) + 2n-p − 1,

2f4(p + 1) + 2n-p-1 − 1 ≥ 2f4(р) + 2n-p − 1.

Удобно пользоваться первыми разностями для функции f4:

d(р) = f4(p + 1) − f4(p).

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

d(p − 1) < 2n-p-1, d(р) ≥ 2n-p-2.

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

g(р − 1) ~ 2n-2 ≤ g(р).

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

h(р) = log2(g(р)) = р + Iog2(d(р)).

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

h(р − 1) < n − 1 ≤ h(р).

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

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