Получение псевдослучайных чисел

КУРСОВАЯ РАБОТА

ПО ДИСЦИПЛИНЕ

"ТЕХНОЛОГИЯ ПРОГРАММИРОВАНИЯ"

"Получение псевдослучайных чисел"

Содержание

Введение

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

2. Методы получение псевдослучайных чисел

Линейный конгруэнтный метод

Метод Фибоначчи

Вихрь Мерсенна

3. Тестирование псевдослучайных последовательностей

4. Генератор случайных чисел в Borland C++

Заключение

5. Список использованных источников

Приложение

Введение

Программа предназначена для формирования и просмотра команды для олимпиады по программированию.

а) Ввод информации.

По запросу с клавиатуры поочередно вводятся фамилия, имя студента, а также язык программирования, на котором он предпочитает писать программы (Pascal, C,C++).

б) Просмотр введенного списка.

Если список не пустой, то при выборе этого пункта меню на экран поочередно выводится полная информация о каждом студенте.

в) Отбор команды.

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

г) Проверка, может ли быть укомплектована команда.

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

Реализовать программу на базе связного списка.

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

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

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

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

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

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

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

2. Методы получение псевдослучайных чисел

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

Линейный конгруэнтный метод

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

Этот алгоритм заключается в итеративном применении следующей формулы:

,

где a>0, c>0, m>0 - некоторые целочисленные константы. Получаемая последовательность зависит от выбора стартового числа  и при разных его значениях получаются различные последовательности случайных чисел. В то же время, многие свойства этой последовательности определяются выбором коэффициентов в формуле и не зависят от выбора стартового числа. Ясно, что последовательность чисел, генерируемая таким алгоритмом, периодична с периодом, не превышающим m. При этом длина периода равна m тогда и только тогда, когда:

) НОД (c, m) = 1 (то есть c и m взаимно просты)

) a - 1 кратно p для всех простых p - делителей m;

) a - 1 кратно 4, если m кратно 4.

Статистические свойства получаемой последовательности случайных чисел полностью определяются выбором коэффициентов a и c.

Метод Фибоначчи

Интересный класс генераторов псевдослучайных последовательностей основан на использовании последовательностей Фибоначчи. Классический пример такой последовательности {0,1,1,2,3,5,8,13,21,34 …} - за исключением первых двух ее членов, каждый последующий член равен сумме двух предыдущих.

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

В связи с этим линейный конгруэнтный алгоритм постепенно потерял свою популярность, и его место заняло семейство фибоначчиевых алгоритмов, которые могут быть рекомендованы для использования в алгоритмах, критичных к качеству случайных чисел. В англоязычной литературе фибоначчиевы датчики такого типа называют обычно "Subtract-with-borrow Generators" (SWBG).

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

Один из широко распространённых фибоначчиевых датчиков основан на следующей итеративной формуле:

=

где  - вещественные числа из диапазона [0,1), a,b - целые положительные числа, называемые лагами. Для работы фибоначчиеву датчику требуется знать max{a,b} предыдущих сгенерированных случайных чисел. При программной реализации для хранения сгенерированных случайных чисел используется конечная циклическая очередь на базе массива. Для старта фибоначчиевому датчику требуется max{a,b} случайных чисел, которые могут быть сгенерированы простым конгруэнтным датчиком.

Лаги a и b - "магические" и их не следует выбирать произвольно. Рекомендуются следующие значения лагов: (a, b) = (55,24), (17,5) или (97,33). Качество получаемых случайных чисел зависит от значения константы, a чем оно больше, тем выше размерность пространства, в котором сохраняется равномерность случайных векторов, образованных из полученных случайных чисел. В то же время, с увеличением величины константы a увеличивается объём используемой алгоритмом памяти.

Значения (a,b) = (17,5) можно рекомендовать для простых приложений, не использующих векторы высокой размерности со случайными компонентами. Значения (a,b) = (55,24) позволяют получать числа, удовлетворительные для большинства алгоритмов, требовательных к качеству случайных чисел. Значения (a,b) = (97,33) позволяют получать очень качественные случайные числа и используются в алгоритмах, работающих со случайными векторами высокой размерности. Получаемые случайные числа обладают хорошими статистическими свойствами, причём все биты случайного числа равнозначны по статистическим свойствам.

Вихрь Мерсенна

Вихрь Мерсенна (Mersenne twister) - это генератор псевдослучайных чисел, основанный на свойствах простых чисел Мерсенна и обеспечивает быструю генерацию высококачественных псевдослучайных чисел. Вихрь Мерсенна лишен многих недостатков присущих другим ГПСЧ таких как малый период, предсказуемость, легко выявляемая статистическая зависимость.

