Урок 71. Генерация случайных чисел. Функции srand() и rand()

   ⁄ 

 Обновлено 8 Июл 2017

  ⁄   

Возможность генерировать случайные числа очень полезна в некоторых видах программ, в частности в играх, программах научного или статистического моделирования. Возьмем, например, игры без рандомных (случайных) событий — монстры всегда будут атаковать вас одинаково, вы всегда будете находить одни и те же предметы (или артефакты), макеты темниц, подземелий никогда не будет меняться …, в общем, сюжет такой игры – не очень и вряд ли вы долго будете её наслаждаться.

Так как же генерировать случайные числа? В реальной жизни мы часто бросаем монетку (орел/решка), кости или перетасовываем карты. Эти события включают в себя так много физических переменных (например, сила тяжести, трение, сопротивление воздуха …), что они становятся почти невозможными для прогнозирования или контроля и выдают результаты, которые во всех смыслах случайны.

Однако компьютеры не предназначены для использования физических переменных – они не могут бросить монетку, кости или перетасовать реальные карты. Компьютеры живут в контролируемом электрическом мире, где есть только два значения (false и true), чего-то среднего между ними нет. По своей природе компьютеры предназначены для получения прогнозируемых результатов. Когда мы говорим компьютеру посчитать, сколько будет 2 + 2, мы всегда хотим, чтобы ответ был 4. Не 3 и не 5.

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

Генератор псевдослучайных чисел (ГПСЧ) – это программа, которая принимает стартовое (начальное) число и выполняет с ним определенные математические операции, чтобы преобразовать его в другое число, которое совсем не связанное со стартовым. Затем программа использует это сгенерированное значение и выполняет с ним те же математические операции, что и с начальным числом, чтобы преобразовать его в еще одно другое новое число — третье, которое не связано ни с первым, ни со вторым числом. Применяя этот алгоритм к последнему сгенерированному значению, программа может сгенерировать целый ряд новых чисел, которые будут казаться случайными (при условии, что алгоритм будет достаточно сложным).

На самом деле написать ГПСЧ довольно просто. Вот небольшая программа, которая генерирует 100 рандомных чисел:

Результат:

18256   4675    32406   6217    27484
975     28066   13525   25960   2907
12974   26465   13684   10471   19898
12269   23424   23667   16070   3705
22412   9727    1490    773     10648
1419    8926    3473    20900   31511
5610    11805   20400   1699    24310
25769   9148    10287   32258   12597
19912   24507   29454   5057    19924
11591   15898   3149    9184    4307
24358   6873    20460   2655    22066
16229   20984   6635    9022    31217
10756   16247   17994   19069   22544
31491   16214   12553   23580   19599
3682    11669   13864   13339   13166
16417   26164   12711   11898   26797
27712   17715   32646   10041   18508
28351   9874    31685   31320   11851
9118    26193   612     983     30378
26333   24688   28515   8118    32105

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

Генерация случайных чисел в C++

C (и C++ также) имеет свой собственный встроенный генератор случайных чисел. Он реализован в двух отдельных функциях, которые находятся в заголовочном файле cstdlib:

srand() – устанавливает передаваемое значение пользователем, как стартовое число. srand() следует вызывать только один раз — в начале программы (обычно в верхней части функции main()).

rand() — генерирует следующее случайное число в последовательности. Оно будет из диапазона от 0 до RAND_MAX (константа в cstdlib, значение которой — 32767).

Вот пример программы, использующей эти две функции:

Результат:

14867   24680   8872    25432   21865
17285   18997   10570   16397   30572
22339   31508   1553    124     779
6687    23563   5754    25989   16527
19808   10702   13777   28696   8131
18671   27093   8979    4088    31260
31016   5073    19422   23885   18222
3631    19884   10857   30853   32618
31867   24505   14240   14389   13829
13469   11442   5385    9644    9341
11470   189     3262    9731    25676
1366    24567   25223   110     24352
24135   459     7236    17918   1238
24041   29900   24830   1094    13193
10334   6192    6968    8791    1351
14521   31249   4533    11189   7971
5118    19884   1747    23543   309
28713   24884   1678    22142   27238
6261    12836   5618    17062   13342
14638   7427    23077   25546   21229

Стартовое число и последовательности в ГПСЧ

