Реализация класса RandomNumber
Для создания псевдослучайных чисел используется линейный конгруэнтный алгоритм. Этот алгоритм использует большой нечетный постоянный множитель и постоянное слагаемое вместе с seed-значением для итеративного создания случайных чисел и обновления seed-значения:
const unsigned long maxshort = 65536;
const unsigned long multiplier = 1194211693;
const unsigned long adder = 12345;
Последовательность случайных чисел начинается с начального значения для длинного целого randSeed. Задание этого значения называется настройкой (seeding) генератора случайных чисел и выполняется конструктором.
Конструктор позволяет клиенту передавать seed-значение или использовать для его получения машинно-зависимую функцию time. Мы подразумеваем, что функция time объявляется в файле <time.h>. При вызове конструктора с параметром 0 функция time возвращает беззнаковое длинное (32-битовое) число, указывая количество секунд, прошедших после базового времени. Используемое базовое время включает полночь 1-го января 1970 года и полночь 1-го января 1904 года. В любом случае, это большое беззнаковое длинное значение:
//генерация seed-значения
RandomNumber::RandomNumber (unsigned long s)
{
if (s == 0)
randSeed = time(0); //использование системной функции time
else
randSeed = s; //пользовательское seed-значение
}
В каждой итерации используем константы для создания нового беззнакового длинного seed-значения:
randSeed=multiplier*randSeed+adder;
В результате умножения и сложения верхние 16 битов 32-битового значения randSeed являются случайными ("хорошо перемешанными") числами. Наш алгоритм создает случайное число в диапазоне от 0 до 65535, сдвигая 16 битов вправо. Мы отображаем это число на диапазон 0…n-1, беря остаток от деления на n. Результатом является значение Random(n).
//возвращать случайное целое 0<=value<=n-1<65536
unsigned short RandomNumber::Random (unsigned long n)
{
randSeed=multiplier*randSeed+adder;
return (unsigned short) ((randSeed)>>16)%n) ;
}
Для числа с плавающей точкой сначала вызываем метод Random(maxshort), который возвращает следующее случайное целое число в диапазоне от 0 до maxshort-1. После деления на double(maxshort) получаем действительное число в интервале 0<=fRandom() < 1.0.
double RandomNumber::fRandom (void)
{
return Random(maxshort)/double(maxshort);
}
Объявление и реализация RandomNumber содержится в файле "random.h".
Приложение: Частота выпадения лицевой стороны при бросании монет. Класс RandomNumber используется для имитации повторяемого бросания 10 монет. Во время бросания некоторые монеты падают лицевой стороной (head)1 вверх, а другие - обратной. Бросание десяти монет имеет результатом число падений лицевой стороной в диапазоне 0-10. Интуитивно вы подразумеваете, что 0 лицевых сторон или 10 лицевых сторон в бросании 10 монет - это относительно невероятно. Более вероятно, что количества выпадений разных сторон будут примерно равными. Число лицевых сторон будет находиться где-нибудь в середине диапазона 0-10, скажем, 4-6. Мы проверим это интуитивное предположение большим числом (50 0000) повторений бросания. Массив head ведет подсчет количества раз, когда соответствующий подсчет лицевых сторон составляет 0,1,…,10.
Значение head[i] (0<=i<=10) - это количество раз в 50 000 повторениях, когда ровно i лицевых сторон выпадает во время бросания 10 монет.
Программа 3. График частоты
Бросание 10 монет составляет событие. Метод Random с параметром 2 моделирует одно бросание монеты, интерпретируя возвращаемое значение 0 как обратные стороны, а возвращаемое значение 1 как лицевые стороны. Функция TossCoins объявляет статический объект coinToss типа Random-Number, использущий автоматическое задание seed-значения. Так как этот объект является статическим, каждый вызов TossCoins использует следующее значение в одной последовательности случайных чисел. Бросание указанного количества монет выполняется суммированием 10 значений, выдаваемых CoinToss.Random(2). Возвращаемый результат приращивает соответствующий счетчик в массиве лицевых сторон.
Выходом программы является частотный график количества лицевых сторон. График с числом лицевых сторон на оси х и относительным числом событий (occurences) — на оси y обеспечивает наглядное представление того, что известно как биномиальное распределение. Для каждого индекса i относительное число событий, при которых лицевые стороны выпали ровно i раз, составляет
heads[i]/float(NTOSSES)
Это значение используется для помещения символа * в относительном местоположении между 1-й и 72-й позицией строки. Результирующий график является аппроксимацией биномиального распределения.
#include <iostream.h>
#include <iomanip.h>
#include "random.h" // включает генератор случайных чисел
// "бросить" numberCoins монет и возвратить общее число
// выпадений лицевой стороны
int TossCoins(int numberCoins)
{
static RandomNumber coinToss;
int if tosses = 0;
for (i=0;i<numberCoins;i++ )
// Random (2)=1 индицирует лицевую сторону
tosses += coinToss.Random(2) ;
return tosses;
}
void main (void)
{
// число монет в бросании и число бросаний
const int NCOINS = 10;
const long NTOSSES = 50000;
// heads [0]=сколько раз не выпало ни одной лицевой стороны
// heads [1]=сколько раз выпала одна лицевая сторона и т .д.
long i, heads [NCOINS+1] ;
int j, position;
// инициализация массива heads
for (j=0;j<=NCOINS+1; j++)
heads [j] = 0;
//"бросать" монеты NTOSSES раз и записывать результаты
//в массив heads
for (i=0;i<NTOSSES; i++)
heads [TossCoins(NCOINS)] ++;
// печатать график частот
for (i=0;i < NCOINS+1;I++)
{
position=int(float(heads[i])/float(NTOSSES)*72);
cout << setw(6) << i << " ";
for (j=0;j<position-1; j++)
cout << " " ;
// ' *' относительное число бросаний с i лицевыми сторонами
cout << ' *' << endl;
}
}