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

• Название: Программирование игр и головоломок
• Автор: Жак Арсак
• Издательство: Наука. Гл. ред. физ.-мат. лит.
• Жанр: Программирование
• Год: 1990
• ISBN: 5-02-013959-9

Рассматриваются способы программирования различных занимательных игр и головоломок с числами, геометрическими фигурами и др. Изложение большинства игр и головоломок ведется в несколько этапов. Сначала разъясняется сама постановка задачи и требования, предъявляемые к алгоритму ее решения.

В следующем разделе книги обсуждается сам алгоритм и возможные пути его реализации.

В конце книга по многим играм и головоломкам даются наброски их программной реализации. Используемый при этом язык типа Паскаля допускает перевод на другие широко распространенные языки программирования.

Для начинающих программистов, студентов вузов и техникумов.

---

WHILE условие DO

  BEGIN последовательность операторов END

Цикл

ВЫПОЛНЯТЬ

  последовательность операторов, содержащая слово КОНЧЕНО

ВЕРНУТЬСЯ

работает так:

Последовательность инструкций, заключенная между скобками операторов ВЫПОЛНЯТЬ — ВЕРНУТЬСЯ, повторяется неограниченно. Слово КОНЧЕНО означает, что цель цикла достигнута, повторяемая работа закончена. На этом цикл останавливается и программа продолжается со следующего за циклом оператора В английских книгах и статьях вместо КОНЧЕНО обычно пишут EXIT: выйти из цикла (также сделано и в языке Ада). Но EXIT вызывает идею действия: выхода. Я предпочитаю ему слово КОНЧЕНО, которое лучше отражает идею не действия, а ситуации: я достиг цели цикла, с ним все кончено.,..

Простых эквивалентов этого цикла на Бейсике, LSE или Паскале нет. Можно применить операторы ALLER EN или GO ТО для симуляции такого цикла.

— На Бейсике можно использовать дополнительную переменную Z:

FOR Z = 1 ТО 0 заменяет ВЫПОЛНЯТЬ

LET Z = 0 заменяет КОНЧЕНО

NEXT Z заменяет ВЕРНУТЬСЯ

Кроме того, нужно перепрыгнуть в цикле все, что стоит после слова КОНЧЕНО, т. е. после оператора LET Z = 0. Так как это можно сделать с помощью GO ТО, то я считаю предпочтительным использовать таким образом GO ТО для циклов. Если ваш язык не структурирован, то красивых циклов вы никогда не получите…

— На языке Паскаль используйте булеву переменную z, которой до начала цикла присвоено значение TRUE, и тогда цикл примет вид

WHILE z DO BEGIN END

Слово КОНЧЕНО придется заменить оператором z := FALSE, включенным в конструкцию так, чтобы сделать этот оператор последним выполняемым оператором цикла. Если структура языка нехороша…

Цикл

ДЛЯ i := exp 1 ШАГ exp 2 ДО exp 3 ВЫПОЛНЯТЬ…

ВЕРНУТЬСЯ

повторяет последовательность операторов, заключенную между ВЫПОЛНЯТЬ и ВЕРНУТЬСЯ, придавая i значения из арифметической прогрессии с разностью exp 2 (постоянная величина в данном цикле), начиная с exp 1 и останавливаясь на exp 3, Если шар равен 1, то фрагмент ШАГ 1 можно опустить.

Часть I. Условия задач

1. Случайные числа

Генерация случайного числа

Можно сделать из этого настоящую головоломку: написать программу, выполнение которой на компьютере дает число, случайным образом расположенное в данном интервале, например, между 0 и 1. Но это невозможно.

Некоторые языки содержат функцию, значение которой есть непредсказуемое число в данном интервале. Если ваш компьютер использует LSE, достаточно набрать на клавиатуре

? ALE(0)

чтобы получить в ответ непредсказуемое число между 0 и 1, которое может рассматриваться как полученное случайным образом.

На языке Бейсик команда RND(0) дает тот же эффект при условии, что предварительно выполнена инструкция RANDOM. Но Бейсик — это скорее общее имя для целого класса языков, чем обозначение совершенно определенного стандартизованного языка, не меняющегося от одной машины к другой. Так что сверьтесь с описанием к вашему компьютеру…

Если используемый вами язык допускает описанные выше или аналогичные возможности, то получить случайное число в интервале (0, 1) — это никакая не головоломка, это тривиально.

