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

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

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

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

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

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

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

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

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

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