Если вы запустите программу выше (генерация случайных чисел) нескольких раз, то заметите, что в результате одни и те же числа каждый раз! Это означает, что, хотя каждое число в последовательности кажется случайным относительно предыдущего, вся последовательность не является случайной вообще! А это, в свою очередь, означает, что наша программа полностью предсказуема (одни и те же значения ввода приводят к одним и тем же значениям вывода). Бывают случаи, когда это может быть полезно или даже желательно (например, если вы хотите, чтобы научная симуляция повторялась, или вы пытаетесь отлаживать причины сбоя вашего генератора рандомных подземелий).

Но часто это не то, что нужно. Если вы пишете игру типа hi-lo (где у пользователя есть 10 попыток угадать число, а компьютер говорит ему, насколько его предположения близки или далеки от реального числа), вы бы не хотели, чтобы программа выбирала одни и те же числа каждый раз. Итак, давайте более подробно рассмотрим, почему это происходит, и как это можно исправить.

Помните, что каждое число в последовательности ГПСЧ генерируется из предыдущего определенным способом. Таким образом, при любом начальном числе ГПСЧ всегда будет генерировать одну и ту ​​же последовательность! В программе выше последовательность чисел всегда одинакова, так как стартовое число всегда равно 4541.

Чтобы это исправить нам нужен способ выбрать стартовое число, которое не будет фиксированным значением. Первое, что приходит на ум — использовать рандомное число! Это хорошая мысль, но если нам нужно случайное число для генерации случайных чисел, то это какой-то замкнутый круг, вам не кажется? Оказывается, нам не обязательно использовать случайное стартовое число — нам просто нужно выбрать что-то, что будет меняться каждый раз при новом запуске программы. Затем мы сможем использовать наш ГПСЧ для генерации уникальной последовательности рандомных чисел из этого уникального начального числа.

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

В языке C есть функция time(), которая возвращает время как общее количество секунд от полуночи 1 января 1970 года. Чтобы использовать эту функцию, нам просто нужно подключить заголовок ctime, а затем инициализировать функцию srand() вызовом функции time(0).

Вот та же программа, что выше, но уже с использованием вызова функции time() в качестве начального числа:

Теперь наша программа будет генерировать разные последовательности случайных чисел! Попробуйте сами.

Генерация случайных чисел в заданном диапазоне

В большинстве ситуаций нам не нужны рандомные числа между 0 и RAND_MAX — нам нужны числа между двумя другими значениями — min и max. Например, если нам нужно сымитировать бросок кубика, то диапазон значений будет невелик – от 1 до 6.

Вот небольшая функция, которая конвертирует результат функции rand() в нужный нам диапазон значений:

Чтобы сымитировать бросок кубика — вызываем функцию getRandomNumber(1, 6).

Что такое хороший ГПСЧ?

Как я уже упоминал, генератор случайных чисел, который мы написали выше, не очень хороший. Сейчас мы рассмотрим почему.

Хороший ГПСЧ должен иметь ряд свойств:

Во-первых, ГПСЧ должен генерировать каждое число с примерно одинаковой вероятностью. Это называется равномерностью распределения. Если некоторые числа генерируются чаще, чем другие, то результат программы, использующей ГПСЧ, будет предсказуем!

Например, предположим, вы пытаетесь написать генератор случайных предметов для игры. Вы выбираете случайное число от 1 до 10, и если результатом будет 10, то игрок получит крутой предмет вместо среднего. Шансы будут 1 к 10. Но если ваш ГПСЧ не равномерно генерирует числа, например, 10-тки генерируются чаще, чем должны, то ваши игроки будут получать более редкие предметы чаще, чем предполагалось, и сложность, и интерес к такой игре автоматически снижается.

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

Во-вторых, метод, с помощью которого генерируется следующее число в последовательности, не должен быть очевиден или предсказуем. Например, рассмотрим следующий алгоритм ГПСЧ: num = num + 1. Он абсолютно отвечает в равномерности распределения рандомных чисел, но не очень полезен в качестве таких чисел!

В-третьих, ГПСЧ должен иметь хорошее диапазонное распределение чисел. Это означает, что маленькие, средние и большие числа должны возвращаться случайным образом. ГПСЧ, который возвращает все маленькие числа, а затем все большие – предсказуем и приведет к таким же результатам.

