Написать программу игры в пятнашки

МИНИСТЕРСТВО ОБРАЗОВАНИЯ  И НАУКИ

РЕСПУБЛИКИ КАЗАХСТАН

МЕЖДУНАРОДНАЯ БИЗНЕС-АКАДЕМИЯ

 

Кафедра ИТ и ОТД

 

 

КУРСОВАЯ РАБОТА

 

Дисциплина: “ Технология программирования ”

Тема: " Написать программу игры в пятнашки"

 

Выполнил: Соловьев Н.Е.

Группа: ИС – 11

Проверил: Краснов. А. М.

Леонов. В.В.

 

Караганда

2012

РЕФЕРАТ

 Пояснительная записка к курсовой работе: 42c., 3 рис., 6 раздела, 1 приложение, 5 источников.

Цель работы – разработка программы для игры в пятнашки.

Метод исследования – изучение литературы, написание, отладка программы на компьютере.

Программа написана на языке С++ в  среде Code Blocks 10.05, используя GCC/GNU Compiler.

 

 

 

 

 

 

 

 

 

 

 

 

СОДЕРЖАНИЕ

Введение

1 Математическая теория игры

2 Проектирование структур программы

3 Среда программирования Code::Blocks

4 Инструкция пользователя

5 Выводы

6 Список использованной литературы

7 Приложение

 

 

 

 

 

 

 

 

 

 

ВВЕДЕНИЕ

Целью курсового проекта  являлось составление игры «Пятнашки».

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

В узком смысле слова, программирование рассматривается  как кодирование — реализация одного или нескольких взаимосвязанных алгоритмов на некотором языке программирования. Под программированием также может пониматься разработка логической схемы для ПЛИС, а также процесс записи информации в ПЗУ. В более широком смысле программирование — процесс создания программ, то есть разработка программного обеспечения.

Большая часть работы программиста связана с написанием исходного кода на одном из языков программирования.

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

Единственный язык, напрямую выполняемый процессором — это машинный язык (также называемый машинным кодом). Изначально все программисты прорабатывали каждую мелочь в машинном коде, но сейчас эта трудная работа уже не делается. Вместо этого программисты пишут исходный код, и компьютер (используя компилятор, интерпретатор или ассемблер) транслирует его, в один или несколько этапов, уточняя все детали, в машинный код, готовый к исполнению на целевом процессоре. Даже если требуется полный низкоуровневый контроль над системой, программисты пишут на языке ассемблера, мнемонические инструкции которого преобразуются один к одному в соответствующие инструкции машинного языка целевого процессора.

В данной курсовой работе я представил программу, написанную на языке С++ в которой мы можем  играть в игру пятнашки.

Самый первый вопрос, который  мы должны себе задать, звучит примерно так: "Что должна делать эта программа? Какие функции она должна выполнять? Какими особенностями должна она обладать? Как должна выглядеть работа программы?" Ответы на эти вопросы составят приблизительный список требований, предъявляемый к программе и помогут нам яснее представить себе, что именно нам предстоит сделать.

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

 

 

1 МАТЕМАТИЧЕСКАЯ ТЕОРИЯ ИГРЫ

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

Рисунок 1.- Нерешаемая комбинация.

Можно показать, что ровно  половину из всех возможных 1 307 674 368 000 (=15!) начальных положений пятнашек невозможно привести к собранному виду: пусть квадратик с числом   расположен до (если считать слева направо и сверху вниз)   квадратиков с числами меньшими  . Будем считать  , то есть если после костяшки с  -м числом нет чисел, меньших  , то  . Также введем число   — номер ряда пустой клетки (считая с 1). Если сумма

является нечётной, то решения головоломки не существует.

 

 

 

 

 

 

2 ПРОЕКТИРОВАНИЕ  СТРУКТУР ПРОГРАММЫ

Следующий не менее вопрос, который вам предстоит себе задать, после того, как вы определились с конкретизацией своей цели: "Какова должна быть структура программы? Из каких частей она должна состоять? Как эти части должны взаимодействовать друг с другом. На этом этапе нам уже необходимо обратиться к особенностям конкретного языка программирования (вообще говоря, выбор средств и инструментов, таких как конкретный язык программирования предшествует данному этапу, но для нас такой вопрос не стоит, поэтому мы его опустим). Во-первых, как театр начинается с вешалки, так и выполнение программы, написанной на языке C++, начинается с функции main. Она должна стать центром, в котором происходит обращение ко всем прочим частям и элементам программы. Кроме того, функция main должна во многом отражать структуру программы. Чаще всего в главной функции, и в главном модуле программы содержится меньшая часть кода по сравнению со всеми прочими частями. Итак, в функцию main мы сведем все прочие элементы программы, придав им четкую и ясную структуру. Но сначала определимся с этими самыми элементами.

 Работая на языке  C++ мы для разделения кода данной  конкретной игры применим функции,  каждая из которых будет выполнять строго определенные действия, реализуя вполне определенные части поставленной задачи. Итак, как должна выглядеть игра "Пятнашки", и какими данными должна оперировать программа?

 Разумеется, что центральным  объектом в данной игре является  игровое поле размером 4 на 4 клетки. Естественным образом будет представить его в виде массива целых чисел - каждый элемент массива будет содержать в себе номер костяшки. Представляется, что других фундаментальных объектов нам не понадобится.

 Теперь представим себе, какие  действия и в каком порядке должна будет выполнять программа. Во-первых, нам нужно будет сгенерировать первоначальное расположение костяшек. Во-вторых, нам, несомненно, потребуется рисовать поле. В-третьих, игра должна завершиться как только поле будет собрано правильно, поэтому нам понадобится функция, выполняющая проверку правильности текущего положения костяшек. Сам же процесс игры будет происходить следующим образом. Сначала программа генерирует поле с учетом всех требований. Затем вплоть до завершения сборки поля происходит игровой цикл, включающий в себя: считывание с клавиатуры нажатия клавиши, перемещение костяшек в соответствии с нажатой клавишей, перерисовку поля. И наконец (после выхода из игрового цикла, т.е. после сборки поля) программа поздравляет победителя и завершается.

