Программа поиска кратчайшего пути в лабиринте

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

РОССИЙСКОЙ  ФЕДЕРАЦИИ

                         КУРСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

Кафедра программного обеспечения 

и администрирование информационных систем

 

                                               Курсовая работа

Программа поиска кратчайшего пути в лабиринте.

 

Работу принял:                                                  Работу выполнил:

доцент к. т. н.                              ст. 213 гр. МОиАИС.

Белова Т. М.                                               Корневская Г.О.  

 

________________________

(оценка)         

Подпись:__________________   Подпись:______________

Дата:_____________________   Дата:_________________ Курск 2012

 

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

РОССИЙСКОЙ  ФЕДЕРАЦИИ

КУРСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

              Кафедра программного обеспечения  и администрирование

                                        информационных систем                      

                                                

 

 УТВЕРЖДАЮ:                                                         

   Зав.  кафедрой ПОиАИС

                                                                                ______________ Жмакин А. П.

 

ЗАДАНИЕ

на  курсовой проект (работу)

                          по дисциплине «Программирование»

Студентка  __________ Кореневская Г.О.

подпись и расшифровка подписи 

Шифр 

 

Факультет  ФМИ

Специальность  МОиАИС.

Группа  213 

Руководитель __________

подпись и расшифровка подписи

 

Тема курсового проекта (работы): программа реализации поиска кратчайшего пути выхода из лабиринта.

 

Состав и  этапы работы: (составляется преподавателем)

1. Ознакомиться  с рекомендуемой литературой.  Дать аналитический обзор проблемы.

2. Теоретический  материал

3. Исходные  данные

_______________________________________________________________

Среда разработки Borland C++Builder 6.

4. Цель работы

________________________________________________________________

________________________________________________________________

________________________________________________________________

5. Отчетный материал курсового проекта (работы)

1. Техническое задание

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

6. Контрольные этапы и даты:

Этап	1	2	3
Дата
Подпись руководителя

 

 

 

Задание получено: «____» _______________ 2012г.

 

Студент ______________________________

подпись и расшифровка подписи

Руководитель _________________________                                                                                                                     

подпись и расшифровка подписи

 

 

Отзыв руководителя

________________________________________________________________

________________________________________________________________

________________________________________________________________

________________________________________________________________

 

 

Оценка: «_____»

Руководитель _________________________         

         Дата  ________________                                                                                                                    

подпись и  расшифровка подписи__________                        

 

 

 

 

 

 

Содержание:

1   Техническое задание ……………………………………………………….8

1.1 Введение ……………………………………………………………..8 

1.2 Основания  для разработки ………………………………………….8 

  1.3 Функциональное и эксплуатационное назначение изделия ……...8 

1.4 Методические ограничения ………………………………………...9

1.4.1 Стандарты …………………………………………………...9

          1.4.2 Программная совместимость ……………………………... 9

1.4.3 Требования к составу и  параметрам технических 

средств …………………………………………………………….10

1.4.4 Входные данные ……………………………………………10

1.4.5 Выходные данные …………………………………………..10

1.4.6 Безопасность и секретность ………………………………..10

1.4.7 Мобильность ………………………………………………..10

1.5 Стадии  и этапы разработки ………………………………………..11

1.6 Технико-экономические   показатели разработки ………………...11

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

2.1 Функциональные  и эксплуатационные характеристики  ………...12

2.2 Удобство эксплуатации …………………………………………….12

     2.3 Описание программы ……………………………………………….12

                   2.3.1 Функциональное описание ………………………………….13                                         

                   2.3.2 Форма программы в проекте ……………………………14-15

                   2.3.3 Описание среды программирования  для реализации    

                            практических частей курсовой работы …………………….16

                   2.3.4 Интерфейс программного продукта ……………………17-20 

 Приложение: текст программы  с комментариями, блок-схемы основных  алгоритмов, список литературы.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1   ТЕХНИЧЕСКОЕ ЗАДАНИЕ

•         1.1 Введение

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

 

Задание:

Задан лабиринт, составленный из комнат, в каждой из комнат имеется не менее 2 и не более 3 дверей, соединяющих между собой соседние комнаты. Одна из дверей называется входом в лабиринт, другая - выходом. Найти кратчайший путь от входа в лабиринт к его выходу, отобразить решение графически выделив цветом результат.

 

        1.2 Основания для разработки

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

        1.3 Функциональное и эксплуатационное назначение изделия

• Перечень требований пользователя к программному изделию.

 

 

Программа должна обеспечивать:

• удобный интерфейс;
• лёгкость в использовании;

 

1.4 Методические ограничения

 

1.4.1 Стандарты

Разработка  программной документации и программы  должна производиться согласно ЕСПД, ГОСТ 19.701-90, ГОСТ 2.304-88.

 

1.4.2 Программная совместимость

Выход должен работать под управлением операционной систем Windows 98/NT/XP/Vista/se7en.

 

1.4.3 Требования к составу и параметрам технических средств

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

