Алгоритм поиска источника орграфа

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Министерство образования и науки

Республики Казахстан

Усть-Каменогорский колледж экономики и финансов

Специальность «Программное обеспечение вычислительной техники и автоматизированных систем»

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

к курсовому проекту

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

Студент Ахмедова П.О

Группа ТП-31

Руководитель Хомова Т.М

Усть-Каменогорск

2010

Задание на курсовое проектирование

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

11.11.10

График выполнения курсового проекта

№ Этапа	Содержание этапа	Сроки выполнения
		План	Факт
1	Раздача тем. Обзор рекомендуемой литературы	11.11.10	11.11.10
2	Готовность 25% Подбор литературы. Разработка укрупненного алгоритма. Определение структур данных	26.11.10	26.11.10
3	Готовность 50 % Написание программы с заглушками	6.12.10
4	Готовность 75% Детализация заглушек. Завершение разработки программы	20.12.10
5	Готовность 100% Подготовка отчета и доклада к защите	3.01.11	3.01.11
6	Защита курсового проекта	10.01.11	10.01.11

Содержание

Введение

1. Основные элементы языка программирования

1.1 Обзор элементов языка программирования

2. Описание решение задач проекта

2.1 Общая постановка задачи

2.2 Описание программного комплекса

2.3 Макро блок-схема

2.4 Таблица идентификаторов комплекса

2.4.1 Таблица глобального контекста

2.4.2 Таблица локального контекста

2.5 Описание наборов данных

2.6 Постановка проблемных подпрограмм

3. Организация производства

3.1 Комплекс технических средств необходимых для решения задачи

3.2 Инструкция пользователю по работе программой

4. ЗАКЛЮЧЕНИЕ

5. Приложение А(текст программы)

6. Приложение В(окна результатов)

7. Список используемых источников

ВВЕДЕНИЕ

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

Карта дорог между городами может быть изображена в виде графа - набора вершин, обозначающих дороги.

Процесс поиска может быть представлен как последовательность шагов. На каждом шаге с использованием некоторого критерия выбирается точка, в которую можно попасть из текущей. Если очередная выбранная точка совпала с заданной конечной точкой. То маршрут найден. Если не совпала, то делаем еще шаг. Так как текущая точка может быть соединена с несколькими другими, то сначала будем выбирать точку с наименьшим номером.

Алгоритм поиска имеет рекурсивный характер: чтобы сделать шаг, мы выбираем точку и опять делаем шаг, до тех пор пока не достигнем цели.

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

1. Тему дискретной математики - “Графы”:

- Узнать: что такое орграф;

- Как его можно представить в программе;

- Что называется источником орграфа.

1. Основные элементы языка программирования

1.1 Обзор элементов языка программирования

Алгоритм поиска имеет рекурсивный характер: чтобы сделать шаг, мы выбираем точку и опять делаем шаг, до тех пор пака не достигаем цели.

Рекурсия

Способ организации вычислительного процесса, при котором подпрограмма в ходе выполнения составляющих ее операторов обращается сама к себе. Рекурсивный вызов может быть косвенным, в этом случае подпрограмма обращается к себе опосредованно, то есть путем вызова другой подпрограммы, в которой содержится обращение к первой.

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

Недостатки:

- рекурсивная форма организация алгоритма работает медленно.

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

Для представления орграфа используется двумерный массив

Массив

Это фиксированный набор однотипных данных объеденных единым именем. Каждый элемент имеет свой уникальный номер для массивов в целом задано количество элементов.

	1	2	3	4	5
1	0	1	1	1	0
2	0	0	1	0	0
3	0	0	0	0	0
4	0	0	1	0	0
5	0	0	0	0	0

Для сохранения вершин пути и для определения источника орграфа используются множества

Множества.

Множество - это набор взаимосвязанных объектов, которые можно рассматривать как единое целое. Каждый такой объект, называемый элементом множества, должен принадлежать одному из простых типов, кроме вещественного типа.

2. Описание решение задач проекта

2.1 Общая постановка задачи

Ориентированный граф (кратко орграф) - (мульти) граф, ребрам которого присвоено направление.

Направленные ребра именуются дугами.

Источник - вершина, от которой достижимы все остальные вершины.

Матрица смежности - это квадратная матрица, строки и столбцы которой соответствуют вершинам графа. Элемент матрицы (i,j) равен 1, если вершина i связана с вершиной j ребром, иначе элемент матрицы равен 0.

2.2 Описание программ комплекса

Procedure init - данная процедура создает матрицу смежности и заполняет её нулями.

Procedure init2 - данная процедура обнуляет массивы road (маршрут- номера точек карты) и incl (если точка с номером i включена в карту).

Procedure print - данная процедура выводит на экран матрицу смежности.

Procedure Vvod - данная процедура заполняет массив единицами там, где заданно ребро орграфа.

Procedure step - данная процедура ищет в графе все возможные пути

Procedure findictok - данная процедура ищет источник орграфа который задан пользователем.

2.3 Макро блок схема

Укрупненная схема приложения представлена на рис.1



Рис.1

2.4 Таблица идентификаторов комплекса

2.4.1 Таблица глобального контекста

Таблица 1

Имя	Тип	Размер	Назначение в программе
n	Integer	-32768..32767	Содержит количество ребер
q	mn	0..255	Множество. Содержит номера вершин орграфа
z	mn	0..255	Множество. Содержит пройденный путь
f	Integer	-32768..32767	Конечная точка маршрута
p	Integer	-32768..32767	Номер искомой точки маршрута
s	Integer	-32768..32767	Точка, из которой делается шаг
m	myarray	-32768..32767	Массив, содержит матрицу смежности
road	integer	-32768..32767	Массив, содержит номера точек карты
incl	boolean	True, false	Incl[i]:=true, если точка с номером I включена в road
е	mn	0..255	Множество. Содержит номер источника орграфа
n	integer	-32768..32767	Кол-во вершин орграфа

2.4.2 Таблица локального контекста

Таблица 2

Имя	Тип	Размер	Назначение в программе
i	Integer	-32768..32767	Вспомогательная переменная для цикла
j	Integer	-32768..32767	Вспомогательная переменная для цикла
st	string	0..255	Вспомогательная переменная
St2	string	0..255	Переменная для преобразования целого числа в строку
c	byte	0..255	Вспомогательная переменная цикла

2.5 Описание наборов данных

m=array[1..n,1..n] of integer в этой матрице содержатся 1 и 0 то есть матрица соединение между вершинами (матрица смежности).

road:array[1..n] of integer в этой матрице содержится карта(вершины).

incl:array[1..n] of boolean; проверяется точка I, включена ли она в карту.

2.6 Постановка проблемной под программы процедуры

procedure step - данная процедура находит все возможные пути.

Блок схема процедуры step представлена на рис.2

Рис.2

Procedure init - данная процедура создает матрицу смежности и заполняет её нулями.

Блок схема процедуры init представлена на рис.3

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Рис.3

procedure init2 - данная процедура обнуляет массив road и incl.

Блок схема процедуры init2 представлена на рис.4

Рис.4

procedure print - данная процедура выводит на экран матрицу смежности.

Блок схема процедуры init2 представлена на рис.5

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Рис.5

procedure Vvod - данная процедура записывает введенный пользователем граф в файл.

Блок схема процедуры init2 представлена на рис.6

Рис.6

procedure findictok - данная процедура ищет источник орграфа который задан пользователем.

Блок схема процедуры init2 представлена на рис.7

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Рис.7

программа орграф таблица язык

3. Организация производства

3.1 Комплекс технических средств необходимых для решения задачи

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

Pentium I 200 Mhz

32 Mb Оперативной памяти

Интегрированная видео карата.

Windows 95, 98, XP, Vista, 7.

Клавиатура

Мышь

3.2 Инструкция пользователю по работе программой

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

см. приложение В рис.8

1 Создание новой матрицы

- заполняет матрицу смежности 0

2 вывод матрицы на экран

- вывод графа в виде матрицы смежности

