Игровая программа. Раскраска графа

Автор работы: Пользователь скрыл имя, 17 Июня 2013 в 18:45, курсовая работа

Описание работы

Пусть задан простой неориентированный граф G = (V, E), как конечное множество вершин V и множество E неупорядоченных пар ребер. Так же дано число К – количество красок для раскрашивания графа.
Выбираем случайную вершину из множества вершин V, окрашиваем ее в случайный цвет, выбираем цвет и окрашиваем все смежные неокрашенные вершины в него. И так поступаем, пока не раскрасим весь граф. После чего сравниваем потребовавшихся цветов Кп и К, если К>Кп, то выводим на экран получившееся, в противном случае выдаем сообщение о том, что граф невозможно раскрасить К цветами.

Содержание работы

Цель работы …………………………………………………………………… 3
Постановка задачи …………………………………………………………….. 3
Метод решения ………………………………………………………………… 3
Общая структура программы ………………………………………………… 4
Сценарий диалога с пользователем …………………………………………... 5
Разработка основных данных и алгоритмов ………………………………… 6
Методика тестирования ………………………………………………………. 8
Примеры работы программы ………………………………………………… 9
Выводы ………………………………………………………………………… 11
Библиографический список ……………………………

Скачать архив (419.48 Кб) Сколько стоит заказать работу?
Файлы: 1 файл

курсовик образец Макс.doc

— 521.00 Кб (Скачать файл)

Федеральное агентство  по образованию РФ

 

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

 

Кафедра ВТ

 

 

 

 

 

 

 

 

 

 

 

 

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

 

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

 

«Игровая программа. Раскраска графа»

 

 

 

 

 

 

 

 

 

Выполнил:  

 

Проверил:   проф. Зотов И. В.

 

 

 

 

 

 

 

 

Курск 2009

Содержание

Цель работы …………………………………………………………………… 3

Постановка задачи …………………………………………………………….. 3

Метод решения ………………………………………………………………… 3

Общая структура программы  ………………………………………………… 4

Сценарий диалога с  пользователем …………………………………………... 5

Разработка основных данных и алгоритмов ………………………………… 6

Методика тестирования ………………………………………………………. 8

Примеры работы программы ………………………………………………… 9

Выводы ………………………………………………………………………… 11

Библиографический список ………………………………………………….. 12

Приложение …………………………………………………………………… 13

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Цель работы

 

Изучение приемов формализации, составления алгоритмов и программирования при решении прикладных задач, а  также глубокое овладение языком программирования С++ и приемами программирования в интегрированной среде разработки Borland C++ Builder 6.

 

Постановка задачи

 

Задание на курсовую работу. Вариант 14.

Прикладная программа. Раскраска графа.

Описание задачи.

Заданы граф , где V — множество вершин; E — множество ребер, и положительное целое число , где — мощность множества V. Раскрасить вершины графа K красками так, чтобы ни одно его ребро не имело соцветных концов. Если такая раскраска невозможна, выдать на экран соответствующее сообщение. Предусмотреть графическое представление исходного графа и цветовое выделение его вершин на экране.

 

Метод решения

.

 Пусть задан простой неориентированный граф G = (V, E), как конечное множество вершин V и множество E неупорядоченных пар ребер. Так же дано число К – количество красок для раскрашивания графа.

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

 

 

 

 

 

 

 

 

 

 

 

 

Общая структура программы


 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Программа состоит из 1 функционального модуля:

  • Main.cpp – модуль, располагающий в себе основные элементы интерфейса пользователя (в частности, процедуры обработки функциональных кнопок), функцию раскраски графа, а также функцию перерисовки экрана.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Сценарий диалога с  пользователем

 

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

 

 

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

Программа содержит функциональные кнопки:

    1. «Генерация» - осуществляет генерацию ребер графа.
    2. «Раскрасить» - раскрашивает граф.

 

 

 

 

 

 

 

 

Разработка основных данных и алгоритмов

 

В качестве входных данный программа использует:

    1. MatrSmeg - матрица смежности вершин графа
    2. Col_Verh = 3 - количество вершин
    3. ColorArray[15] – массив цветов для раскраски графа (TColor)
    4. Verh – массив содержит координаты вершин на поле (TPoint)
    5. VerhC – массив, содержащий цвет вершин (TColor)
    6. select - номер выделенной вершины

Для ввода и редактирования графа используются функции:

void PaintVerh() – функция раскраски вершин графа.

void Random_Generate_V() – функция в случайном порядке определяет координаты вершин.

void Random_Generate() – ф-я генерирует матрицу смежности вершин графа.

void PaintGraf() - функция прорисовывает граф на форме.

