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

u i = f ( u i −1),

Сказать, что последовательность u i становится периодической — то же, что сказать, что существует некоторое p , для которого

u i + p = u i

для достаточно больших i . Но если это выполняется для данного i , то

u i + p +1= f ( u i + p ) = f ( u i ) = u i +1

и, следовательно, 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 на единицу и повторяете процедуру.