Урок №71. Генерация случайных чисел

  Юрий  | 

  Обновл. 15 Сен 2020  | 

 123143

 ǀ   32 

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

Генератор псевдослучайных чисел

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

Однако компьютеры не предназначены для использования физических переменных — они не могут подбросить монетку, бросить кости или перетасовать реальные карты. Компьютеры живут в контролируемом электрическом мире, где есть только два значения (true и false), чего-то среднего между ними нет. По своей природе компьютеры предназначены для получения прогнозируемых результатов. Когда мы говорим компьютеру посчитать, сколько будет 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

Каждое число кажется случайным по отношению к предыдущему. Главный недостаток этого алгоритма — его примитивность.

Функции srand() и rand()


Языки Cи и C++ имеют свои собственные встроенные генераторы случайных чисел. Они реализованы в 2-х отдельных функциях, которые находятся в заголовочном файле 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: ГПСЧ должен генерировать каждое новое число с примерно одинаковой вероятностью. Это называется равномерностью распределения. Если некоторые числа генерируются чаще, чем другие, то результат программы, использующей ГПСЧ, будет предсказуем! Например, предположим, вы пытаетесь написать генератор случайных предметов для игры. Вы выбираете случайное число от 1 до 10, и, если результатом будет 10, игрок получит крутой предмет вместо среднего. Шансы должны быть 1 к 10. Но, если ваш ГПСЧ неравномерно генерирует числа, например, десятки генерируются чаще, чем должны, то ваши игроки будут получать более редкие предметы чаще, чем предполагалось, и сложность, и интерес к такой игре автоматически уменьшаются.

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

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

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

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

Например, вот представлены первые 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, как второе число, а затем как шестнадцатое? ГПСЧ застревает, генерируя последовательность между этими двумя 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»), который генерирует отличные результаты и относительно прост в использовании.

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

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

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

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


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

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

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

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

Звёзд: 1Звёзд: 2Звёзд: 3Звёзд: 4Звёзд: 5 (300 оценок, среднее: 4,80 из 5)
Загрузка...

