Лабораторная работа №4
Программирование алгоритмов генерации псевдослучайных чисел
Задание
Написать программу, осуществляющую генерацию определенного количества псевдослучайных чисел из заданного пользователем интервала заданным методом и вывод их на экран. Количество чисел и интервал вводит пользователь. Программа должна также записывать сгенерированную псевдослучайную последовательность в файл. Формат файла – двоичный.
Метод середины квадрата
Первым алгоритмический метод получения равномерно распределенных псевдослучайных чисел предложил Джон фон Нейман (один из основоположников кибернетики). Метод получил название "метод середины квадрата" .
Суть метода: предыдущее случайное число возводится в квадрат, а затем из результата извлекаются средние цифры.
Например:
и т.д.
Как видно метод середины квадрата довольно хорошо должен
"перемешивать" предыдущее число. Однако он имеет недостатки:
Если какой-нибудь член последовательности окажется равным нулю, то все последующие члены также будут нулями.
Последовательности имеют тенденцию "зацикливаться", т. е. в конце концов, образуют цикл, который повторяется бесконечное число раз.
Свойство "зацикливаться" присуще всем последовательностям,
построенных по рекуррентной формуле xi+1=f(xi).
Повторяющийся цикл называется периодом. Длина периода у различных последовательностей разная. Чем больше, тем лучше.
Мультипликативный метод
Мультипликативный метод задает последовательность неотрицательных целых чисел {Xi} не превосходящих М по формуле:
|
|
, |
|
|
|
|
|
где |
– неотрицательные |
целые числа. |
Выражение |
(3.8) |
|||
означает: |
равно |
остатку |
от |
деления |
на M. |
В |
силу |
детерминированности |
метода |
|
получают |
воспроизводимые |
последовательности. В качестве выбирают произвольное нечетное число; М – число, определяющее наибольшее значение получаемых СЧ, при
машинной реализации: , где р – основание системы счисления, g –
число бит в машинном слове.
Для р =2 алгоритм сводится к выполнению следующих операций.
1.Вычислить , где t – любое целое положительное число;
2.Найти произведение взять g младших разрядов в качестве первого члена последовательности , а остальные отбросить;
3.Определить дробь из интервала (0,1);
4.Присвоить и вернуться к п.2.
Варианты
Алгоритм поиска
1 – метод середин
квадратов
2 – мультипликативный
метод
Содержание отчета
1.Титульный лист
2.Задание + вариант
3.Блок-схема или пошаговое описание алгоритма генерации
4.Текст программы
5.Пример выполнения: скриншот выполнения программы и выходной файл