3 создание ребер

-если заданные точки соединены между собой тогда нужно ввести 1, если нет то 0

4 нахождение всех путей

-вывод на экран всех возможных путей в орграфе

5 нахождение источников

-вывод на экран номер точки, от которой достижимы все вершины.

ЗАКЛЮЧЕНИЕ

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

Во время разработки данного приложения мною самостоятельно была изучена тема «графы».

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

Приложение A

uses wincrt;

type myarray=array [1..20,1..20] of integer;

mn=set of byte;

var

q,z,e:mn;

m:myarray;

v,j,i,f,s,p,c,n:integer;

road:array[1..20] of integer;

incl:array[1..20] of boolean;

start,finish:integer;

procedure init(var m:myarray); {процедура инициализации матрицы смежности}

begin

writeln('введите кол-во вершин орграфа');

readln(n);

for i:=1 to n do

for j:=1 to n do

m[i,j]:=0;

end;

procedure init2(var m:myarray); {процедура обнуления массивов}

begin

for i:=1 to n do

road[i]:=0;

incl[i]:=false;

end;

procedure print(m:myarray);{процедура печати матрицы смежности}

begin

for i:=1 to n do

begin

writeln;

for j:=1 to n do

write (m[i,j]:2);

end;

writeln;

end;

procedure vvod(var m:myarray);{процедура создание ребер}

begin

writeln('Введите элементы матрицы смежности орграфа:');

readln;

for i:=1 to n do

for j:=1 to n do

begin

if (i<>j) then

begin

write('m[',i,',',j,'] =>');

read(m[i,j]);

readln;

end;

end;

end;

procedure step(s,f,p:byte);{s-точка, из которой делается шаг

f-конечная точка маршрута

p-номер искомой точки маршрута}

var

c:byte; {номер точки, в которую делается очередной шаг}

begin

if s=f then {точки s и f совпали}

begin

write('Путь: ');

for i:=1 to p-1 do write(road[i],' ');

writeln;

end

else begin {выбираем очередную точку}

for c:=1 to n do begin {проверяем все вершины}

if (m[s,c]<>0) and (not incl[c]) then

{точка соединена с текущей и не включена в маршрут}

begin

road[p]:=c; {добавим вершину в путь}

incl[c]:=true; {пометим вершину как включеную}

z:=z+[c];

step(c,f,p+1);

incl[c]:=false;

road[p]:=0;

end;

end;

end;

end;

procedure step2;

var

st,st2:string;

begin

for i:=1 to n do

for j:=1 to n do

begin

if m[i,j]<>0 then q:=q+[i,j];

e:=q-z;

if i in e then

begin

str(I,st2);{заносим в переменную st2 значение переменной i}

st:='источником является вершина под номером `+st2;

end;

end;

writeln(st);

end;

begin

while v<>6 do

begin

writeln(' выберите номер из пункта меню. ');

writeln(' 1.создание новой матрицы ');

writeln(' 2.вывод матрицы на экран ');

writeln(' 3.создание ребр ');

writeln(' 4.нахождение всех путей');

writeln(' 5.нахождение источников');

read(v);

case v of

1:init(m);

2:print(m);

3:vvod(m);

4:begin

for start:=1 to n do

for finish:=1 to n do

begin

if start<>finish then

begin

init2(m);

road[1]:=start;

incl[i]:=true;

step(start,finish,2);

end;

end;

end;

5:step2;

end;

end;

Приложение В

Рис.8



Рис.9



Рис.10

Рис.11



Рис.12

Рис.13



Рис.14

Рис.15

Список используемых источников

1. Культин «Турбо Паскаль 7.0»

2. Новиков «Дискретная математика для программистов»

3. Киракозов А.. «Поиск гамильтонова цикла».

4. Берж К. «Теория графов и ее применения»

5. Немлюгин С.А. Turbo Pascal: практикум. - СПб.: Питер, 2002.

6. Программирование на языке Паскаль: задачник / под ред. Усковой О.Ф. - СПб.: Питер, 2003.

Размещено на Allbest.ru