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

Государственное образовательное учреждение высшего профессионального образования

«Московский государственный технический университет им. Н. Э. Баумана»

Калужский филиал кафедра

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

Пояснительная записка к курсовой работе по дисциплине:

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

на тему:

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

Калуга 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 19 937.

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

1. Он был разработан с целью иметь огромный период, размером 2^19 937? 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.

6. В .Net упрощена подготовка программы к исполнению.

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

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

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

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

Данный проект состоит из файлов

Ниже представлено описание основных файлов:

ѕ Form1. cs — файл, в котором содержится код, отвечающий за работу главной формы программы;

ѕ Form1. resx — файл, в котором содержится информация о графическом представлении главной формы «Сапер»;

ѕ Form2. cs — файл, в котором содержится код, отвечающий за работу формы настроек игрового поля;

ѕ Form2. resx — файл, в котором содержится информация о графическом представлении формы настроек игрового поля;

ѕ AboutBox1. cs — файл, в котором содержится код, отвечающий за работу формы «О программе»;

ѕ AboutBox1. resx — файл, в котором содержится информация о графическом представлении формы «О программе»;

ѕ Справка. htm — HTML-страница, в которой содержится справка по игре;

ѕ Мина. jpg — изображение мины на форме «О программе»

ѕ Сапер. exe — закомпилированный файл программы, находящийся в папке debug, которая находится в папке bin

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

Для его запуска необходимо кликнуть кнопку Пуск, выбрать в пункте Все программы Microsoft Visual Studio .NET 2005Microsoft Visual Studio .NET 2005. Далее в запустившемся приложении кликнуть кнопку Open Project и используя проводник, выбрать файл Сапер.sln. Программа откроет приложение. Для изменения внешнего вида программы необходимо воспользоваться ярлыком Design. Можно добавить новые элементы формы, перетащив их из окна Toolbox. В моей работе это HelpProvider и MenuStrip при конструировании главной формы, Label, TextBox и Button при создании формы настроек игрового поля. Свойства компонентов можно изменить, зайдя в меню View — Properties Windows или в коде программы:

//задается текст компонентов формы О программе

this.Text = String. Format («О программе»);

this.labelProductName.Text = «Cапер» ;

this.labelVersion.Text = String. Format («Версия {0}», AssemblyVersion);

this.labelCopyright.Text = «Автор Темерев Кирилл» ;

this.labelCompanyName.Text = «КФ МГТУ им. Н. Э. Баумана, группа САПР-31» ;

this.textBoxDescription.Text ="Программа создана в Microsoft Visual Studio

Щелкнув значок Молния в меню Properties можно найти все события и дважды щелкнув на одно из них, написать обработчик.

2.2.1.Классы

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

public partial class Form1: Form //главная форма программы

{

…

public Form1() //конструктор главной формы

{

InitializeComponent ();

//присваиваем начальные значения полям

MR = 10;

MC = 10;

NM = 10;

W = 40;

H = 40;

this.newGame (1);//вызов метода newGame (int r)

}

…

}

public partial class Form2: Form //форма настроек игрового поля

{

…

public Form2()//конструктор формы Настройки

{

InitializeComponent ();

}

…

}

partial class AboutBox1: Form //форма «О программе»

{

…

public AboutBox1()//конструктор формы О программе

{

InitializeComponent ();

//задается текст компонентов формы О программе

this.Text = String. Format («О программе»);

this.labelProductName.Text = «Cапер» ;

this.labelVersion.Text = String. Format («Версия {0}», AssemblyVersion);

this.labelCopyright.Text = «Автор Темерев Кирилл» ;

this.labelCompanyName.Text = «КФ МГТУ им. Н. Э. Баумана, группа САПР-31» ;

this.textBoxDescription.Text ="Программа создана в Microsoft Visual Studio 2005 для среды .NET Framework" ;

}

…

}

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

Поля

Полем называется член-переменная, содержащий некоторое значение. В ООП поля иногда называют данными объекта.

Для классов

public partial class Form1: Form

public partial class Form2: Form

полями являются следующие переменные:

private int

MR,//кол-во клеток по вертикали

MC,//кол-во клеток по горизонтали

NM,//кол-во мин

W,//ширина клетки поля

H;//высота клетки поля

private int

nMin,//кол-во найденных мин

nFlag;//кол-во поставленных флагов

private int status;/*отражает различные этапы работы программы:

0-начало игры,

1-игра,

2-конец игры*/

private int[,] Pole;/*элемент массива задает клетку поля и принимает значения

0−8 -кол-во мин в соседних клетках,

9 -в клетке мина,

100−109 -клетка открыта,

200−209 -в клетку поставлен флаг*/

Следует отметить, что переменная Pole хранит в себе ссылку на двумерный массив. Массивы в C# разделяются на два типа: одномерные и многомерные.

Элементы многомерных массивов идентифицируются набором индексов — «координат» в многомерном пространстве. Каждое измерение имеет свою размерность, не зависящую от других.

Инициализация

Pole = new int[MR + 2, MC + 2];

происходит в методе

private void newGame (int r)

{

}

который будет рассмотрен далее.

Доступ к элементам производится с помощью оператора [ ], в котором индексы указываются через запятую. Присвоение значений элементам присваивается в методе:

private void newGame (int r)

{

…

/*неотражаемым элементам массива минного поля присваиваем

значение -3 для завершения процесса открытия клеток*/

for (row = 0; row <= MR + 1; row++)

{

Pole[row, 0] = -3;

Pole[row, MC + 1] = -3;

}

for (col = 0; col <= MC + 1; col++)

{

Pole[0, col] = -3;

Pole[MR + 1, col] = -3;

}

//обнуление элементов массива минного поля

for (row = 1; row <= MR; row++)

{

for (col = 1; col <= MC; col++)

{

Pole[row, col] = 0;

}

}

…

}

а также в других методах.

Методы

Методом называется реальный код, воздействующий на данные объекта (или поля). При объявлении методов используется конструкция вида:

<�модиф_дост><�тип_возвр_знач><�идент_метода>(<�формальн_парам>_opt)

{

<�тело_метода>

}

Метод в процессе своей работы может не только изменять поля объекта, но и вычислять некоторые дополнительные значения. Если возвращать значения не нужно, то в качестве типа возвращаемого значения указывается void.

Методы, используемые в разработанном приложении и обеспечивающие процесс игры:

private void newGame (int r)//метод, запускающий новую игру

{

…

//выбор метода расстановки мин

int random = r;

if (random == 1)

{

this.Rand ();//вызов метода Rand ()

}

if (random == 2)

{

this.Lin ();//вызов метода Lin ()

}

if (random == 3)

{

this.BBS ();//вызов метода BBS ()

}

…

}

//способы расстановки мин

private void Rand ()//метод, основанный на использовании класса Random

{

int n = 0;//кол-во поставленных мин

int row, col;

Random rnd = new Random ();//генеретор случайных чисел

//расстановка мин

do

{

row = rnd. Next (MR) + 1;

col = rnd. Next (MC) + 1;

if (Pole[row, col] ≠ 9)

{

Pole[row, col] = 9;

n++;

}

}

while (n ≠ NM);

}

private void Lin ()//метод, основанный на использовании линейного конгруэнтного метода

{

int n = 0;

int row, col;

double a = Convert. ToInt64(Math.Exp ((double)5 * Math. Log (7))),

m = Convert. ToInt64(Math.Exp ((double)31 * Math. Log (2))) — 1;

int x = 27 011 989, c = 19;

//расстановка мин

do

{

//для нахождения пвевдослучайного числа Х используется формула x (k+1)=(a * x (k) + c) mod m

x = (int)((a * x + c) % m);

//находится пвевдослучайный индекс клетки на [0,MR]

row =Convert.ToInt32(Math.Ceiling ((double) MR * x / (m-1)));

x = (int)((a * x + c) % m);

//находится пвевдослучайный индекс клетки на [0,MС]

col = Convert. ToInt32(Math.Ceiling ((double)MC * x / (m-1)));

if (Pole[row, col] ≠ 9)

{

Pole[row, col] = 9;

n++;

}

}

while (n ≠ NM);

}

