Как написать программу генератор случайных чисел

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

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

Этот источник используется для накопления энтропии с последующим получением из неё начального значения (initial value, seed), которое необходимо генераторам случайных чисел (ГСЧ) для формирования случайных чисел.

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

Энтропия?—?это мера беспорядка. Информационная энтропия?—?мера неопределённости или непредсказуемости информации.

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

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

Придумываем свой алгоритм ГПСЧ

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

Мы можем взять последовательность каких-то чисел и брать от них модуль числа. Самый простой пример, который приходит в голову. Нам нужно подумать, какую последовательность взять и модуль от чего. Если просто в лоб от 0 до N и модуль 2, то получится генератор 1 и 0:

function* rand() {
  const n = 100;
  const mod = 2;
  let i = 0;
  while (true) {
    yield i % mod;
    if (i++ > n) i = 0;
  }
}
let i = 0;
for (let x of rand()) {
 if (i++ > 100) break;
  console.log(x);
}

Эта функция генерит нам последовательность 01010101010101… и назвать ее даже псевдослучайной никак нельзя. Чтобы генератор был случайным, он должен проходить тест на следующий бит. Но у нас не стоит такой задачи. Тем не менее даже без всяких тестов мы можем предсказать следующую последовательность, значит такой алгоритм в лоб не подходит, но мы в нужном направлении.

А что если взять какую-то известную, но нелинейную последовательность, например число PI. А в качестве значения для модуля будем брать не 2, а что-то другое. Можно даже подумать на тему меняющегося значения модуля. Последовательность цифр в числе Pi считается случайной. Генератор может работать, используя числа Пи, начиная с какой-то неизвестной точки. Пример такого алгоритма, с последовательностью на базе PI и с изменяемым модулем:

const vector = [...Math.PI.toFixed(48).replace('.','')];
function* rand() {
 for (let i=3; i<1000; i++) {
   if (i > 99) i = 2;
    for (let n=0; n<vector.length; n++) {
      yield (vector[n] % i);
    }
  }
}

Но в JS число PI можно вывести только до 48 знака и не более. Поэтому предсказать такую последовательность все так же легко и каждый запуск такого генератора будет выдавать всегда одни и те же числа. Но наш генератор уже стал показывать числа от 0 до 9.

Мы получили генератор чисел от 0 до 9, но распределение очень неравномерное и каждый раз он будет генерировать одну и ту же последовательность.

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

function* rand() {
 let newNumVector = () => [...(+new Date)+''].reverse();
 let vector = newNumVector();
 let i=2;
 while (true) {
    if (i++ > 99) i = 2;
    let n=-1;
    while (++n < vector.length) yield (vector[n] % i);
    vector = newNumVector();
  }
}

// TEST:
let i = 0;
for (let x of rand()) {
  if (i++ > 100) break;
  console.log(x)
}

Вот это уже похоже на генератор псевдослучайных чисел. И тот же Math.random()?—?это ГПСЧ, про него мы поговорим чуть позже. При этом у нас каждый раз первое число получается разным.

Собственно на этих простых примерах можно понять как работают более сложные генераторы случайных числе. И есть даже готовые алгоритмы. Для примера разберем один из них?—?это Линейный конгруэнтный ГПСЧ(LCPRNG).

Линейный конгруэнтный ГПСЧ

Линейный конгруэнтный ГПСЧ(LCPRNG)?—?это распространённый метод для генерации псевдослучайных чисел. Он не обладает криптографической стойкостью. Этот метод заключается в вычислении членов линейной рекуррентной последовательности по модулю некоторого натурального числа m, задаваемой формулой. Получаемая последовательность зависит от выбора стартового числа?—?т.е. seed. При разных значениях seed получаются различные последовательности случайных чисел. Пример реализации такого алгоритма на JavaScript:

const a = 45;
const c = 21;
const m = 67;
var seed = 2;
const rand = () => seed = (a * seed + c) % m;
for(let i=0; i<30; i++)
  console.log( rand() )

Многие языки программирования используют LСPRNG (но не именно такой алгоритм(!)).

Как говорилось выше, такую последовательность можно предсказать. Так зачем нам ГПСЧ? Если говорить про безопасность, то ГПСЧ?—?это проблема. Если говорить про другие задачи, то эти свойства?—?могут сыграть в плюс. Например для различных спец эффектов и анимаций графики может понадобиться частый вызов random. И вот тут важны распределение значений и перформанс! Секурные алгоритмы не могут похвастать скоростью работы.

