Материал: Получение случайных чисел на ЭВМ
Методы Монте-Карло и случайные величины
Методами Монте-Карло называются численные методы решения математических задач при помощи моделирования случайных величин. Как правило, в качестве стандартной выбирают непрерывную случайную величину , равномерно распределенную в интервале (0, 1). Основные характеристики этой величины: плотность , функция распределения , математическое ожидание , дисперсия .
Иногда в качестве стандартной используются дискретная случайная величина , принимающая с одинаковой вероятностью значения 0,1,2,…,9. Величина называется случайной цифрой, а величина - случайным числом. Связь между и устанавливается разложением числа в бесконечную десятичную дробь:
или . (1)
Справедливо утверждение: если - произвольное целое положительное число, то случайная величина равномерно распределена в интервале (0,1), где - дробная часть числа .
Способы получения случайных величин
Метод таблиц
Осуществляют независимых опытов, в результате которых получают случайных цифр: . Записав эти цифры в порядке появления в таблицу, получают таблицу случайных цифр. Достоинства метода: однократная проверка, возможность воспроизводить числа. Недостатки: ограниченный запас чисел, таблица большого объема занимает много места в накопителе. Этот метод используют главным образом при расчетах вручную; для расчетов на ЭВМ им практически не пользуются.
Метод датчиков
Генераторами, или датчиками, случайных величин называют различные технические устройства, вырабатывающие случайные величины. Чаще всего для построения датчика используют радиоэлектронные приборы (диоды, тиратроны, газотроны и др.). Простейшим датчиком двоичных цифр является счетчик, выдающий число , т.е. 0 при четном и 1 при нечетном . Обычно датчики случайных чисел содержат генераторов описанного типа, работающих независимо, так, что датчикам выдается приближенное случайное число , записанное в форме m-разрядной двоичной дроби. Этот метод в основном применяется в системах автоматического регулирования и аналоговых вычислительных машинах, значительно реже - в методах Монте-Карло. Достоинства метода: неограниченный запас чисел, сверхбыстрое их получение, запас чисел не занимает много места в накопителе. Недостатки: периодическая проверка, невоспроизводимость чисел, требуется специальное устройство.
Метод случайных чисел
Псевдослучайными числами называют числа , которые вычисляются по какой-либо заданной формуле и могут быть использованы вместо случайных чисел при решении некоторых задач. Достоинства метода: однократная проверка, воспроизводимость чисел, их быстрое получение, запас чисел занимает мало места в накопителе. Недостатки: запас чисел ограничен. Этот метод - самый удобный с практической точки зрения и является основным при расчетах методом Монте-Карло.
Алгоритмы получения псевдослучайных чисел
Большинство алгоритмов представляют собой рекуррентные формулы первого порядка
, (2)
где начальное число задано.
Метод середины квадрата (Неймана)
Число представляют 2k -значным:
.
Чтобы получить число , надо возвести в квадрат: , а затем отобрать средние 2K цифр этого квадрата: .
Этому методу соответствует функция
(3)
или (что то же самое)
, (4)
где - целая часть числа x.
Недостатком этого метода является наличие больше, чем нужно, малых чисел. Кроме этого, при некоторых наблюдается вырождение последовательности, т.е. при n.
Метод сравнений (Лемера)
В этом методе , т.е. , где - большое целое число. Если задать , где - целые числа и взаимно просто с , то все будут несократимыми дробями вида , где числители определяются по формуле
(5)
Последняя запись означает, что равно остатку, полученному при делении на .
На практике обычно используют формулу (5). Вопрос о пригодности псевдослучайных чисел, в конечном счете, решается эмпирически. При некоторых , получают удовлетворительные последовательности, при других - плохие.
Метод Коробова
Псевдослучайные числа вычисляются по формуле
, (6)
где ; ;; i=1,2,…,n;
m - простое число вида (- тоже простое число);
n - число псевдослучайных точек.
Заданиe: Получить десять псевдослучайных точек, равномерно распределенных на интервале (0,1), методами Неймана, Лемера и Коробова. Необходимые для вычислений значения параметров указаны в вариантах задания (таблица).
Выполнение:
А) Метод середины квадрата (Неймана)
Листинг:
случайный величина монте карло
#include <iostream>
#include <cmath>
using namespace std;
double F(double x)
{ int k=1;
int celoe= pow(x,2)*pow(10, 3*k);
double drobnoe = (celoe * pow(10, -2*k));
if (drobnoe>0)
{
drobnoe-=floor(drobnoe);
}
return drobnoe;
}
int main()
{ //Русский язык
setlocale(LC_ALL,"russian");
double x0; //начальное число
int const nn=20; //максимальное количество элементов в массиве
int n;
double x[nn+1]; //массив цифр
int y[nn+1]; //массив хранения полученных чисел
cout<<"Генерация случайных чисел с помощью метода середины квадрата(Неймана)"<<endl;
cout<<"Сколько псевдослучайных точек вы бы хотели видеть на интервале (0,1)?"<<endl<<"n = ";
cin>>n;
cout<<"Введите начальное число x0"<<endl;
cin>>x0;
x[0]=x0;
x[1]=F(x[0]);
for (int i=1;i<n+1;i++)
{
x[i]=F(x[i-1]);
} cout<<endl;
for(int i=1;i<n+1;i++)
{
cout<<x[i]<<endl;
}
return 0;
}
Результат работы программы:
Б) Метод сравнений (Лемера)
Листинг:
#include <iostream>
#include <cmath>
using namespace std;
int main()
{ setlocale(LC_ALL,"Russian");
cout<<"Генерация случайных чисел методом сравнений (Лемера)."<<endl;
int const n = 10;
double m0 = 1.6;
double g = pow(5,5);
double M = pow(2,15);
double y[n+1];
double m[n+1];
m[0]=m0;
for (int i = 1; i<n+1; i++)
{
m[i]=(g*m[i-1])/M;
m[i]-=floor(m[i]); //получим остаток (дробь)
// cout<<m[i]<<endl;
y[i]=g*m[i-1]/M;
y[i]-=floor(y[i]);
cout<<y[i]<<endl;
}
return 0;
}
Результат работы программы:
