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

и, следовательно, u_j+p = u_j для любого j, большего i. Пусть r — наименьший из индексов, для которых u_r+p = u_r.

От вас не требуют найти число r, нужно найти только число p. Можно предложить два решения:

— если i — достаточно большое число, кратное p, то u_2i = u_i;

— выберите исходное значение d и длину интервала h. Для любого i от d + 1 до d + h посмотрите, не равно ли соответствующее значение u числу u_d. Если равно, то вы нашли период и все закончилось. Если же никакого равенства не получается, то либо d меньше, чем r, либо h меньше p, либо и то, и другое. Попытайтесь сделать то же еще раз с большими d и h.

Есть много способов реализовать вторую из этих стратегий. По крайней мере в некоторых случаях она быстрее первой.

Головоломка 2.

Совершенно ясно, что вы не можете начинать проводить какие-либо статистические подсчеты до того, как вы реализуете m бросаний. Наш маленький вундеркинд хотел бы сделать единственный цикл, в котором m– 1 первых ходов подвергаются специальной обработке. Это — совершенно бесполезная сложность. Составьте первый цикл по данным m первым ходам. Затем — второй цикл, проводящий статистику.

Наш маленький вундеркинд совершил и вторую ошибку, для меня еще более необъяснимую: он объединил последовательные ходы в таблицу. Но это совершенно бесполезно. В любой момент единственное, в чем вы нуждаетесь, это в результатах m последних бросаний. С каждым новым бросанием результат наиболее старого из учитывающихся ранее бросаний теряет силу. Поэтому вы можете его упразднить, Если и есть таблица, то ее размер m, а не n!

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

Но можно сделать еще и по-другому. Речь идет об «орле» и «решке». Нам нужно только два различных символа, например, 0 и 1. Эти m символов 0 и 1 могут рассматриваться как цифры числа в двоичной записи. Тогда вам не нужна ни таблица, ни цепочки символов. В соответствии с выбором нужно выполнить либо умножение на 2 (что сводится к одному сложению), либо деление на 2.

Относительные успехи трех наших решений зависят от используемой вами системы. В зависимости от управления, принятого для таблиц и цепочек, в зависимости от искусства программиста, составившего систему интерпретации вашего языка высокого уровня, либо таблица одолевает цепочки, либо наоборот.

В составленной мною системе на языке LSE использованы двоичные числа, дающие несколько лучший результат, чем полученные с помощью цепочки., которые, в свою очередь, дают заметно лучший результат, чем полученный с помощью таблиц.

Игра 3.

Единственная трудность в этой программе: перетасовать карты. Я уже упомянул об этом, описывая условия игры. Есть много возможных идей:

— приготовить сначала карточную колоду, затем вытаскивать их из стопки одну за другой. В этом случае у вас будет выбор, как поступать:

либо расположить карты в таблицу в 52 полями, либо создать цепочку ив 52 символов. Но нужно ли это на самом деле? Почему бы не исходить из простой начальной ситуации: упорядоченной таблицы или отсортированной цепочки, затем выбирать элемент этого множества с помощью случайного бросания, вынимать его из множества и повторять процедуру с меньшим количеством элементов.

Если так поступать, то применение таблицы становится тонкой задачей: как изъять элемент из множества?

Его можно изъять «физически». Все элементы, расположенные выше него, спускаются в таблице вниз на одну ступеньку. Это сохраняет порядок оставшихся элементов.

Но нужно ли это? Почему бы, что гораздо проще, не переставить выбранный элемент с последним элементом таблицы в процессе выполнения операции?

Как только мы это обнаружили, становится очевидно, что в перетасовывании карт, исходя из начальной колоды, больше никаких трудностей нет: вы размещаете колоду в упорядоченную таблицу из n карт, вы выбираете случайным образом целое число между 1 и n, вы меняете местами соответствующий элемент с элементом n, затем вы уменьшаете n на единицу и повторяете процедуру.

Элементарно, когда все испробовано!

Игра 4.

Я уже дал все необходимые пояснения, кроме порождения лабиринта. Первую попытку я предпринял со следующим алгоритмом:

— поставить i в начальное положение (правый нижний угол),

— выбрать случайным образом направление перемещения (целое от 1 до 8); если это перемещение невозможно — перейти к следующему перемещению, пока не будет найдено возможное перемещение;

— передвинуть i в соответствии с этим перемещением;

— если i оказался на поле прибытия, то все закончено, в противном случае повторить процедуру.

Опыт показывает, что чаще всего эта программа не останавливается.

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

Так как у меня еще были и другие задачи, я решил останавливать случайный выбор, когда i оказывается в маленьком прямоугольнике вверху слева. Полученный реестр (сделанный из таблицы или цепочки символов) дает тогда путь, ведущий из каждой из точек этого прямоугольника к полю прибытия.

Остальное просто.

Игра 5.

Эта игра не представляет никаких трудностей. Пусть вы не пытаетесь гарантировать Тони возможность выхода. В программе — никакой стратегии: один ход на два поля, два препятствия на горизонтальной линии на двух свободных полях (вы выбираете клетку случайным образом. Если она или ее соседка справа не свободны, то вы повторяете выбор. Если они свободны — вы их помечаете. Тем хуже для Тони, если он накрыт), два препятствия случайным образом на двух вертикальных полях.