Алгоритмы дискретной математики

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

Министерство образования и науки Российской Федерации

Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования

«Сибирская государственная автомобильно-дорожная академия

(СибАДИ)»

Факультет Информационные системы в управлении (ИСУ)

Специальность Автоматизированные системы обработки информации и управления (АСОИУ)

Кафедра Компьютерные информационные автоматизированные системы (КИАС)

Курсовая работа по дисциплине: «Математическая логика и теория алгоритмов»

Тема: «Алгоритмы дискретной математики»

Выполнил: студент гр.АС-10И2

Курганов И.Д.

Проверил: преподаватель

Палий И.А.

Омск 2012



1. Логические функции (Функции алгебры логики)

1. Логическая функция A двух переменных

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

2. Логическая функция B двух переменных.

Расставить скобки в формуле своего варианта в соответствии со старшинством логических операций, так чтобы сделать явной последовательность вычисления значений логической функции. Составить таблицу истинности. Применяя равносильные преобразования, построить КНФ и СКНФ этой функции.

3. Логическая функция C трех переменных.

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

4. Логическая функция D трех переменных.

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

5. Логическая функция E четырех переменных.

Построить минимальные ДНФ и КНФ функции E четырех переменных своего варианта, заданной вектором своих значений. Воспользоваться двумя алгоритмами: методом Квайна и картами Карно. Определить, к каким классам Поста принадлежит эта функция, дать подробные объяснения.

Логическая функция A двух переменных 1

Построим таблицу истинности заданной функции:

x	y
0	0	1	1	1	0	1
0	1	1	1	1	1	0
1	0	0	1	1	0	1
1	1	0	0	0	1	1

Применяя равносильные преобразования, попытаемся построить ДНФ и СДНФ этой функции:

1)

2)

ДНФ:

Построим СДНФ:

:

СДНФ:

Логическая функция B двух переменных

Построим таблицу истинности заданной функции:

x	y					f
0	0	1	1	1	1	1
0	1	0	1	1	1	1
1	0	1	1	1	1	1
1	1	0	0	0	1	1

КНФ и СКНФ для этой функции равны единице, так как эта функция является "константой 1".

КНФ = СКНФ =1

Логическая функция C трех переменных

Построим таблицу истинности заданной функции:

x	y	z
0	0	0	1	1	0	0
0	0	1	1	0	1	1
0	1	0	0	0	1	0
0	1	1	0	1	0	1
1	0	0	0	0	0	0
1	0	1	0	1	1	1
1	1	0	0	0	0	1
1	1	1	0	1	1	0

Применяя равносильные преобразования, попытаемся построить ДНФ и СДНФ этой функции:

ДНФ

1)

2)

3)

4)

СДНФ:

СКНФ:

СПНФ:

Логическая функция D трех переменных

Построим таблицу истинности заданной функции:

x	y	z
0	0	0	1	1	1	0	1	1	1
0	0	1	1	1	1	0	1	1	1
0	1	0	1	0	1	0	1	1	1
0	1	1	1	0	0	1	1	1	0
1	0	0	0	1	1	0	1	1	1
1	0	1	0	1	1	0	1	1	1
1	1	0	0	0	1	0	1	1	1
1	1	1	0	0	0	1	1	1	0

Проверим функцию на линейность

f	f1
0	1
1	1
0	1
1	1
1	1
1	1
0	1
0	1

Проверим функцию на монотонность

111>110

Проверим функцию на сохранение нуля

Проверим функцию на сохранение единицы

Проверим функцию на самодвойственность

f	f*
1	1
1	0
1	0
0	0
1	1
1	0
1	0
0	0

Построим таблицу поста для этой функции

Логическая функция E четырех переменных 0111010000101101

Восстановим таблицу истинности функции по её вектору значения:

X1	X2	X3	X4	F(x1,x2,x3,x4)
0	0	0	0	0
0	0	0	1	1
0	0	1	0	1
0	0	1	1	1
0	1	0	0	0
0	1	0	1	1
0	1	1	0	0
0	1	1	1	0
1	0	0	0	0
1	0	0	1	0
1	0	1	0	1
1	0	1	1	0
1	1	0	0	1
1	1	0	1	1
1	1	1	0	0
1	1	1	1	1

Выпишем СДНФ и СКНФ для этой функции

СДНФ:

СКНФ:

Составим карту Карно для ДНФ

	1
	1	1		1
			1	1
		1	1

Минимальная ДНФ:

Составим карту Карно для КНФ

		0	0	0
			0
	0	0
	0			0

Минимальная КНФ:

квантификация предикат флойд программирование

Минимизация по методу Квайна для ДНФ

Выпишем двоичные наборы на которых функция равна 1и рассортируем их в столбцы по количеству единиц:

	0011
0001	1010	1101	1111
0010	0101
	1100

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

_101	0_01	00_1	001_
_010		11_1	110_

Выполнить дополнительные склейки нельзя.

Получим 7 двоичных наборов:

_010, _101, 0_01, 00_1, 11_1, 001_,110_

	0001	0011	1010	1101	0010	0101	1100	1111
_010+			1+		1+
_101?				1?		1?
0_01^	1^					1^
00_1?	1?	1?
11_1+				1+				1+
001_^		1^			1^
110_				1+			1+

Ядро функции: {}

минимальные ДНФ

Минимизация по методу Квайна для КНФ

Выпишем двоичные наборы на которых функция равна 0 и рассортируем их в столбцы по количеству нулей:

0111	0110	0100	0000
1110	1001	1000
1011

После проведенных склеек получим:

_110	0_00	10_1	011_
_000		01_0	100_

Выполнить дополнительные склейки нельзя.

Получим 7 двоичных наборов:

_110, _000, 0_00, 10_1, 01_0, 011_,100_

	0000	0100	0110	0111	1000	1001	1011	1110
_110+			0+					0+
_000	0?				0?
0_00	0^	0^
10_1+						0+	0+
01_0		0?	0?
011_+				0+
100_			0^		0^

Ядро функции: {}

В результате получим минимальная КНФ

Определим принадлежность функции к основным классам поста:

Проверим функцию на линейность

X1	X2	X3	X4	f	f1
0	0	0	0	0	0
0	0	0	1	1	1
0	0	1	0	0	1
0	0	1	1	0	0
0	1	0	0	1	0
0	1	0	1	0	1
0	1	1	0	1	1
0	1	1	1	1	0
1	0	0	0	1	0
1	0	0	1	1	1
1	0	1	0	0	1
1	0	1	1	1	0
1	1	0	0	0	0
1	1	0	1	0	1
1	1	1	0	0	1
1	1	1	1	1	0

Проверим функцию на монотонность

1011>1010

Проверим функцию на сохранение нуля

Проверим функцию на сохранение единицы

Проверим функцию на самодвойственность

f	f1
0	0
1	1
1	0
1	0
0	1
1	0
0	1
0	1
0	1
0	1
1	0
0	1
1	0
1	0
0	0
1	1

Построим таблицу поста для этой функции

	+	+

2. Логические исчисления

1. Доказать или опровергнуть данные клаузы, используя анализ таблицы истинности; метод от противного и метод резолюций

¦ ;

¦ .

2. Ввести необходимые обозначения и записать каждое из высказываний как формулу исчисления предикатов. Обосновать справедливость (ложность) заключения при помощи диаграмм Эйлера-Венна.

Некоторые писатели - женщины. Все женщины любят цветы. Следовательно, среди тех, кто любит цветы, есть писатели.

3. Пусть предметная область , «x < y». Рассмотреть все варианты одновременной квантификации переменных двухместного предиката . Определить истинность получаемых выражений.

Решение

1.1 ¦ ;

Попытаемся доказать данную клаузу методом резолюций:

Логическое следствие верно.

Докажем данную клаузу методом от противного:

;

Положим : и =0 A=1, C=1, B=0, D=0

Не удалось обратить все посылки в единицу, логическое следствие верно

Докажем данную клаузу методом анализа таблицы истинности:

A	B	C	D
0	0	0	0	(1	1)	0	0	1<
0	0	0	1	1	0	0	1	0
0	0	1	0	1	0	1	0	0
0	0	1	1	(1	1)	1	1	1<
0	1	0	0	0	1	0	1	0
0	1	0	1	0	0	0	1	0
0	1	1	0	0	0	1	1	1
0	1	1	1	0	1	1	1	1
1	0	0	0	0	1	1	0	0
1	0	0	1	0	0	1	1	1
1	0	1	0	0	0	1	0	0
1	0	1	1	0	1	1	1	1
1	1	0	0	(1	1)	1	1	1<
1	1	0	1	1	0	1	1	1
1	1	1	0	1	0	1	1	1
1	1	1	1	(1	1)	1	1	1<

