Теги: си рандом, си случайные числа, генерация случайных чисел, ГСЧ, псевдослучайные числа, метод монте-карло
Псевдослучайные числа
Г енерация псевдослучайных чисел – это сложная математическая задача. Данная статья не ставит перед собой задачи охватить эту тему. Далее понятие «случайное число» будет означать псевдослучайное, если это не оговорено особо.
С примерами использования случайных чисел вы сталкиваетесь повсюду. Псевдослучайные числа используются в дизайне и графике, для генерации уровней в компьютерных играх и симулирования ИИ. Наборы случайных чисел используются в математических алгоритмах (см. Методы Монте-Карло).
Очевидно, что задача генерации случайных чисел на классическом процессоре не может быть решена, так как работа компьютера детерминирована по определению. Тем не менее, можно сгенерировать очень длинные наборы чисел такие, что их распределение будет иметь те же свойства, что и наборы истинно случайных чисел.
Важно, что для решения той или иной задачи необходимо правильно выбирать генератор, или как минимум знать его свойства. Например, при моделировании физического процесса можно получить совершенно разные и часто неверные результаты, в зависимости от выбора генератора случайных чисел.
Посмотрим стандартный генератор.
#include
Для начала необходимо инициализировать генератор случайных чисел (ГСЧ, или RNG - random number generator), задать зерно – seed, на основе которого в дальнейшем будет происходить генерация. Важно, что для одного и того же начального значения генератор будет возвращать одни и те же числа.
Srand(42);
Присваиваем переменной r случайное значение
R = rand();
Значение будет лежать в диапазоне от 0 до RAND_MAX.
Для того, чтобы при следующем запуске получить новый набор чисел, нужно инициализировать генератор каждый раз разными значениями. Например, можно использовать системной время:
Srand(time(NULL));
Srand(_getpid());
Функция getpid библиотеки process.h возвращает идентификатор процесса (можно также использовать getpid, не POSIX версию функции).
Центральная Предельная Теорема
Очень важно сразу напомнить или познакомить с центральной предельной теоремой. Неформальное определение – распределение суммы слабо зависимых случайных величин стремится к нормальному. Пальцеобразное объяснение: если сложить несколько случайных величин, независимо от их распределения, то распределение суммы будет нормальным. Часто можно увидеть такой код
#include
Генерация случайных чисел на заданном отрезке
Во-первых, получим случайное число от нуля до единицы:
Const float RAND_MAX_F = RAND_MAX; float get_rand() { return rand() / RAND_MAX_F; }
Для получения числа в отрезке от нуля до N умножим N на случайное число от нуля до единицы. Для получения случайного числа от M До N, сдвинем полученное число на M.
Float get_rand_range(const float min, const float max) { return get_rand() * (max - min) + min; }
Для получения целого числа, будем брать остаток от деления на длину интервала. Но остаток от деления будет возвращать число на единицу меньше, чем наш интервал, поэтому увеличим его на единицу:
Int get_rand_range_int(const int min, const int max) { return rand() % (max - min + 1) + min; }
Пример использования случайных чисел для вычисления интеграла. Пусть у нас есть некоторая гладкая функция от одной переменной. Ограничим её квадратом от a до b, и от 0 до некоторой точки, которая заведомо больше нашей функции.
Будем случайным образом кидать точки на нашем квадрате. Если они лежат выше функции (на рисунке изображены зелёными крестиками), то отнесём их к первой группе A, если ниже функции (на рисунке красные), то отнесём их ко второй группе B. Положение точек случайное и распределено равномерно (т.к. стандартный генератор даёт равномерное распределение. Этот простой пример, кстати, уже показывает, насколько важно знать свойства ГСЧ). Тогда отношение красных точек к общему числу точек будет равно отношению площади под графиком к общей площади. А общая площадь – это квадрат (b-a) на q.
Src="/images/c_random_integral.png" alt="Всё, что случайно попадает выше нашей функции - зелёное, всё что ниже - красное.
Отношение зелёного к красному будет равно отношению площади над графиком к площади под графиком."> Всё, что случайно попадает выше нашей функции - зелёное, всё что ниже - красное.
Отношение зелёного к красному будет равно отношению площади над графиком к площади под графиком.
Применим наши выкладки – найдём интеграл функции x^2 на отрезке от 0 до двух двумя способами.
#include
Поиграйте со значением ROUNDS, измените его и посмотрите, как меняется точность вычислений.
Генерация истинно случайных чисел
Для генерации настоящих случайных чисел используют генераторы, основанные на каких-то случайных физических процессах. Например, на тепловых шумах, на подсчёте числа делений радиоактивного вещества, на атмосферных шумах и т.п. Недостаток таких генераторов – низкая скорость работы (количество сгенерированных чисел в секунду) ; конечно, такие генераторы обычно являются отдельным устройством.
В обучающих алгоритмических задачках довольно часто встречается необходимость генерации случайных целых чисел. Конечно, можно получать их от пользователя, но с заполнением массива случайными числами в количестве 100 штук могут возникнуть проблемы.
На помощь нам приходит функция стандартной библиотеки языка Си (не C++) rand() .
int rand (void);
Она генерирует псевдослучайное целое число на интервале значений от 0 до RAND_MAX . Последнее является константой, которая варьируется в зависимости от реализации языка, но в большинстве случаев составляет 32767.
А что если нам нужны случайные числа от 0 до 9? Типичный выход из ситуации — использование операции деления по модулю.
Если нам нужны числа от 1 (а не от 0) до 9, то можно прибавить единичку…
Идея такая: генерируем случайное число от 0 до 8, и после прибавления 1 оно превращается в случайное число от 1 до 9.
И последнее, самое печальное.
К сожалению, функция rand() генерирует псевдослучайные числа, т.е. числа, которые кажутся случайными, но на самом деле являются последовательностью значений, вычисленных по хитрому алгоритму, в качестве параметра принимающему так называемое зерно (seed). Т.е. сгенерированные функцией rand() числа будут зависеть от значения, которое имеет зерно в момент ее вызова. А зерно всегда устанавливается компилятором в значение 1. Иными словами, последовательность чисел будет хоть и псевдослучайной, но всегда одинаковой.
А это не то, что нам надо.
Исправить ситуацию помогает функция srand() .
void srand (unsigned int seed);
Она устанавливает зерно равным значению параметра, с которым была вызвана. И последовательность чисел тоже будет другая.
Но проблема осталась. Как сделать случайным зерно, ведь от него все зависит?
Типичный выходит из ситуации — использование функции time() .
time_t time (time_t* timer);
Она тоже досталась в наследство от языка Си и, будучи вызвана с нулевым указателем в качестве параметра, возвращает количество секунд, прошедших с 1 января 1970 года. Нет, это не шутка.
Теперь значение этой функции мы можем передать в функцию srand() (при этом выполняется неявное приведение типа), и у нас будет замечательное случайное зерно.
И числа будут замечательные и неповторяющиеся.
Для использования функций rand() и srand() нужно подключить заголовочный файл
Вот полноценный пример.
#include
#include
#include
using namespace std;
int main()
{
cout << "10 random numbers (1..100): " << endl;
srand(time(NULL));
for(int i=0;i<10;i++) cout << rand() % 100 + 1 << " ";
cin.get();
return 0;
}
Пожалуйста, приостановите работу AdBlock на этом сайте.
Иногда может возникнуть необходимость в генерации случайных чисел. Простой пример.
Пример: Определение победителя в конкурсе репостов.
Имеется список из 53 человек. Необходимо выбрать из них победителя. Если вы выберете его самостоятельно, то вас могут обвинить в предвзятости. Поэтому вы решили написать программу. Она будет работать следующим образом. Вы вводите количество участников N , после чего программа выводит одно число – номер победителя.
Как получить число от игрока, вам уже известно. А вот как заставить компьютер загадать случайное число? В этом уроке вы этому научитесь.
Функция rand().
Данная функция возвращает случайное целое число в диапазоне от нуля до RAND_MAX . RAND_MAX это специальная константа языка Си, в которой содержится максимальное целое число, которое может быть возвращено функцией rand() .
Функция rand() определена в заголовочном файле stdlib.h . Поэтому, если хотите использовать rand в своей программе, не забудьте подключить этот заголовочный файл. Константа RAND_MAX тоже определена в этом файле. Вы можете найти этот файл у себя на компьютере и посмотреть её значение.
Давайте посмотрим на эту функцию в действии. Запустим следующий код:
Листинг 1.
#include
Должно получиться что-то вроде этого.
Рис.1 Пять случайных чисел, сгенерированных функцийе rand
Но нам бы хотелось получить числа от 1 до 53 , а не всё подряд. Ниже описано несколько трюков, позволяющих наложить ограничения на функцию rand() .
Ограничить случайные числа сверху.
Кто в школе ждал момента, когда ему пригодится математика, приготовьтесь. Этот момент наступил. Чтобы ограничить сверху случайные числа, можно воспользоваться операцией получения остатка от деления, которую вы изучили в прошлом уроке. Наверное вы знаете, что остаток от деления на числа K всегда меньше числа K . Например, при делении на 4 могут получиться остатки 0, 1, 2 и 3 . Поэтому если вы хотите ограничить сверху случайные числа числом K , то просто возьмите остаток от деления на K . Вот так:
Листинг 2.
#include
Рис.2 Пять случайных чисел меньше 100
Ограничить числа снизу.
Функция rand возвращает случайные числа из отрезка . А что если нам нужны только числа большие числа M (например, 1000 )? Как быть? Всё просто. Просто прибавим к тому, что вернула функция rand, наше значение M . Тогда если функция вернёт 0 , итоговый ответ будет M , если 2394 , то итоговый ответ будет M + 2394 . Этим действием мы как бы сдвигаем все числа на M единиц вперёд.
Задать границы функции rand сверху и снизу.
Например, получить числа от 80 до 100 . Кажется, нужно просто объединить два способа, которые приведены выше. Получим что-то вроде этого:
Листинг 3.
#include
Попробуйте запустить эту программу. Удивлены?
Да, такой способ работать не будет. Давайте прокрутим эту программу руками, чтобы убедиться в том, что мы допустили ошибку. Допустим rand() вернула число 143 . Остаток от деления на 100 равен 43 . Дальше 80 + 43 = 123 . Значит такой способ не работает. Подобная конструкция выдаст числа от 80 до 179 .
Давайте разберём по действиям наше выражение.
rand()%100
может выдать числа от 0
до 99
включительно. Т.е. из отрезка
.
Операция + 80
сдвигает наш отрезок на 80
единиц вправо. Получаем
.
Как видим, проблема у нас заключается в правой границе отрезка, она сдвинута вправо на 79
единиц. Это наше исходное число 80
минус 1
. Давайте наведём порядок и сдвинем правую границу назад: 80 + rand()%(100 - 80 + 1)
. Тогда всё должно сработать как надо.
В общем случае если нам нужно получить числа из отрезка
, то необходимо воспользоваться следующей конструкцией:
A + rand()%(B-A+1)
.
Согласно этой формуле перепишем нашу последнюю программу:
Листинг 4.
#include
Результат работы:
Рис.3 Случайные числа из диапазона
Ну вот, теперь вы можете решить исходную задачу урока. Сгенерировать число из отрезка . Или не можете?
Но прежде ещё немного полезной информации. Запустите последнюю программу три раза подряд и записывайте себе случайные числа, которые она генерирует. Заметили?
Функция srand().
Да, каждый раз появляются одни и те же одинаковые числа. «Так себе генератор!» – скажете вы. И будете не совсем правы. Действительно, генерируются всё время одинаковые числа. Но мы можем на это повлиять, для этого используется функция srand() , которая также определена в заголовочном файле stdlib.h . Она инициализирует генератор случайных чисел начальным числом.
Скомпилируйте и запустите несколько раз вот эту программу:
Листинг 5.
#include
Теперь поменяйте аргумент функции srand() на другое число (надеюсь вы ещё не забыли, что такое аргумент функции?) и снова скомпилируйте и запустите программу. Последовательность чисел должна измениться. Как только мы меняем аргумент в функции srand – меняется и последовательность. Не очень практично, не правда ли? Чтобы изменить последовательность, нужно перекомпилировать программу. Вот бы это число туда подставлялось автоматически.
И это можно сделать. Например, воспользуемся функцией time() , которая определена в заголовочном файле time.h . Данная функция, если ей в качестве аргумента передать NULL , возвращает количество секунд, прошедших c 1 января 1970 года . Вот посмотрите, как это делается.
Листинг 6.
#include
Вы спросите, а что такое NULL ? Резонный вопрос. А я вам пока отвечу, что это специальное зарезервированное слово такое. Могу ещё сказать, что им обозначает нулевой указатель, но т.к. это для вас никакой информации не несёт, то на данный момент рекомендую об этом не думать. А просто запомнить как некоторый хитрый трюк. В будущих уроках мы остановимся на этой штуке поподробнее.
Очень часто в программах возникает необходимость использования случайных чисел - от заполнения массива до криптографии. Для получения последовательности случайных чисел в языке C# имеется класс Random . Этот класс предусматривает два конструктора:
- Random () - инициализирует экземпляр класса Random с помощью начального значения, зависящего от текущего времени. Как известно, время может быть представлено в тиках - 100-наносекундных импульсах, начиная с 1 января 0001 года. И значение времени в тиках представляет собой 64-битное целое число, которое и будет использоваться для инициализации экземпляра генератора случайных чисел.
- Random (Int32 ) - инициализирует экземпляр класса Random с помощью указанного начального значения. Такая инициализация генератора случайных чисел может быть удобна на этапе отладки программы, поскольку в этом случае при каждом запуске программы будут генерироваться одни и те же "случайные" числа.
- Next() - возвращает случайное целое неотрицательное число формата Int32 .
- Next(Int32 ) - возвращает случайное целое неотрицательное число, которое меньше указанного значения.
- Next(Int32
min, Int32
max)
- возвращает случайное целое число в указанном диапазоне. При этом должно соблюдаться условие min
- NextBytes(Byte ) - заполняет элементы указанного массива байтов случайными числами.
- NextDouble()
- возвращает случайное число с плавающей запятой, в диапазоне )
break ; // совпадение найдено, элемент не подходит
}
if (j == i)
{ // совпадение не найдено
a[i] = num; // сохраняем элемент
i++; // переходим к следующему элементу
}
}
for (int i = 0; i < 100; i++)
{
if (i % 10 == 9)
Console .WriteLine();
}
Console .ReadKey();
}
}
}
Однако чем ближе к концу массива, тем больше генераций необходимо производить для получения неповторяющегося значения.
Следующий пример отображает количество вызовов метода Next() для получения каждого элемента, а также общее количество сгенерированных случайных чисел для заполнения массива из 100 элементов неповторяющимися значениями.1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53using System;
void Main(string args)
namespace MyProgram
{
class Program
{
static void Main(string args)
{
Random rnd = new Random ();
int a = new int ; // массив элементов
int count = new int ; // массив количества генераций
a = rnd.Next(0, 101);
int c = 0; // счетчик количества генераций
count = 1; // a генерируется только 1 раз
for (int i = 1; i < 100;)
{
int num = rnd.Next(0, 101);
c++; // сгенерировали элемент еще один раз
int j;
for (j = 0; j < i; j++)
{
if (num == a[j])
break ;
}
if (j == i)
{
a[i] = num; i++;
count[i] = c; c = 0; // сохраняем количество генераций
}
}
// Вывод значений элементов
Console .WriteLine("Значения элементов" );
for (int i = 0; i < 100; i++)
{
Console .Write("{0,4} " , a[i]);
if (i % 10 == 9)
Console .WriteLine();
}
Console .WriteLine();
// Вывод количества генераций
Console .WriteLine("Количество генераций элементов" );
int sum = 0;
for (int i = 0; i < 100; i++)
{
sum += count[i];
Console .Write("{0,4} " , count[i]);
if (i % 10 == 9)
Console .WriteLine();
}
Console .WriteLine("Общее количество генераций - {0}" , sum);
Console .ReadKey();
}
}
}
{
Random rnd = new Random ();
int a = new int ;
for (int i = 0; i < 100; i++)
a[i] = i;
for (int i = 0; i < 50; i++)
{
int i1 = rnd.Next(0, 100); // первый индекс
int i2 = rnd.Next(0, 100); // второй индекс
// обмен значений элементов с индексами i1 и i2
int temp = a;
a = a;
a = temp;
}
Console .WriteLine("Значения элементов" );
for (int i = 0; i < 100; i++)
{
Console .Write("{0,4} " , a[i]);
if (i % 10 == 9)
Console .WriteLine();
}
Console .ReadKey();
}
}
}
Перемешивание значений является более эффективным если диапазон значений совпадает с их количеством (или близок к нему), поскольку в этом случае значительно сокращается количество генераций случайных элементов.
У нас есть последовательность чисел, состоящая из практически независимых элементов, которые подчиняются заданному распределению. Как правило, равномерному распределению.
Сгенерировать случайные числа в Excel можно разными путями и способами. Рассмотрим только лучше из них.
Функция случайного числа в Excel
- Функция СЛЧИС возвращает случайное равномерно распределенное вещественное число. Оно будет меньше 1, больше или равно 0.
- Функция СЛУЧМЕЖДУ возвращает случайное целое число.
Рассмотрим их использование на примерах.
Выборка случайных чисел с помощью СЛЧИС
Данная функция аргументов не требует (СЛЧИС()).
Чтобы сгенерировать случайное вещественное число в диапазоне от 1 до 5, например, применяем следующую формулу: =СЛЧИС()*(5-1)+1.
Возвращаемое случайное число распределено равномерно на интервале .
При каждом вычислении листа или при изменении значения в любой ячейке листа возвращается новое случайное число. Если нужно сохранить сгенерированную совокупность, можно заменить формулу на ее значение.
- Щелкаем по ячейке со случайным числом.
- В строке формул выделяем формулу.
- Нажимаем F9. И ВВОД.
Проверим равномерность распределения случайных чисел из первой выборки с помощью гистограммы распределения.
Диапазон вертикальных значений – частота. Горизонтальных – «карманы».
Функция СЛУЧМЕЖДУ
Синтаксис функции СЛУЧМЕЖДУ – (нижняя граница; верхняя граница). Первый аргумент должен быть меньше второго. В противном случае функция выдаст ошибку. Предполагается, что границы – целые числа. Дробную часть формула отбрасывает.
Пример использования функции:
Случайные числа с точностью 0,1 и 0,01:
Как сделать генератор случайных чисел в Excel
Сделаем генератор случайных чисел с генерацией значения из определенного диапазона. Используем формулу вида: =ИНДЕКС(A1:A10;ЦЕЛОЕ(СЛЧИС()*10)+1).
Сделаем генератор случайных чисел в диапазоне от 0 до 100 с шагом 10.
Из списка текстовых значений нужно выбрать 2 случайных. С помощью функции СЛЧИС сопоставим текстовые значения в диапазоне А1:А7 со случайными числами.
Воспользуемся функцией ИНДЕКС для выбора двух случайных текстовых значений из исходного списка.
Чтобы выбрать одно случайное значение из списка, применим такую формулу: =ИНДЕКС(A1:A7;СЛУЧМЕЖДУ(1;СЧЁТЗ(A1:A7))).
Генератор случайных чисел нормального распределения
Функции СЛЧИС и СЛУЧМЕЖДУ выдают случайные числа с единым распределением. Любое значение с одинаковой долей вероятности может попасть в нижнюю границу запрашиваемого диапазона и в верхнюю. Получается огромный разброс от целевого значения.
Нормальное распределение подразумевает близкое положение большей части сгенерированных чисел к целевому. Подкорректируем формулу СЛУЧМЕЖДУ и создадим массив данных с нормальным распределением.
Себестоимость товара Х – 100 рублей. Вся произведенная партия подчиняется нормальному распределению. Случайная переменная тоже подчиняется нормальному распределению вероятностей.
При таких условиях среднее значение диапазона – 100 рублей. Сгенерируем массив и построим график с нормальным распределением при стандартном отклонении 1,5 рубля.
Используем функцию: =НОРМОБР(СЛЧИС();100;1,5).
Программа Excel посчитала, какие значения находятся в диапазоне вероятностей. Так как вероятность производства товара с себестоимостью 100 рублей максимальная, формула показывает значения близкие к 100 чаще, чем остальные.
Перейдем к построению графика. Сначала нужно составить таблицу с категориями. Для этого разобьем массив на периоды:
На основе полученных данных сможем сформировать диаграмму с нормальным распределением. Ось значений – число переменных в промежутке, ось категорий – периоды.
