Генераторы случайных чисел реферат
Обновлено: 26.06.2024
Овладение навыками алгоритмизации и программирования задач с использованием датчиков случайных чисел, способами получения случайных чисел с различными законами распределения, навыками оценки качества псевдослучайных чисел и их соответствия заданному закону распределения.
1.2. Задания для самостоятельной подготовки
способы получения случайных чисел с различными законами распределения;
-способы использования в программах обращений к функциям или подпрограммам для получения псевдослучайных чисел с различными законами распределения;
способами использования случайных чисел для моделирования.
Разработать алгоритм решения в соответствии с заданием.
Составить программу решения задачи.
Подготовить тестовый вариант программы и исходных данных.
1.3. Задание к работе
1. Выполнить на ЭВМ программу в соответствии со следующим заданием:
Сгенерировать последовательность из 50 случайных чисел с нормальным законом распределения а=5, =4) и последовательность из 50 случайных чисел с экспоненциальным законом распределения с параметром =5. Все числа свести в массив, расположив их по возрастанию. Вычислить среднее значение, дисперсию и вывести результаты на печать в виде гистограммы, разбив последовательность чисел на десять интервалов
2. Проверить правильность выполнения программы с помощью тестового варианта.
2. Руководство программиста .
Прежде, чем приступить к самому процессу алгоритмизации и программирования заглянем в теорию, по которой, собственно, и дано задание.
2.1. Теоретическая база.
2.1.1. Нормальное распределение.
Н
ормальным называют распределение вероятностей непрерывной случайной величины, которое описывается плотностью
Мы видим, что нормальное распределение определяется двумя параметрами: а и . Достаточно знать эти параметры, чтобы задать нормальное распределение. Покажем, вероятностный смысл этих параметров таков: а есть математическое ожидание, —среднее квадратическое отклонение нормального распределения.
2.1.2 Показательное (экспоненциальное) распределение.
П
оказательным (экспоненциальным) называют распределение вероятностей непрерывной случайной величины X, которое описывается плотностью
где - постоянная положительная величина.
Мы видим, что показательное распределение определяется одним параметром . Эта особенность показательного распределения указывает на его преимущество по сравнению с распределениями, зависящими от большего числа параметров. Обычно параметры неизвестны и приходится находить их оценки (приближенные значения); разумеется, проще оценить один параметр, чем два или три и т. д. Примером непрерывной случайной величины, распределенной по показательному закону, может служить время между появлениями двух последовательных событий простейшего потока.
2.2. Начало алгоритмизации.
Для получения двух последовательностей из 50 случайных чисел с показательным и нормальным законами распределения необходимо организовать цикл, который будет выполнятся 50 раз. Внутри цикла будем пользоваться функцией из Турбо Паскаля random(a) - эта функция выдает произвольное число из интервала от 1 до a, a 65535. Каждое полученное число будет вносится в массив, причем первые 50 элементов этого массива получены по нормальному закону, а другие 50 - по показательному.
Для упорядочивания массива случайных величин создадим двойной цикл. Для расчета мат. ожидания и дисперсии упорядоченного массива также создадим двойной цикл, с учетом того, что массив уже надо разбить на 10 частей и расчет проводить по каждому из промежутков. Для построения гистограммы воспользуемся средствами модуля Graph.tpu.
Блок-схемой основной программы будет приведена в приложении. Также в приложении будут размещщены блок-схемы подпрограмм-процедур, используемых в данной программе.
Перед процессом программирования составим таблицу используемых в программе и подпрограммах таблицу переменных и констант.
Таблица 1. Описание переменных и констант.
Тип в Turbo Pascal
Переменный для хранения параметров вызова процедур.
Символьные переменные для управления интерфейсной частью .основной программы и процедур соответственно.
Логические параметры, задающие выход из процедур и основной программы. Позволяют делать программу болле гибкой в применении.
Переменные, содержащие данные о типе графического драйвера и его режиме работы. Установленны в программе на автоматическое определение.
Массив для хранения входных данных в программе. Начальное знаачение [5,4,5].
Массив для хранения элементов генерируемой последовательности.
array[1..100] of real
Массивы, используемые для более компактности ввода параматров генерации последовательности в процедуре DoWorkс параметром work=1.
Массивы с данными о дисперсии и мат.ожидании по промежуткам последовательности.
Мат.ожидание и дисперсия по всей последовательности.
Временная переменная (буфер).
Массив для управления выбора пункта меню.
Константы для задания цветов меню.
2.3. Пояснения к программе.
2.3.1. Основная программа.
В начале основной программы происходит задание первоначальных параметров меню, входных данных по условию задания и автоматическое определения типа и режима работы графического адаптера.
После определения происходит первоначальная (чернвая) прорисовка интерфейсной части программы. Для этого используется три блока, прорисовывающие строку помощи (drawhelp(0)), диалогового окна (drawwin) и строки меню (drawmenu(5)).
Значение параметра work
Задание параметров для построения последовательностей.
Работы основной программы заверщается при истонном значении переменной exitprog, чего можно достичь комбинацией Alt-x (об этом тоже информирует строка помощи).
2.3.2. Процедура drawhelp.
Эта процедура полностью предназначена для навигации оператора с работой в программе.
Для вызова используется один параметр (help), чего достаточно для вывода полной подсказки далнейших действий. Ниже приводится таблица со значением параметра и строки, которая высвечивается внизу экрана.
Значение параметра help
Вид строки помощи
F1-Парам. F2-Посл-ти F3-Гистогр. F10-Меню (Alt-x)-Выход
Esc-Закончить изменение параметров. BckSp-Изменить параметр. F4-Постр. посл-ть'
Нажмите Up или Down для просмотра или Esc для выхода
В блок-схеме к этой процедуре использованы сокращения. Так s1 означает, что help=1; s2 – help=2 и так далее.
2.3.3 Процедура drawwin .
Все, что делает эта процедура – составление диалогового окна. Прорисока окна идет посредством обычной псевдографики (ASCII-кодировка). При это экран делится на три части. В верхней происходит уведомление пользователя о выборе пункта меню, а в двух нижних происходит задание параметров построения последовательностей (в случае вызова dowork(1)) или же просмотр последовательностей (в случае вызова dowork(2)). Если не происходит вызова dowork, то окно остается пустым, за исключением верхнего фрейма, где написано “Последовательности”.
При построении схемы и в коде программы не используется ни одной нестандартной подпрограммы. Схема тривиальна и общедоступна.
Основная программа нужна для организации диалога с пользователем. Но, собственно, сам диалог и все действия производятся именно в этой процедуре. Именно этой части программы стоит уделить наибольшее внимание.
Дальнейшее пояснение будет основываться на таблице 2. Ход повествования прямым образом зависит от значения параметра work. В каждой части вызывается справка по использованию и горячим клавишам, за исключением третьей части – вывода гистограммы.
Первая часть – задание/просмотр параметров генерации последовательностей.
Быстрый вызов – F1.
Здесь происходит, как ясно из заголовка пункта, задание новых или просмотр текущих параметров для генерации последовательностей. На блок-схеме этой подпрограммы это блоки 1-30.
Первым делом происходит разделение верхнего фрейма на два, в них прорисовывается пояснение – в какой из частей нижнего фрейма для какого закона распределения задаются параметры.
Для удобного задания параметров используется символьная переменная action. Именно через нее происходит перехват событий, от чего и зависит изменить параметры, оставить их неизменными, задать последовательности или же выйти из подпрограммы.
Стоит обратить внимание на то, как происходит ввод новых параметров. Положение курсора для ввода задается двумя массивами (они, как впрочем и остальные переменные, описаны в таблице 1): Xcor(3), Ycor(3). Измененные параметры записываются в массив Dat(3). Подобная схема очень удоьна для испльзования и для изменения как конфигурации.
Переход между состоянием просмотр/изменение происходит путем использования кодов ASCII для клавиш Esc, Tab, Enter и F4 – генерация последовательности.
Параметр справки – 5.
Вторая часть – просмотр сгенерированной последовательности.
Быстрый вызов – F2.
На блок-схеме представлена блоками 31-47.
Просмотр последовательности происходит через обычный цикл по одному параметру. Вся последовательность выводится по двум столбам, в каждом из которых по 50 элементов. Управление просмотром организовано через коды клавиш скролинга (прокрутки) по общепринятому стандарту – Up/Down. Элементы выводятся с приближением до шести символов после зяпятой, дабы не засорять рабочее пространство.
Параметр справки – 6.
Третья часть – просмотр гистограммы.
Быстрый вызов – F3.
В блоках 49-58 происходит вычисление математического ожидания и дисперсии как для каждого из промежутков, так и для всей последовательности целиком.
Блок 59 представляет собой (смотри код программы) прорисовку сетки для более удобной визуализации, вывод значений математического ожидания и дисперсии, легенды. Легенда необходима для определения того, какой тип столбцов что демонстрирует.
Вся визуальная часть процедуры dowork с параметром work=3 осуществлена при помощи модуля Graph.tpu. Тип адаптера и его режим определяются в основной программе. Необходимо, чтобы этот модуль находился в одной папке с файлом программы, иначе вывод бедт невозможен, что приведет к выходу из программы.
Выходом служит нажатие на любую клавишу.
2.3.5. Процедура drawmenu .
Быстрый вызов – F10.
Можно сказать, что весь интерфейс программы, ее простота использовиния во многом зависит от грамотно созданного меню. Некое подобие меню как раз возложено на создание этой процедуры.
Предусмотрен первоначальный вывод меню без выбора какого-нибудь из пунктов. Это необходимо для прорисовки интерфейса в начале работы программы и после просмотра гистограммы.
При выборе любого из пунктов меню происходит вызов процедуры drawhelp со значением 1-4 в зависимости от того какой пункт был выбран. Значение 1 предано крайнему левому пункту, 4 – правому. Подробнее о текстах справки можно посмотреть в таблице 3.
3. Рукводство пользователя.
Этот раздел предназначен для пояснения как общатся с программой.
Данная программа предназначена для построения гистограммы последовательности чисел полученной по двум законам распределения – нармальному и экспоненциальному. При выводе используется графический режим. Перед выводом последовательность разбивается на 10 интрвалов и демонстрацией результата является мат.ожидание и дисперсия для каждого из интервалов.
При запуске форимируется окно с разделением на три области: меню, диалоговую часть и строку помощи. При выборе любого из пункта меню происходит вызов определенной части программы, а также смена интерфейса.
Просмотр гистограммы производится при выборе одноименного пункта. Гистограмма имеет легенду. Выходом из просмотра является нажатие на любую клавишу.
Для выхода можно воспользоватся комбинацией клавиш Alt-x или же через меню.
* Данная работа не является научным трудом, не является выпускной квалификационной работой и представляет собой результат обработки, структурирования и форматирования собранной информации, предназначенной для использования в качестве источника материала при самостоятельной подготовки учебных работ.
Генератор случайных чисел
1. Способы получения случайных чисел 3
2. Характеристики ГСЧ 5
3. Применение ГСЧ 6
4. Генерирование равномерно распределенных случайных чисел 9
5. Генерирование чисел с произвольным распределением 12
6. Тестирование ГСЧ 17
7. Генератор случайных чисел в Borland C++ 21
8. Практические задания 23
8.1 Случайные числа в заданном диапазоне 23
8.2 Двумерные случайные величины 23
8.3 Генерация одномерной случайной величины 23
8.4 Оценить вероятность. 23
8.5. Медианы треугольника. 24
9. Лабораторные задания 25
9.1 ГСЧ фон Неймана 25
9.2 Случайная матрица 25
9.3 Площадь фигуры 26
9.4 Случайная величина с заданными свойствами 26
10. Дополнительные задания 27
10.1 Многомерные случайные величины 27
10.2 Быки и коровы 27
Библиографический список 28
1. Способы получения случайных чисел
В программировании достаточно часто находят применение последовательности чисел, выбранных случайным образом из некоторого множества. В качестве примеров задач, в которых используются случайные числа, можно привести следующие:
некоторые задачи численного анализа;
имитация пользовательского ввода.
Для получения случайных чисел можно использовать различные способы. В общем случае все методы генерирования случайных чисел можно разделить на аппаратные и программные. Устройства или алгоритмы получения случайных чисел называют генераторами случайных чисел (ГСЧ) или датчиками случайных чисел.
К программным ГСЧ относятся различные алгоритмы генерирования последовательности чисел, которая по своим характеристикам напоминает случайную. Для формирования очередного числа последовательности используются различные алгебраические преобразования. Одним из первых программных ГСЧ является метод средин квадратов, предложенный в 1946 г. Дж. фон Нейманом. Этот ГСЧ формирует следующий элемент последовательности на основе предыдущего путем возведения его в квадрат и выделения средних цифр полученного числа. Например, мы хотим получить 10-значное число и предыдущее число равнялось 5772156649. Возводим его в квадрат и получаем 33317792380594909201; значит, следующим числом будет 7923805949. Очевидным недостатком этого метода является зацикливание в случае, если очередное число будет равно нулю. Кроме того, существуют и другие сравнительно короткие циклы.
В дальнейшем мы будем рассматривать лишь программные генераторы псевдослучайных чисел.
2. Характеристики ГСЧ
Последовательности случайных чисел, формируемых тем или иным ГСЧ, должны удовлетворять ряду требований. Во-первых, числа должны выбираться из определенного множества (чаще всего это действительные числа в интервале от 0 до 1 либо целые от 0 до N). Во-вторых, последовательность должна подчиняться определенному распределению на заданном множестве (чаще всего распределение равномерное). Необязательным является требование воспроизводимости последовательности. Если ГСЧ позволяет воспроизвести заново однажды сформированную последовательность, отладка программ с использованием такого ГСЧ значительно упрощается. Кроме того, требование воспроизводимости часто выдвигается при использовании ГСЧ в криптографии.
3. Применение ГСЧ
Одна из задач, в которых применяются ГСЧ, – это грубая оценка объемов сложных областей в евклидовом пространстве более чем четырех или пяти измерений. Разумеется, сюда входит и приближенное вычисление интегралов. Обозначим область через R; обычно она определяется рядом неравенств. Предположим, что R – подмножество n?мерного единичного куба K. Вычисление объема множества R методом Монте-Карло сводится к тому, чтобы случайным образом выбрать в K большое число N точек, которые с одинаковой вероятностью могут оказаться в любой части K. Затем подсчитывают число M точек, попавших в R, т.е. удовлетворяющих неравенствам, определяющим R. Тогда M/N есть оценка объема R. Можно показать, что точность такой оценки будет довольно низкой. Тем не менее, выборка из 10 000 точек обеспечит точность около 1%, если только объем не слишком близок к 0 или 1. Такой точности часто бывает достаточно, и добиться лучшего другими методами может оказаться очень трудно.
В качестве примера можно рассмотреть вычисление площади фигуры, заданной некоторой системой неравенств. Пусть фигура будет определена следующим образом:
где ?(z) – некоторая гамма-функция, определяемая следующим соотношением:
Таким образом, для натуральных z гамма-функция равна факториалу z. Для вычисления знаменателя можно воспользоваться известным значением
Рис. 2. Области, из которых выбираются точки
Для получения равномерно распределенных случайных чисел из прямоугольника, стороны которого параллельны осям координат (см. рис.2, а), достаточно извлекать из ГСЧ последовательно пары чисел, приводить их к нужным интервалам и использовать как координаты точки:
где uj – равномерно распределенное случайное число из отрезка [0, m].
Окружность можно представить одномерным множеством точек с угловой координатой ?, принимающей значения на интервале (0, 2?). Таким образом, декартовы координаты очередной точки можно вычислить следующим образом:
Функция F(x) для любой случайной величины является неубывающей на всем интервале (–?; +?), стремится к 0 при x? –? и к 1 при x? +?. Для получения случайных чисел с заданным распределением F(x) необходимо найти функцию, обратную к F(x), т.е. такую функцию G, что для всех y=F(x) выполняется G(y)=x. Это можно пояснить следующим образом. Предположим, что мы многократно выбираем число y, равномерно распределенное на интервале [0; 1]; каждому y мы ставим в соответствие некоторое x=G(y). Выбору 50000 игреков соответствует выбор 50000 иксов. Таким образом, доля выбранных y, лежащих между двумя фиксированными значениями, скажем y1 и y2, в точности равна доле x, лежащих в интервале [x1; x2]. Но вероятность первого из названных событий равна | y2 – y1 |, если y распределено равномерно; следовательно, верна цепочка равенств:
доля чисел в интервале [x1; x2] = доля чисел в интервале [y1; y2] = y2 – y1 = F(x2) – F(x1) = ,
которая и показывает, что в случае равномерного распределения игреков x имеет распределение с плотностью f(?). Сложной проблемой в этом подходе является достаточно быстрое и точное формирование обратной функции распределения G(y).
Рассмотрим в качестве примера получение случайного числа с экспоненциальным распределением. Это распределение характеризуется одним параметром ?>0 и имеет следующие функции распределения и плотности распределения:
где P (j, l) – вероятность появления j единиц в l разрядах числа Xi;
p(1) = p(0) = 0,5 – вероятность появления единицы и нуля в любом разряде числа Xi;
Тогда при фиксированной точке выборки N теоретически ожидаемое число появления случайных чисел Xi с j единицами в проверяемых l разрядах будет равно
Читайте также: