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

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

Перемещение диска 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, а четные диски — в другом направлении.

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