Навигация
Генератор случайных чисел
26408
знаков
0
таблиц
6
изображений
Кафедра: Автоматика и Вычислительная Техника
Генератор случайных чисел
Содержание
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). Во-вторых, последовательность должна подчиняться определенному распределению на заданном множестве (чаще всего распределение равномерное). Необязательным является требование воспроизводимости последовательности. Если ГСЧ позволяет воспроизвести заново однажды сформированную последовательность, отладка программ с использованием такого ГСЧ значительно упрощается. Кроме того, требование воспроизводимости часто выдвигается при использовании ГСЧ в криптографии.
Поскольку псевдослучайные числа не являются действительно случайными, качество ГСЧ очень часто оценивается по «случайности» получаемых чисел. В эту оценку могут входить различные показатели, например, длина цикла (количество итераций, после которого ГСЧ зацикливается), взаимозависимости между соседними числами (могут выявляться с помощью различных методов теории вероятностей и математической статистики) и т.п. Подробнее оценка качества ГСЧ рассмотрена ниже.
Похожие работы
... на выходах генератора формируются два числа (на выходе счётчика 2 и выходе сумматора 10). Первое из них соответствует нечёткому значению интервала времени, необходимого для достижения поставленной цели, а второе - нечёткому значению результата настройки. В отличие от известных предложенный метод (алгоритм) позволил создать простой по своей структуре генератор случайных чисел, у которого наработка
... η с функцией распределения F(y) из случайной величины ζ, равномерно-распределенной в интервале [0,1], используются различные методы. К основным методам моделирования случайных чисел с заданным законом распределения относятся: - метод обратной функции - метод отбора или исключения - метод композиции. 2. Метод обратной функции Если ζ- равномерно-распределенная на интервале ...
... величины, распределенной по показательному закону, может служить время между появлениями двух последовательных событий простейшего потока.2.2. Начало алгоритмизации. Для получения двух последовательностей из 50 случайных чисел с показательным и нормальным законами распределения необходимо организовать цикл, который будет выполнятся 50 раз. Внутри цикла будем пользоваться функцией из Турбо Паскаля ...
... нельзя в полной мере назвать случайными, поскольку между ними имеется зависимость, а также наличие периодов в последовательности псевдослучайных чисел. К алгоритмическим методам получения ГСЧ относиться метод серединных квадратов, предложенный в 1946 г. Дж. фон Нейманом. Метод серединных квадратов Имеется некоторое четырехзначное число R0. Это число возводится в квадрат и заносится в R1. Далее ...
0 комментариев