• микропроцессор Intel Celeron с тактовой частотой 1.2 ГГц;
• видеоадаптер SVGA с цветным дисплеем;
• объём ОЗУ 128 Мб;
• объём свободного места на жестком диске 1 Mб;
• USB-порт.
• CD – ROM .

 

 

1.4.4 Входные данные 

Входными данными программы  являются действия пользователя.

 

 

1.4.5 Выходные  данные

Результатом работы программы является вывод  результатa на экран в зависимости от заданного графа.

 

 

 

1.4.6 Безопасность  и секретность

Программа  не требует защиты и  может свободно распространяться.

 

1.4.7 Мобильность 

Для копирования программы с  диска или flash-USB  на компьютер необходимо:

1. Распаковать RAR-архив, расположенный на диске (flash-USB), в какую-либо папку на жёстком диске компьютера.

2. Запустить программу.

•     1.5 Стадии и этапы разработки

Выполнение разработки должно включать две стадии:

1  Техническое  задание

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

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

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

 

       1.6 Технико-экономические   показатели разработки

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

 

 

 

 

 

 

 

  2   ПОЯСНИТЕЛЬНАЯ ЗАПИСКА

2.1 Функциональные и  эксплуатационные характеристики 

Программа обладает следующими характеристиками:

• удобный интерфейс;
• лёгкость в использовании;

 

        2.2 Удобство  эксплуатации

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

 

        2.3 Описание  программы

2.3.1 Функциональное описание

(Основные процедуры, использованные  в программе)

void CreatePole(TImage *image) – создаем поле, в котором будем размещать лабиринт;

 

void ShowPole(TImage *image) – показывает то , что есть на поле ;

 

void MakeNullPole() – обнуляет массив поля;

 

bool CreateRoom(int x, int y) – добавляет комнату в матрицу поля;

 

bool CreateLine(int x, int y, TImage*image) – строит  линию;

 

createStrelka(TImage*image) – рисует стрелку;

 

String Deicstr(int V1, int Vn, TImage* image) – реализует алгоритм Дейкстры;

 

int Rec(int v, int vn) – выполняет главную задачу алгоритма Дейкстры;

 

addHelpMas(int n) – добавляет вспомогательный массив;

 

clearHelpMas() – очищает вспомогательный массив;

 

 

 

 

 

 

 

 

 

2.3.2 Форма программы в проекте

После запуска  программы на экран выводится  заставка программы:

 

 

 

 

 

Форма программы:

 

 

 

 

 

 

2.3.3   Описание  среды программирования для реализации     практических частей курсовой  работы

 

В практической части данной курсовой работы используются следующие визуальные и невизуальные компоненты среды  программирования Borland C++Builder 6: TButton, TImage, TMainMenu, TMenuItem;

 

 

 

2.3.4 Интерфейс программного продукта 

После запуска  программы на экран выводится  основное окно программы:

Управление программой производится с помощью мыши.

 

 

Указываем связи между комнатами

 

 

Расставляем начало и конец лабиринта

 

 

 

Ищем кратчайший путь

 

 

 

 

 

 

 

 

Приложение

Текст программы:

#include <vcl.h>

#pragma hdrstop

 

#include <shellapi.h>

#include "Unit1.h"

#include "Unit2.h"

#include "Unit3.h"

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

#pragma package(smart_init)

#pragma resource "*.dfm"

TForm1 *Form1;

tt *oo =new tt(true);

int HelpMas[100];

struct mys{

        int value;

        int v;

        int x;

        int y;

};

struct mys2{

        int sum;

        int value;

        bool visible;

        int prev;

        mys2(){

                sum = 9999;

                value = 0;

                visible = true;

                prev = 0;

        }

};

mys2 Deic[100];

int Start = -1;

int End = -1;

int mas[100][100];

int i_prev=-1;

int j_prev=-1;

int vN = 0;

int N_1=-1;

int N2=-1;

bool F_1 = 0;                         //esli 1 to stavim komnatu

bool F_2 = 0;                        // esli 1 to provodim put`

bool F_3 = 0;

bool F_4 = 0;

const razmPolya = 10;               //razmer polya

mys Pole[razmPolya][razmPolya];    //matrica polya;

void CreatePole(TImage *image);   //chertim pole

void ShowPole(TImage *image);    //pokazuvaem vse chto est na pole

void MakeNullPole();            //obnulyaem massiv polya

bool CreateRoom(int x, int y); //dobavlyaem komnatu v matricu polya

bool CreateLine(int x, int y, TImage*image);//stroim liniyu

String Deicstr(int V1, int Vn, TImage* image);

int Rec(int v, int vn);

addHelpMas(int n);

clearHelpMas();

createStrelka(TImage*image);//otrisovuvatstrelki

 

//===============================================

createStrelka(TImage *image){

        int i_prev;

        int j_prev;

        int i_next;

        int j_next;

        for(int i=0; i<100; i++){

                for(int j=0; j<100; j++){

                        if(mas[i][j]!=0){

                                for(int i_2=0; i_2<100; i_2++){

                                        for(int j_2=0; j_2<100; j_2++){

                                                if(Pole[i_2][j_2].v == i+1){