Негосударственная некоммерческая образовательная организация

  Московский открытый социальный университ

                          Марийский филиал

     Факультет информационной безопасности

     Кафедра безопасности информационных технологий

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

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

“Методы программирования ”

Программа

Эйлеровые и Гамильтоновы цепи и циклы

 

 
 
Разработал: 
студент группы КБ-41

   Флигинских  А.В.

   Консультировала ст. преподаватель:   

                         _________     _________     ________

                     оценка              дата            подпись

Йошкар-Ола

2004

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

 

Программа “Эйлеровые и Гамильтоновы цепи и циклы” 

Основные характеристики, которым должна удовлетворять программа: 

1. Программа должна быть написана в соответствии с данными алгоритмами потска решений.
2. Программа должна представлять собой приложение, запускаемое исполняемым файлом с расширением exe и работать в среде Windows X (NT, XP) в оконном режиме.
3. Программа должна представлять интерактивный кнопочный интерфейс с легко управляемыми компонентами.
4. Надежность и невышебаемость программы.
5. Простота в использовании.
6. Основные функции программы:Поиск и решение поставленной задачи по определению Эйлеровых и Гамильтоновых цепей и циклов. Оформление и пользовательский интерфейс должны включать:  рабочую область с набором кнопок.
7. Язык программирования Паскаль, среда программирования – Delphi.
8. Объем памяти, занимаемой программой не должен превышать 1.4 Мб. Программа должна свободно запускаться и работать без сбоев и замедления на процессоре   с тактовой частотой 75 Гц и больше.

10.  Возможность  обновления. 

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

 

Аннотация 

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

      Курсовая  работа по предмету “Методы программирования”. Сдается в качестве зачетной работы по предмету.

Annotation

     The given course work represents the description and process of realization of software for the end user. The program represents programm for searching Alerov’s and Gamiltov’s chains and circles, concerning to the category of education. The course work contains the detailed description of programm, its applicability, functional blocks, general and detailed description of structure and other. But to tell the truth, this work nobody will read and thats why i say such a fuckin work.

Course work in a subject "Programming methods". Surrenders as test work in a subject. 
Содержание

Введение……………………………………………………………………………5

1. Инструкция для пользователя………………………………………………....6
1. Описание программы и теоритические сведения……...………………..6
2. Управление………………………………………………………………....6
3. Комплектация……………………………………………………………....7
4. Эксплуатация…………………………………………………………….....7
2. Инструкция для программиста…………………………………………….......8

2.1  Руководство  системному программисту…………………………….........8

2.2 Стандартные  процедуры и функции………………………………….........8

2.3 Функциональная схема………………………………………………….......9

     Заключение………………………………………………………………………....10

     Список  литературы………………………………………………………………...11

     Приложения………………………………………………………………………...12

1. Текст программы…………………………………………………………....12
2. Результат работы программы………………………………………….......16

 

 

Введение

    В 50-е годы ХХ века появились первые языки программирования высокого уровня, это были Fortran, Cobol и Algol. Fortran и Cobol –  это языки долгожители, которые  здравствуют и поныне, а Algol стал родоначальником целого семейства  языков програмирования, в том числе и Pascal. В настоящее время насчитывается несколько тысяч языков программирования, большая часть из которых имеет довольно узкую специализацию.

    В 1970 году был создан новый язык программирования. Никлаус Вирт, создатель языка, назвал его в честь великого французского математика и философа XVII века Блеза Паскаля.

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

    С течением времени появились различные  версии языка и его расширения. Наиболее известным стал пакет Turbo Pascal фирмы Borland, появившейся в 1983 году и сразу ставней событием в мире компьютерных технологий и созданная позже среда для написания приложений для операционных систем - Delphi. Первое упоминание о нём содержалось в рекламе, опубликованной в журнале BYTE, а сам пакет предназначался для операционной системы CP/M. В начале 1994 года приобрёл огромную популярность. С тех пор появилось несколько версий этой среды программирования.

    Фирма Borland/Inprise завершила линию продуктов Turbo Pascal и перешла к выпуску системы визуальной разработки для Windows – Delphi. Несмотря на это, Turbo Pascal сохраняет своё значение отличного языка для первого знакомства с миром “серьёзного” программирования. Это связано как с его чёткой логической структурой, так и с теми возможностями, которые позволяют использовать  Pascal для решения разнообразных задач. Среди них вычисление и обработка данных, компьютерная графика, работа со звуком, системное программирование. Pascal позволяет применять приёмы объектно-ориентированного программирования, которое стало одной из ведущих современных технологий программирования. 
 
 

 

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

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

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

     Основные  возможности программы:

1. Визуальное  изображение графа

2. Ведение матриц смежности для вершин и ребер

3. Быстрота  выполнения алгоритма

    Теоритические сведения.

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

1. Сгенерировать все возможные варианты путей через граф.
2. Исключить все пути, которые не проходят через заданные начальную и конечные вершины.
3. Исключить те пути, что проходят через число вершин, отличное от n.
4. Исключить все пути, которые проходят через какую-либо вершину по нескольку раз.
5. Если после этого хотя бы один путь остался, то это именно тот, что нужен.

Эйлеровый цикл и цепь имеет тотже принцип, но в этом случае рассматриваются ребра.

    Управление

  Управление в этой программе производится с использованием  мыши. При отсутствии таковой работа программы становится невозможной.

     Ниже  приведена таблица действий при  нажатии кнопок мыши:

Комплектация

 

Помимо  основной программы пакет содержит следующие файлы:

Project1.cfg, Project1.dof, Project1.dpr, Project1.res,Unit1.dcu, Unit1.ddp, Unit1.dfm, Unit1.pas. -  программные файлы. Их наличие при выполнении программы необязательно.

Эксплуатация

 

      Для запуска программы необходимо  запустить файл KURSOVAYA.EXE в папке с пакетом или посредством ярлыка на рабочем столе системы. Появиться запущенное приложение с программой. На появившемся рабочем поле необходимо посредством нажатий на кнопки мыши изобразить иследуемый граф. Затем, используя кнопки управления программой начать выполнение действий. 

  Описание  кнопок:

Эйлеровый цикл и цепь – определение Эйлерового цикла и цепи

Гамильтонов цикл и цепь - определение Гамильтонова цикла и цепи

Default –   задание параметра цикла поиска 

Руководство системного программиста.

  Аппаратные  требования:

Pentium 75 и выше, 2 RAM и выше, разрешение экрана не менее 800x600,Windows X, 1,4 Mб свободного места на диске(желательно), мышь и много терпения.

Замечание: Программа изначально поставляется урезанной в своих функциональных возможностях. Для полной версии необходима регистрация. Стоимость полной версии составляет 100$. Регистрация: fligy@rambler.ru.

Для корректной работы программы необходим лишь исполняемый файл.

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

 

     ClickStartButton - процедура, отвечающая за начало нового поля.

Входные данные: level,tip; Выходные данные: result;

     ClickEditButton - процедура, отвечающая за редактирование  нового поля.

Входные данные: нет Выходные данные: нет

     ClickExitButton - процедура, отвечающая за выход  из программы.

Входные данные: нет Выходные данные: нет

     ClickAboutButton - процедура, отвечающая за вывод  информации об авторе.