В-четвертых, все ГПСЧ являются циклическими, т.е. в какой-то момент последовательность генерируемых чисел начнет повторяться. Как упоминалось ранее, ГПСЧ являются детерминированными, и с одним значением ввода мы получим одно и то же значение вывода. Подумайте, что произойдет, когда ГПСЧ сгенерирует число, которое уже ранее было сгенерировано. С этого момента начнется дублирование последовательности чисел между первым и следующим появлением этого числа. Длина этой последовательности называется периодом.

Например, вот представлены первые 100 чисел, сгенерированных ГПСЧ с плохой периодичностью:

112   9      130    97    64
31    152    119    86    53
20    141    108    75    42
9     130    97     64    31
152   119    86     53    20
141   108    75     42     9
130   97     64     31   152
119   86     53     20   141
108   75     42      9   130
97    64     31    152   119
86    53     20    141   108
75    42      9    130    97
64    31    152    119    86
53    20    141    108    75
42     9    130     97    64
31   152    119     86    53
20   141    108     75    42
9    130     97     64    31
152  119     86     53    20
141  108     75     42     9

Заметили, что он сгенерировал 9 как второе число, а затем как 16-е. ГПСЧ застревает, генерируя последовательность между этими двумя 9-ми: 9-130-97-64-31-152-119-86-53-20-141-108-75-42- (повтор).

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

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

rand() – это посредственный ГПСЧ

Алгоритм, используемый для реализации rand(), может варьироваться в разных компиляторах, и соответственно результаты также могут быть разными. В большинстве реализаций rand() используется Линейный Конгруэнтный Метод (ЛКМ). Если вы посмотрите на первый пример в этом уроке, то заметите, что там на самом деле используется ЛКМ, хотя и с намеренно подобранными плохими константами.

Одним из основных недостатков rand() является то, что RAND_MAX обычно устанавливается как 32767 (15-битное значение). Это означает, что если вы захотите сгенерировать числа в более широком диапазоне (например, 32-битные целые числа), функция rand() не подойдет. Кроме того, она не подойдет, если вы захотите сгенерировать случайные числа типа с плавающей запятой (например, между 0.0 и 1.0), что часто используется при статистическом моделировании. Наконец, rand() имеет относительно короткий период по сравнению с другими алгоритмами.

Тем не менее, он отлично подходит для изучения программирования и для программ, в которых высококлассный ГПСЧ не является необходимостью.

Для приложений, где требуется высококлассный ГПСЧ, я бы рекомендовал использовать алгоритм Вихрь Мерсенна (Mersenne Twister), который производит отличные результаты и относительно прост в использовании.

Заметка для пользователей Visual Studio

Реализация rand() в Visual Studio имеет один существенный недостаток — первое генерируемое случайное число не сильно отличается от стартового. Это означает, что при использовании time() для определения начального числа, первое число не будет сильно отличатся или изменяться и при следующих прогонах от стартового.

Однако есть простое решение: вызовите функцию rand() один раз и сбросьте результат. Затем вы сможете использовать rand() как обычно в вашей программе.

Отладка программ, использующих случайные числа

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

Поэтому при отладке полезно использовать в качестве стартового числа (через srand()) определенное значение (например, 0), которое вызовет ошибочное поведение программы. Это будет гарантировать, что наша программа каждый раз генерирует одни и те же результаты (что значительно облегчит отладку). После того, как мы найдем и исправим ошибку, мы сможем снова использовать системные часы для генерации рандомных результатов.

Рандомные числа в C++ 11

C++ 11 добавила тонну функциональности в генерации случайных чисел в стандартную библиотеку C++, включая алгоритм Вихрь Мерсенна, а также генераторы различных видов (равномерные, Poisson и т. д.). Доступ к ним осуществляется через подключение заголовочного файла <random>.

Вот пример генерации случайных чисел в C++ 11 через Вихрь Мерсенна:

Вихрь Мерсенна генерирует случайные 32-битные целые числа unsigned (не 15-битные целые числа, как в случае с rand()), что позволяет использовать гораздо больший диапазон значений. Существует также версия (std::mt19937_64) для генерации 64-битных целых чисел unsigned!

В <random> так много функциональности, что упомянуть об этом только в одном уроке было бы непростительно. Поэтому более подробно о <random> мы поговорим еще в следующих уроках.

Оценить статью:

Звёзд: 1Звёзд: 2Звёзд: 3Звёзд: 4Звёзд: 5 (11 оценок, среднее: 5,00 из 5)
Загрузка...
Поделиться в:
Подписаться на обновления:

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *