Студент Иванова Анжелика Анатольевна
Факультет ЗХТ ЗДО Группа 22-04
Тема: Исследование и программная реализация алгоритмов теории графов
Вариант X.
Привести формулировку варианта. (заменяется собственным текстом)
Задания к выполнению курсовой работы:
1. Интерпретировать задачу, выданную преподавателем в терминах теории графов.
2. Выбрать алгоритм, позволяющий решить данную задачу.
3. Реализовать алгоритм на выбранном языке программирования. Осуществлять задание графа с помощью какой-либо из возможных матриц (смежности, инцидентности, связности, длин ребер). По возможности реализовать ввод с помощью оконных форм. Предусмотреть возможность ввода разнообразных входных данных.
4. Реализовать графическое представление введенного графа.
5. Произвести расчеты по соответствующему алгоритму.
6. Реализовать вывод результатов решенной задачи.
Пояснение:
Файлы программы после сдачи задания скопировать в папку группы. Собственные имена файлов должны соответствовать фамилии студента и номеру варианта задания Предложенную задачу сформулировать в терминах теории графов и подобрать соответствующий алгоритм.
|
|
Реализовать выбранный алгоритм на языке программирования. Предусмотреть возможность ввода разнообразных входных данных.
Окончательный вариант выходных данных программы обязательно должен отображать смысловую постановку задачи.
Приложить распечатки экранов.
Календарный план выполнения работы
1 – 5.10.13 - формализация задачи
6 – 10.10.13 - уточнение входной и выходной информации
11 – 18.10.13 – составление схемы алгоритма
19 – 30 10.13 – проведение расчетов
1 - 10.12.13 – отладка и тестирование
11 - 20.12.13 - оформление пояснительной записки
23.12.13 – защита курсовой работы
Задание выдано ___ 01.10.13
Руководитель __________ Иванилова Т.Н.
Приложение А3
Содержание
Содержание
Реферат…………………………………………………………………………..5
Введение…………………………………………………………………………6
1 Алгоритм построения (заменяется собственным текстом) … …...………..7
2 Решение задачи..………………………………………………………….….7
2.1 Входная и выходная информация………………………………….....7
2.2 Схема алгоритма......................................................................................7
2.3 Текст программы………………………………………………...…...7
2.4 Протокол контрольного расчета……………………………..…......8
3 Инструкция по работе с программой……………………………………...9
Заключение……………………………………………………………….…...10
Список использованных источников………………………………………..11
|
|
Приложение А4
Реферат
Реферат
Расчетно-графическая работа представляет собой решение задачи по расчету (заменяется собственным текстом).
Расчет выполнен с помощью языка программирования (заменяется собственным текстом).
Пояснительная записка включает в ххх страниц текста, ххх распечатки экрана, схему алгоритма, ххх использованных литературных источника.
Ключевые слова: (заменяется собственным текстом).
Цель работы – овладение навыками работы с алгоритмом построения (заменяется собственным текстом).
Метод исследования – теория графов, алгоритмизация, язык программирования (заменяется собственным текстом).
Данная программа позволяет:
1) определить способ задания графа;
2) ввести граф, используя матрицу (заменяется собственным текстом);
3) рассчитать (заменяется собственным текстом);
4) провести тестирование алгоритма.
Приложение А5
Алгоритм и Решение задачи
Введение
Необходимо написать о применении методов теории графов в практических задачах.
1 Алгоритм построения… (заменяется собственным текстом)
Напечатайте текст из учебников или лекций, далее выполните разделы в соответствии с содержанием.
Решение задачи
2.1 Входная и выходная информация
Необходимо описать способ представления входной и выходной информации программы, возможности ввода графов с разным количеством вершин и ребер. Описать ограничения (если есть) по объему входной информации.
2.2 Схема алгоритма
Необходимо представить укрупненную блок-схему алгоритма
2.3 Текст программы
Program Di_mat;
Uses crt,graph;
const r=20;
var
gfx,gfy:array[1..20] of integer;
matrix: array[1..20,1..20] of integer;
fx:array[1..20] of boolean;
grline: array [1..20] of byte;
gdx,gdy,n,i,j:integer;
d: Real;
procedure init;
var graphdriver,graphmode,errorcode:integer;
begin
graphdriver:= detect;
initgraph(graphdriver,graphmode,'');
errorcode:=graphresult;
if errorcode <> grok then
begin
write('Error');
halt;
end;
end;
procedure DrawGraph(i:Integer);
var
s:string;
begin
circle(gfx[i],gfy[i],r);
settextstyle(1,0,1);
settextjustify(1,1);
str(i,s);
outtextxy(gfx[i],gfy[i]-r div 5,s);
end;
procedure DrawLink(i,j: Integer);
var
s:string;
begin
gdx:=gfx[j]-gfx[i];
gdy:=gfy[j]-gfy[i];
d:=sqrt(LongInt(gdx)*gdx+LongInt(gdy)*gdy);
gdx:=round(gdx*r/d);
gdy:=round(gdy*r/d);
Line(gfx[i]+gdx,gfy[i]+gdy,gfx[j]-gdx,gfy[j]-gdy);
end;
2.4 Протокол контрольного расчета
Возьмем 6 городов, а длины телефонных кабелей зададим матрицей длин дуг.
¥ | 23 | 12 | 67 | 36 | 25 |
23 | ¥ | 89 | 75 | 51 | 45 |
12 | 89 | ¥ | 3 | 93 | 89 |
67 | 75 | 3 | ¥ | 6 | 18 |
36 | 51 | 93 | 6 | ¥ | 41 |
25 | 45 | 89 | 18 | 42 | ¥ |
Рисунок 1- Расположение городов с помощью матрицы
В результате получается граф, показанный на рисунке 2.
Задание выдано ____________________
Руководитель Иванилова Т.Н.
Рисунок 2- Граф
Минимальное остовное дерево графа, полученное после расчетов, выглядит так:
Рисунок 3- Минимальное остовное дерево