Логическое следствие истинно на всех интерпретациях, на которых одновременно истинны все гипотезы , Логическое следствие верно

1.2 ¦ .

Попытаемся доказать данную клаузу методом резолюций:

¦

¦¦

¦¦ ¦

¦

Логическое следствие неверно

Опровергнем данную клаузу методом от противного:

1.

2.

3.

Логическое следствие не верно

Опровергнем данную клаузу, используя анализ таблицы истинности

A	B	C
0	0	0	1	1	(1	1	1)	0	0	0<
0	0	1	1	1	(1	1	1)	0	0	0<
0	1	0	0	1	(1	1	1)	1	0	1<
0	1	1	1	1	(1	1	1)	1	0	1<
1	0	0	1	1	1	1	0	0	1	1
1	0	1	1	1	1	1	0	0	1	1
1	1	0	0	0	0	1	1	0	0	0
1	1	1	1	0	1	1	1	0	0	0

Логическое следствие истинно не на всех интерпретациях, на которых одновременно истинны все гипотезы ,, Логическое следствие не верно

2. Некоторые писатели - женщины. Все женщины любят цветы. Следовательно, среди тех, кто любит цветы, есть писатели.

Введем следующие обозначения:

U - Вселенная;

A(x) - х женщина;

B(x) - х писатель;

C(x) - х любит цветы;

Получим следующее логическое следствие:

,

Обоснуем справедливость (ложность) заключения при помощи диаграмм Эйлера-Венна:

A - Множество женщин;

B - Множество писателей;

С - Множество любителей цветов;

Таким образом:

Верное рассуждение.

3. Пусть предметная область , «x < y».

Рассмотрим все варианты одновременной квантификации переменных двухместного предиката . Определим истинность полученных результатов.

-"Существует два натуральных числа, таких что, х<y" - Тождественная Истина. Пример " у=х+1 х=любое число"

-"Любые два натуральных числа таковы, что одно из них меньше другого". Тождественная Ложь. Пример "х=1 у=1"

-"Существует такое натуральное х, которое меньше всякого натурального y". Тождественная Ложь. Пример "x=1 у=1"

-"Для всякого натурального у можно найти натуральное х, которое меньше него". Тождественная Ложь. Пример "х=1 у=1"

-" Для всякого натурального числа х найдется натуральное число, у которое больше него". Тождественная Истина. Пример "х=Любое число у=х+1, предметная область бесконечно велика"

-" Существует натуральное число y, больше любого натурального числа х". Тождественная Ложь. Пример " х=Любое число у=1"

3 Графы

Задание

Задание 1. Определить кратчайшие пути от вершины 1 до всех остальных вершин графа, используя алгоритм Дейкстры. Построить дерево кратчайших путей. Отрицательные длины в матрице заменить положительными (матрица 1).

Задание 2. Определить кратчайшие пути от вершины 1 до всех остальных вершин графа, пользуясь алгоритмом Беллмана. Построить дерево кратчайших путей (матрица 1).

Матрица 1

	1	2	3	4	5	6	7	8	9	10
1	?	?	?	?	2	5	3	?	?	?
2	7	?	5	?	10	5	?	?	-1	?
3	7	?	?	?	?	6	2	?	?	10
4	?	6	8	?	?	?	?	7	2	?
5	3	8	?	1	?	?	7	?	10	7
6	2	?	10	-2	6	?	?	3	?	?
7	?	?	9	7	?	?	?	?	?	?
8	?	3	?	7	?	?	2	?	?	9
9	?	?	7	?	6	?	-1	?	?	?
10	1	?	?	?	?	8	8	?	6	?

Задание 3. Определить кратчайшие пути между всеми парами вершин графа, используя алгоритм Флойда. Построить деревья кратчайших путей (матрица 2).



Матрица 2

	1	2	3	4	5
1	?	?	-3	?	8
2	?	?	9	7	?
3	?	9	?	3	8
4	-3	1	?	?	?
5	1	?	1	10	?

Задание 4. Отыскать гамильтонов контур наименьшей длины, пользуясь алгоритмом ветвей и границ (матрица 3).

