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

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

* Головоломка 2. Последовательности «орлов» и «решек».

Осуществим n выбрасываний «орла» и «решки» с большим n (например 10000). Сколько раз встретится в ней данная комбинация из m следующих друг за другом выбрасываний (например, 10 раз «орел» или чередование из 10 выбрасываний «орла» и «решки», начиная с «орла»).

Есть много способов решить это упражнение. Они не все равноценны по времени вычисления. Я взял большое n и относительно большое m, чтобы прояснить явление. Ваша программа не должна работать долгие часы…

Другие азартные игры

* Игра 3. Покер — М — С.

Я не уверен, что это следует писать. Я знаю эту игру только по услышанной мною радиопередаче какой то периферийной радиостанции (угадайте какой?). Тасуем карточную колоду. Разыгрывается некоторая сумма. Верен верхнюю карту из пачки и требуем от игрока, чтобы он угадал, является ли следующая карта младшей или старшей по отношению к только что взятой. Учитывается только число очков, а не масть карты. Валет всегда больше девяти, король больше валета, туз больше всех. Если игрок угадал правильно, сумма в игре возрастает (я не знаю точно, добавляется ли при этом некоторое фиксированное количество или сумма удваивается, но это не так уж важно. В любом случае ваш компьютер не имеет связи с распределителем банковских билетов. Жаль, быть может…). Если он не угадывает, он теряет все, В конце некоторого фиксированного числа бросаний (кажется 6; я слушал недостаточно внимательно, я прошу прощения у упомянутой станции) игрок, если он всегда оказывался прав, присваивает сумму игры.

Составьте программу, которая позволит вам быть игроком, а компьютер пусть будет всем остальным (за исключением того, что вы называете и сумму игры). На мой взгляд, хотя я могу и ошибаться, единственная трудная задача — перетасовать карты…

?** Игра 4. Лабиринт для шахматного коня.

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

Чтобы освободиться от графических задач, рассмотрим другую форму лабиринта. Его создание составляет головоломку, а использование — игру. Пусть дана прямоугольная область, образованная n строками с p полями на каждой из них. На моем компьютере, где приходится учитывать формат экрана, числа n = 12 и p = 20 дают хорошие результаты. Занятые места считаются препятствиями (обозначенными здесь 0), пусть как-то помечены свободные места (здесь — точкой), пусть значок * обозначает всадника. Конь перемещается, как конь в шахматах: два шага в одном направлении и еще один шаг перпендикулярно предыдущему направлению. Конь может перемещаться только с одного свободного места на другое, В начальный момент он находится в правом нижнем углу. Он должен попасть в верхний левый угол (который, таким образом, тоже должен быть свободным). Число ходов игры ограничено. На рис. 1 изображен типичный пример лабиринта.

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

— возьмите случайным образом путь, связывающий эти два угла. Это — маленькая головоломка. Может быть, вы знаете задачу Эйлера о шахматном коне: составить такой путь коня по шахматной доске, чтобы он побывал на каждом поле один и только один раз. Но здесь у вас больше свободы. Тем не менее не представляется разумным проходить два раза одно и то же поле (если ваш путь будет содержать круг, то он будет предоставлять возможность для короткого замыкания, т. е. удаления этого круга). Но, может быть, это и не необходимо. Если мы много раз попадаем на одно и то же поле, то мы предоставляем много возможностей выбора, и осложняем задачу воссоздания пути. Не нужно использовать какой-либо систематический алгоритм прохода, иначе ваш лабиринт будет расшифровываться слишком быстро. Следующий за данным полем шаг на нашем пути должен выбираться случайным образом. Как тогда мы сможем быть уверены в попадании в левый верхний угол?

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

дуть будет почти полностью определен (на рисунке препятствия занимают приблизительно 2/3 полей. Это — верхняя грань);

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

Остается обеспечить движение коня. Вот как действую я. Сначала я подсчитываю число полей на исходном пути, которые были выбраны случайно, и вывожу это число в качестве верхней границы числа ходов. Я свидетельствую, что всегда обнаруживался более короткий путь. Я не пытался объяснить этот экспериментальный факт…

Компьютер сообщает число оставшихся ходов и требует ваших указаний о движении. Ответ дается в виде двух букв: первая из этих букв дает направление, в котором нужно переместиться на два шага, вторая буква дает перпендикулярное предыдущему направление, в котором нужно сделать один шаг: Н — для нижней, В — для верхней, П — для правой, Л — для левой сторон. В случае на рис. 1 первое движение предписывает ЛВ — два шага влево, один вверх.

Компьютер анализирует ответ. Если превышено число ходов или ход встречает препятствие, то игрок проигрывает. Если нет — звездочка, изображающая коня, перемещается в новое положение, число оставшихся ходов уменьшается на единицу, и игра продолжается.

Игра 5. Спящая красавица.

Краткое содержание предыдущих эпизодов. Доктор Жабуэ не убил великолепную Жюли, он только приостановил жизненные процессы. Ее мог бы разбудить надлежащий лицевой массаж, но это его не беспокоит, впереди еще много времени. Из замка вывезено все, что имело хоть какую-то ценность: обстановка, картины, произведения искусства… Молодой повеса обнаруживает пустой замок и находит, что он должен быть замечательным треком для мотогонок…

13-й эпизод.

Рыжий Тони входит в темную комнату. Несмотря на грохот мотоцикла, отчетливо воспринимается равномерный храп. Он зажигает фару и обнаруживает безмятежно спящую прекрасную Жюли. Ослепленный ее красотой, он приближается к ней и гладит ее по лицу. Ничего больше и не нужно. Жюли внезапно просыпается и, приходя в сознание с удивительной быстротой, восклицает: «Бежим отсюда скорее, в замке западня, все сейчас взорвется». Тони садится на мотоцикл. Жюли вскакивает на сиденье за Тони и пристегивается к нему. Но уже повсюду гремят взрывы, и огонь охватывает деревянный потолок. Тони мчится зигзагами среди обломков. Обрушиваются куски горящих балок, угрожая раздавить их в любой момент.

Удастся ли им выбраться из замка? Продолжение в следующем эпизоде.

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