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

Перемещение диска n со стержня d на стержень а помещает n в основание стержня а, так что при этом свойство четности для а подтверждается. Проверьте, что для стержней d и 3 - а - d оно также подтверждается. Для этого разложите Н (n, d, а) на 5 операций:

Н (n - 2, d, а) n и n - 1 на стержне d

Р (n - 1, d, 3 - а - d) n на d, n - 1 на 3 - а - d

Н (n - 2, а, 3 - а - d)

Р (n, d, а) n на а, n - 1 на 3 - а - d

Н (n - 2, 3 - a - d, d)

Р (n - 1, 3 - а - d, а) n на а, n - 1 на а

Н (n - 2, d, а).

Предположим, что искомое свойство четности выполняется для n - 1. Тогда остается заниматься только теми дисками, которые ложатся на диск n.

В первой операции диск n - 1 находится на диске n, они разной четности, и, таким образом, здесь свойство четности выполняется. Во время игры Н(n - 2, а, 3 - а - d) диск n находится на стержне, который для этой игры является запасным. Диски, которые в этой игре ложатся в основание этого стержня — и потому ложатся на диск n — имеют четность, противоположную четности числа n - 2, следовательно, четность, противоположную четности n, что и проверяет на этом этапе наше условие четности. Вы легко завершите это рассуждение.

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

Игра 33.

Предположите, что в Н (n - 1, d, а) диск 1 перемещается всегда в одном и том же направлении. Для Н (n, d, а) вы должны выполнить

Н (n - 1, d, 3 - а - d)

Н (n - 1, 3 - а - d, а).

Вместо того, чтобы непосредственно переходить от d к а, вы осуществляете этот переход с помощью стержня 3 - а - d, иначе говоря, вы делаете два перемещения в обратном направлении. Диск 1 продолжает перемещаться всегда в одном и том же направлении, но это направление меняется при переходе от n - 1 к n. Для n = 1 этот диск перемещается в направлении от d к а. Это всегда будет так для всех нечетных n, в то время как для четных n он будет перемещаться в направлении от а к d.

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

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

d := 0; k:= 2n - 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(р).