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

бббб..Хаааа

Теперь вы можете заняться X (если для этой комбинации вам решение уже известно) и получить

ббббY ..аааа

Таким образом, остается переместить два а с крайних полей справа на свободные поля, и все закончено. Следовательно, если вы умеете исследовать комбинацию Х с р парами букв а, б, то вы умеете исследовать и комбинацию с р + 4 парами.

Я уже предложил вам решение для четырех пар. Таким образом вы получаете решение для 8, 12,…

Главные решения — это решения для 4, 5, 6, 7 пар. Вот одно из решений для строчки из 5 пар

..абабабабаб

Искомое расположение имеет вид

бббббааааа..

Можно задаться целью удалить все буквы а (особенную трудность при перемещениях вызывает то, что их число нечетно) из первой половины (первых 5 позиций, в которых букв а в исходном положении не столько же, сколько букв б).

..абабабабаб

баабабаба..б

бааб..абаабб

бааббаа..абб

б..ббааааабб

бббббааааа..

Предлагаю вам разыграть 6 и 7 пар. Совершенно бесполезно подключать к этому делу компьютер. А где же программирование, спросите вы? Я отвечу, что это упражнение вводит вас в рекурсивные или индуктивные рассуждения. Это оздоровляет Наши способы рассуждать…

Игра 30.

Единственная настоящая задача, если вы работаете итеративным способом — организовать испытания так, чтобы иметь возможность совершенно систематически проводить их и обновлять игру, сохраняя список ходов, чтобы иметь возможность вернуться назад.

Игра имеет ту же конфигурацию, что и для лис и кур. Поле обозначается своим положением в цепочке. Перемещение в данном направлении реализуется добавлением некоторой константы к данному положению. Таблица из четырех элементов дает эти константы для всех четырех направлений. Свободное поле представляется точкой, занятое поле — крестиком x.

Вы ищете первый крестик в цепочке и вы начинаете с первого возможного перемещения i = 1. Если есть возможность взятия в этом направлении, то вы регистрируете данные x, i в цепочке или таблице (во втором случае вы симулируете кучу). Вы выполняете взятие и начинаете сначала. Если же возможности взятия в данном направлении нет, то вы переходите к следующему i. Если вы достигаете четырех, то с этим крестиком все кончено, и вы переходите к следующему. Если их больше нет, то вы возвращаетесь к последней зарегистрированной в куче паре данных x, 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(р) = 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.