Кафедра: Автоматика и Вычислительная Техника

Генератор случайных чисел

Содержание

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. Очевидным недостатком этого метода является зацикливание в случае, если очередное число будет равно нулю. Кроме того, существуют и другие сравнительно короткие циклы.

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