Генерирование псевдослучайных чисел на примере создания игры Сапер

Государственное образовательное учреждение

высшего профессионального образования

«Московский государственный технический университет

им. Н. Э. Баумана»

Калужский филиал

кафедра

«Системы автоматизированного проектирования»

Пояснительная записка

к курсовой работе

по дисциплине:

«Программирование на языке высокого уровня»

на тему:

«Генерирование псевдослучайных чисел на примере создания игры “Сапер”»

Калуга 2007

Содержание

Введение3

1.Исследовательская часть4

1.1.Генерирование псевдослучайных чисел

1.2.Целесообразность выбора языка

2.Конструкторская часть

2.1.Структура проекта.

2.2. Программная реализация основных элементов C#.

2.2.1.Классы

2.2.2.Члены класса

3.Технологическая часть

3.1.Системные требования

3.2.Запуск и процесс игры.

Заключение

Литература

Приложение

Линейный конгруэнтный метод

Данный алгоритм был предложен Д. Х. Лемером в 1948 году. Применяется в простых случаях и не обладает криптографической стойкостью. Используется в качестве стандартного генератора многими компиляторами.

Этот алгоритм заключается в итеративном применении формулы (1):

(1)

где a > 0, c > 0, M > 0 — некоторые целочисленные константы. Получаемая последовательность зависит от выбора стартового числа X₀ и при разных его значениях получаются различные последовательности случайных чисел. В то же время, многие свойства последовательности X_j определяются выбором коэффициентов в формуле и не зависят от выбора стартового числа. Ясно, что последовательность чисел, генерируемая таким алгоритмом, периодична с периодом, не превышающим m. При этом длина периода равна m тогда и только тогда, когда:

1. НОД (c, m) = 1 (то есть c и m взаимно просты);

2. a - 1 кратно p для всех простых p — делителей m;

3. a - 1 кратно 4, если m кратно 4.

При реализации выгодно выбирать m = 2^e , где e — число бит в машинном слове, поскольку это позволяет избавиться от относительно медленной операции приведения по модулю.

Формула (2) для вычисления n -й члена последовательности, зная только 0-й

(2)

Метод Фибоначчи с запаздываниями.

Особенности распределения случайных чисел, генерируемых линейным конгруэнтным алгоритмом, делает невозможным их использование в статистических алгоритмах, требующих высокого разрешения.[2]

В связи с этим линейный конгруэнтный алгоритм постепенно потерял свою популярность и его место заняло семейство фибоначчиевых алгоритмов, которые могут быть рекомендованы для использования в алгоритмах, критичных к качеству случайных чисел.

Наибольшую популярность фибоначчиевы датчики получили в связи с тем, что скорость выполнения арифметических операций с вещественными числами сравнялась со скоростью целочисленной арифметики, а фибоначчиевы датчики естественно реализуются в вещественной арифметике.

Один из широко распространённых фибоначчиевых датчиков основан на следующей итеративной формуле (3):

X(k) = left{ begin{matrix} X(k-a)-X(k-b), & mbox{if } X(k-a)geq X(k-b); X(k-a)-X(k-b)+1, & mbox{if } X(k-a) < X(k-b);end{matrix}right. (3)

где X(k) — вещественные числа из диапазона [0, 1),

a, b — целые положительные числа, называемые лагами.

Для работы фибоначчиеву датчику требуется знать max(a, b) предыдущих сгенерированных случайных чисел. При программной реализации для хранения сгенерированных случайных чисел используется конечная циклическая очередь на базе массива. Для старта фибоначчиевому датчику требуется max(a, b) случайных чисел, которые могут быть сгенерированы простым конгруэнтным датчиком.

Рекомендуются следующие значения: a = 55, b = 24; a = 17, b = 5;

a = 97, b = 33.

Алгоритм Блюма, Блюма и Шуба (Blum Blum Shub, BBS)

Предложен в 1986 году Ленор и Мануэлем Блюм и Майклом Шубом.

BBS заключается в применении формулы (4):

x_{n +1} = (x_n )² mod M (4)

где M=p*q является произведением двух больших простых p и q.

На каждом шаге алгоритма выходные данные получаются из x_n путём взятия либо бита чётности, либо одного или больше наименее значимых бит x_n.

Два простых числа, p и q, должны быть оба сравнимы с 3 по модулю 4 и НОД(φ(p-1), φ(q-1)) должен быть мал.

Интересной особенностью этого алгоритма является то, что для получения x_n необязательно вычислять все n - 1 предыдущих чисел, если известно начальное состояние генератора x₀ и числа p и q. n-ное значение может быть вычислено "напрямую" используя формулу (5):

x_n = x₀ ^{(2 ^ n) mod ((p-1)(q-1))} mod M (5)

Вихрь Мерсенна (Mersennetwister)

Разработан в 1997 японскими учёными Макото Мацумото и Такудзи Нисимура. Он обеспечивает быструю генерацию высококачественных псевдослучайных чисел, так как изначально был разработан с учётом ошибок, найденных в других алгоритмах.

Существуют по меньшей мере два общих варианта алгоритма, различающихся только размером использующегося пр

Внимание, отключите Adblock

Вы посетили наш сайт со включенным блокировщиком рекламы!
Ссылка для скачивания станет доступной сразу после отключения Adblock!

Скачать