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

Вы уже проделали более трудную работу для самого длинного взятия в игре с курами и лисами.

Игра 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(р) = 2^pg(0).

Так как f(0) = 0, g(0) = f(0) + 1 = 1, g(р) = 2^p, то, наконец

f(р) = 2^p– 1.

Для игры с 50 дисками нужно 2⁵⁰– 1 ходов. Но 2¹⁰ равно 1024, или порядка 10³. Следовательно, 2⁵⁰ порядка 10¹⁵.

В часе 3600 секунд, в сутках 3600 x 24 = 86400 секунд, за год получаем 86400 x 365 — или порядка 3 x 10⁷ секунд, откуда, наконец, 3 x 10⁹ секунд за столетие. Поэтому нужно порядка 10¹⁵/3 x 10⁹, или порядка 3 x 10⁵ веков для игры с 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.