Мегаобучалка Главная | О нас | Обратная связь  


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




Введение

 

Тема моей курсовой работы «игра “Тетрис”». В ходе выполнения работы были поставлены следующие цели:

¾ изучить основные подходы при создании Windows приложений;

¾ приобрести навыки работы с 2D графикой в Windows приложениях в С#;

¾ исследовать методы генерации псевдослучайных чисел.

Задачей курсовой работы является разработка игры «Сапер» с расположением мин на основе нескольких методов генерации случайных чисел.

Даная тема является актуальной, так как в ходе разработки игры есть возможность изучить процесс создания Windows приложений и работу с 2D графикой, а «генерация случайных чисел — слишком важное дело, чтобы оставлять её на волю случая» (Джон фон Нейман).


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

 

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

 

Для расстановки мин на игровом поле в игре «Сапер» необходимо случайным образом задать координаты клетки с миной. Для этого в программе используются различные методы генерирования таких координат.

Генератор псевдослучайных чисел (ГПСЧ) — алгоритм, генерирующий последовательность чисел, элементы которой почти независимы друг от друга и подчиняются заданному распределению.[1]



Современная информатика широко использует псевдослучайные числа в самых разных приложениях — от метода Монте-Карло до криптографии. Генераторы псевдослучайных чисел широко используются в имитационном моделировании.

Термин ГПСЧ часто используется для описания ГПСБ (PRBG) — генераторов псевдослучайных бит, а так же различных поточных шифров. Предназначение ГПСЧ — генерация последовательностей чисел, которые невозможно отличить от случайных. Никакой детерминированный алгоритм не может генерировать полностью случайные числа, а только лишь аппроксимировать некоторые свойства случайных чисел.

Самые простые аппаратные ГСЧ (АГСЧ) основаны на тех свойствах элементов электронных схем, с которыми так долго и упорно боролись инженеры - схемотехники. Это свойство - собственные шумы электронного прибора.

В отдельный подкласс АГСЧ стоит вынести разработки, в которых вместо дискретного электронного компонента применяется куда более сложный источник естественной случайности. Например, помещенная в специальный футляр при полном отсутствии света ПЗС-матрица камеры приводится управляющей программой в наихудший режим, при котором шумовые характеристики максимальны и картина чистого, природного хаоса пригодна к дальнейшей обработке.

Второму обширному классу АГСЧ лучше всего подойдет название "функциональный". Здесь в качестве "источника энтропии" используются фундаментальные функциональные свойства электронных приборов, например счетчиков Гейгера-Мюллера. Неприятной особенностью подобных устройств является необходимость применения радиоизотопных источников.

Третий класс АГСЧ– это "фундаментальный" класс. Наиболее яркий представитель "фундаментальных" АГСЧ - оптический квантовый генератор случайных чисел". Также существует устройство, в котором фундаментальные физические принципы, наносекундная синхронизация и самая современная электроника подчинены решению самой утилитарной задачи - получению случайных чисел, обновляющихся 100 тыс. раз в секунду.

Четвертый класс АГСЧ можно условно назвать "паразитным персонально-компьютерным". К их свойствам относятся прежде всего тепловые шумы и флуктуации в подсистеме аналогового ввода/вывода звукового адаптера.

В отдельный класс "курьезных" АГСЧ можно выделить специализированных роботов, методично бросающих... обычные игральные кости и оснащенных системой технического зрения для считывания выпавших очков.

Большинство простых арифметических генераторов хотя и обладают большой скоростью, но страдают от многих серьёзных недостатков:

¾ Слишком короткий период/периоды

¾ Последовательные значения не являются независимыми

¾ Некоторые биты «менее случайны», чем другие

¾ Неравномерное одномерное распределение

¾ Обратимость

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

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

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

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

       (1)

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

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

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

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

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

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

(2)

Поможем в ✍️ написании учебной работы
Поможем с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой



Читайте также:
Генезис конфликтологии как науки в древней Греции: Для уяснения предыстории конфликтологии существенное значение имеет обращение к античной...
Как вы ведете себя при стрессе?: Вы можете самостоятельно управлять стрессом! Каждый из нас имеет право и возможность уменьшить его воздействие на нас...
Организация как механизм и форма жизни коллектива: Организация не сможет достичь поставленных целей без соответствующей внутренней...



©2015-2020 megaobuchalka.ru Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. (125)

Почему 1285321 студент выбрали МегаОбучалку...

Система поиска информации

Мобильная версия сайта

Удобная навигация

Нет шокирующей рекламы



(0.019 сек.)
Поможем в написании
> Курсовые, контрольные, дипломные и другие работы со скидкой до 25%
3 569 лучших специалисов, готовы оказать помощь 24/7