Вихрь Мерсенна является витковым регистром сдвига с обобщённой отдачей (twisted generalised feedback shift register, TGFSR). "Вихрь" - это преобразование, которое обеспечивает равномерное распределение генерируемых псевдослучайных чисел в 623 измерениях (для линейных конгруэнтных генераторов оно ограничено 5-ю измерениями). Поэтому корреляция между последовательными значениями в выходной последовательности Вихря Мерсенна пренебрежимо мала.

Вихрь Мерсенна имеет огромный период, а именно, доказано, что его период равен числу Мерсенна 219937−1, что более чем достаточно для многих практических приложений.

Существуют эффективные реализации Вихря Мерсенна, превосходящие по скорости многие стандартные ГПСЧ (в частности, в 2-3 раза быстрее линейных конгруэнтных генераторов). Алгоритм основан на следующем рекуррентном выражении:

= + () A, (k=0,1,2…)

где n - целое, которое обозначает степень рекуррентности,- целое, 1< m < n,

А - матрица размера WxW

В правой части обозначает "старшие w-r бит" , и , "младшие r бит"

3. Тестирование псевдослучайных последовательностей

Тестирование псевдослучайных последовательностей (ПСП) - совокупность методов определения меры близости заданной псевдослучайной последовательности к случайной. В качестве такой меры обычно выступает наличие равномерного распределения, большого периода, равной частоты появления одинаковых подстрок и т.п.

Существует несколько методов тестирования ПСП:

. Графический тест.

К этой категории относятся тесты, результаты которых отображаются в виде графиков, характеризующих свойства исследуемой последовательности. Среди них:

а) гистограмма распределения элементов последовательности (позволяет оценить равномерность распределения символов в последовательности и определить частоту повторения каждого символа);

б) распределение на плоскости (предназначено для определения зависимости между элементами последовательности);

в) проверка серий (позволяет определить равномерность отдельных символов в последовательности, а так же равномерность распределения серий из k бит);

г) проверка на монотонность.

. Статистический тест.

В отличие от графических тестов, статистические тесты выдают численную характеристику последовательности и позволяют однозначно сказать, пройден ли тест.

4. Генератор случайных чисел в Borland C++

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

В языке программирования C получить случайное число можно с помощью функции rand (), которая входит в стандартную библиотеку языка. Эта функция не принимает никакие параметры. Функция rand () возвращает целое число от 0 до значения присвоенного константе RAND_MAX. Значение RAND_MAX зависит от системы и определено в заголовочном файле stdlib. h. Так, например, оно может быть равно 32767 (двухбайтовое целое) или 2147483647 (четырехбайтовое целое).

Код ниже выводит на экран 50 случайных чисел:

#include <stdio. h>

#include <stdlib. h>() {i;(i = 1; i <= 50; i++) {("%15d", rand ());(i % 5 == 0) printf ("\n");

}

}

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

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

Однако это начальное число можно изменить с помощью функции srand (), которой в качестве параметра передается любое целое число. Инициализирующее значение привязывают к какому-либо процессу, протекающему в операционной системе, например, к часам. Время (учитывая не только время суток, но и дату) никогда не бывает одинаковым. Значит значение для srand (), преобразованное в целое из системного времени, будет различным.

Текущее время можно узнать с помощью функции time (), прототип которой описан в файле time. h. Передав time () в качестве параметра NULL, мы получим целое число, которое можно передать в srand ():(time (NULL));

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

(float) rand () / RAND_MAX * (max - min) + min

Функция rand () генерирует любое случайное число от 0 до RAND_MAX с равной долей вероятности. Другими словами, у числа 100 есть такой же шанс выпасть, как и у числа 25876.

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

#include <stdio. h>

#include <time. h>

#define N 500() {i;arr [5] = {0};(time (NULL));(i=0; i < N; i++)(rand () % 5) {0: arr [0] ++; break;1: arr [1] ++; break;2: arr [2] ++; break;3: arr [3] ++; break;4: arr [4] ++; break;

}(i=0; i < 5; i++)("%d - %.2f%%\n", i, ( (float) arr [i] / N) * 100);

}

В приведенной программе массив из пяти элементов сначала заполняется нулями. Случайные числа генерируются от 0 до 4 включительно. Если выпадает число 0, то увеличивается значение первого элемента массива, если число 1, то второго, и т.д. В конце на экран выводится процент выпадения каждого из чисел.

Заключение

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

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

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

