Алгоритм поиска источника орграфа
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
Министерство образования и науки
Республики Казахстан
Усть-Каменогорский колледж экономики и финансов
Специальность Программное обеспечение вычислительной техники и автоматизированных систем
ПОЯСНИТЕЛЬНАЯ ЗАПИСКА
к курсовому проекту
по предмету: Основы алгоритмизации и программирования
Студент Ахмедова П.О
Группа ТП-31
Руководитель Хомова Т.М
Усть-Каменогорск
Задание на курсовое проектирование
Источником орграфа называют вершину, от которой достижимы все другие вершины. Разработать алгоритм и написать программу, позволяющую найти все источники орграфа.
.11.10
График выполнения курсового проекта
№ ЭтапаСодержание этапаСроки выполненияПланФакт1Раздача тем. Обзор рекомендуемой литературы11.11.1011.11.102Готовность 25% Подбор литературы. Разработка укрупненного алгоритма. Определение структур данных26.11.1026.11.103Готовность 50 % Написание программы с заглушками6.12.104Готовность 75% Детализация заглушек. Завершение разработки программы20.12.105Готовность 100% Подготовка отчета и доклада к защите3.01.113.01.116Защита курсового проекта10.01.1110.01.11
Содержание
Введение
1.Основные элементы языка программирования
1.1Обзор элементов языка программирования
2.Описание решение задач проекта
2.1Общая постановка задачи
2.2Описание программного комплекса
.3Макро блок-схема
.4Таблица идентификаторов комплекса
2.4.1 Таблица глобального контекста
.4.2 Таблица локального контекста
.5Описание наборов данных
2.6Постановка проблемных подпрограмм
3.Организация производства
3.1Комплекс технических средств необходимых для решения задачи
3.2Инструкция пользователю по работе программой
4.ЗАКЛЮЧЕНИЕ
5.Приложение А(текст программы)
.Приложение В(окна результатов)
.Список используемых источников
ВВЕДЕНИЕ
Данная работа позволяет найти все источники орграфа. Решение этой проблемы имеет практическую ценность, если несколько городов соединены дорогами, то очевидно, что попасть из одного города в другой, проходя по каждой из дорог не более одного раза, можно по различным маршрутам. Задача состоит в том, что надо найти все возможные маршруты.
Карта дорог между городами может быть изображена в виде графа - набора вершин, обозначающих дороги.
Процесс поиска может быть представлен как последовательность шагов. На каждом шаге с использованием некоторого критерия выбирается точка, в которую можно попасть из текущей. Если очередная выбранная точка совпала с заданной конечной точкой. То маршрут найден. Если не совпала, то делаем еще шаг. Так как текущая точка может быть соединена с несколькими другими, то сначала будем выбирать точку с наименьшим номером.
Алгоритм поиска имеет рекурсивный характер: чтобы сделать шаг, мы выбираем точку и опять делаем шаг, до тех пор пока не достигнем цели.
Для выполнения данной работы необходимо разработать приложение, которое будет находить все источники орграфа. Для создания данного приложения нужно изучить:
. Тему дискретной математики - Графы:
Узнать: что такое орграф;
Как его можно представить в программе;
Что называется источником орграфа.
1. Основные элементы языка программирования
.1 Обзор элементов языка программирования
Алгоритм поиска имеет рекурсивный характер: чтобы сделать шаг, мы выбираем точку и опять делаем шаг, до тех пор пака не достигаем цели.
Рекурсия
Способ организации вычислительного процесса, при котором подпрограмма в ходе выполнения составляющих ее операторов обращается сама к себе. Рекурсивный вызов может быть косвенным, в этом случае подпрограмма обращается к себе опосредованно, то есть путем вызова другой подпрограммы, в которой содержится обращение к первой.
Преимущество: достаточно сложные алгоритмы могут быть представлены в простой логической форме.
Недостатки:
рекурсивная форма организация алгоритма работает медленно.
может вызвать переполнения стека памяти, так как при каждом входе в подпрограмму ее переменные размещаются в специальной области памяти программном стеке.
Для представления орграфа используется двумерный массив
Массив
Это фиксированный набор однотипных данных объеденных единым именем. Каждый элемент имеет свой уникальный номер для массивов в целом задано количество элементов.
12345101110200100300000400100500000Для сохранения вершин пути и для определения источника орграфа используются множества
Множества.
Множество - это набор взаимосвязанных объектов, которые можно рассматривать как единое целое. Каждый такой объект, называемый элементом множества, должен принадлежать одному из простых типов, кроме вещественного типа.
2. Описание решение задач проекта
.1 Общая постановка задачи
Ориентированный граф (кратко орграф) - (мульти) граф, ребрам которого присвоено направление.
Направленные ребра именуются дугами.
Источник - вершина, от которой достижимы все остальные вершины.
Матрица смежности - это квадратная матрица, строки и столбцы которой соответствуют вершинам графа. Элемент матрицы (i,j) равен 1, если вершина i связана с вершиной j ребром, иначе элемент матрицы равен 0.
2.2 Описание программ комплекса
in