Матрица 3

	1	2	3	4	5	6	7
1	?	13	6	12	9	10	5
2	14	?	10	11	10	5	9
3	13	7	?	7	15	8	14
4	8	6	10	?	4	12	3
5	8	7	9	14	?	3	7
6	5	3	15	1	10	?	12
7	5	3	15	8	9	15	?

Задание 5. В графе на рис. 1 найти центр, главный центр, абсолютный центр, медиану, главную медиану, абсолютную медиану.

Решение

Задание 1.

1. Положим и будем считать эту метку постоянной.

2.

3.

4.

5.

6.

7.

8.

9. Из вершины 10 можно попасть в вершины 1,6,7,9, но для них уже найдены постоянные кратчайшие пути, переходим к следующей метке.

10.

11.

	1	2	3	4	5	6	7	8	9	10
1											p=1
2					2+	5	3				p=5
3		10		3+	2+	5	3		12	9	p=4
4		9	11	3+	2+	5	3+	10	5	9	p=7
5		9	11	3+	2+	5	3+	10	5+	9	p=9
6		9	11	3+	2+	5+	3+	10	5+	9	p=6
7		9	11	3+	2+	5+	3+	8+	5+	9	p=8
8		9	11	3+	2+	5+	3+	8+	5+	9+	p=10
9		9+	11	3+	2+	5+	3+	8+	5+	9+	p=2
10		9+	11+	3+	2+	5+	3+	8+	5+	9+	p=3

Построим дерево кратчайших путей

Задание 2

	1	2	3	4	5	6	7	8	9	10
1	0	?	?		2	5
2	0	10	12	3	2	5		8	12	9
3	0	9			2	5
4	0			3	2	5

;;

;;

;;;

;;

;.

;

;;;.

Построим дерево кратчайших путей

Задание 3.

	1	2	3	4	5
1	0	7	?	2	?
2	?	0	7	9	6
3	5	12	0	7	-1
4	?	1	6	0	?
5	5	-2	?	7	0

_.

	1	2	3	4	5
1	0	7	14	2	13
2	?	0	7	9	6
3	5	12	0	7	-1
4	?	1	6	0	7
5	5	-2	5	7	0

_;

_;

_.

	1	2	3	4	5
1	0	7	14	2	12
2	12	0	7	9	6
3	5	12	0	7	-1
4	11	1	6	0	5
5	5	-2	5	7	0

_;

_;

_;

_;

_.

	1	2	3	4	5
1	0	7	8	2	7
2	12	0	7	9	6
3	5	8	0	7	-1
4	11	1	6	0	5
5	5	-2	5	7	0

_{; ; ; .}

	1	2	3	4	5
1	0	3	8	2	7
2	11	0	7	9	6
3	4	-3	0	6	-1
4	10	1	6	0	5
5	5	-2	5	7	0

_{; ;}

Построим деревья кратчайших путей

Задание 4.

Шаг 1

	1	2	3	4	5	6	7
1		13	6	12	9	10	5	5
2	14		10	11	10	5	9	5
3	13	7		7	15	8	14	7
4	8	6	10		4	12	3	3
5	8	7	9	14		3	7	3
6	5	3	15	1	10		12	1
7	5	3	15	8	9	15		3

Шаг 2

	1	2	3	4	5	6	7
1		8	1	7	4	5	0
2	9		5	6	5	0	4
3	6	0		0	8	1	7
4	5	3	7		1	9	0
5	5	4	6	11		0	4
6	4	2	14	0	9		11
7	2	0	12	5	6	12
	2		1		1

Нижняя граница: 5+5+7+3+3+1+3+2+1+1=31

Шаг 3

	1	2	3	4	5	6	7
1		8	04	7	3	5
2	7		4	6	4	04	4
3	4	00		00	7	1	7
4	3	3	6		03	9
5	3	4	5	11		03	4
6	2	2	13	02	8		11
7	02	00	11	5	5	12

Шаг 4

	1	2	4	5	6	7
2	7		6	4	04	4
3		00	00	7	1	7
4	3	3		04	9
5	3	4	11		03	4
6	2	2	02	8		11
7	02	00	5	5	12

Не до приводится

Шаг 5

	1	2	4	5	7
3		0	0	7	7
4	3	3		0
5	3	4	11		4	3
6	2		0	8	11
7	0	0	5	5

Доприводим 5 строку на 3

Шаг 6

	1	2	4	5	7
3		00	00	7	7
4	3	3		05
5	01	1	8		1
6	2		02	8	11
7	00	00	5	5

Шаг 7

	1	2	4	7
3			0
5	0	1		1
6	2		0	11
7			5
				1

Доприводим 7 столбец на единицу

Шаг 8

	1	2	4	7
3			00
5	00	1		06
6	2		02	10
7			5

Шаг 9

	1	2	4
3			00
6	2
7

Не доприводим

Шаг 10

	1	3
2
6

Гамильтонов контур: 4---5---7---1---3---2---6---4(4+7+5+6+7+5+1=35)

Задание 5.

Рассмотрим граф на рис. 1 с матрицей D (табл.1)

Найдем внешний центр.

j i	1	2	3	4	?
1	0	10	4	19	33
2	10	0	9	9	28
3	4	9	0	18	31
4	7	15	6	0	28
?	21	34	19	46

D =; ;

; ;

Внешний центр графа - это вершина 2.

Найдем внутренний центр для графа

; ;

; ;

;

Внутренний центр для графа - вершина 2. В табл. числа выделены курсивом.

Найдем внешнюю медиану для графа на рис.

; ;

; ;

=28, внешняя медиана - вершины 2 и 4. Число 9 выделено в табл. жирным шрифтом.

Найдем внутреннюю медиану для графа на рис. 1

; ;

; ;

=19, внутренняя медиана - вершина 3. Число 9 выделено в табл. жирным шрифтом.

	1	10	4	11,5	25	19	26	95,5
D1 =	2	10	11,5	9	15	9	16	70,5
	3	11,5	4	9	24	18	25	91,5
	4	16	8,5	15	6	24	7	76,5

Найдем Главный внешний центр графа таблицы.

В этом графе главный внешний центр - вершина 2. Число 16 выделено жирным курсивом.

Найдем Главную внешнюю медиану графа

min(95,5;70,5;91,5;76,5)=70,5.

Главная внешняя медиана - это вершина 2. Число 70,5 выделено в табл. жирным шрифтом.

D2 =	Вершина Ребро(дуга)	1	2	3	4
		10	10	11,5	19
		4	11,5	4	20,5
		11,5	9	9	18
		10	15	6	24
		16	24	15	9
		7	17	11	26
	?	58,5	86,5	56,5	116,5

Найдем главный внутренний центр графа таблица.

Min(16,24,15,26)=15

В графе один внутренний центр - вершина 3. Число 15 в табл. выделено также курсивом.

Найдем главную внутреннюю медиану графа таблица.

Min(58,5;86,5;56,5;116,5)=56,5; главная внутренняя медиана - это вершина 3. Число 56,5 выделено в табл. жирным шрифтом.

Найдем внешний абсолютный центр

Построим графики расстояний точка-вершина для всех точек ребра (1,2) до всех вершин графа.

Минимум максимальных расстояний точка-вершина для точек ребра (1,2) равен 9,5 и достигается при f =

Построим графики расстояний точка-вершина для всех точек ребра (1,3) до всех вершин графа.

Минимум максимальных расстояний точка-вершина для точек ребра (1,3) равен 18 и достигается при f = 1, то есть в вершине 3.

Построим графики расстояний точка-вершина для всех точек ребра (1,4) до всех вершин графа.

Минимум максимальных расстояний точка-вершина для точек ребра (2,3) равен 10 и достигается при f = 0, т. е. в вершине 2

Ребро
(1, 2)	9.5	19/20
(1,3)	10	0(вершина 3)
(2,3)	18	1(вершина 2)
Внешний центр		Вершина 2

Абсолютным внешним центром этого графа является 19/20-точка ребра

(1, 2); абсолютный минимум расстояний точка-вершина равен 9.5

Абсолютная внешняя медиана совпадет с внешней медианой, это вершины 2 и 4

Найдем абсолютный внутренний центр графа.

Рассмотрим ребро (1, 2).

Минимум максимальных расстояний точка-вершина для точек ребра (1,2) равен 8,5 и достигается при f =

Рассмотрим ребро (1, 3).

Минимум максимальных расстояний точка-вершина для точек ребра (1,3) равен 9 и достигается при f = 1, т.е. в вершине 3.

Рассмотрим ребро (2,3).