В начале XX века случайные последовательности имитировались с помощью простейших случайных экспериментов: бросание монеты или игральной кости, извлечение шаров из урны, раскладывание карт, рулетка и т.д. В 1927 г.Л. Типпетом впервые были опубликованы таблицы, содержащие свыше 40000 случайных цифр, "произвольно извлечённых из отчётов о переписи населения". В 1939 г. с помощью специально сконструированного механического устройства - генератора случайных чисел, М. Дж. Кендалл и Б. Бэбингтон-Смит создали таблицу, включающую 105 случайных цифр. В 1946 г. американский математик Джон фон Нейман впервые предложил компьютерный алгоритм генерации случайных чисел. В 1955 г. компания RAND Corporation опубликовала получившие широкую популярность таблицы, содержащие 106 случайных цифр, сгенерированных на ЭВМ.

5. Список использованных источников

1) Керниган Б. Язык программирования Си: Задачи по языку Си. / Б. Керниган, Д. Ритчи, А. Фьюэр М.: Финансы и статистика, 1985.190 - 192 с.

) Подбельский В.В., Фомин С.С. Программирование на языке Си. Учеб. пособие. М.: Финансы и статистика, 2004.382-385 с.

Приложение

#include <iostream. h>

#include <stdlib. h>

#include <conio. h>

#include <string. h>

#include <fstream. h>students {prog{* fam;* name;* lang;* next;() {fam=""; name="";=""; next=NULL; };ostream & operator<< (ostream& os, prog * pr) {<<pr->fam<<'\t'<<pr->name<<'\t'<<pr->lang<<endl;os; }

};progCount;* first;* current;:() {=0;=current=NULL; };* getfirst () {this->first;

}Add (char* f, char* n, char * l, int len) {* b= (prog *) new char [len];* f1= new char (strlen (f) +1),

*n1= new char (strlen (n) +1),

*l1= new char (strlen (l) +1);(f1,f);(n1,n);(l1,l);>fam=f1; b->name=n1; b->lang=l1;(progCount==0) {first=b; }current->next=b;=b;++;>next=NULL;

}Show (prog * p) {*cur=p;(progCount==0) {cout<<"No data. "<<endl; return; };(cur) {<<cur;=cur->next;

}

}Remove (char * f, char * n, char * l) {* rem=first, *prev=rem;i=0;(progCount==0) {cout<<"No data. "<<endl; return; };(! strcmp (first->fam,f) &&! strcmp (first->name,n) &&! strcmp (first->lang,l)) {++; progCount--;=first->next;rem;=rem=first;

}(rem! =NULL) {(! strcmp (rem->fam,f) &&! strcmp (rem->name,n) &&! strcmp (rem->lang,l)) {>next=rem->next;rem;=prev->next;++; progCount--; }{prev=rem;=rem->next; }

};(i==0) {cout<<"Not found. "<<endl; return; }{cout<<i<<" programmer (s) ="<<f<<' '<<n<<' '<<l<<" is (are) deleted. "<<endl; }

}RemoveAll () {* rem=first;(rem! =NULL) {=first->next;rem;=first;

}=0;

}Select (char * l) {i=0;* cur=first;(cur) {(! strcmp (cur->lang, l)) {=cur->next;++; }{cur=cur->next; }(i==3) {break; }

}(i<3) {<<"Can't select team"<<endl; return; }{ cout<<"Your team: "<<endl; i=0; cur=first;(cur) {(! strcmp (cur->lang, l)) {<<cur;=cur->next;++; }{cur=cur->next; }(i==3) {break; }

} }

}Save () {* cur=first;nf;. open ("YEARWORK\\Program. txt");(nf==NULL) {<<"Can't open file"<<endl;; }(cur) {<<cur;=cur->next;

}. close ();<<"File created successfully!"<<endl;

}

};a;menu () {();<<"Menu: "<<endl;<<"1. Add student. "<<endl;<<"2. Show student (s). "<<endl;<<"3. Remove student (s). "<<endl;<<"4. Remove all student (s). "<<endl;<<"5. The selection of team. "<<endl;<<"6. Save (file ""Program. txt""). "<<endl;<<"7. Clear screen. "<<endl;<<"0. Exit. "<<endl;

};main () {* f, *n, *l;c, len;();{<<"Choose and type: ";>>c;(c) {1: {cout<<"Family: "; cin>>f;<<"Name: "; cin>>n;<<"Language (Pascal/ C/ C++): "; cin>>l;=strlen (f) +strlen (n) +strlen (l) +3;. Add (f,n,l, len); break; }2: {a. Show (a. getfirst ()); break; }3: {cout<<"Family: "; cin>>f;<<"Name: "; cin>>n;<<"Language (Pascal/ C/ C++): "; cin>>l;. Remove (f,n,l); break; }4: {a. RemoveAll (); break; }5: {cout<<"What language: ";>>l;. Select (l);; }6: {a. Save (); break; }7: {menu (); break; }0: {break; }: {cout<<"Invalid menu option. "<<endl; break; }

}

}(c! =0);

}