Но если в языке такой возможности нет,; то это больше чем головоломка, это невозможно. Предположим, что мы сделали программу, производящую такое число. Эта программа не может иметь исходных данных, иначе это не она вытаскивает, случайное число, а именно вы при введении данных… Если же у нее нет данных, то она действует, исходя из констант. Но тогда нет переменных элементов, и последовательные запуски программы дают совпадающие результаты. Как же вы получите с помощью такой программы случайное число?[2]

Поэтому если ваш компьютер не допускает функции, дающей стохастическое число, я вижу только одно решение[3]: введите сами случайное число в ваш компьютер. Как это сделать? Вот предложение. Вы берете колоду из 52 карт, перетасовываете. Затем вы делите колоду на верхнюю и нижнюю части и берете из нижней части три верхние карты. Небольшая и очень простая программа читает три целых числа x, y, z. В качестве значений этих целых чисел вы задаете численные значения трех выбранных карт, считая туза за 1, валета — за 11, даму — за 12, короля — за 13. Компьютер вычисляет значение

(((x − 1)/13 + у − 1)/13 + z − 1)/13.

Например, если вы достанете, как только что случилось со мной, семерку бубен, десятку червей и еще шестерку бубен, то

x =7 y= 10 z = 6

и компьютер получит 0.440601.

Эго значение не является воистину непредсказуемым. Как только вы достанете карты, вы уже сможете понять порядок величины результата. С другой стороны, таким способом вы не сможете получить более 13³ = 2197 различных чисел. Но этого на самом деле достаточно для приложений, которые мы рассматриваем в этой книге. А если вы и в самом деле хотите получить что-либо непредсказуемое, прочтите следующий раздел.

Непредсказуемые числовые последовательности

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

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

Может случиться, что используемый вами язык предоставляет эту возможность непосредственно в виде одной из конструкций языка.

Так, на LSE команда ALE(x) дает число, лежащее в интервале (0, 1), значение которого зависит от x, но непредвиденным образом и, кроме того, не специфицированным в языке: значение будет различным на разных машинах. Если вы трижды зададите один и тот же вопрос

? ALE (0.1)

вы каждый раз получите один и тот же ответ, но между ALE(0.1) и ALE(0.2) нет простого соотношения.

На Бейсике функция RND играет ту же самую роль. Она порождает непредсказуемую последовательность, значения которой зависят только от начального числа — оно одно и то же для данного компьютера. Инструкция RANDOM дает случайное число и ставит его начальным элементом последовательности, что позволяет порождать различные последовательности.

Может быть, интересно посмотреть, как можно строить подобные последовательности. Вот метод, предложенный А. Энгелем [ENG]. Если x — число между 0 и 1, то следующий за x элемент последовательности есть

дробная часть ((x + 3.14159)8)

Конечно, восьмая степень вычисляется тремя последовательными возведениями в квадрат! Она дает число между 9488 (для x = 0) и 86564. Очень небольшое изменение x вызывает сильное изменение (x + π)8, и, в частности, оно может перейти через ближайшее целое, так что новое значение (дробная часть результата) может оказаться меньше предыдущей.

Возьмем, например, x = 0.52000; тогда

(x + 3.14159)8 = 32311.5437

так что за 0.5200 следует 0.5437.

Но для x = 0.52005 имеем

(x + 3.14159)8 = 32315.0736

и за 0.52005 следует 0.0736.

Так как мы берем дробную часть, то полученное число, разумеется, лежит между 0 и 1.

Упражнение 1. Поведение последовательности.

Речь идет о том, чтобы увидеть, как ведут себя числовые последовательности, порожденные таким образом. Для этого вычислим большое число членов последовательности, порожденной своим первым элементом. Поместим каждый из этих членов в один из 50 интервалов длины 0.02, составляющих интервал от 0 до 1. Выведем число членов последовательности, попавших в каждый из этих интервалов. Если числа из последовательности равномерно распределены в интервале (0, 1), мы должны будем обнаружить, что их количество в разных интервалах имеет ощутимую тенденцию к постоянству.

Составьте программу для проверки зтого утверждения. Начальное значение может, например, вводиться в начале каждого вычисления.

Упражнение 2. Поиск других последовательностей.

Число π, использованное при вычислении наших последовательностей, не обладает никаким специальным свойством, и можно спросить себя, действительно ли выбор этого числа является наилучшим возможным. Числа (x + π)8 довольно велики, а берем мы от них только дробную часть. При этом мы отбрасываем значащие цифры целой части, и — поскольку вычисления на компьютере проводятся с фиксированным количеством значащих цифр — на дробную часть остается относительно небольшое количество цифр. Предположим, что числа представляются с помощью 24 двоичных цифр. Нужно 14 двоичных цифр, чтобы записать 9488, так как