Минимум максимальных расстояний точка-вершина для точек ребра (2,3) равен 7,5 и достигается при f =

Ребро
(1, 2)	8,5	3/20
(1,3)	9	1(вершина 1)
(2,3)	7,5	15/18
Внутренний центр		Вершина (2)

Абсолютным внутренним центром этого графа является 15/18-точка ребра (2, 3); абсолютный минимум расстояний точка-вершина равен 7,5.

Абсолютная внутренняя медиана совпадет с внутренней медианой, это вершина 3

4. Программирование алгоритма дискретной математики

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

Общие положения. При выполнении задания необходимо

1. Подробно описать алгоритм.

2. Подробно описать программу, реализующую алгоритм: типы и структуры данных, блок-схему программы и т.п.

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

4. Привести результаты решения не мене трех тестовых примеров с различными исходными данными.

Решение

1. Описание алгоритма.

Алгоритм Флойда-Уоршелла -- динамический алгоритм для нахождения кратчайших расстояний между всеми вершинами взвешенного ориентированного графа. Разработан в 1962 году Робертом Флойдом и Стивеном Уоршеллом.

Алгоритм:

Пусть вершины графа пронумерованы от 1 до и введено обозначение для длины кратчайшего пути от i до j, который кроме самих вершин проходит только через вершины . Очевидно, что -- длина (вес) ребра (i, j) , если таковое существует (в противном случае его длина может быть обозначена как ).

Существует два варианта значения :

1. Кратчайший путь между i, j не проходит через вершину , тогда

2. Существует более короткий путь между i, j проходящий через , тогда он сначала идёт от до , а потом от до . В этом случае, очевидно,

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

Тогда рекуррентная формула для имеет вид:

-- длина ребра

Алгоритм Флойда-Уоршелла последовательно вычисляет все значения для от 1 до n. Полученные значения являются длинами кратчайших путей между вершинами i,j.

Для реализации алгоритма Флойда, граф будем задавать матрицей инцидентности C(NxN).

Кроме матрицы смежности, воспользуемся еще одной матрицей - WL (NxN), в ней мы будем хранить длины путей из вершины в вершину.

В цикле над матрицей WL (NxN) выполняется n итераций. После k-ой итерации, WL[i,j] содержит значение наименьшей длинны путей из вершины i в вершину j, которые не проходят через вершины с номером, большим k.
На k-ой итерации для вычисления матрицы WL, за основу взята следующая формула:

WL k[i,j] = min (WL k-1[i,j], WL k-1[i,k]+ WL k-1[k,j]).

Сложность алгоритма

Время выполнения программы, имеет порядок O(n3), так как в ней нет практически ничего, короче 3 вложенных друг в друга циклов.

Сохранение маршрутов.

Что бы сохранять маршруты, от одной вершины к другой, следует, ввести еще одну матрицу, в которой каждому элементу H[i,j] присваивать вершину K (номер), полученную при нахождении наименьшего значения WL [i,j].

2. Блок схема программы.

Основной блок программы

Процедура определения матрицы длин дуг

Процедура нахождения кратчайших путей и их длин

Процедура вывода найденных значений

3. Листинг программы

program alg_floyda;

{$APPTYPE CONSOLE}

uses

SysUtils,

Windows;

Const

M=19; //максимальное число вершин графа

Type

Dmas = Array[1..M,1..M] Of Integer;

Var

FLAG: char;

N, {Число вершин графа}

Nac, {Номер начальной вершины}

Kon: Integer; {Номер конечной вершины}

WL, {Матрица, хранящая длины путей}

H, {Матрица, хранящая пути}

C: Dmas; {Матрица, хранящая длины дуг}

{-------------------------------------------------------}

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

{-------------------------------------------------------}

{====Функция коррекции вывода====}

function Rus(P1:PAnsiChar):PAnsiChar;

begin

GetMem(Result,Length(P1)+1);

AnsiToOem(P1,Result);

end;

Procedure Dlina;

VAR

I,J:integer;

{====Процедура инициализации матрицы длин дуг====}

Begin

Write (Rus('Введите число вершин графа: '));

Readln(N); //инициализация числа вершин

If N>M Then Halt; //выход из программы, если вершин больше чем M

If N>5 Then //задание значений длин дуг автоматически

For I:=1 To N Do

