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

Воспроизводимая непредсказуемая последовательность

Воспроизводимая непредсказуемая последовательность

Вы научились порождать последовательности непредсказуемых чисел, или, допуская неточность речи, принятую в информатике, случайных чисел (эти последовательности совершенно не случайны; они полностью детерминированы, но, поскольку мы не можем найти простого способа перехода от данного числа к следующему и поскольку эти числа приблизительно регулярно размещены в промежутке 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). Маленький местный вундеркинд закончил свою довольно простую (не так ли!) программу, и преподаватель предложил ему следующую задачу:

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

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

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

Гораздо более правдоподобно, что этот мальчик (как и подобные ему) встречают естественные затруднения в общении с другими людьми. Он нашел в информатике страну, в которой можно избежать такого общения и где машина принимает все, что он скажет, какова бы ни была форма и структура, лишь бы только синтаксис был соблюден. Именно поэтому феномен «информатических клубов» оказывается опасным. В рамках преподавания информатики нужно, чтобы преподаватель требовал от своих учеников анализа поставленной задачи и словесного выражения на обыденном языке результата этого анализа. Программирование может начаться только после этого. На этом уровне преподаватель заботится о качестве стиля программ, написанных по ясному плану… (Я надеюсь, что и вы работаете именно так, иначе вас нужно остерегаться.) В обстановке, когда подростков недостаточно контролируют и они находятся как бы на самообучении, они могут оказаться свободно предоставленными своим естественным склонностям. Если организованное преподавание помогало бы им учиться выражать и структурировать свои мысли, то всетерпимость к средствам выражения, свойственная машине, позволяет им оставаться в их собственном мирке, и случайные — но настоящие — успехи ошибочно убеждают их, что искать других путей не нужно. Это ли нужно подросткам, испытывающим трудности при общении?

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

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

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

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

Оглавление книги