Еще одно свойство?—?воспроизводимость. Некоторые реализации позволяют задать seed, и это очень полезно, если последовательность должна повторяться. Воспроизведение нужно в тестах, например. И еще много других вещей существует, для которых не нужен безопасный ГСЧ.

Как устроен Math.random()

Метод Math.random() возвращает псевдослучайное число с плавающей запятой из диапазона [0, 1), то есть, от 0 (включительно) до 1 (но не включая 1), которое затем можно отмасштабировать до нужного диапазона. Реализация сама выбирает начальное зерно для алгоритма генерации случайных чисел; оно не может быть выбрано или сброшено пользователем.

Как устроен алгоритм Math.random()?—?интересный вопрос. До недавнего времени, а именно до 49 Chrome использовался алгоритм MWC1616:

uint32_t state0 = 1;
uint32_t state1 = 2;
uint32_t mwc1616() {
   state0 = 18030 * (state0 & 0xffff) + (state0 >> 16);
   state1 = 30903 * (state1 & 0xffff) + (state1 >> 16);
   return (state0 << 16) + (state1 & 0xffff);
}

Именно этот алгоритм генерит нам последовательность псевдослучайных чисел в промежутке между 0 и 1.

Предсказываем Math.random()

Чем это было чревато? Есть такой квест: alf.nu/ReturnTrue

В нем есть задача:

{
	let rand = Math.random();
	function random4(x) {
	    return rand === x;
	}
}

random4(???)

Что нужно вписать вместо вопросов, чтобы функция вернула true? Кажется что это невозможно. Но, это возможно, если вы заглядывали в спеку и видели алгоритм ГПСЧ V8. Решение этой задачи в свое время мне показал Роман Дворнов:

random4(function(){var A=18030,B=36969,F=65535,Z=16,M=Math,I=M.imul,c=M.random,M=M.pow(2,32),k,d,g=c()*M,h=c()*M;for(k=0;F^k&&(c=I(A,g>>>Z)+k++)&F^h>>>Z;);for(k=0;F^k&&(d=I(B,g&F)+k++)&F^h&F;);for(k=2;k—;g=c<<Z|d&F)c=c/A|c%A<<Z,d=d/B|d%B<<Z;return(g<0?g+M:g)/M}())

Этот код работал в 70% случаев для Chrome < 49 и Node.js < 5. Рома Дворнов, как всегда, показал чудеса магии, которая не что иное, как глубокое понимание внутренних механизмов браузеров. Я все жду, когда Роман сделает доклад на основе этих событий или напишет более подробную статью.

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

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

Выходит что мы можем отреверсить Math.random() и предсказать, какое было загадано число на основе того, что получили в данный момент времени. Для этого получаем два значения через Math.random(). Затем вычисляем внутреннее состояние по этим значениям. Имея внутреннее состояние можем предсказывать следующие значения Math.random() при этом не меняя внутреннее состояние. Меняем код так так, чтобы вместо следующего возвращалось предыдущее значение. Собственно все это и описано в коде-решении для задачи random4. Но потом алгоритм изменили (подробности читайте в спеке). Его можно будет сломать, как только у нас в JS появится нормальная работа с 64 битными числами. Но это уже будет другая история.

Новый алгоритм выглядит так:

uint64_t state0 = 1;
uint64_t state1 = 2;
uint64_t xorshift128plus() {
   uint64_t s1 = state0;
   uint64_t s0 = state1;
   state0 = s0;
   s1 ^= s1 << 23;
   s1 ^= s1 >> 17;
   s1 ^= s0;
   s1 ^= s0 >> 26;
   state1 = s1;
   return state0 + state1;
}

Его все так же можно будет просчитать и предсказать. Но пока у нас нет “длинной математики” в JS. Можно попробовать через TypedArray сделать или использовать специальные библиотеки. Возможно кто-то однажды снова напишет предсказатель. Возможно это будешь ты, читатель. Кто знает

Сrypto Random Values

Метод Math.random() не предоставляет криптографически стойкие случайные числа. Не используйте его ни для чего, связанного с безопасностью. Вместо него используйте Web Crypto API (API криптографии в вебе) и более точный метод window.crypto.getRandomValues().

Пример генерации случайного числа:

let [rvalue] = crypto.getRandomValues(new Uint8Array(1));
console.log( rvalue )

Но, в отличие от ГПСЧ Math.random(), этот метод очень ресурсоемкий. Дело в том, что данный генератор использует системные вызовы в ОС, чтобы получить доступ к источникам энтропии (мак адрес, цпу, температуре, etc…).

В статье вы узнаете, как использовать std.random и чем он хорош

