Ирина Эланс

Автор который поможет с любыми образовательными и учебными заданиями

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

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

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

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

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

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

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

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

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

Программа

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

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

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

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

_________ _________ ________

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

Йошкар-Ола

2004

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

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

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

Программа должна быть написана в соответствии с данными алгоритмами потска решений.
Программа должна представлять собой приложение, запускаемое исполняемым файлом с расширением exe и работать в среде Windows X (NT, XP) в оконном режиме.
Программа должна представлять интерактивный кнопочный интерфейс с легко управляемыми компонентами.
Надежность и невышебаемость программы.
Простота в использовании.
Основные функции программы:Поиск и решение поставленной задачи по определению Эйлеровых и Гамильтоновых цепей и циклов. Оформление и пользовательский интерфейс должны включать: рабочую область с набором кнопок.
Язык программирования Паскаль, среда программирования – Delphi.
Объем памяти, занимаемой программой не должен превышать 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

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

Описание программы и теоритические сведения……...………………..6
Управление………………………………………………………………....6
Комплектация……………………………………………………………....7
Эксплуатация…………………………………………………………….....7

Инструкция для программиста…………………………………………….......8

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

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

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

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

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

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

Текст программы…………………………………………………………....12
Результат работы программы………………………………………….......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 позволяет применять приёмы объектно-ориентированного программирования, которое стало одной из ведущих современных технологий программирования.

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

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

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

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

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

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

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

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

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

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

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

Управление

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

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

Действие

Действие после нажатия

Нажата левая кнопка мыши (одинарное или двойное)

На рабочем поле – отображение в нажатом месте вершины графа.

На вершине – установка активности данной вершины для последующего образования ребра с другой вершиной.

На кнопках управляющих программой – выполняет непосредственно действие, предписанное данной кнопке.

Нажата правая кнопка мыши

(одинарное или двойное)

На рабочем поле – очистка поля

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

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

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$. Регистрация: [email protected].

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

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

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

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

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

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

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

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

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

fy">Входные данные: нет Выходные данные: нет

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

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

FormCreate - процедура, отвечающая за задание первоначальных значение переменным.

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

Функциональная схема программы:

Заключение

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

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

1. Фаронов В.В. Turbo Pascal 7.0. “Начальный курс”. Учебное пособие. - М.: “Нолидж”, 1997. - 667с.

2. Немнюгин С.А. “Turbo Pascal. Практикум”. - СПб, 2001. - 456с.

3. Марченко А.И., Марченко Л.А. “Программирование в среде Turbo Pascal 7.0” / Под ред. Тарасенко В.П. - изд. 6-е. - К.: ВЕК+, 2000. - 464с.

4. Андреенко П.К. “Книга халявных программ для случая, если вам нужно написать курсовую”.

5. Рукосуев П.К. Программирование в среде Turbo Pascal 9.11

6. Флигинских А.В. “Delphi или курсовая нахаляву”

7. Скакуновчиков Ц.Ч. “Паскаль и Дельфи от нечего делать”

8. Проволкин Ж.О. “Delphi для профов”

9. Припадковкин Я.Щ. “Программирование в среде Turbo Pascal 7.0 для детей дошкольного возраста”.

10. Кармагедонов А.Б. “Дельфи для чайников”

11. Ореховосоев В.Г. “Бейсик для специалистов”

12. Компов М.Б. “Негативное воздействие компьютера на организм человека”

Internet:

www.Halyvnieprogi.com

www.kursovieZadarom.com

www.ViktorPelevin.com

www.SdayKursachNa5.com

Приложение

Замечание: Так как текст программы занимает в объеме печатного текста более 60 листов, здесь будут приведены блоки, включающие только основные процедуры программы.

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

unit Unit1;

interface

uses

Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,

Dialogs, StdCtrls, ExtCtrls, Buttons;

type

TForm1 = class(TForm)

RadioButton1: TRadioButton;

RadioButton2: TRadioButton;

RadioButton3: TRadioButton;

RadioButton4: TRadioButton;

RadioButton5: TRadioButton;

BitBtn1: TBitBtn;

RadioButton6: TRadioButton;

RadioButton7: TRadioButton;

RadioButton8: TRadioButton;

RadioButton9: TRadioButton;

RadioButton10: TRadioButton;

RadioButton11: TRadioButton;

RadioButton12: TRadioButton;

RadioButton13: TRadioButton;

RadioButton14: TRadioButton;

RadioButton15: TRadioButton;

RadioButton16: TRadioButton;

Bevel1: TBevel;

Bevel2: TBevel;

Bevel3: TBevel;

Bevel4: TBevel;

BitBtn3: TBitBtn;

BitBtn4: TBitBtn;

BitBtn2: TBitBtn;

Memo1: TMemo;

Memo2: TMemo;

Shape1: TShape;

BitBtn5: TBitBtn;

Memo3: TMemo;

Memo4: TMemo;

Edit1: TEdit;

BitBtn6: TBitBtn;

Label3: TLabel;

Bevel7: TBevel;

Label4: TLabel;

Panel1: TPanel;

procedure FormMouseDown(Sender: TObject; Button: TMouseButton;

Shift: TShiftState; X, Y: Integer);

procedure BitBtn1Click(Sender: TObject);

procedure FormCreate(Sender: TObject);

procedure RadioButton1Click(Sender: TObject);

procedure RadioButton2Click(Sender: TObject);

procedure RadioButton3Click(Sender: TObject);

procedure RadioButton4Click(Sender: TObject);

procedure RadioButton5Click(Sender: TObject);

procedure RadioButton6Click(Sender: TObject);

procedure RadioButton7Click(Sender: TObject);

procedure RadioButton8Click(Sender: TObject);

procedure RadioButton9Click(Sender: TObject);

procedure RadioButton10Click(Sender: TObject);

procedure RadioButton11Click(Sender: TObject);

procedure RadioButton12Click(Sender: TObject);

procedure RadioButton13Click(Sender: TObject);

procedure RadioButton14Click(Sender: TObject);

procedure RadioButton15Click(Sender: TObject);

procedure RadioButton16Click(Sender: TObject);

procedure BitBtn2Click(Sender: TObject);

procedure BitBtn3Click(Sender: TObject);

procedure BitBtn4Click(Sender: TObject);

procedure Timer1Timer(Sender: TObject);

procedure BitBtn5Click(Sender: TObject);

procedure BitBtn6Click(Sender: TObject);

procedure Panel1Click(Sender: TObject);

private

{ Private declarations }

public

{ Public declarations }

end;

var

Form1: TForm1;

chet,i,j,koff,prov1,prov2,koor1,koor2,ver,qwe,o:integer;

s:string;

xy:array[1..16,1..2]of integer;

c:array[1..16,1..16]of integer;

cc:array[1..256,1..256]of integer;

mas:array[1..16]of integer;

re:array[1..256,1..2]of integer;

implementation

{$R *.dfm}

procedure TForm1.FormMouseDown(Sender: TObject; Button: TMouseButton;

Shift: TShiftState; X, Y: Integer);

begin

memo2.text:='';

if button=mbRight then BitBtn1Click(Sender)else begin

if (x>22)and(x<480)and(y>22)and(y<287) then begin

inc(chet);

if chet=1 then begin radiobutton1.Left:=x-7;radiobutton1.top:=y-7;xy[1,1]:=x;xy[1,2]:=y;end;

if chet=2 then begin radiobutton2.Left:=x-7;radiobutton2.top:=y-7;xy[2,1]:=x;xy[2,2]:=y;end;

if chet=3 then begin radiobutton3.Left:=x-7;radiobutton3.top:=y-7;xy[3,1]:=x;xy[3,2]:=y;end;

if chet=4 then begin radiobutton4.Left:=x-7;radiobutton4.top:=y-7;xy[4,1]:=x;xy[4,2]:=y;end;

if chet=5 then begin radiobutton5.Left:=x-7;radiobutton5.top:=y-7;xy[5,1]:=x;xy[5,2]:=y;end;

if chet=6 then begin radiobutton6.Left:=x-7;radiobutton6.top:=y-7;xy[6,1]:=x;xy[6,2]:=y;end;

if chet=7 then begin radiobutton7.Left:=x-7;radiobutton7.top:=y-7;xy[7,1]:=x;xy[7,2]:=y;end;

if chet=8 then begin radiobutton8.Left:=x-7;radiobutton8.top:=y-7;xy[8,1]:=x;xy[8,2]:=y;end;

if chet=9 then begin radiobutton9.Left:=x-7;radiobutton9.top:=y-7;xy[9,1]:=x;xy[9,2]:=y;end;

if chet=10 then begin radiobutton10.Left:=x-7;radiobutton10.top:=y-7;xy[10,1]:=x;xy[10,2]:=y;end;

if chet=11 then begin radiobutton11.Left:=x-7;radiobutton11.top:=y-7;xy[11,1]:=x;xy[11,2]:=y;end;

if chet=12 then begin radiobutton12.Left:=x-7;radiobutton12.top:=y-7;xy[12,1]:=x;xy[12,2]:=y;end;

