Жак Арсак - Программирование игр и головоломок

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

Опыт показывает, что для первых значений n реализация игры Н ( n , d , а ) дает следующее;

— диски, попадающие в основание стержней d и а , имеют ту же четность, что и n ,

— диски, попадающие в основание запасного стержня, имеют другую четность.

Предположим, что это свойство справедливо для 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 n − 1 число ходов, которые осталось сделать:

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

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

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

Игра 34.

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

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

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

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