Контрольная работа по метрологии, стандартизации, сертификации

Отчет по контрольной работе




По дисциплине: Структуры и алгоритмы обработки данных








Оглавление

Задание №1 3
Задание №2 8
Задание №3 11



Задание№1



Задание:
1. Написать программу, генерирующую граф:
Таблица 1. Количество вершин и ребер
|Количество вершин |13|
|Количество ребер |15 |Формат нумерации вершин должен выглядеть как – А1 … А13.
Топология сети задается произвольно.
Вес ребер задается произвольно в заданных вариантом промежутках.

Таблица 2. Вес ребер
|Вес ребер привершине |


А1 |А2 |А3 |А4 |А5 |А6 |А7 |А8 |А9 |А10 |А11 |А12 |А13 | |3 |10 |7|4 |6 |3 |1 |6 |2 |6 |4 |2 |7 | |
2. Реализовать функцию поиска кратчайшего пути к вершине по алгоритму Дейкстры.
3. Искомая вершина должна задаваться через пользовательскийинтерфейс.
4. Оценить сложность алгоритма программы.
5. Представить граф, как в графической форме, так и в виде матриц.


На рис.1 представлен произвольно построенный граф с определеннымколичеством ребер (15) и вершин (13).


[pic]




Рис.1. Граф в графической форме.
В таблице 3 представлена матрица смежности для данного графа.


Таблица 3. Матрицасмежности
|1 |2 |3 |4 |5 |6 |7 |8 |9 |10 |11 |12 |13 | |1 |0 |3 |- |- |- |- |- |- |2 |- |- |- |- | |2 |3 |0 |10 |- |- |- |- |- |- |5 |- |- |- | |3 |- |10 |0 |7 |- |- |- |- |- |- |- |- |- | |4 |- |- |7 |0 |4 |-|- |- |- |- |- |- |- | |5 |- |- |- |4 |0 |6 |- |- |- |- |- |- |7 | |6 |- |- |- |- |6 |0 |3 |- |- |- |- |- |- | |7 |- |- |- |- |- |3 |0 |1 |- |- |- |9 |- | |8 |- |- |- |- |-...