В 2011 году новый стандарт C++11 добавил в язык заголовок <random>, в котором описаны средства для работы со случайными числами на профессиональном уровне. Эти средства заменяют функцию rand и дают гораздо больше гибкости.

Но чтобы этим воспользоваться, надо немного разбираться в теории.

Почему в IT все числа неслучайные

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

• Для генерации по-настоящему случайных, ничем не связанных чисел операционной системе приходится использовать средства, недоступные обычным приложениям; такие случайные числа называются криптографически стойкими случайными числами
• Генерация системой таких случайных чисел работает медленно, и при нехватке скорости система просто отдаёт приложениями псевдослучайные числа либо заставляет их ожидать, пока появится возможность вернуть случайное число

Вы можете узнать об этом подробнее, прочитав о разнице между устройствами /dev/random и /dev/urandom в ОС Linux

Pseudo-random Numbers Generator (PRNG)

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

Общий принцип генерации легко показать в примере:

#include <iostream>

int main()
{
    unsigned value = 18;
    // Порождаем и выводим 20 чисел, используя число 18 как зерно
    for (int i = 0; i < 20; ++i)
    {
        // Итеративно вычисляем новое значение value.
        value = (value * 73129 + 95121) % 100000;
        std::cout << value << std::endl;
    }
}

Несложная итеративная формула, содержащая умножение, сложение и деление по остатку на разные константы, создаёт целую серию чисел, похожих на случайные:

11443
10268
83693
13222
6759
74032
13953
64058
25307
70724
3221
43630
13391
65560
65065
66210
98915
82860
96765
55510

Очевидно, что между числами есть взаимосвязь: они вычислены по одной и той же формуле. Но для пользователя видимой взаимосвязи нет.

Время как источник случайности

Если вы запустите предыдущую программу несколько раз, вы обнаружите проблему: числа будут те же самые. Причина проста — в начале последовательности мы используем всегда одно и то же число, 18. Для последовательности это число является зерном (англ. seed), и чтобы последовательность менялась с каждым запуском, зерно должно быть случайным.

Простейший, но не самый лучший способ получения зерна: взять текущее календарное время в секундах. Для этой цели мы воспользуемся функцией std::time_t time(std::time_t* arg).

Функция std::time возвращает число, представляющее время, прошедшее с полуночи 1 января 1970 года. Обычно это время в секундах, также известное как UNIX Timestamp. Параметр arg можно игнорировать и передавать нулевой указатель (вы можете в этом убедиться, прочитав документацию).

#include <iostream>
#include <ctime>

int main()
{
    unsigned value = unsigned(std::time(nullptr));
    // Порождаем и выводим 20 чисел, используя время UNIX как зерно.
    for (int i = 0; i < 20; ++i)
    {
        value = (value * 73129 + 95121) % 100000;
        std::cout << value << std::endl;
    }
}

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

Такие случайные числа далеко не идеальны: например, их нельзя использовать в криптографии, потому что злоумышленник может примерно оценить, в каком промежутке времени были созданы случайные числа, и сильно сократить затраты на дешифровку сообщения. В разработке простых учебных приложений такие числа вполне подходят

Ограничение числа по диапазону

Ограничить числа по диапазону можно путём деления по остатку (что сократит длину входного диапазона) и добавления нижней границы диапазона:

#include <iostream>
#include <ctime>
#include <cassert>

// Структура генератора псевдослучайных чисел хранит одно число,
//  зерно следующего случайного числа.
struct PRNG
{
    unsigned seed = 0;
};

void initGenerator(PRNG& generator)
{
    // Получаем случайное зерно последовательности
    generator.seed = unsigned(std::time(nullptr));
}

// Генерирует число на отрезке [minValue, maxValue].
unsigned random(PRNG& generator, unsigned minValue, unsigned maxValue)
{
    // Проверяем корректность аргументов
    assert(minValue < maxValue);
    // Итеративно изменяем текущее число в генераторе
    generator.seed = (generator.seed * 73129 + 95121);
    
    // Приводим число к отрезку [minValue, maxValue]
    return (generator.seed % (maxValue + 1 - minValue)) + minValue;
}

int main()
{
    PRNG generator;
    initGenerator(generator);
    
    // Порождаем и выводим 10 чисел на отрезке [0, 7].
    std::cout << "ten numbers in range [0, 7]:" << std::endl;
    for (int i = 0; i < 10; ++i)
    {
        std::cout << random(generator, 0, 7) << std::endl;
    }
    
    // Порождаем и выводим 10 чисел на отрезке [10, 20].
    std::cout << "ten numbers in range [10, 20]:" << std::endl;
    for (int i = 0; i < 10; ++i)
    {
        std::cout << random(generator, 10, 20) << std::endl;
    }
}

