Есть много способов реализовать вторую из этих стратегий. По крайней мере в некоторых случаях она быстрее первой.
Головоломка 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 оказался на поле прибытия, то все закончено, в противном случае повторить процедуру.