Жак Арсак - Программирование игр и головоломок
Игра 30.
Единственная настоящая задача, если вы работаете итеративным способом — организовать испытания так, чтобы иметь возможность совершенно систематически проводить их и обновлять игру, сохраняя список ходов, чтобы иметь возможность вернуться назад.
Игра имеет ту же конфигурацию, что и для лис и кур. Поле обозначается своим положением в цепочке. Перемещение в данном направлении реализуется добавлением некоторой константы к данному положению. Таблица из четырех элементов дает эти константы для всех четырех направлений. Свободное поле представляется точкой, занятое поле — крестиком ×.
Вы ищете первый крестик в цепочке и вы начинаете с первого возможного перемещения i = 1. Если есть возможность взятия в этом направлении, то вы регистрируете данные ×, i в цепочке или таблице (во втором случае вы симулируете кучу). Вы выполняете взятие и начинаете сначала. Если же возможности взятия в данном направлении нет, то вы переходите к следующему i. Если вы достигаете четырех, то с этим крестиком все кончено, и вы переходите к следующему. Если их больше нет, то вы возвращаетесь к последней зарегистрированной в куче паре данных ×, i, отменяете соответствующее взятие (изменение состояния игры) и продолжаете переходом к следующему i.
Вы уже проделали более трудную работу для самого длинного взятия в игре с курами и лисами.
Игра 31.
Число ходов f(р) для переноса р дисков получается переносом сначала p − 1 дисков со стержня d на стержень 3 − а − d за f(р − 1) ход, затем из перемещения диска р, что требует в точности одного хода, а затем возвращения р − 1 дисков из запаса на стержень прибытия за f(р − 1) ход, откуда получаем:
f(р) = 2 * f(р − 1) + 1,
g(p) = f(p) + 1 = 2 * f(р − 1) + 2 = 2 * (f(p − 1) + 1) − 2 * g(р − 1).
По индукции g(р) = 2pg(0).
Так как f(0) = 0, g(0) = f(0) + 1 = 1, g(р) = 2p, то, наконец
f(р) = 2p − 1.
Для игры с 50 дисками нужно 250 − 1 ходов. Но 210 равно 1024, или порядка 103. Следовательно, 250 порядка 1015.
В часе 3600 секунд, в сутках 3600 × 24 = 86400 секунд, за год получаем 86400 × 365 — или порядка 3 × 107 секунд, откуда, наконец, 3 × 109 секунд за столетие. Поэтому нужно порядка 1015/3 × 109, или порядка 3 × 105 веков для игры с 50 дисками, которая, таким образом, требует около 300000 веков…
Вот другой способ доказывать свойство четности. Пусть диски обозначены их порядковыми номерами, начиная с первого — самого маленького, и нужно показать, что два диска с номерами одной четности никогда не попадают непосредственно один на другой.
Опыт показывает, что для первых значений 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. Начните с 2n − 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.