Всё то же, только лучше: заголовок <random>

Заголовок random разделяет генерацию псевдослучайных чисел на 3 части и предоставляет три инструмента:

• класс std::random_device, который запрашивает у операционной системы почти случайное целое число; этот класс более удачные зёрна, чем если брать текущее время
• класс std::mt19937 и другие классы псевдо-случайных генераторов, задача которых — размножить одно зерно в целую последовательность чисел
• класс std::uniform_int_distribution и другие классы распределений

Класс mt19937 реализует алгоритм размножения псевдослучайных чисел, известный как Вихрь Мерсенна. Этот алгоритм работает быстро и даёт хорошие результаты — гораздо более “случайные”, чем наш самописный метод, показанный ранее.

О распределениях скажем подробнее:

• линейное распределение вероятностей (uniform distribution) возникает, когда вероятность появления каждого из допустимых чисел одинакова, т.е. каждое число может появиться с равным шансом
• в некоторых прикладных задачах нужны другие распределения, в которых одни числа появляются чаще других — например, часто используется нормальное распределение (normal distribution)

В большинстве случаев вам подойдёт линейное распределение. Изредка пригодится нормальное, в котором вероятность появления числе тем ниже, чем дальше оно от среднего значения:

Теперь мы можем переписать

#include <iostream>
#include <random>
#include <cassert>

struct PRNG
{
    std::mt19937 engine;
};

void initGenerator(PRNG& generator)
{
    // Создаём псевдо-устройство для получения случайного зерна.
    std::random_device device;
    // Получаем случайное зерно последовательности
    generator.engine.seed(device());
}

// Генерирует целое число в диапазоне [minValue, maxValue)
unsigned random(PRNG& generator, unsigned minValue, unsigned maxValue)
{
    // Проверяем корректность аргументов
    assert(minValue < maxValue);
    
    // Создаём распределение
    std::uniform_int_distribution<unsigned> distribution(minValue, maxValue);
    
    // Вычисляем псевдослучайное число: вызовем распределение как функцию,
    //  передав генератор произвольных целых чисел как аргумент.
    return distribution(generator.engine);
}

// Генерирует число с плавающей точкой в диапазоне [minValue, maxValue)
float getRandomFloat(PRNG& generator, float minValue, float maxValue)
{
    // Проверяем корректность аргументов
    assert(minValue < maxValue);
    
    // Создаём распределение
    std::uniform_real_distribution<float> distribution(minValue, maxValue);
    
    // Вычисляем псевдослучайное число: вызовем распределение как функцию,
    //  передав генератор произвольных целых чисел как аргумент.
    return distribution(generator.engine);
}

int main()
{
    PRNG generator;
    initGenerator(generator);
    
    // Порождаем и выводим 10 чисел на отрезке [0, 7]
    std::cout << "ten integer numbers in range [0, 7]:" << std::endl;
    for (int i = 0; i < 10; ++i)
    {
        std::cout << random(generator, 0, 7) << std::endl;
    }
    
    // Порождаем и выводим 10 чисел на отрезке [10, 20]
    std::cout << "ten float numbers in range [10, 20]:" << std::endl;
    for (int i = 0; i < 10; ++i)
    {
        std::cout << getRandomFloat(generator, 10.f, 20.f) << std::endl;
    }
}

Особенность платформы: random_device в MinGW

Согласно стандарту C++, принцип работы std::random_device отдаётся на откуп разработчикам компилятора и стандартной библиотеки. В компиляторе G++ и его стандартной библиотеке libstdc++ класс random_device правильно работает на UNIX-платформах, но на Windows в некоторых дистрибутивах MinGW вместо случайных зёрен он возвращает одну и ту же константу!

В качестве обходного манёвра мы можем использовать текущее время в качестве зерна случайности. Для этого изменим функцию initGenerator:

#include <iostream>
#include <random>
#include <cassert>
#include <ctime>

struct PRNG
{
    std::mt19937 engine;
};

void initGenerator(PRNG& generator)
{
    // Используем время с 1 января 1970 года в секундах как случайное зерно
    const unsigned seed = unsigned(std::time(nullptr));
    generator.engine.seed(seed);
}

Приём №1: выбор случайного значения из предопределённого списка

Допусти, вы хотите случайно выбрать имя для кота. У вас есть список из 10 имён, которые подошли бы коту, но вы хотите реализовать случайный выбор. Достаточно случайно выбрать индекс в массиве имён! Такой же метод подошёл не только для генерации имени, но также для генерации цвета из заранее определённой палитры и для других задач.