private void BBS ()//метод, основанный на использовании алгоритма Блюма, Блюма и Шуба

{

int n = 0;

int row, col;

int x = 2701;

int p=2047,q=8191;

int M = p * q;

//расстановка мин

do

{

//для нахождения пвевдослучайного числа Х используется формула x (k+1)=(x (k)^2) mod m

x = Math. Abs ((int)((x * x) % M));

//находится пвевдослучайный индекс клетки на [0,MR]

row = Convert. ToInt32(Math.Ceiling ((double)MR * x / (M-1)));

x = Math. Abs ((int)((x * x) % M));

//находится пвевдослучайный индекс клетки на [0,MС]

col = Convert. ToInt32(Math.Ceiling ((double)MC * x / (M-1)));

if (Pole[row, col] ≠ 9)

{

Pole[row, col] = 9;

n++;

}

}

while (n ≠ NM);

}

private void showPole (Graphics g, int status)//метод, отрисовывающий поле

{

for (int row = 1; row <= MR; row++)

{

for (int col = 1; col <= MC; col++)

{

this.kletka (g, row, col, status);//вызов метода kletka ()

}

}

}

private void kletka (Graphics g, int row, int col, int status)

//метод, выводящий содержимое клетки

{

…

// в клетке флаг

if (Pole[row, col] >= 200)

this.flag (g, x, y);

//отрисовываем границы клетки

g.DrawRectangle (Pens.Black, x — 1, y — 1, x + W, y + H);

// если игра завершена (status=2), показываем мины

if ((status == 2) && ((Pole[row, col] % 10) == 9))

this.mina (g, x, y);

…

}

private void open (int row, int col)//метод, открывающий текущую и все соседние клетки, в которых нет мин

{

…

//рекурсивный процесс открытия всей пустых соседих клеток

if (Pole[row, col] == 0)

{

Pole[row, col] = 100;

//отобразить содержимое клетки

this.Invalidate (new Rectangle (x, y, W, H));

//открыть примыкающие клетки слева, справа, сверху, снизу

this.open (row, col — 1);

this.open (row — 1, col);

this.open (row, col + 1);

this.open (row + 1, col);

//примыкающие диагонально

this.open (row — 1, col — 1);

this.open (row — 1, col + 1);

this.open (row + 1, col — 1);

this.open (row + 1, col + 1);

}

…

}

а также два метода, основанных на работе с графикой:

private void mina (Graphics g, int x, int y)//метод, рисующий мину

{

//корпус

g.FillRectangle (Brushes.Green, x + 16, y + 26, 8, 4);

g.FillRectangle (Brushes.Green, x + 8, y + 30, 24, 4);

g.DrawPie (Pens.Black, x + 6, y + 28, 28, 16, 0, -180);

g.FillPie (Brushes.Green, x + 6, y + 28, 28, 16, 0, -180);

//полоса на корпусе

g.DrawLine (Pens.Black, x + 12, y + 32, x + 28, y + 32);

//вертикальный «ус»

g.DrawLine (Pens.Black, x + 20, y + 22, x + 20, y + 26);

//боковые «усы»

g.DrawLine (Pens.Black, x + 8, y + 30, x + 6, y + 28);

g.DrawLine (Pens.Black, x + 32, y + 30, x + 34, y + 28);

}

private void flag (Graphics g, int x, int y)//метод, рисующий флаг

{

Point[] p = new Point[3];

Point[] m = new Point[5];

//флажок

p[0]. X = x + 4;

p[0]. Y = y + 4;

p[1]. X = x + 30;

p[1]. Y = y + 12;

p[2]. X = x + 4;

p[2]. Y = y + 20;

g.FillPolygon (Brushes.Red, p);

//древко

g.DrawLine (Pens.Black, x + 4, y + 4, x + 4, y + 35);

//буква М на флажке

m[0]. X = x + 8;

m[0]. Y = y + 14;

m[1]. X = x + 8;

m[1]. Y = y + 8;

m[2]. X = x + 10;

m[2]. Y = y + 10;

m[3]. X = x + 12;

m[3]. Y = y + 8;

m[4]. X = x + 12;

m[4]. Y = y + 14;

g.DrawLines (Pens.White, m);

}