if chet=13 then begin radiobutton13.Left:=x-7;radiobutton13.top:=y-7;xy[13,1]:=x;xy[13,2]:=y;end;

if chet=14 then begin radiobutton14.Left:=x-7;radiobutton14.top:=y-7;xy[14,1]:=x;xy[14,2]:=y;end;

if chet=15 then begin radiobutton15.Left:=x-7;radiobutton15.top:=y-7;xy[15,1]:=x;xy[15,2]:=y;end;

if chet=16 then begin radiobutton16.Left:=x-7;radiobutton16.top:=y-7;xy[16,1]:=x;xy[16,2]:=y;end;

if chet=17 then memo2.text:='Демо-версия программы работает только не более чем с 16 вершинами. Купить полную версию: [email protected]';

memo1.Text:='';

if chet=17 then chet:=16;

BitBtn2Click(Sender);

end;

procedure TForm1.BitBtn1Click(Sender: TObject);

begin

panel1.Visible:=true;

panel1.Visible:=false;

form1.Canvas.Pen.Color:=clred;

bitbtn1.Font.Color:=clnavy;

memo2.Text:='';

memo3.Text:='';

memo4.Text:='';

memo1.Text:='';

chet:=0;

prov1:=0;

o:=1;

for i:=1 to 16 do for j:=1 to 2 do xy[i,j]:=-1;

for i:=1 to 16 do for j:=1 to 16 do c[i,j]:=0;

for i:=1 to 256 do for j:=1 to 2 do re[i,j]:=0;

for i:=1 to 256 do for j:=1 to 256 do cc[i,j]:=0;

radiobutton1.Left:=840;radiobutton1.top:=33;

radiobutton2.Left:=840;radiobutton2.top:=49;

radiobutton3.Left:=840;radiobutton3.top:=65;

radiobutton4.Left:=840;radiobutton4.top:=81;

radiobutton5.Left:=840;radiobutton5.top:=97;

radiobutton6.Left:=840;radiobutton6.top:=113;

radiobutton7.Left:=840;radiobutton7.top:=129;

radiobutton8.Left:=840;radiobutton8.top:=145;

radiobutton9.Left:=840;radiobutton9.top:=161;

radiobutton10.Left:=840;radiobutton10.top:=177;

radiobutton11.Left:=840;radiobutton11.top:=193;

radiobutton12.Left:=840;radiobutton12.top:=209;

radiobutton13.Left:=840;radiobutton13.top:=225;

radiobutton14.Left:=840;radiobutton14.top:=241;

radiobutton15.Left:=840;radiobutton15.top:=257;

radiobutton16.Left:=840;radiobutton16.top:=273;

end;

procedure TForm1.FormCreate(Sender: TObject);

begin

form1.Canvas.Font.Color:=clyellow;

form1.Canvas.Brush.Color:=clblack;

form1.Canvas.Pen.Color:=clred;

bitbtn1.Font.Color:=clnavy;

o:=1;

chet:=0;

prov1:=0;

prov2:=0;

for i:=1 to 16 do for j:=1 to 2 do xy[i,j]:=-1;

for i:=1 to 16 do for j:=1 to 16 do c[i,j]:=0;

for i:=1 to 256 do for j:=1 to 2 do re[i,j]:=0;

for i:=1 to 256 do for j:=1 to 256 do cc[i,j]:=0;

memo2.Text:='';

memo3.Text:='';

memo4.Text:='';

memo1.Text:='';

end;

procedure TForm1.RadioButton1Click(Sender: TObject);

begin

memo2.Text:='';

if prov1=1 then begin

str(o,s);

form1.Canvas.TextOut(koor1+round((xy[1,1]-koor1)/2),koor2+round((xy[1,2]-koor2)/2),'X'+s);

form1.Canvas.MoveTo(koor1,koor2);

form1.Canvas.LineTo(xy[1,1],xy[1,2]);

prov1:=0; c[1,ver]:=1;

c[ver,1]:=1;

radiobutton1.Checked:=false;memo1.Text:='';BitBtn2Click(Sender);

re[o,1]:=1;

re[o,2]:=qwe;inc(o);BitBtn5Click(Sender);

end else begin qwe:=1;

koor1:=xy[1,1];

koor2:=xy[1,2];

ver:=1;prov1:=1; end;

end;

procedure TForm1.RadioButton2Click(Sender: TObject);

begin memo2.Text:='';

if prov1=1 then begin

str(o,s);

form1.Canvas.TextOut(koor1+round((xy[2,1]-koor1)/2),koor2+round((xy[2,2]-koor2)/2),'X'+s);

form1.Canvas.MoveTo(koor1,koor2);