Идея проиллюстрирована в коде

#include <iostream>
#include <vector>
#include <string>
#include <random>
#include <ctime>

struct PRNG
{
    std::mt19937 engine;
};

void initGenerator(PRNG& generator)
{
    // Используем время с 1 января 1970 года в секундах как случайное зерно
    const unsigned seed = unsigned(std::time(nullptr));
    generator.engine.seed(seed);
}

// Генерирует индекс в диапазоне [0, size)
size_t getRandomIndex(PRNG& generator, size_t size)
{
    // Создаём распределение
    std::uniform_int_distribution<size_t> distribution(0, size - 1);
    
    // Вычисляем псевдослучайное число: вызовем распределение как функцию,
    //  передав генератор произвольных целых чисел как аргумент.
    return distribution(generator.engine);
}

int main()
{
    std::vector<std::string> names = {
        "Barsik",
        "Murzik",
        "Pushok",
        "Amor",
        "Balu",
        "Vert",
        "Damar",
        "Kamelot",
        "Mavrik",
        "Napoleon"
    };
    
    PRNG generator;
    initGenerator(generator);
    
    // Порождаем и выводим 3 случайных имёни из заданного списка
    
    std::cout << "3 random cat names:" << std::endl;
    for (int i = 0; i < 3; ++i)
    {
        const size_t nameIndex = getRandomIndex(generator, names.size());
        std::cout << names[nameIndex] << std::endl;
    }
}

Приём №2: отбрасываем неподходящее значение

Если предыдущую программу запустить несколько раз, то рано или поздно у вас возникнет ситуация, когда одно и то же имя было выведено дважды. Что, если вам нужно уникальное значение, не выпадавшее прежде за время запуска программы?

Тогда используйте цикл, чтобы запрашивать случайные значения до тех пор, пока очередное значение не попадёт под ваши требования. Будьте аккуратны: если требования нереалистичные, вы получите бесконечный цикл!

Доработаем программу, добавив цикл while в функцию main. Для сохранения уже использованных имён воспользуемся структурой данных std::set из заголовка <set>, представляющей динамическое множество.

#include <iostream>
#include <vector>
#include <string>
#include <set>
#include <random>
#include <ctime>

struct PRNG
{
    std::mt19937 engine;
};

void initGenerator(PRNG& generator)
{
    // Используем время с 1 января 1970 года в секундах как случайное зерно
    const unsigned seed = unsigned(std::time(nullptr));
    generator.engine.seed(seed);
}

// Генерирует индекс в диапазоне [0, size)
size_t getRandomIndex(PRNG& generator, size_t size)
{
    // Создаём распределение
    std::uniform_int_distribution<size_t> distribution(0, size - 1);
    
    // Вычисляем псевдослучайное число: вызовем распределение как функцию,
    //  передав генератор произвольных целых чисел как аргумент.
    return distribution(generator.engine);
}

int main()
{
    std::vector<std::string> names = {
        "Barsik",
        "Murzik",
        "Pushok",
        "Amor",
        "Balu",
        "Vert",
        "Damar",
        "Kamelot",
        "Mavrik",
        "Napoleon"
    };
    
    PRNG generator;
    initGenerator(generator);
    
    // Множество, хранящее индексы использованных имён.
    std::set<size_t> usedIndexes;

    // Порождаем и выводим 3 случайных имёни из заданного списка
    std::cout << "3 random cat names:" << std::endl;
    for (int i = 0; i < 3; ++i)
    {
        size_t nameIndex = 0;
        while (true)
        {
            // Запрашиваем случайный индекс
            nameIndex = getRandomIndex(generator, names.size());
            // Проверяем, что индекс ранее не встречался
            if (usedIndexes.find(nameIndex) == usedIndexes.end())
            {
                // Если не встречался, добавляем в множество и выходим
                //  из цикла: уникальный индекс найден
                usedIndexes.insert(nameIndex);
                break;
            }
            else
            {
                // Отладочная печать отброшенного индекса
                std::cout << "discard index " << nameIndex << std::endl;
            }
        }
        std::cout << "index: " << nameIndex << std::endl;
        std::cout << names[nameIndex] << std::endl;
    }
}

Содержание

• 1. Как в C++ сгенерировать случайное число? Функция rand(). Пример
• 2. Функция srand(). Назначение. Пример
• 3. Функция time(). Назначение. Сочетание функций rand(), srand(), time(). Пример
• 4. Как сгенерировать случайное целое число в заданных пределах? Пример
• 5. Заполнение двумерной матрицы случайными целыми числами в указанных пределах. Пример
• 6. Как сгенерировать случайное число с плавающей запятой в указанных пределах? Пример
• Связанные темы

Поиск на других ресурсах:

1. Как в C++ сгенерировать случайное число? Функция rand(). Пример

В языке C++ существуют средства для генерирования случайных чисел. Чтобы сгенерировать случайное число используется функция rand(), которая размещается в библиотечном файле stdlib.h. Синтаксис объявления функции следующий:

int rand();

Функция возвращает случайное целочисленное значение, которое лежит в пределах от 0 до 32767.

Пример.

#include <iostream>
#include <stdlib.h>
using namespace std;

void main()
{
  // Получить случайное число
  int x;
  x = rand();
  cout << "x = " << x << endl;

  // Получить еще одно случайное число
  int y;
  y = rand();
  cout << "y = " << y << endl;
}

Результат выполнения программы

x = 41
y = 18467

  ⇑

2. Функция srand(). Назначение. Пример

Если несколько раз запустить текст программы из п. 1, то будет получен один и тот же результат (одни и те же числа). Значит, сама по себе функция rand() генерирует одни и те же последовательности чисел. Чтобы получить разные последовательности чисел нужно объединить функцию rand() с функцией srand().

Функция srand() из библиотеки stdlib.h предназначена для установки начальной точки, из которой происходит генерирование случайных чисел. Синтаксис объявления функции следующий:

void srand(unsigned int startValue);

здесь startValue – целочисленное значение, которое служит отправной точкой для генерирования последовательности случайных чисел функцией rand(). Изменяя значение startValue, можно получать разные последовательности случайных чисел.

Пример.

#include <iostream>
#include <stdlib.h>
using namespace std;

void main()
{
  // Установить начальную точку генерирования последовательности
  srand(55);

  // Получить случайное число
  int x;
  x = rand();
  cout << "x = " << x << endl;

  // Получить еще одно случайное число
  int y;
  y = rand();
  cout << "y = " << y << endl;
}

Результат выполнения программы

x = 218
y = 9057

  ⇑

3. Функция time(). Назначение. Сочетание функций rand(), srand(), time(). Пример

Как видно из примера в п. 2, последовательность случайных чисел изменилась. Если в функции srand() вместо числа 55 установить другое число, то будет получена другая последовательность. Однако, текст программы статический и при многократном запуске программы это число будет неизменным. В результате будет получаться одна и та же последовательность случайных чисел. Во избежание этого недостатка, нужно чтобы стартовое значение в функции srand() постоянно изменялось.

Для того, чтобы в функции srand() получить разные начальные значения используется функция time() из библиотеки time.h.

Если функцию time() вызвать с параметром NULL, то эта функция возвратит количество миллисекунд, которые прошли с 1 января 1970 года. Значит, число миллисекунд будет зависеть от момента времени, в который пользователь запустил программу на выполнение. А этот момент каждый раз будет другим.

Если эти миллисекунды поместить в функцию srand() как показано ниже

srand(time(NULL));

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

Пример. В примере демонстрируется генерирование последовательности из двух случайных чисел. Каждый раз при запуске программы будет получена новая последовательность.

#include <iostream>
#include <stdlib.h>
#include <time.h>
using namespace std;

void main()
{
  // Установить начальную точку генерирования последовательности
  // использовать функцию time(NULL)
  srand(time(NULL));

  // Получить случайное число
  int x;
  x = rand();
  cout << "x = " << x << endl;

  // Получить еще одно случайное число
  int y;
  y = rand();
  cout << "y = " << y << endl;
}

Результат выполнения программы

x = 19040
y = 24635

  ⇑

4. Как сгенерировать случайное целое число в заданных пределах? Пример

В примере приведена функция GetRandomNumber(), которая генерирует случайное число в заданных пределах.

#include <iostream>
#include <stdlib.h> // нужен для вызова функций rand(), srand()
#include <time.h> // нужен для вызова функции time()
using namespace std;

// Функция генерирования случайного целочисленного числа в указанных пределах.
// Диапазон чисел: [min, max]
int GetRandomNumber(int min, int max)
{
  // Установить генератор случайных чисел
  srand(time(NULL));

  // Получить случайное число - формула
  int num = min + rand() % (max - min + 1);

  return num;
}

void main()
{
  // Использование функции GetRandomNumber()
  int number;
  number = GetRandomNumber(-10, 10); // Диапазон чисел: [-10, 10]
  cout << "number = " << number << endl;;
}

  ⇑

5. Заполнение двумерной матрицы случайными целыми числами в указанных пределах. Пример

Условие задачи. Дана двумерная матрица порядка n (n столбцов, n строк) целых чисел. Найти наибольшее из значений элементов, которые размещены в закрашенной части матрицы. Значение элементов матрицы формируются случайным образом и находятся в пределах [-5; +5].

Текст программы следующий

#include <iostream>
#include <stdlib.h> // нужен для вызова функции rand(), srand()
#include <time.h> // нужен для вызова функции time()
using namespace std;

void main()
{
  // Двумерные массивы.
  // Вычислить максимальный элемент нижней части матрицы

  // 1. Объявление переменных
  const int MAX_N = 10; // максимально-допустимая размерность матрицы
  const int MIN_VALUE = -5; // максимальное значение элементов матрицы
  const int MAX_VALUE = 5; // минимальное значение
  int A[MAX_N][MAX_N]; // исходная матрица
  int n; // текущий размер матрицы n*n
  int max; // результат - максимальное значение

  // 2. Ввод n
  cout << "n = ";
  cin >> n;

  // 3. Проверка n на корректность
  if ((n <= 1) || (n > MAX_N))
  {
    cout << "Wrong size of array." << endl;
    return;
  }

  // 4. Формирование матрицы A случайных чисел,
  // установить генератор случайных чисел
  srand(time(NULL));

  for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
    {
      // взять случайное число
      A[i][j] = MIN_VALUE + rand() % (MAX_VALUE - MIN_VALUE + 1);
    }

  // 5. Вывести массив A для проверки
  cout << endl << "Array A:" << endl;
  for (int i = 0; i < n; i++)
  {
    for (int j = 0; j < n; j++)
      cout << A[i][j] << 't';
    cout << endl;
  }

  // 6. Вычисление максимального значения
  bool f_first = true; // флажок первого элемента

  for (int i = 0; i < n; i++) // i - строки
    for (int j = 0; j < i; j++) // j - столбцы
      if (f_first)
      {
        // первый элемент принимается максимальным
        max = A[i][j];
        f_first = false;
      }
      else
      {
        if (max < A[i][j])
          max = A[i][j];
      }

  // 7. Вывод результата
  cout << endl << "max = " << max << endl;
}

  ⇑

6. Как сгенерировать случайное число с плавающей запятой в указанных пределах? Пример

В примере демонстрируется функция GetRandomNumberFloat(), которая генерирует случайное число с плавающей запятой в указанных пределах.

#include <iostream>
#include <stdlib.h> // нужен для вызова функции rand(), srand()
#include <time.h> // нужен для вызова функции time()
using namespace std;

// Функция, которая генерирует случайное число с плавающей запятой и указанной точностью
// Функция получает 3 параметра:
// - min - нижний предел;
// - max - верхний предел;
// - precision - точность, количество знаков после комы.
double GetRandomNumberFloat(double min, double max, int precision)
{
  // Установить стартовую точку
  srand(time(NULL));

  double value;

  // получить случайное число как целое число с порядком precision
  value = rand() % (int)pow(10, precision);

  // получить вещественное число
  value = min + (value / pow(10, precision)) * (max - min);

  return value;
}

void main()
{
  // Использование функции GetRandomNumberFloat()
  double number;

  srand(time(NULL));

  // Получить число в диапазоне [0; 2] с точностью 2 знака после запятой
  number = GetRandomNumberFloat(0, 2, 2);
  cout << "number = " << number << endl;
}

  ⇑

Связанные темы

• Разработка класса Random генерирования случайных чисел

  ⇑

Given n numbers, each with some frequency of occurrence. Return a random number with probability proportional to its frequency of occurrence.

Example: 

Let following be the given numbers.
  arr[] = {10, 30, 20, 40}  

Let following be the frequencies of given numbers.
  freq[] = {1, 6, 2, 1}  

The output should be
  10 with probability 1/10
  30 with probability 6/10
  20 with probability 2/10
  40 with probability 1/10

It is quite clear that the simple random number generator won’t work here as it doesn’t keep track of the frequency of occurrence. 

We need to somehow transform the problem into a problem whose solution is known to us.

One simple method is to take an auxiliary array (say aux[]) and duplicate the numbers according to their frequency of occurrence. Generate a random number(say r) between 0 to Sum-1(including both), where Sum represents summation of frequency array (freq[] in above example). Return the random number aux[r] (Implementation of this method is left as an exercise to the readers).

The limitation of the above method discussed above is huge memory consumption when frequency of occurrence is high. If the input is 997, 8761 and 1, this method is clearly not efficient.

How can we reduce the memory consumption? Following is detailed algorithm that uses O(n) extra space where n is number of elements in input arrays.
1. Take an auxiliary array (say prefix[]) of size n. 
2. Populate it with prefix sum, such that prefix[i] represents sum of numbers from 0 to i. 
3. Generate a random number(say r) between 1 to Sum(including both), where Sum represents summation of input frequency array. 
4. Find index of Ceil of random number generated in step #3 in the prefix array. Let the index be indexc. 
5. Return the random number arr[indexc], where arr[] contains the input n numbers.
  Before we go to the implementation part, let us have quick look at the algorithm with an example: 
      arr[]: {10, 20, 30} 
      freq[]: {2, 3, 1} 
      Prefix[]: {2, 5, 6} 
  Since last entry in prefix is 6, all possible values of r are [1, 2, 3, 4, 5, 6] 
         1: Ceil is 2. Random number generated is 10. 
         2: Ceil is 2. Random number generated is 10. 
         3: Ceil is 5. Random number generated is 20. 
         4: Ceil is 5. Random number generated is 20. 
         5: Ceil is 5. Random number generated is 20. 
         6. Ceil is 6. Random number generated is 30. 
  In the above example 
      10 is generated with probability 2/6. 
      20 is generated with probability 3/6. 
      30 is generated with probability 1/6.

How does this work? 
Any number input[i] is generated as many times as its frequency of occurrence because there exists count of integers in range(prefix[i – 1], prefix[i]] is input[i]. Like in the above example 3 is generated thrice, as there exists 3 integers 3, 4 and 5 whose ceil is 5. 

Output: May be different for different runs 

4
3
4
4
4

Time Complexity: O(n)
Auxiliary Space: O(n) because extra space for the array has been used

This article is compiled by Aashish Barnwal. Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.

Given n numbers, each with some frequency of occurrence. Return a random number with probability proportional to its frequency of occurrence.

Example: 

Let following be the given numbers.
  arr[] = {10, 30, 20, 40}  

Let following be the frequencies of given numbers.
  freq[] = {1, 6, 2, 1}  

The output should be
  10 with probability 1/10
  30 with probability 6/10
  20 with probability 2/10
  40 with probability 1/10

It is quite clear that the simple random number generator won’t work here as it doesn’t keep track of the frequency of occurrence. 

We need to somehow transform the problem into a problem whose solution is known to us.

One simple method is to take an auxiliary array (say aux[]) and duplicate the numbers according to their frequency of occurrence. Generate a random number(say r) between 0 to Sum-1(including both), where Sum represents summation of frequency array (freq[] in above example). Return the random number aux[r] (Implementation of this method is left as an exercise to the readers).

The limitation of the above method discussed above is huge memory consumption when frequency of occurrence is high. If the input is 997, 8761 and 1, this method is clearly not efficient.

How can we reduce the memory consumption? Following is detailed algorithm that uses O(n) extra space where n is number of elements in input arrays.
1. Take an auxiliary array (say prefix[]) of size n. 
2. Populate it with prefix sum, such that prefix[i] represents sum of numbers from 0 to i. 
3. Generate a random number(say r) between 1 to Sum(including both), where Sum represents summation of input frequency array. 
4. Find index of Ceil of random number generated in step #3 in the prefix array. Let the index be indexc. 
5. Return the random number arr[indexc], where arr[] contains the input n numbers.
  Before we go to the implementation part, let us have quick look at the algorithm with an example: 
      arr[]: {10, 20, 30} 
      freq[]: {2, 3, 1} 
      Prefix[]: {2, 5, 6} 
  Since last entry in prefix is 6, all possible values of r are [1, 2, 3, 4, 5, 6] 
         1: Ceil is 2. Random number generated is 10. 
         2: Ceil is 2. Random number generated is 10. 
         3: Ceil is 5. Random number generated is 20. 
         4: Ceil is 5. Random number generated is 20. 
         5: Ceil is 5. Random number generated is 20. 
         6. Ceil is 6. Random number generated is 30. 
  In the above example 
      10 is generated with probability 2/6. 
      20 is generated with probability 3/6. 
      30 is generated with probability 1/6.

How does this work? 
Any number input[i] is generated as many times as its frequency of occurrence because there exists count of integers in range(prefix[i – 1], prefix[i]] is input[i]. Like in the above example 3 is generated thrice, as there exists 3 integers 3, 4 and 5 whose ceil is 5. 

Output: May be different for different runs 

4
3
4
4
4

Time Complexity: O(n)
Auxiliary Space: O(n) because extra space for the array has been used

This article is compiled by Aashish Barnwal. Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.