События

Событие вызывает исполнение некоторого фрагмента кода. События — неотъемлемая часть программирования для Microsoft Windows. Например, события возникают при движении мыши, щелчке или изменении размеров окна. Важнейшую роль играет обработчики событий— методы, исполняемые при генерации событий:

private void Сапер_MouseDown (object sender, MouseEventArgs e)//нажатие кнопки мыши на игровом поле

{

}

private void новаяИграToolStripMenuItem1_Click (object sender, EventArgs e) //щелчок на пункте меню Новая игра

{

this.newGame (1);

this.Invalidate ();

}

//обработчики щелчков на пунктах меню, в которых указывается размер поля и кол-во мин

private void минToolStripMenuItem_Click (object sender, EventArgs e)

{

}

private void минToolStripMenuItem1_Click (object sender, EventArgs e)

{

}

private void минToolStripMenuItem2_Click (object sender, EventArgs e)

{

}

private void минToolStripMenuItem3_Click (object sender, EventArgs e)

{

}

private void минToolStripMenuItem4_Click (object sender, EventArgs e)

{

}

private void минToolStripMenuItem5_Click (object sender, EventArgs e)

{

}

private void особыеToolStripMenuItem_Click (object sender, EventArgs e) //щелчок на пункте меню Особые

{

Настройки settings = new Настройки ();//создание экземпляра формы Настройки

settings.ShowDialog ();//появление формы Настройки

//присваиваем значения полям на основе введенных пользователем на форме Настройки

MR = settings. MR;

MC = settings. MC;

NM = settings. NM;

W = 30;

H = 30;

this.newGame (1);

this.Invalidate ();

}

//обработчики щелчков на пунктах меню, в которых указывается способ расстановки мин

private void randomToolStripMenuItem_Click (object sender, EventArgs e)

{

}

private void инейныйКонгруэнтныйМеоToolStripMenuItem_Click (object sender, EventArgs e)

{

}

private void алгоритмToolStripMenuItem_Click (object sender, EventArgs e)

{

}

private void выходToolStripMenuItem_Click (object sender, EventArgs e)

//щелчок на пункте меню Выход

{

this.Close ();

}

private void справкаToolStripMenuItem_Click (object sender, EventArgs e) //щелчок на пункте меню Справка

{

Help.ShowHelp (this, this. helpProvider1.HelpNamespace);//вызов файла справки

}

private void оПрограммеToolStripMenuItem_Click (object sender, EventArgs e) //щелчок на пункте меню О программе

{

AboutBox1 saper = new AboutBox1();//создание экземпляра формы О программе

saper.ShowDialog ();//появление формы О программе

}

Отдельного внимания заслуживает событие Paint, которое сообщает программе о необходимости отобразить информацию в окне. Paint информирует программу о том, что вся клиентская область или ее часть недействительна (invalid) и требует перерисовки. Когда форма только что создана, вся клиентская область недействительна, так как программа еще ничего в ней не показывала. В программе происходит первое событие Paint, сообщающее о необходимости показать что-нибудь в клиентской области. Когда окна перемещаются по экрану, так что они перекрывают друг друга, Windows не запоминает вид клиентской области, закрытой другим окном. Потом, когда клиентская область снова открывается, программа должна восстановить ее вид. Поэтому в ней и происходит событие Paint. Когда окно программы после свертывания возвращается в нормальное состояние, в ней также происходит событие Paint.

private void Form1_Paint (object sender, PaintEventArgs e)//обработчик события

Paint

{

this.showPole (e.Graphics, status); //вызов метода showPole

}

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

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

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

1. Процессор Pentium 3.

2. Частота процессора 800 Мгц.

3. 256 Мб ОЗУ.

4. Видеоадаптер Radeon 9600 и аналогичные.

5. Visual Studio 2003 или 2005.

6. Операционная система Windows 2000 и более поздние версии

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

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

1.Вставьте диск «Курсовая работа Темерева К., гр. САПР-31. Игра „Сапер“» в дисковод.