Комментариев: 32

  1. Аватар winnie:

    Во-первых абсолютно не понятна логика работы этого распределения, было бы не плохо пояснить. Во-вторых я написал код в котором два массива заполняются количеством выпавших вариантов рандома, используя вышеприведенную функцию, а так же способом rand()%max+min. И как показала статистика на 10000 итераций (с разными диапазонами, я пробовал и 1-100, 1-5, 1-10, 1-6) количество выпаданий каждого числа диапазона примерно одинаково в обоих вариантах с точностью +- 10%. Так же пробовал и на маленьком количестве итераций. например с диапазоном 1-10 делал 10 итераций, или как в примере, 1-6 — 10 итераций. Вариативность плюс-минус одинаковая. И один и другой способ возвращает зачастую по 3 повторения одного и того-же числа.
    Короче, суть всего выше написанного в том, что я не понимаю и не вижу смысла применять вариант

    вместо

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

  2. Аватар Дарья:

    Подскажите, пожалуйста, а как можно сгенерировать случайные числа так, чтобы среди них были и отрицательные в том числе?

    1. Аватар Геннадий:

      использовать uniform_int_distribution<> "любое имя"("нужный диапазон")

  3. Аватар Влад:

    Подскажите обязательно ли подключать библиотеку cstdlib для rand.
    В Visual Studio и CodeBlocks достаточно подключить iostream чтобы rand заработал.
    Или в iostream уже подулючена cstdlib?

    1. Аватар Ruslan:

      Присоединяюсь к вопросу, аналогично:
      с функцией time () нужно ли подключать <ctime>,
      с функцией exit () нужно ли подключать <cstdlib>,
      с функцией sqrt () нужно ли подключать <cmath>,
      т.к. компилируется без предупреждений, работают и без этих заголовочных файлов? (впрочем как и с ними).
      Нужно ли указывать перед этими функциями std:: ( работает и с указанием и без) ?
      Компилятор g++.

      1. Аватар Я:

        Да, в <iostream> уже подключены все эти либи (не во всех IDE). А на счёт пространства имён (std::) то если вы его юзали (using namespace std) то, тогда не нужно каждый раз писать std::. Но юзать std:: не оч хорошо — могут возникать конфликты имён с другими либами. Да и вообще, лучше стараться держать глобальную область видимости как можно чище.

  4. Аватар nickatin:

    Очень крутой сайт!!! Автору огромное спасибо за труды. Дошел до 6 главы занятий, все понятно но не много не понял курс с генерацией случайных чисел, какие то сложные алгоритмы))
    Вопрос вот написал маленький код для случайных чисел кубика от 1 до 6, в чем он плох, распределение будет ужасное? Прошу посмотреть и прокомментировать)

    1. Аватар Максим:

      Здесь уже задавали вопрос про "рандом от остатка", но так никто и не ответил.
      На мой (ученический) глаз рандом у чисел получается хороший.

      Набросал программку для определения распределения случайных чисел от 0 до 10.
      Чем больше выставлять количество итераций, тем равномернее получается распределение чисел.

      1. Аватар Олег:

        Похоже, массивы еще не изучали…

    2. Аватар RexStar:

      Главное здесь скорость… Операции деления и остатка "весят" на порядок выше других математических операций (не всех 🙂 )

  5. Аватар Furxie Fluke:

    Придумал функцию конвертации рандомного числа в диапазон значений чуть проще, без константной переменной и нескольких лишних вычислений
    Пытался просто придумать сам как это реализовать математически, не смотря на пример в задании, и придумав — сравнил, был рад увидеть что итоги схожи ) Но ещё более рад был увидеть что придумал функцию попроще, с одинаковым функционалом :3

    *0.999 — потому что если без неё то шестёрка будет выпадать только примерно раз в 32767 раз (в среднем), когда рандомное значение достигнет своей границы. А это не то что нам нужно.
    Не 1.0 — потому что тогда помимо шестёрки будет так же (хоть и редко) выпадать 7, тоже в среднем раз в 32767 раз, этого тоже стоит избегать.
    Поэтому "идеальный" вариант 0.999, — потому что даже при максимальном значении рандомного числа (32767), получится 6.999, что округлится к 6. И так же не будет потерян диапазон вероятности выпадения шестёрки, тоесть шанс её выпадения не уменьшится, ну.. разве что на 0.001 %, что вроде не столь значимо, и если добавить ещё девяток — будет ещё меньше

  6. Аватар zashiki:

    а чем для диапазона малых значений(от 1 до 6 и тд) хуже рандом от остатка, чем рандом с округлением дроби?

    К примеру, вот так пытаюсь, выходит норм

  7. Аватар Лев:

    Получилось добавить возможность указывать количество чисел, строк, min, max. Но главное, что это работает с Вихрем Мерсенна!)
    Хотел спросить, не допустил ли каких-то потенциальных ошибок?

  8. Аватар Алексей:

    При генерации через системные часы первое число всегда будет одинаковым? Или я не так что-то сделал?

    1. Аватар Onium:

      Нужно сбросить rand(). Как написано в последнем абзаце урока.

  9. Аватар Денис:

    Функция для вывода рандомных чисел! Работает хорошо, результат не повторяется! можно не делать 2 переменные для цикла, я сделал для оформления, но так даже надёжней (не точно) 🙂
    P.S. Если использовать "srand(static_cast<unsigned int> (time(0)));", результат в цикле очень схожий.

    1. Аватар Борис:

      1) Что за "GetRandomNum"?
      2) Выравнивание для аккуратности реализовано похабно. Можно сделать гораздо проще и лаконичнее (подсказка: использовать функцию длины строки, хотя есть и другие варианты).

  10. Вячеслав Вячеслав:

    Вот так у меня получилась прога с случайным броском кубика:

  11. Аватар Dagon:

    Как сделать диапазон для Мерсенна?!Спасибо.

  12. Аватар Oleksiy:

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

    Не понятно, как происходит конвертация. Там идет округление конечного результата? Когда в знаменателе стоит выражение:
    (static_cast<double>(RAND_MAX) + 1.0)
    то при rand() = RAND_MAX выражение (rand() * fraction * (max — min + 1) + min) не даст "чистую" шестерку. Этот алгоритм основан на том, что int max намного меньше RAND_MAX?

  13. Аватар Эдуард:

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

    Не понимаю как реализовать сброс результата.

    1. Юрий Юрий:

      Просто вызвать rand() в начале функции main():

      А затем, когда уже будет нужно сгенерировать число — опять вызвать rand(). Таким образом у вас будет 2 вызова rand(), первый из которых будет выполнять сброс.

  14. Аватар Алексей:

    А что такого плохого в генерации числа близкого к начальному в Visual Studio, оно все равно генерируется от миллионов секунд. Обычный пользователь вряд ли будет их высчитывать.

    1. Юрий Юрий:

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

  15. Аватар Герман:

    С математикой все ясно. Не совсем ясен алгоритм работы программы:

    Почему в каждой итерации цикла функция PRNG() возвращает разные значения?

    1. Юрий Юрий:

      Так ведь в комментариях это объясняется. 4541, 8253729, 2396403, 32768 — это большие числа и переменная seed типа unsigned int не сможет хранить столь большое число, которое получится после выполнения всех арифметических операций с seed — произойдет переполнение переменной и мы получим какое-то вообще левое число. И так будет со всеми 99-тью следующими числами. Алгоритм построен на переполнении переменной.

      1. Аватар Герман:

        То что алгоритм построен на переполнении переменной это понятно, не понятно другое, как влияет на значение переменной Static, ведь после каждой итерации цикла значение seed разное, а убрав у переменной атрибут static- все 100 значений переменной становиться одинаковое!

        1. Юрий Юрий:

          Ключевое слово static делает переменную статической — её значение сохраняется за пределами блока, в котором она определена и используется. После выхода из блока её значение не уничтожается, а сохраняется. Область видимости такой переменной уже не локальная, а статическая. Смотрите урок 51.

        2. Аватар Дасти:

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

  16. Аватар Герман:

    Уважаемый автор, не совсем ясно как работает инкремент переменной seed в данном фрагменте при итерациях цикла FOR.

    1. Юрий Юрий:

      Конкретизируйте ваш вопрос — что именно непонятно? Здесь выполнение арифметических операторов, не больше. Умножение, сложение и остаток.

      1. Аватар Игорь:

        Может он имел в виду то, что если функция постоянно вызывается циклом то почему переменной seed заново не присваивается значение 4541. А как я понимаю, суть как раз в статической переменной, которая после первой инициации, второй раз уже её игнорит.

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

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