Генерирование псевдослучайных чисел. Линейный конгруэнтный метод, алгоритм Фибоначчи с запаздываниями и метод Блюма. Генерирование псевдослучайных чисел классом Random в С . Метод середины квадрата. Постановка задачи, разработка и кодирование алгоритма.
Аннотация к работе
В автоматизированных цехах и заводах широко применяется оборудование с использованием микропроцессоров и микро ЭВМ. Их использование в составе промышленного оборудования обеспечивает снижение его стоимости по сравнению с системами на элементах малой и средней степени интеграции, что и является актуальностью курсовой работы. В своей курсовой работе я попыталась показать, как можно реализовать на элементах простой логики довольно сложную функцию - генерацию псевдослучайного числа. Цель курсовой работы - охарактеризовать псевдослучайные числа.В языках программирования обычно предусмотрены функции, позволяющие генерировать случайные числа в определенном по умолчанию диапазоне. Генератор псевдослучайных чисел (ГПСЧ) - алгоритм, генерирующий последовательность чисел, элементы которой почти независимы друг от друга и подчиняются заданному распределению [1]. Предназначение ГПСЧ - генерация последовательностей чисел, которые невозможно отличить от случайных. Интересной особенностью этого алгоритма является то, что для получения xn необязательно вычислять все n - 1 предыдущих чисел, если известно начальное состояние генератора x0 и числа p и q. n-ное значение может быть вычислено "напрямую" используя формулу (5): xn = x0 (2 ^ n) mod ((p-1)(q-1)) mod M (5) Сравнив методы получения псевдослучайных чисел для реализации в программе, я выбрала, помимо метода, основанного на использовании системного класса Random, линейный конгруэнтный метод и алгоритм Блюма, Блюма и Шуба, исходя из преимуществ этих методов перед другими: 1) более простое математическое представление, а следовательно и программная реализация;Тогда функцию ?(?n) определим следующим образом: ?n 1=?(?n)=Franc{10-2k *Int(103k*?2n)} т.е. возведем ?n в квадрат и получим. ?n2=0, b1, b2,… b4k. В результате работы программы должны получить математическое ожидание и дисперсию, определенные для последовательности из 50 000 элементов. Есть вероятность, что числа, генерируемые при помощи алгоритма обнулятся, при условии х0 <104. чтобы избежать этого нужно длину отрезка апериодичности L увеличить, что подробно будет рассмотрено ниже. Есть вероятность, что числа, генерируемые при помощи алгоритма обнулятся, при условии х0 <104. чтобы избежать этого нужно длину отрезка апериодичности L увеличить. Теперь функция ?n примет следующий вид: ?(?n)= if , Для реализации алгоритма нужно определить наибольшее возможное значение k (чем больше это число, тем больше число значащих разрядов, а, следовательно, и длина отрезка апериодичности).псевдослучайный число алгоритм Число Х получаем удалением по k разрядов с каждого конца Y При k=2 и х0=0.2134 в соответствии с первым оператором Шаг2 получим Y= =0.04 5539 56. после применения второго оператора х1=0.5539. если х0<104, то все числа, генерируемые при помощи данного алгоритма, будут тождественно равны нулю. Для реализации алгоритма потребуется написать процедуру, реализующую метод середины квадрата, которую назовем Rand, в которой при первом обращении задается целое число IX из [0.999999] и между вызовами оно не должно меняться. На выходе имеем числа: Rand числа типа Single из (0,1), IX числа типа LONGINT из (0,999999), K числа типа LONGINT из (0, К 1).Begin z:=Ix; x:=z {*1.e-6}; {обнулим 7 и далее разряды числа Х.} z1:=x 1.e-6; y:=z1*z1*1.e-12; {вычислим квадрат Х.} z1:=y*1.e 3; y:=z1-Trunc(z1); {выберем 4…9 разряды числа Y.} if y<1.e-6 then {определили новое целое случайное число IX из [0.999999] и случайную величину из [0.1]} k:=Round((k 1)*y); {вычисляем число К из [0, К 1]} В результате работы алгоритма, после создания текстового файла по указанному адресу, получаем файл Rand, содержащий результат - математическое ожидание и дисперсию. Для этого воспользуемся способом, заключающимся в подсчете арифметических операций, необходимых для выполнения алгоритма (в этом случае определяется рабочая функция). Определим (n) как рабочую функцию, дающую верхнюю границу для максимального числа основных операций, которые должен выполнить алгоритм G(n) для решения любой задачи размерности n.Для этого воспользуемся управляющим графом (ориентированный граф, вершины которого - операторы, а дуги соединяют операторы, между которыми возможна передача управления). На приведенной выше схеме Мартынюка путь является простым, так как он не содержит ни одной вершины или дуги более одного раза. Схема правильная, так как выполняется условие, что каждая вершина принадлежит хотя бы одному пути по графу. Все элементы 1 столбца равны 1, значит в 1 вершину управление не передается ни из какой другой. Все элементы 1 строки равны 1, значит из 1 вершины управление не передается ни в какую другую, отсюда следует, что схема программы является правильной.В ходе выполнения курсовой работы были рассмотрены и проанализированы основные методы генерирования псевдослучайных чисел: линейный конгруэнтный метод, метод Фибоначчи с запаздываниями, алгоритм Блюма, Блюма и Шуба, Вихрь Мерсенна.
План
Содержание
Введение
Глава 1. Теоретическая часть
1.1 Генерирование псевдослучайных чисел
1.2 Генерирование псевдослучайных чисел с помощью класса Random в С