2.

— нажмите кнопку Пуск

— двойным щелчком левой кнопки мыши откройте Мой компьютер

— двойным щелчком откройте

3.На экране появится окно (см. рис. 3.1)

4.Если на компьютере не установлена платформа .NET нужно открыть папку Microsoft .NET Framework 3.0 и двойным щелчком запустить установочный файл dotnetfx3.exe

5.Запуск игры осуществляется двойным щелчком на файле

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

Чтобы начать игру в меню Игра нужно выбрать команду Новая игра (рис. 3.2).

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

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

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

Чтобы настроить игровое поле в меню Игра следует выбрать команду Игровое поле (рис. 3.2), а далее:

ѕ выбрать размер поля 10 * 10 или 20 *20, затем количество мин 10, 15, 20, 40, 60

или выбрать команду Особые и задать размер поля, указав количество клеток по горизонтали и вертикали, а также ввести число мин. (рис. 3.3)

Чтобы изменить способ расстановки мин на поле, в меню Игра нужно выбрать команду Способ расстановки мин, а далее:

ѕ Random

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

ѕ Алгоритм Блюма, Блюма и Шуба.

Чтобы найти инструкцию по игре, нужно выбрать в меню Справка, а для ознакомления с информацией о приложении выбрать

О программе

Заключение

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

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

Выдвинуты требования к функциональности приложения, исходя из специфики игры «Сапер» и сформулированы необходимые характеристики того языка программирования, с помощью которого предполагалось выполнить поставленную задачи, проанализированы преимущества и недостатки разных языков и сделан выбор в пользу языка С#.

В конструкторской части были использованы новые визуальные компоненты. На основе имеющихся и полученных знаний об основных структурах языка С# реализованы алгоритм игры и графический интерфейс.

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

Задание на курсовую работу было выполнено полностью.

1. Кнут Д. Искусство программирования, т. 2. Получисленные методыМ.: «Вильямс», 2007. — С. 832.

2. Зубинский А. В поисках случайности. — Компьютерное Обозрение,

29 (2003)

3. Шилдг Г. Полный справочник по С#/Пер. с англ. — М.: Издательский дом «Вильямc», 2004. — 752 с.

4. Ватсон К. С#. — М.: Издательство «Лори», 2005

5. Рихтер Дж. Программирование на платформе Microsoft .NET Framework. — М.: Издательско-торговый дом «Русская Редакция», 2003.-464 с.

6. Фролов А. В. Фролов Г. В. Язык С#. Самоучитель. — М: Издательство «ДИАЛОГ-МИФИ», 2003. — 560 с.

Приложение 1

Код программы

public partial class Form1: Form //главная форма программы