void PaintBox1MouseDown(TObject *Sender,

      TMouseButton Button, TShiftState Shift, int X, int Y) – перемещает вершины, изменяя их месторасположение.

 

Стоит отметить подпрограмму, являющуюся решением основной задачи работы – раскраски графа. Она вызывается после нажатия кнопки «Раскрасить» , т.е. является обработчиком события Button2Click.

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

 

 

 

 

 

 

 

 

 

Рассмотрим алгоритм раскраски вершин отдельно от общего алгоритма программы.

 

 

 

 

 

 

 

 

 

 

 

 

Методика тестирования

Проверим корректность работы алгоритма и программы  в целом на ряде примеров.

№

Тестовый набор

Эталон

Результат

Вывод

1

Для тестирования программы  зададим граф, содержащий 4 вершины и определяющийся следующей матрицей смежности:

Потребуется 2 цвета краски.

Потребовалось 2 цвета краски.

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

2

Для тестирования программы зададим граф, содержащий 6 вершин и определяющийся следующей матрицей смежности:

Потребуется 3 цвета краски.

Потребовалось 3 цвета  краски.

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


 

 

 

 

 

 

 

 

 

 

Примеры работы программы

Начальный граф, состоящий  из 5 вершин.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Раскрасим граф используя 3 цвета краски.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Выводы

В процессе выполнения работы я изучил приемы формализации, составления  алгоритмов и программирования при  решении прикладных задач, освоил язык программирования С++, а также овладел приемами программирования в ОС Windows и разработки программ в среде С++ Builder

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Библиографический список

  1. Borland С++ Builder Help.
  2. Культин Н.Б. C++ Builder в задачах и примерах. – Санкт-Петербург: БХВ-Петербург, 2007г.
  3. Архангельский А.Я., Тагин М.А. Программирование в C++ Builder 6 и 2006 – М.: ЗАО «Издательство БИНОМ», 2007г.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Приложение

Листинг файла Main.h

 

//---------------------------------------------------------------------------

 

#include <vcl.h>

#pragma hdrstop

 

#include "Main.h"

//---------------------------------------------------------------------------

#pragma package(smart_init)

#pragma link "CSPIN"

#pragma resource "*.dfm"

TForm1 *Form1;

byte MatrSmeg [100][100]; // матрица смежности вершин

int Col_Verh = 3;  // Колличество вершин

TColor ColorArray[15];

TPoint Verh [100];  // Координаты вершин на поле

TColor VerhC [100];

int select = -1;  // номер выделеннолй вершины

 

//---------------------------------------------------------------------------

__fastcall TForm1::TForm1(TComponent* Owner)

        : TForm(Owner)

{

}

//---------------------------------------------------------------------------

void PaintVerh()  // раскраска графа

{

bool okrV = true;

int Vindex = 0;

int colorIndex = 0;

 

while (okrV)

{

  if (VerhC[Vindex] == clGreen)

  {

   VerhC[Vindex] = ColorArray[colorIndex];

   for (int i =0; i<Col_Verh; i++)

    if (MatrSmeg[Vindex][i] == 0)

     if (Vindex  < i)

      {

         bool r =true;

         for (int k =0; k<Col_Verh; k++)

            if ((MatrSmeg[i][k] == 1)&&(VerhC[k] == ColorArray[colorIndex]))

              r = false;

 

          if (r)

           VerhC[i] = ColorArray[colorIndex];

      }

     colorIndex++;

    }

    else

      Vindex++;

 

  okrV = false;

  for (int i = 0; i<Col_Verh; i++)

     if (VerhC[i] == clGreen)

         okrV =true;

  }

  ShowMessage("Потребовалось "+IntToStr(colorIndex)+" цветов");

}

//---------------------------------------------------------------------------

void Random_Generate_V()   // подпрограмма  в случайном порядке определяет

{                          // координаты вершин

  Randomize;

  for (int i = 0; i<Col_Verh; i++)

  {

    int x = 50 + random(Form1->PaintBox1->Width - 50);   // генерация координат

    int y = 50 + random(Form1->PaintBox1->Height - 50);

     Verh[i].x = x;      // присвоение координат

     Verh[i].y = y;

  }

}

//---------------------------------------------------------------------------

void Random_Generate()  // Подпрограмма генерирует  матрицу смежности вершин графа

{

Randomize;

Randomize;

Randomize;

int CountR = random(Col_Verh*(Col_Verh/3)); // генерация колличества ребер

 

for (int i = 0; i<CountR; i++)

   {

      int x = random(Col_Verh);  // генерация позиции ребра

      int y = random(Col_Verh);

      if (x != y)

      {

      MatrSmeg[x][y] = 1;       // занесение ребра в матрицу смежности

      MatrSmeg[y][x] = 1;

      Form1->StringGrid1->Cells[x][y] = "1";

      Form1->StringGrid1->Cells[y][x] = "1";

      }

   }

}