Итак, начинаем оформлять все эти  мысли в виде кода, понятного нашему компилятору. Первым делом мы объявим  объект, который будет представлением игрового поля. Как я уже говорил  выше, мы представим его в виде массива, причем двумерного, целых чисел. Для каждого типа T существует тип T[N] - массив элементов типа T. Массив представляет собой набор из N элементов (N должна быть константой) данного типа, пронумерованных от 0 до N - 1.

Многомерные массивы представляются как массивы массивов: int Matrix[3][3] - массив элементов типа массив целых чисел, по сути - двумерный массив (матрица) целых чисел.

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

 int Field[4][4];

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

 int EmptyX, EmptyY;

 Теперь же перейдем к функциям. Самой первой мы напишем функцию генерации поля, коль скоро она у нас первой и вызывается. Определимся сначала с алгоритмом, который мы будем использовать. Как известно, среди всех возможных комбинаций расположения костяшек не всякое является разрешимым. Мы же изначально требовали, чтобы при генерации было получено поле, которое можно привести к правильному виду. Зачастую эту проблему решают не слишком изящно, просто устанавливая сначала поле в правильное положение, а потом перемешивая костяшки по правилам игры. Чтобы получить пристойный результат, надо совершить достаточно большое количество случайных перемещений костяшек, да и алгоритм получается не самым простым.

 Но - открою вам секрет! - на  самом деле так мучиться не  надо! Существует гораздо более  простой и рациональный способ определить разрешимое начальное положение костяшек. Для этого мы прибегнем к помощи математической теории игры "пятнашки". Лично я необходимые для этого знания почерпнул давно - после того, как в детском саду стал обладателем книжек "Занимательные задачи для маленьких" и "Смекалка для малышей".Именно, первая из них, составленная на основе книг Я. И. Перельмана, рассказывала об истории этой игры, разрешимых и неразрешимых задачах в ней, а также о способе, позволяющем узнать, можно ли данное расположение костяшек привести к исходному. Суть его заключается в следующем. Пусть у нас имеется некоторое расположение костяшек на поле, причем в правом нижнем углу костяшек нет. Беспорядком называется такое положение костяшки, при котором она стоит ранее другой костяшки, имеющей меньший номер. Сколько костяшек с меньшими номерами стоят после данной - таково количество беспорядков для нее. Если общее число беспорядков на всем поле - четное, то его можно привести в правильное расположение, если же нечетное - то этого никак нельзя сделать согласна правилам игры.

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

void CreateField()

  {

  bool NumIsFree[15]; //NumIsFree[i] показывает, определили ли мы уже позицию i-й костяшки

  int Nums[15]; //Nums[i] содержит номер костяшки, находящейся в i-й позиции

  for (int i = 0; i < 15; i++) //Объявляем, что изначально все костяшки свободны

   NumIsFree[i] = true;

  randomize(); //randomize позволяет при каждом прогоне программы получать разные последовательности псевдослучайных чисел

  bool Ok; //Флаг, определяющий корректность выбора костяшки для данной позиции

  int RandNum; //Номер костяшки, генерируемый в дальнейшем случайным образом

  for (int i = 0; i < 15; i++) //Нам надо определить номер костяшки, находящейся в каждой из 15 позиций поля

   {

   Ok = false; //Каждый раз сбрасываем значение флага

   while (!Ok) //Продолжаем случайным образом определять номер костяшки, пока он не окажется корректным

    {

    RandNum = random(15) + 1; //random(n) генерирует псевдослучайное число от 0 до n - 1, а нам нужно от 1 до 15

    if (NumIsFree[RandNum - 1]) //Если костяшка с таким номером еще свободна

     Ok = true; //то мы определили ее номер корректно

    }

   Nums[i] = RandNum; //Записываем этот корректный номер в i-ю позицию

   NumIsFree[RandNum - 1] = false; //Костяшка с этим номером теперь занята

   }

  }

 

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

int Chaos = 0; //Количество беспорядков на поле

  int CurrNum; //Костяшка, для которой мы рассматриваем беспорядки

  for (int i = 0; i < 14; i++) //Считаем для костяшек на первых 14 позициях (для 15-й это бессмысленно)

   {

   CurrNum = Nums[i];

   for (int j = i + 1; j < 15; j++)

    if (CurrNum > Nums[j])

     Chaos++;

   }

  if (Chaos % 2 == 1) //Если общее число беспорядков нечетное,

   { //меняем местами  костяшки на 14-й и 15-й позициях

   int temp = Nums[13];

   Nums[13] = Nums[14];

   Nums[14] = temp;

   }

 

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