{

private int

MR,//кол-во клеток по вертикали

MC,//кол-во клеток по горизонтали

NM,//кол-во мин

W,//ширина клетки поля

H;//высота клетки поля

private int

nMin,//кол-во найденных мин

nFlag;//кол-во поставленных флагов

private int status;/*отражает различные этапы работы программы:

0-начало игры,

1-игра,

2-конец игры*/

private int[,] Pole;/*элемент массива задает клетку поля и принимает значения

0−8 -кол-во мин в соседних клетках,

9 -в клетке мина,

100−109 -клетка открыта,

200−209 -в клетку поставлен флаг*/

private void newGame (int r)/*метод, запускающий новую игру;

значение формального параметра r указывает на способ расстановки мин

1-используя системный класс Random,

2-используя линейный конгруэнтный метод,

3-используя алгоритм Блюма, Блюма и Шуба*/

{

this.ClientSize = new Size (W * MC + 1, H * MR + 1+25);/*устанавливаем размер формы в соответствии

с размером игрового поля*/

int row, col;//индексы клетки

int k;//кол-во мин в соседних клетках

Pole = new int[MR + 2, MC + 2]; //инициализация массива минного поля

/*неотражаемым элементам массива минного поля присваиваем значение -3

для завершения процесса открытия клеток*/

for (row = 0; row <= MR + 1; row++)

{

Pole[row, 0] = -3;

Pole[row, MC + 1] = -3;

}

for (col = 0; col <= MC + 1; col++)

{

Pole[0, col] = -3;

Pole[MR + 1, col] = -3;

}

//обнуление элементов массива минного поля

for (row = 1; row <= MR; row++)

{

for (col = 1; col <= MC; col++)

{

Pole[row, col] = 0;

}

}

//метод расстановки мин

int random = r;

if (random == 1)

{

this.Rand ();//вызов метода Rand ()

}

if (random == 2)

{

this.Lin ();//вызов метода Lin ()

}

if (random == 3)

{

this.BBS ();//вызов метода BBS ()

}

//для каждой клетки вычисляем кол-во мин в соседних клетках

for (row = 1; row <= MR; row++)

{

for (col = 1; col <= MC; col++)

{

if (Pole[row, col] ≠ 9)

{

k = 0;

if (Pole[row — 1, col — 1] == 9)

k++;

if (Pole[row — 1, col] == 9)

k++;

if (Pole[row — 1, col + 1] == 9)

k++;

if (Pole[row, col — 1] == 9)

k++;

if (Pole[row, col + 1] == 9)

k++;

if (Pole[row + 1, col — 1] == 9)

k++;

if (Pole[row + 1, col] == 9)

k++;

if (Pole[row + 1, col + 1] == 9)

k++;

Pole[row, col] = k;

}

status = 0;//начало игры

nMin = 0;//нет обнаруженных мин

nFlag = 0;//нет поставленных флагов

}

}

}

//способы расстановки мин

private void Rand ()//метод, основанный на использовании системного класса Random,

{

int n = 0;//кол-во поставленных мин

int row, col;

Random rnd = new Random ();//генеретор случайных чисел

//расстановка мин

do

{

row = rnd. Next (MR) + 1;

col = rnd. Next (MC) + 1;

if (Pole[row, col] ≠ 9)

{

Pole[row, col] = 9;

n++;

}

}

while (n ≠ NM);

}

private void Lin ()//метод, основанный на использовании линейного конгруэнтного метода

{

int n = 0;

int row, col;

double a = Convert. ToInt64(Math.Exp ((double)5 * Math. Log (7))), m = Convert. ToInt64(Math.Exp ((double)31 * Math. Log (2))) — 1;

int x = 27 011 989, c = 19;

//расстановка мин

do

{

//для нахождения пвевдослучайного числа Х используется формула x (k+1)=(a * x (k) + c) mod m

x = (int)((a * x + c) % m);

//находится пвевдослучайный индекс клетки на [0,MR]

row =Convert.ToInt32(Math.Ceiling ((double) MR * x / (m-1)));

x = (int)((a * x + c) % m);

//находится пвевдослучайный индекс клетки на [0,MС]

col = Convert. ToInt32(Math.Ceiling ((double)MC * x / (m-1)));

if (Pole[row, col] ≠ 9)

{

Pole[row, col] = 9;

n++;

}

}

while (n ≠ NM);

}

private void BBS ()//метод, основанный на использовании алгоритма Блюма, Блюма и Шуба

{

int n = 0;

int row, col;

int x = 2701;

int p=2047,q=8191;

int M = p * q;

//расстановка мин

do

{

//для нахождения пвевдослучайного числа Х используется формула x (k+1)=(x (k)^2) mod m

x = Math. Abs ((int)((x * x) % M));

//находится пвевдослучайный индекс клетки на [0,MR]

row = Convert. ToInt32(Math.Ceiling ((double)MR * x / (M — 1)));

x = Math. Abs ((int)((x * x) % M));

//находится пвевдослучайный индекс клетки на [0,MС]

col = Convert. ToInt32(Math.Ceiling ((double)MC * x / (M — 1)));

if (Pole[row, col] ≠ 9)

{

Pole[row, col] = 9;

n++;

}

}

while (n ≠ NM);

}

private void showPole (Graphics g, int status)//метод, отрисовывающий поле

{

for (int row = 1; row <= MR; row++)

{

for (int col = 1; col <= MC; col++)

{

this.kletka (g, row, col, status);//вызов метода kletka (Graphics g, int row, int col, int status)

}

}

}

private void kletka (Graphics g, int row, int col, int status)//метод, выводящий содержимое клетки

{

//координаты области вывода

int x = (col — 1) * W + 1, y = (row — 1) * H + 1 + 25;

//неоткрытые клетки — серые

if (Pole[row, col] < 100)

{

g.FillRectangle (SystemBrushes.ControlLight, x — 1, y — 1, x + W, y + H);

}

//открытые или помеченные клетки

if (Pole[row, col] >= 100)

{

//открываем клетку, открытые-белые

if (Pole[row, col] ≠ 109)

g.FillRectangle (Brushes.White, x — 1, y — 1, x + W, y + H);

//подрыв на мине, клетка красная

else

g.FillRectangle (Brushes.Red, x — 1, y — 1, x + W, y + H);

//если рядом с клеткой есть мины, подписываем их кол-во

if ((Pole[row, col] >= 101) && (Pole[row, col] <= 108))

g.DrawString ((Pole[row, col] - 100).ToString (), new Font («Tahoma», 20, FontStyle. Bold), Brushes. Blue, x + 3, y + 2);

}

// в клетке флаг

if (Pole[row, col] >= 200)

this.flag (g, x, y);

//отрисовываем границы клетки

g.DrawRectangle (Pens.Black, x — 1, y — 1, x + W, y + H);

// если игра завершена (status=2), показываем мины

if ((status == 2) && ((Pole[row, col] % 10) == 9))

this.mina (g, x, y);

}

private void open (int row, int col)//метод, открывающий текущую и все соседние клетки, в которых нет мин

{

//координаты области вывода

int x = (col — 1) * W + 1, y = (row — 1) * H + 1 + 25;

if (Pole[row, col] == 0)

{

Pole[row, col] = 100;

//отобразить содержимое клетки

this.Invalidate (new Rectangle (x, y, W, H));

//открыть примыкающие клетки слева, справа, сверху, снизу

this.open (row, col — 1);

this.open (row — 1, col);

this.open (row, col + 1);

this.open (row + 1, col);

//примыкающие диагонально

this.open (row — 1, col — 1);

this.open (row — 1, col + 1);

this.open (row + 1, col — 1);

this.open (row + 1, col + 1);

}

else

if ((Pole[row, col] < 100) && (Pole[row, col] ≠ -3))

{

Pole[row, col] += 100;

//отобразить содержимое клетки

this.Invalidate (new Rectangle (x, y, W, H));

}

}

private void mina (Graphics g, int x, int y)//метод, рисующий мину

{

//корпус

g.FillRectangle (Brushes.Green, x + 16, y + 26, 8, 4);

g.FillRectangle (Brushes.Green, x + 8, y + 30, 24, 4);

g.DrawPie (Pens.Black, x + 6, y + 28, 28, 16, 0, -180);

g.FillPie (Brushes.Green, x + 6, y + 28, 28, 16, 0, -180);

//полоса на корпусе

g.DrawLine (Pens.Black, x + 12, y + 32, x + 28, y + 32);

//вертикальный «ус»

g.DrawLine (Pens.Black, x + 20, y + 22, x + 20, y + 26);

//боковые «усы»

g.DrawLine (Pens.Black, x + 8, y + 30, x + 6, y + 28);

g.DrawLine (Pens.Black, x + 32, y + 30, x + 34, y + 28);

}

private void flag (Graphics g, int x, int y)//метод, рисующий флаг

{

Point[] p = new Point[3];

Point[] m = new Point[5];

//флажок

p[0]. X = x + 4;

p[0]. Y = y + 4;

p[1]. X = x + 30;

p[1]. Y = y + 12;

p[2]. X = x + 4;

p[2]. Y = y + 20;

g.FillPolygon (Brushes.Red, p);

//древко

g.DrawLine (Pens.Black, x + 4, y + 4, x + 4, y + 35);

//буква М на флажке

m[0]. X = x + 8;

m[0]. Y = y + 14;

m[1]. X = x + 8;

m[1]. Y = y + 8;

m[2]. X = x + 10;

m[2]. Y = y + 10;