//---------------------------------------------------------------------------

void PaintGraf()  //Подпрограмма прорисовывает граф на форме

{

Form1->PaintBox1->Canvas->Brush->Color =clCream;

Form1->PaintBox1->Canvas->Rectangle(0,0,Form1->PaintBox1->Width,Form1->PaintBox1->Height);

  for (int i =0; i< Col_Verh; i++)

   for (int j =0; j< Col_Verh; j++)

     if (MatrSmeg[i][j] == 1)

     {

        Form1->PaintBox1->Canvas->MoveTo(Verh[i].x,Verh[i].y);

        Form1->PaintBox1->Canvas->LineTo(Verh[j].x,Verh[j].y);

     }

 

Form1->PaintBox1->Canvas->Pen->Width = 1;

Form1->PaintBox1->Canvas->Pen->Color = clBlack;   

 

Form1->PaintBox1->Canvas->Brush->Color = clGreen;

 

for (int i =0; i< Col_Verh; i++)

{

    Form1->PaintBox1->Canvas->Brush->Color = VerhC[i];

    Form1->PaintBox1->Canvas->Ellipse(Verh[i].x-10,Verh[i].y-10,Verh[i].x+10,Verh[i].y+10);

    if(i<10) Form1->PaintBox1->Canvas->TextOutA(Verh[i].x-4,Verh[i].y-7,IntToStr(i+1));

    else Form1->PaintBox1->Canvas->TextOutA(Verh[i].x-6,Verh[i].y-7,IntToStr(i+1));

}

    if (select != -1)

      {

         Form1->PaintBox1->Canvas->Brush->Color = clYellow;

         Form1->PaintBox1->Canvas->Ellipse(Verh[select].x-10,Verh[select].y-10,Verh[select].x+10,Verh[select].y+10);

      }

}

//---------------------------------------------------------------------------

void __fastcall TForm1::PaintBox1Paint(TObject *Sender)

{

   PaintGraf();

}

//---------------------------------------------------------------------------

// обработка нажатия клавиши  мыши, изменение позиции вершин

void __fastcall TForm1::PaintBox1MouseDown(TObject *Sender,

      TMouseButton Button, TShiftState Shift, int X, int Y)

{

if (select == -1)  // если нет выделенных  вершин и произведен щелчек

{

   for (int i =0; i<Col_Verh; i++)  // по  координатам курсора во время  щелчка определяем

    if ((Verh[i].x-10 < X)&&(Verh[i].y-10 < Y)&&  //надо ли  выделять вершину

    (Verh[i].x+10 > X)&&(Verh[i].y+10 > Y))

     {

        select = i;              //если да то выделяем вершину

     }

} else {

  Verh[select].x = X;     // если  вершина выделенна и произведен  щелчек

  Verh[select].y = Y;     // перемещаем на эту вершину на то место на форме геде был произведен щелчек

  select = -1;

}

PaintGraf();

}

//---------------------------------------------------------------------------

// изменение размеров формы

void __fastcall TForm1::FormResize(TObject *Sender)

{

Random_Generate_V(); 

}

//---------------------------------------------------------------------------

// кнопка «Генерация»

void __fastcall TForm1::Button1Click(TObject *Sender)

{

  Random_Generate();

  PaintGraf();

}

//---------------------------------------------------------------------------

// определяет количество вершин

void __fastcall TForm1::CSpinEdit1Change(TObject *Sender)

{

  Col_Verh = CSpinEdit1->Value;

  StringGrid1->RowCount = Col_Verh;

  StringGrid1->ColCount = Col_Verh;

   Random_Generate_V();

  for (int  i = 0; i<Col_Verh; i++)

  for (int  j = 0; j<Col_Verh; j++)

  {

     StringGrid1->Cells[i][j] = "0";

     MatrSmeg[i][j] = 0;

  }

  for (int  i =0;i<Col_Verh; i++)

     VerhC[i] = clGreen;

  PaintGraf();

}

//---------------------------------------------------------------------------

// добавление/удаление ребер в  StringGrid

void __fastcall TForm1::StringGrid1SelectCell(TObject *Sender, int ACol,

      int ARow, bool &CanSelect)

{

  if (ACol == ARow)

     return;

 

   if (StringGrid1->Cells[ACol][ARow] == "0")

   {

       StringGrid1->Cells[ACol][ARow] = "1";

       StringGrid1->Cells[ARow][ACol] = "1";

       MatrSmeg[ACol][ARow] = 1;

Информация о работе Игровая программа. Раскраска графа