For J:=1 To N Do

If I=J Then C[I,J]:=0

Else C[I,J]:=Random(100)+1 //инициализация случайным значением

Else

Begin //инициализация длин дуг вводом с клавиатуры

For I:=1 To N Do

Begin

Writeln;

For J:=1 To N Do

If I<>J Then

Begin

Write(Rus('Введите вес дуги ['),I,Rus(','),J,Rus(']:= '));

Readln(C[I,J]) //ввод с клавиатуры значения длины дуги

End

Else If I=J Then C[I,J]:=0;

End

End;

{Вывод полученной матрицы дуг}

Writeln(Rus('Матрица длин дуг'));

Writeln;

Write(' ');

For I:=1 To N Do

Write(' ',Chr(64+I),' ');

Writeln;

For I:=1 To N Do

Begin

Write(' ',Chr(64+I),' ');

For J:=1 To N Do

Write(C[I,J]:3,' '); //вывод текущего элемента матрицы

Writeln

End;

Readln

End;

{-----------------------------------------------------}

Procedure Floid;

{===Процедура нахождения кратчайших путей и их длин====}

Var

I,J,K: Integer;

Begin

For I:=1 To N Do

For J:=1 To N Do

Begin

WL[I,J]:=C[I,J]; //начальная установка длин путей

If C[I,J]=100 Then

H[I,J]:=0 //нет дуги из вершины "I" в "J" вершину

Else

H[I,J]:=J //есть дуга из вершины "I" в "J" вершину

End;

For I:=1 To N Do

Begin

For J:=1 To N Do

For K:=1 To N Do

If (I<>J) And (WL[J,I]<>100) And (I<>K) And (WL[I,K]<>100)

And ((WL[J,K]=100) Or (WL[J,K]>WL[J,I]+WL[I,K])) Then

Begin

H[J,K]:=I; //запоминаем новый путь

WL[J,K]:=WL[J,I]+WL[I,K] //запоминаем длину данного нового пути

End;

For J:=1 To N Do

If WL[J,J]<0 Then Break //нет решения: вершина входит в цикл отрицательной длины

End;

{Вывод полученной матрицы путей}

Writeln(Rus('Матрица путей'));

Writeln;

Write(' ');

For I:=1 To N Do

Write(' ',Chr(64+I),' ');

Writeln;

For I:=1 To N Do

Begin

Write(' ',Chr(64+I),' ');

For J:=1 To N Do

Write(H[I,J]:3,' '); //вывод текущего элемента матрицы

Writeln

End;

Readln;

{Вывод полученной матрицы длин путей}

Writeln(Rus('Матрица длин путей'));

Writeln;

Write(' ');

For I:=1 To N Do

Write(' ',Chr(64+I),' ');

Writeln;

For I:=1 To N Do

Begin

Write(' ',Chr(64+I),' ');

For J:=1 To N Do

Write(WL[I,J]:3,' '); //вывод текущего элемента матрицы

Writeln;

End;

Readln;

Write(Rus('Введите номер начальной вершины пути: ')); Readln(Nac);

Write(Rus('Введите номер конечной вершины пути: ')); Readln(Kon);

Writeln;

Write(Rus('Длина пути из вершины '),Chr(64+Nac),Rus(' в вершину '),Chr(64+Kon),Rus(' равна: '),WL[Nac,Kon]);

Readln

End;

{====Процедура вывода найденных значений====}

Procedure Koordinata;

Var

X: Integer;

Begin

{Вывод кратчайшего пути}

Writeln;

Write(Rus('Маршрут из вершины '),Chr(64+Nac), Rus(' в вершину '),Chr(64+Kon), Rus(' :'));

Writeln;

Writeln;

X:=Nac;

Write( Chr(64+X));

Repeat

X:=H[X,Kon]; //переход на следующую вершину в пути

Write('->');

Write(Chr(64+X));

Until X=Kon;

Readln;

End;

Begin

{====Основной блок программы====}

Dlina; //задание длин дуг

Floid; //поиск кратчайшего пути и его длины

Writeln;

Write(Rus('Вывести маршрут? (y/n)'));

Read(flag);

if (flag=('y') )then

Koordinata; //вывод найденных значений

Readln;

End.

4.Результаты работы программы

Тестовый набор данных №1

Тестовый набор данных №2

Тестовый набор данных №3

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