Очень часто в программах возникает необходимость использования случайных чисел - от заполнения массива до криптографии. Для получения последовательности случайных чисел в языке C# имеется класс Random . Этот класс предусматривает два конструктора:
Однако чем ближе к концу массива, тем больше генераций необходимо производить для получения неповторяющегося значения.
Следующий пример отображает количество вызовов метода 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
53
using
System;
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();
}
}
}
Перемешивание значений является более эффективным если диапазон значений совпадает с их количеством (или близок к нему), поскольку в этом случае значительно сокращается количество генераций случайных элементов.
Теги: си рандом, си случайные числа, генерация случайных чисел, ГСЧ, псевдослучайные числа, метод монте-карло
Г енерация псевдослучайных чисел – это сложная математическая задача. Данная статья не ставит перед собой задачи охватить эту тему. Далее понятие «случайное число» будет означать псевдослучайное, если это не оговорено особо.
С примерами использования случайных чисел вы сталкиваетесь повсюду. Псевдослучайные числа используются в дизайне и графике, для генерации уровней в компьютерных играх и симулирования ИИ. Наборы случайных чисел используются в математических алгоритмах (см. Методы Монте-Карло).
Очевидно, что задача генерации случайных чисел на классическом процессоре не может быть решена, так как работа компьютера детерминирована по определению. Тем не менее, можно сгенерировать очень длинные наборы чисел такие, что их распределение будет иметь те же свойства, что и наборы истинно случайных чисел.
Важно, что для решения той или иной задачи необходимо правильно выбирать генератор, или как минимум знать его свойства. Например, при моделировании физического процесса можно получить совершенно разные и часто неверные результаты, в зависимости от выбора генератора случайных чисел.
Посмотрим стандартный генератор.
#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, измените его и посмотрите, как меняется точность вычислений.
Для генерации настоящих случайных чисел используют генераторы, основанные на каких-то случайных физических процессах. Например, на тепловых шумах, на подсчёте числа делений радиоактивного вещества, на атмосферных шумах и т.п. Недостаток таких генераторов – низкая скорость работы (количество сгенерированных чисел в секунду) ; конечно, такие генераторы обычно являются отдельным устройством.
Перевод статьи Random numbers широко известного в узких кругах Джона Скита. Остановился на этой статье, так как в своё время сам столкнулся с описываемой в ней проблемой.
Просматривая темы по .NET и C# на сайте StackOverflow, можно увидеть бесчисленное множество вопросов с упоминанием слова «random», в которых, по сути, поднимается один и тот же извечный и «неубиваемый» вопрос: почему генератор случайных чисел System.Random «не работает» и как это «исправить». Данная статья посвящена рассмотрению данной проблемы и способов её решения.
Я использую Random.Next для генерации нескольких случайных чисел, но метод возвращает одно и то же число при его множественных вызовах. Число меняется при каждом запуске приложения, однако в рамках одного выполнения программы оно постоянное.
Все «внутренности» работы класса Random полностью детерминистичны . Это значит, что если вы возьмёте несколько экземпляров класса Random с одинаковым начальным состоянием, которое задаётся через параметр конструктора seed , и для каждого экземпляра вызовите определённые методы в одинаковом порядке и с одинаковыми параметрами, то в конце вы получите одинаковые результаты.
Так что ж плохого в вышеприведённом коде? Плохо то, что мы используем новый экземпляр класса Random внутри каждой итерации цикла. Конструктор Random, не принимающий параметров , принимает значение текущей даты и времени как seed (начальное состояние). Итерации в цикле «прокрутятся» настолько быстро, что системное время «не успеет измениться» по их окончании; таким образом, все экземпляры Random получат в качестве начального состояния одинаковое значение и поэтому возвратят одинаковое псевдослучайное число.
Сравним это с ранее рассматриваемым классом Random. Предположим, вы вызвали Random.Next(100) десять раз и сохранили результаты. Если вы имеете достаточно вычислительной мощи, то можете сугубо на основании этих результатов вычислить начальное состояние (seed), с которым был создан экземпляр Random, предсказать следующие результаты вызова Random.Next(100) и даже вычислить результаты предыдущих вызовов метода. Такое поведение катастрофически неприемлемо, если вы используете случайные числа для обеспечения безопасности, в финансовых целях и т.д. КриптоГСЧ работают существенно медленнее класса Random, но генерируют последовательность чисел, каждое из которых более независимо и непредсказуемо от значений остальных.
В большинстве случаев более низкая производительность не является препятствием - им является плохой API. RandomNumberGenerator создан для генерации последовательностей байтов - и всё. Сравните это с методами класса Random, где есть возможность получения случайного целого числа, дробного числа, а также набора байтов. Ещё одно полезное свойство - возможность получения случайного числа в указанном диапазоне. Сравните эти возможности с массивом случайных байтов, который выдаёт RandomNumberGenerator. Исправить ситуацию можно, создав свою оболочку (враппер) вокруг RandomNumberGenerator, которая будет преобразовывать случайные байты в «удобный» результат, однако это решение нетривиально.
Тем не менее, в большинстве случаев «слабость» класса Random вполне подходит, если вы сможете решить проблему, описанную в начале статьи. Посмотрим, что здесь можно сделать.
Есть два способа решения проблемы. Во-первых, мы можем использовать не экземплярное, а статическое поле, содержащее экземпляр Random, и тогда вышеприведённый кусок кода создаст лишь один экземпляр, и будет его использовать, вызываясь сколько угодно раз. Во-вторых, мы можем вообще убрать оттуда создание экземпляра Random, переместив его «повыше», в идеале - на самый «верх» программы, где будет создан единичный экземпляр Random, после чего он будет передаваться во все места, где нужны случайные числа. Это отличная идея, которая красиво выражается зависимостями, но она будет работать до тех пор, пока мы используем лишь один поток.
Снова-таки, здесь есть два пути решения проблемы. Первый путь по-прежнему предполагает использование одного экземпляра, однако на этот раз с использованием блокировки ресурса посредством монитора. Для этого необходимо создать оболочку вокруг Random, которая будет оборачивать вызов его методов в оператор lock , обеспечивающий эксклюзивный доступ к экземпляру для вызывающей стороны. Этот путь плох тем, что снижает производительность в многопоточно-интенсивных сценариях.
Другой путь, который я опишу ниже - использование по одному экземпляру на каждый поток. Единственное, нам нужно удостовериться, что при создании экземпляров мы используем разные начальные значения (seed), а потому мы не можем использовать конструкторы по умолчанию. Во всём остальном этот путь относительно прямолинеен.
Нижепредставленный класс полностью статический и содержит лишь один публичный (открытый) метод GetThreadRandom. Этот метод сделан методом, а не свойством, в основном из-за удобства: благодаря этому все классы, которым нужен экземпляр Random, будут зависеть от Func
using System;
using System.Threading;
public static class RandomProvider
{
private static int seed = Environment.TickCount;
private static ThreadLocal
Достаточно просто, не правда ли? Всё потому, что весь код направлен на выдачу правильного экземпляра Random. После того, как экземпляр создан и возвращён, совершенно неважно, что вы будете с ним делать дальше: все дальнейшие выдачи экземпляров совершенно не зависят от текущего. Конечно, клиентский код имеет лазейку для злонамеренного неправильного использования: он может получить один экземпляр Random и передать его в другие потоки вместо вызова в тех, других потоках, нашего RandomProvider.
Было бы очень приятно, если бы провайдеры ГСЧ в фреймворке имели отдельные «источники случайности». В таком случае мы могли бы иметь единый простой и удобный API, который бы поддерживался как небезопасной-но-быстрой реализацией, так и безопасной-но-медленной. Что-ж, мечтать не вредно. Возможно, подобный функционал появится в следующих версиях.NET Framework. Возможно, кто-то не из Microsoft предложит свою реализацию адаптера. (К сожалению, я не буду этим кем-то… правильная реализация подобной задумки удивительно сложна.) Вы также можете создать свой класс, отнаследовав его от Random и переопределив методы Sample и NextBytes, однако неясно, как именно они должны работать, и даже собственная реализация Sample может быть намного сложнее, нежели кажется. Может быть, в следующий раз…
Функция, генерирующая псевдослучайные числа, имеет прототип в файле библиотеки stdlib.h
:
1
2
3
4
5
6
unsigned
long
int
next = 1;
int
rand(void
)
{
next = next * 1103515245;
return
((unsigned
int
)(next / 65536) * 2768);
}
Если необходимо сгенерировать последовательность в диапазоне , то используется формула:
Number = rand()%(M2-M1+1) + M1;
где Number – генерируемое число. M2-M1+1 – полный диапазон представления чисел. M1 – смещение указанного диапазона относительно 0; % — остаток от деления .
Например, если требуется сгенерировать последовательность в диапазоне [-10;10], то вызов функции будет выглядеть как
Number = rand()%(10+10+1)-10
Number = rand()%(21)-10
В результате получения остатка от деления на 21 имеем число от 0 до 20. Вычитая из полученного числа 10, получим число в искомом диапазоне [-10;10].
Однако генерируемая функцией rand() последовательность будет иметь один и тот же вид при каждом запуске программы.
Для генерации различных последовательности при каждом запуске программы необходимо проинициализировать глобальную переменную next
значением, отличным от 1. С этой целью используется функция
void
srand(unsigned int
seed)
{ next = seed; }
Чтобы инициализация next
при каждом запуске программы была различной в качестве аргумента seed
чаще всего используется текущее время.
Пример
Заполнить массив из 20 элементов случайными числами в диапазоне от 0 до 99.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include
#include
#include
#define
SIZE 20
int
main() {
int
a;
srand(time(NULL
));
for
(int
i = 0; i
a[i] = rand() % 100;
printf("%d "
, a[i]);
}
getchar();
return
0;
}
Часто возникает задача расставить уже имеющийся набор значений в произвольном порядке. С этой целью также используется генератор псевдослучайных чисел. При этом создается массив и заполняется значениями.
Сама процедура перемешивания происходит следующим образом. Генерируется два значения индексов массива случайным образом, и значения элементов с полученными индексами меняются местами. Процедура повторяется не менее N раз, где N - количество элементов массива.
В качестве примера рассмотрим перемешивание 20 значений (от 1 до 20) и повторим процедуру 20 раз.
Реализация на Си
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
#include
#include
#include
#define
SIZE 20
int
main() {
int
a;
srand(time(NULL
));
for
(int
i = 0; i < SIZE; i++)
{
a[i] = i + 1;
printf("%2d "
, a[i]);
}
for
(int
i = 0; i < SIZE; i++)
{
// Генерируем случайно два индекса элементов
int
ind1 = rand() % 20;
int
ind2 = rand() % 20;
// и меняем местами элементы с этими индексами
int
temp = a;
a = a;
a = temp;
}
printf("\n"
);
for
(int
i = 0; i < SIZE; i++)
printf("%2d "
, a[i]);
getchar();
return
0;
}
Часто возникает задача произвольного выбора ранее заданных элементов массива. Причем необходимо предусмотреть отсутствие повторений в выборе этих элементов.
Алгоритм такого выбора состоит в следующем:
Реализации на Си
В результате получаем новый массив b
, сформированный произвольной выборкой элементов массива a
.
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
#include
#include
#include
#define
SIZE 20
int
main() {
int
a;
int
b; // результирующий массив
srand(time(NULL
));
// Заполняем массив последовательными значениями от 1 до 20
for
(int
i = 0; i < SIZE; i++)
{
a[i] = i + 1;
printf("%2d "
, a[i]);
}
for
(int
i = 0; i < SIZE; i++)
{
int
ind = rand() % 20; // выбираем произвольный индекс
while
(a == -1) // пока элемент "выбран"
{
ind++; // двигаемся вправо
ind %= 20; // если дошли до правой границы, возвращаемся в начало
}
b[i] = a; // записываем следующий элемент массива b
a = -1; // отмечаем элемент массива a как "выбранный"
}
printf("\n"
);
// Выводим получившийся массив
for
(int
i = 0; i < SIZE; i++)
printf("%2d "
, b[i]);
getchar();
return
0;
}
В обучающих алгоритмических задачках довольно часто встречается необходимость генерации случайных целых чисел. Конечно, можно получать их от пользователя, но с заполнением массива случайными числами в количестве 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;
}