Чтобы освободить игру на одно поле, очищаем поле 1.
Чтобы освободить игру на два поля, мы не можем очистить поле 1, так как тогда мы не могли бы очистить и поле 2. Первое занятое поле — поле 1. Можно очистить поле 2, а затем поле 1.
Для игры с 3 полями, мы очищаем 1, эатем ставим 3, ставим снова 1, очищаем 2, а затем 1.
Если n четно, то мы начинаем с удаления шашки 2, в противном случае мы удаляем шашку 1.
Теперь вам не составит ни малейшего труда написать итеративную программу:
место := 0; игра : = пусто
ВЫПОЛНЯТЬ
ЕСЛИ поле (1) = пусто ТО поставить (1);
место := место + 1
ИНАЧЕ удалить (1);
место := место − 1
КОНЕЦ_ЕСЛИ
ЕСЛИ место = n ТО КОНЧЕНО КОНЕЦ_ЕСЛИ
искать первое занятое поле, номер которого дает число i;
ЕСЛИ поле (i + 1) = пусто ТО поставить (i + 1);
место := место + 1
ИНАЧЕ удалить (i + 1);
место := место − 1
КОНЕЦ_ЕСЛИ
ЕСЛИ место = n ТО КОНЧЕНО КОНЕЦ_ЕСЛИ
ВЕРНУТЬСЯ
Для игры СНИМАТЬ вы действуете аналогично.
В том, что касается последовательностей чисел, порожденных игрой СНИМАТЬ, начнем с рассмотрения конкретного примера. Вот игра СНИМАТЬ для 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.
Единственная настоящая задача, если вы работаете итеративным способом — организовать испытания так, чтобы иметь возможность совершенно систематически проводить их и обновлять игру, сохраняя список ходов, чтобы иметь возможность вернуться назад.
Игра имеет ту же конфигурацию, что и для лис и кур. Поле обозначается своим положением в цепочке. Перемещение в данном направлении реализуется добавлением некоторой константы к данному положению. Таблица из четырех элементов дает эти константы для всех четырех направлений. Свободное поле представляется точкой, занятое поле — крестиком ×.
Вы ищете первый крестик в цепочке и вы начинаете с первого возможного перемещения i = 1. Если есть возможность взятия в этом направлении, то вы регистрируете данные ×, i в цепочке или таблице (во втором случае вы симулируете кучу). Вы выполняете взятие и начинаете сначала. Если же возможности взятия в данном направлении нет, то вы переходите к следующему i. Если вы достигаете четырех, то с этим крестиком все кончено, и вы переходите к следующему. Если их больше нет, то вы возвращаетесь к последней зарегистрированной в куче паре данных ×, i, отменяете соответствующее взятие (изменение состояния игры) и продолжаете переходом к следующему i.