Программирование игр и головоломок - [37]

Игра 3.

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

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

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

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

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

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

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

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

Игра 4.

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

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

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

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

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

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

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

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

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

Игра 5.

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

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

2. Игры с числами

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

Я нашел это упражнение в монографии, посвященной языку Пролог. Предложенное там решение действует методом проб и ошибок. Но задача решается намного проще.

Как всегда, полностью определим задачу. Искомое число представляется в десятичной системе последовательностью цифр

c_nc_n−1…c₂5

Умножая на 5, получаем

5c_nc_n−1…c₃c₂

Отсюда следует, что c₂ = 5. Все цифры c_i точно так же итеративно вычисляются справа налево, обыгрывая оставшееся от предыдущего умножения «в уме»: когда вы умножаете крайнее справа 5 на 5, вы получаете 5 единиц, что и дает c₂ = 5, и 2 «в уме». Тогда вы можете вычислить c₃ и новую цифру «в уме» и продолжать шаг за шагом. Остается маленькая задача о том, как узнать, когда следует остановиться. Изучите ее сами; как обычно, я не хотел бы сообщать вам все…

Вы можете также действовать слева направо:

5c_nc_n−1…c₃c₂ : 5 = c_nc_n−1…c₂5

Деля левую цифру на 5, вы получаете c_n = 1. Имея c_n, вы можете продолжать деление. И здесь тоже вам нужно будет принимать во внимание перенос результата, полученного при предыдущем делении, и нужно будет знать, когда остановиться. Эти два метода по существу равносильны.

Остальное оставляю исследовать вам.

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

Обычно я бываю глубоко разочарован тем, что нахожу в книгах по информатике или по математике касательно квадратных корней. Чаще всего вам предлагают метод Ньютона: пусть вам нужно извлечь квадратный корень из числа x. Вы образуете возвратную последовательность u_i по правилу

u_i+1 = (u_i + (x/u_i))/2.

Вне всякого сомнения, вы можете взять u₀ = 1 в качестве начального значения. Эта последовательность очень быстро сходится к квадратному корню из x. Если, например, взять x = 50 и воспользоваться формулой

u_i+1 = целая_часть ((u_i + (x/u_i))/2),

чтобы иметь дело только с целыми числами, то в качестве последовательных значений и вы получите