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

Вы научились порождать последовательности непредсказуемых чисел, или, допуская неточность речи, принятую в информатике, случайных чисел (эти последовательности совершенно не случайны; они полностью детерминированы, но, поскольку мы не можем найти простого способа перехода от данного числа к следующему и поскольку эти числа приблизительно регулярно размещены в промежутке 0 : 1, то они производят впечатление случайности). Каждое число в этой последовательности зависит только от предыдущего числа. К тому же, как и выше, вы можете получить и в самом деле непредсказуемое число, задавая компьютеру значения трех карт. Вы заставляете его вычислить значение, определенное в разд. 1.1, затем вы берете следующее за этим значением либо с помощью функции ALE или RND вашего компьютера, либо с помощью метода, описанного в разд. 1.2.

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

ВВЕДИТЕ ТРЕХЗНАЧНОЕ ЦЕЛОЕ

затем прочесть значение x этого целого и взять в качестве начального значения случайной последовательности число x/1000.

Исходя из генератора случайных чисел, можно легко построить последовательность целых чисел. Название функции, порождающей случайные числа, меняется от языка к языку; назовем ее

ale (x)

— это функция, сопоставляющая x, 0 ≤ x < 1, следующее за ним число

0 ≤ ale (x) < 1.

Построим теперь последовательность неотрицательных целых чисел, меньших данного числа n. У нас есть две возможности.

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

x := ale (x), p = целая_часть(n * x).

Различные значения x могут давать одно и то же значение p, так что элемент, следующий за p в последовательности целых, не определяется каким-либо предсказуемым образом. Вообще говоря, данное значение p может иметь несколько последующих значений. Маловероятно, что эта последовательность окажется периодической. Это заведомо случится, если последовательность x, определяющая ее, периодична (а это бывает, хотим мы этого или не хотим).

2. Пусть p дано; тогда p/n лежит между 0 и 1. И элемент, следующий за p, можно определить формулой

p := целая_часть (n * ale (p/n)),

Здесь элемент, следующий за p, полностью определен числом p, и эта последовательность неизбежно оказывается периодической. В наиболее удачных случаях она дает n различных значений (n целых от 0 до n − 1), после чего возвращается к уже встретившемуся в последовательности числу, и — так как каждое из чисел имеет однозначно определенное следующее за ним число — мы повторяем уже построенную часть последовательности. Но чаще всего этим способом получаются слишком короткопериодические последовательности.

?? Головоломка 1. Периодическая последовательность.

Построим последовательность целых чисел в промежутке (0, n − 1) только что описанным способом. Предположим, что n достаточно велико (например 10000). Написать программу, определяющую период этой последовательности. Ограничение: вы не имеете права запоминать в таблице последовательные значения элементов последовательности (вы не имеете права запоминать их и в любой другой форме). Именно поэтому n предполагается достаточно большим: не может быть и речи о сохранении всех полученных значений, чтобы смотреть, встречается ли каждое новое значение среди предыдущих. Нужен другой метод. Вам предлагается обнаружить один из них…

Головоломка для маленького вундеркинда.

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

Я находился в зале для практических занятий с детьми 15–16 лет. Преподаватель предложил им составить программу, бросающую две случайные кости и сообщающую число появлений каждой комбинации (см. упражнение 4). Маленький местный вундеркинд закончил свою довольно простую (не так ли!) программу, и преподаватель предложил ему следующую задачу: