Топ контрибуторов
loading
loading
Знаете ли Вы, что

После прохождения теста можно комментировать вопросы теста, а Ваши комментарии увидят модераторы теста и пользователи, которым когда-либо эти вопросы попадались.

Лента обновлений
ссылка 14:57:26
Комментарий от sashka228:
согласна
ссылка 14:56:54
Комментарий от sashka228:
#ресоурсескотився
ссылка 14:54:17
Комментарий от sashka228:
yep.
ссылка 14:12:03
Добавлен вопрос в тест C++ - Средний уровень
ссылка 14:00:35
Комментарий от Anton_2015:
Гарне питання
Статистика

Тестов: 153, вопросов: 8596. Пройдено: 445772 / 2188315.

Программирование генератора псевдослучайных чисел на С++

head tail Статья
категория
C++
дата11.03.2014
авторingwarsmith
голосов6

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

Программисты, использующие C++11, имеют возможность использовать нововведения в стандарт C++, в том числе и генераторы псевдослучайных чисел, подобные имеющимся в библиотеке boost, более серьезные в смысле приближения генерируемых числовых последовательностей к равномерному распределению, чем функция rand() из ANSI-C. Однако самостоятельно реализовать генератор псевдослучайных чисел так же возможно, и это актуально для программистов, использующих стандарт языка C++03.

Одними из наиболее часто используемых методов генерации псевдослучайных чисел являются различные модификации так называемого линейного конгруэнтного метода, схема которого предложена Д.Г. Лемером (Derrick Henry Lehmer) в 1949 г.:

Xn+1 = (aXn + c) mod m, где m – модуль, a – множитель, c – приращение, mod – операция взятия остатка от деления.
Причем m > 0, 0 < a ≤ m, 0 < c ≤ m, также задается начальное значение X0: 0 < X0 ≤ m.

Выбор параметров m, a, c, X0 не может быть произвольным. Пример: при m=7, X0=1, a=2, c=4 получится следующая последовательность: 1,6,2,1,6,2,1,… Таким образом, напрашиваются два вывода:
  • Числа m, a, c, X0 не могут быть случайными.
  • Линейный конгруэнтный метод даёт нам повторяющиеся последовательности – конгруэнтная последовательность ВСЕГДА образует «петли». Этот цикл (период), повторяющийся бесконечное число раз – свойство всех последовательностей вида Xn+1 = f(n)

Таким образом, необходимо выбирать параметры m, a, c, X0 так, чтоб период был максимальным. Модуль m должен быть достаточно большим, т.к. период не больше m. Удобно связать m с длиной слова компьютера и использовать 2e – 1 либо 2e + 1 для e-разрядной машины, а еще лучше – m наибольшее простое, меньшее 2e. При этом длина периода равна m в следующем случае: c и m – взаимно простые числа, b = a – 1 кратно p для любого p, являющегося множителем m, b кратно 4, если m кратно 4.

В языке Си стандарта ANSI-C был реализован линейно-конгруэнтный метод (Д. Кнут, Г. Левис) в виде функции rand():

#define RAND_MAX 32767
unsigned long next=1;
int rand(void)
{ next=next*1103515245+12345;
return((unsigned int)(next/65536)%RAND_MAX);
} void srand(unsigned int seed) { next=seed; }
Использованы значения параметров a=1664525, c=1013904223, m=215-1:
next=1664525*next+1013904223

Системный генератор MS Fortran использует формулу: Xn = 48271Xn-1mod 231-1
Здесь рассмотрим результаты генерации псевдослучайных числовых последовательностей в интервале от 0 до 1000 в результате четырех опытов, в каждом из которых генерировалось 10000 чисел. Формула следующая:
Xn = (253801Xn-1 + 14519) mod 232 – 1. Написан класс MyLKMgenerator.

Листинг mylkmgenerator.h:


#ifndef MYLKMGENERATOR_H
#define MYLKMGENERATOR_H
 
#include <ctime>
 
class MyLKMgenerator
{
public:
    MyLKMgenerator();
 
    void randomization(unsigned long seed);
 
    void randomizationByCTimeFunction();
 
    unsigned long getRandomValueBySpecialLKM();
 
    unsigned long getRndValBySpecLKMFromDefinedInterval(
                   int rangeMinOfInterval,int rangeMaxOfInterval);
 
private:
    //m=(2^32-1)
    static const unsigned long RandMaxSpecLKM=4294967295L;
    unsigned long next;
};
 
#endif //MYLKMGENERATOR_H

Листинг mylkmgenerator.cpp:


#include "mylkmgenerator.h"
 
MyLKMgenerator::MyLKMgenerator()
{
    next=1L;
}
 void MyLKMgenerator::randomization(unsigned long seed)
{
    next=seed;
}
void MyLKMgenerator::randomizationByCTimeFunction()
{
    next=static_cast<unsigned long>(time(NULL));
}
unsigned long MyLKMgenerator::getRandomValueBySpecialLKM()
{
    next=(253801L*next+14519L)%RandMaxSpecLKM;
    return next;
}
unsigned long MyLKMgenerator::getRndValBySpecLKMFromDefinedInterval(
int rangeMinOfInterval,int rangeMaxOfInterval)
{
    unsigned long rndVal = getRandomValueBySpecialLKM() % rangeMaxOfInterval
    + rangeMinOfInterval;
    return rndVal;
}


Листинг main.cpp:


#include <iostream>
#include "mylkmgenerator.h"
 
using namespace std;
 
int main()
{
    MyLKMgenerator generator;
    generator.randomizationByCTimeFunction();
     for(int i=0; i<10000; ++i)
    {
         cout << generator.getRndValBySpecLKMFromDefinedInterval(0,1000)
              << endl;
    }
    return 0;
}

Результаты приведены на четырех гистограммах, по которым видно, что распределение псевдослучайных чисел близко к равномерному:

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

Если Вам понравилась статья, проголосуйте за нее

Голосов: 6  loading...
fdsmerlin   mrgluck   Marik   embarq   sergeyDaz   Hitrak