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

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

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

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

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

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

кафедра

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

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

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

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

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

на тему:

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Калуга 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.Запуск и процесс игры.

Заключение

Литература

Приложение

Введение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Данный алгоритм был предложен Д. Х. Лемером в 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)

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

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

Существуют по меньшей мере два общих варианта алгоритма, различающихся только размером использующегося простого числа Мерсенна. Новейший и наиболее распространённый называется Mersenne Twister MT 19937.

MT 19937 имеет следующие ожидаемые свойства:

1.         Он был разработан с целью иметь огромный период, размером 2¹⁹⁹³⁷ − 1.

2.         Он имеет высокий порядок пространственного эквираспространения.

3.         Он значительно быстрее, чем все остальные генераторы, за исключением статистически-дефектных генераторов.

4.         Он статистически случаен во всех выходных битах.

Генерирование случайных чисел с помощью класса Random в С#.

Чтобы сгенерировать последовательность псевдослучайных чисел, используется класс Random. Начало такой последовательности определяется некоторым начальным числом, которое автоматически предоставляется классом Random или задается явным образом.

В классе Random определены следующие два конструктора:

public Random()

public Random(int seed)

С помощью первой версии конструктора создается объект класса Random, который для вычисления начального числа последовательности случайных чисел использует системное время. При использовании второй версии конструктора начальное число задается в параметре seed.

Класс Random (сокращено)

//Конструкторы

Random ()

Random(int а);

//Методы экземпляра

int Next () ;

int Next(int макс_значение) ;

int Next(int мин_значение, int макс_значение) ;

double NextDouble() ;

Конструкторы возвращают случайные объекты, которые образуют последовательность псевдослучайных чисел. Методы Next возвращают следующее число в последовательности, возможно, между заданными значениями. NextDouble возвращает число в диапазоне от 0.0 до 1.0.

Сравнив методы получения псевдослучайных чисел для реализации в программе, я выбрал, помимо метода, основанного на использовании системного класса Random, линейный конгруэнтный метод и алгоритм Блюма, Блюма и Шуба, исходя из преимуществ этих методов перед другими:

¾        более простое математическое представление, а следовательно и программная реализация;

¾        возможность получения любого числа, располагая только значением стартового.

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

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

1.         Возможность создания Windows приложений.

2.         Создание максимально возможного удобства в работе

3.         Поддержка других языков программирования и платформ

4.         Большое количество библиотек

5.         Простота изучения языка на основе имеющихся знаний.

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

Сформулировав требования, нужно перейти к анализу существующих языков программирования.

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

Машинные языки неудобны для восприятия человеком. Машинные языки являются машинно-зависимыми, т.е. конкретный машинный язык может быть использован только с определённым типом компьютера.

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

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

На практике программисту-одиночке или небольшой рабочей группе придется использовать какие-то мощные средства, вроде визуальных систем программирования (Visual Basic, C++Builder, С#, Delphi) или же универсальную среду разработки типа Borland C++ в сочетании с библиотекой классов, такой, как OWL или MFC. [3]

Бурное развитие вычислительной техники, потребность в эффективных средствах разработки программного обеспечения привели к появлению систем программирования, ориентированных на так называемую "быструю разработку", среди которых можно выделить Borland Delphi , Microsoft Visual Basic. С появлением Visual Basic программирование в Windows не становится более эффективным, но оно становится более простым (в большинстве случаев).

Если говорить о создании программ с интерфейсом Windows, то нельзя, конечно, не обойти вниманием визуальные средства программирования C++Builder. Несколько лет назад рядовому программисту оставалось только мечтать о создании собственных программ, работающих в среде Windows, т. к. единственным средством разработки был Borland C++ for Windows, явно ориентированный на профессионалов, обладающих серьезными знаниями и опытом. C++ Builder буквально навязывает программисту свой собственный стиль программирования, при котором, даже при особом желании, перейти с C++ Builder на что-то другое уже не предоставляется возможным. С++ не поддерживает других языков программирования.

Delphi — это среда быстрой разработки, в которой в качестве языка программирования используется язык Delphi. Язык Delphi — строго типизированный объектно-ориентированный язык, в основе которого лежит хорошо знакомый программистам Object Pascal. Borland Delphi 7 Studio позволяет создавать самые различные программы: от простейших однооконных приложений до программ управления распределенными базами. Delphi- не поддерживает других языков программирования, но способен поддерживать различные платформы.

Однако, при всем этом выбор падает на язык С#, входящий в Visual Studio .Net , так как он имеет ряд преимуществ, которые упрощают процесс создания приложений.

C# создавался Microsoft, как основной язык для .NET Framework. Microsoft спроектировала C# таким образом, что бы С, С++ и Java-программисты смогли легко перейти на него. C# имеет корни в языках С, С++ и Java, поэтому такой переход не должен вызвать затруднений.

Синтаксис у C# не такой сложный как у С++, поэтому его изучение намного легче. Большинство операций, которые вы можете делать на С++, можно сделать и на C#, за исключением операций доступа к низкоуровневым функциям (это все-таки можно сделать с помощью неуправляемого кода).

С# - первый язык, поддерживаемый версиями .NET Framework для других платформ.

C# имеет схожий с C стиль синтаксиса (для управляющих конструкций, блоков кода, описания сигнатуры методов и др.), много общего с Java (отсутствие множественного наследования и шаблонов, наличие сборщика мусора) и Delphi (ориентированность на создание компонент), в то же время имеет и свой колорит.

C# объектно-ориентированный язык, как и вся платформа .NET[7].

В C# представлена концепция пространств имен, аналогичная пакетам в Java. Это позволяет иерархически структурировать систему типов, делая код намного более понятным и позволяя избежать проблем с именованием. Реализация структур как типов, работа с которыми идет по значению, вместе с возможностью использовать не только вложенные массивы (как в Java), но и многомерные позволяет оптимизировать производительность приложений.

Ввиду очень удобного объектно-ориентированного дизайна, C# является хорошим выбором для быстрого конструирования различных компонентов.

Платформа .Net содержит множество важных служб:

1.      .Net предоставляет средства для исполнения инструкций, содержащихся в программе, написанной на C#. Эта часть .Net называется средой исполнения.

2.         .Net помогает реализовать так называемую среду, безопасную к несоответствию типов данных.

3.         .Net освобождает программиста от утомительного и нередко приводящего к ошибкам процесса управления компьютерной памятью, которая используется программой.

4.         .Net предоставляет безопасную среду исполнения.

5.         В состав .Net входят библиотека, содержащая массу готовых программных компонентов, которые можно использовать в собственных программах. Она экономит немало времени, так как программист может воспользоваться готовыми фрагментами кода. Фактически, он повторно использует код, созданный и тщательно проверенный профессиональными программистами Microsoft.