Программирование игр и головоломок
Шрифт:
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 x 24 = 86400 секунд, за год получаем 86400 x 365 — или порядка 3 x 107 секунд, откуда, наконец, 3 x 109 секунд за столетие. Поэтому нужно порядка 1015/3 x 109, или порядка 3 x 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, 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.