Программирование игр и головоломок
Шрифт:
Для игры СНИМАТЬ вы действуете аналогично.
В том, что касается последовательностей чисел, порожденных игрой СНИМАТЬ, начнем с рассмотрения конкретного примера. Вот игра СНИМАТЬ для n = 4.
| 0001 | 1 |
| 0011 | 3 |
| 0010 | 2 |
| 0110 | 6 |
| 0111 | 7 |
| 0101 | 5 |
| 0100 | 4 |
| 1100 | 12 |
| 1101 | 13 |
| 1111 | 15 |
Использованы все числа, меньшие 8, а из больших или равных 8 участвуют только 12, 13 и 15. Для обобщения действуйте по индукции.
Игра 29.
Вот решение для 8 букв и 10 полей.
..абабабаб
баабаба..б
бааб..аабб
б..баааабб
ббббаааа..
Присутствие куска X не меняет последовательности изменений.
..абабХабаб
баабабХа..б
бааб..Хаабб
б..бааХаабб
ббббааХаа..
Последний перенос пары букв аа слева от X в свободные пары справа дает
бббб..Хаааа
Теперь вы можете заняться 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) ход, откуда получаем: