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

б..бааХаабб

ббббааХаа..

Последний перенос пары букв аа слева от X в свободные пары справа дает

бббб..Хаааа

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

ббббY ..аааа

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

f (р) = 2 p − 1.

Для игры с 50 дисками нужно 2 50− 1 ходов. Но 2 10равно 1024, или порядка 10 3. Следовательно, 2 50порядка 10 15.

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