пз_грибович / МСИС_1
.pdfМинистерство образования Республики Беларусь
Министерство образования Республики Беларусь БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИНФОРМАТИКИ И РАДИОЭЛЕКТРОНИКИ
Кафедра метрологии и стандартизации
Метрология, стандартизация и сертификация в информационных технологиях
Практическая работа №1
«Метрики сложности потока управления программ» Вариант 16
Выполнила: |
Студентка группы |
|
972303 |
|
Рушева Маргарита |
|
Владиславовна |
Проверил: |
Грибович Александр |
|
Александрович |
Минск, 2020
1 ИНДИВИДУАЛЬНОЕ ЗАДАНИЕ
Ввести массив А (8, 8). Найти минимальный элемент в побочной диагонали массива А. Поменять местами столбец, в котором находится данный элемент, с первым столбцом массива А. Вывести максимальный элемент, номера строки и столбца, в которых он находится, исходный и результирующий массивы.
2 СХЕМА АЛГОРИТМОВ
Рисунок 1 – Схема работы алгоритма
Рисунок 1(продолжение) – Схема работы алгоритма
3 ОПИСАНИЕ СХЕМЫ АЛГОРИТМОВ
1.Начало программы.
2.Объявление и инициализация константы SIZE = 8.
3.Объявление массива mas[SIZE][SIZE].
4.Вывод строки «Введите массив».
5.Объявление и инициализация переменной i = 0.
6.Внешний цикл: если i < SIZE, то переходим к блоку 7, если нет, то переходим к блоку 12.
7.Объявление и инициализация переменной j = 0.
8.Внутренний цикл: если j < SIZE, то переходим к блоку 9, если нет, то переходим к блоку 11.
9.Ввод элемента mas[i][j].
10.Инкрементация переменной j, переход к блоку 8.
11.Инкрементация переменной i, переход к блоку 6.
12.Объявление и инициализация переменной min = mas[0][SIZE-1].
13.Объявление переменной minJ.
14.Объявление и инициализация переменной i = 0.
15.Объявление и инициализация переменной j = SIZE-1.
16.Цикл: если i < SIZE, то переходим к блоку 17, если нет, то переходим
кблоку 22.
17.Условие: если mas[i][j] <= min, то переходим к блоку 18, если нет, то переходим к блоку 20.
18.Присваивание переменной min значения mas[i][j].
19.Присваивание переменной minJ значения j,
20.Инкрементация переменной i.
21.Декрементация переменной j, переход к блоку 16.
22.Объявление массива new_mas[SIZE][SIZE].
23.Объявление и инициализация переменной i = 0.
24.Внешний цикл: если i < SIZE, то переходим к блоку 25, если нет, то переходим к блоку 33.
25.Объявление и инициализация переменной j = 0.
26.Внутренний цикл: если j < SIZE, то переходим к блоку 27, если нет, то переходим к блоку 29.
27.Присваивание элементу new_mas[i][j] значение элемента mas[i][j].
28.Инкрементация переменной j, переход к блоку 26.
29.Объявление и инициализация переменной change = new_mas[i][0].
30.Присваивание элементу new_mas[i][0] значение элемента new_mas[i][minJ].
31.Присваивание элементу new_mas[i][minJ] значение переменной
change.
32.Инкрементация переменной i, переход к блоку 24.
33.Вывод строки «Исходный массив».
34.Объявление и инициализация переменной i = 0.
35.Внешний цикл: если i < SIZE, то переходим к блоку 36, если нет, то переходим к блоку 43.
36.Объявление и инициализация переменной j = 0.
37.Внутренний цикл: если j < SIZE, то переходим к блоку 38, если нет, то переходим к блоку 41.
38.Вывод элемента mas[i][j].
39.Вывод пробела.
40.Инкрементация переменной j, переход к блоку 37.
41.Переход на новую строку.
42.Инкрементация переменной i, переход к блоку 35.
43.Объявление и инициализация переменной max = new_mas[0][0].
44.Вывод строки «Новый массив».
45.Объявление и инициализация переменной i = 0.
46.Внешний цикл: если i < SIZE, то переходим к блоку 47, если нет, то переходим к блоку 58.
47.Объявление и инициализация переменной j = 0.
48.Внутренний цикл: если j < SIZE, то переходим к блоку 49, если нет, то переходим к блоку 56.
49.Вывод элемента new_mas[i][j].
50.Вывод пробела.
51.Условие: если mas[i][j] > max, то переходим к блоку 52, если нет, то переходим к блоку 48.
52.Присваивание переменной max значение элемента new_mas[i][j].
53.Присваивание переменной maxI значение переменной i.
54.Присваивание переменной maxJ значение переменной j.
55.Инкрементация переменной j, переход к блоку 48.
56.Переход на новую строку.
57.Инкрементация переменной i, переход к блоку 46.
58.Вывод строки «Максимальный элемент : ».
59.Вывод переменной max.
60.Вывод строки «Номер строки : ».
61.Вывод переменной maxI + 1.
62.Вывод строки «Номер столбца : ».
63.Вывод переменной maxJ + 1.
64.Конец программы.
4 РАСЧЁТ МЕТРИКИ МАККЕЙБА И ОПРЕДЕЛЕНИЕ БАЗИСНЫХ НЕЗАВИСИМЫХ ПУТЕЙ
Метрика Маккейба определяется по формуле:
Z(G) = e – ʋ + 2p, где е — число дуг ориентированного графа G; ʋ — число вершин; р — число компонентов связности графа.
Для данного алгоритма: е = 73, ʋ=64, р=1.
Тогда цикломатическое число Маккейба Z(G) = 73-64+2*1= 11, следовательно число базовых независимых путей – 11.
1-й путь: 1-2-3-4-5-6(нет)-12-13-14-15-16(нет)-22-23-24(нет)-33-34- 35(нет)-43-44-45-46(да)-47-48(да)-49-50-51(нет)-55-48(нет)-56-57-46(нет)-58-59- 60-61-62-63-64.
2-й путь: 1-2-3-4-5-6(нет)-12-13-14-15-16(нет)-22-23-24(нет)-33-34- 35(нет)-43-44-45-46(нет)-58-59-60-61-62-63-64.
3-й путь: 1-2-3-4-5-6(да)-7-8(да)-9-10-8(нет)-11-6(нет)-12-13-14-15- 16(нет)-22-23-24(нет)-33-34-35(нет)-43-44-45-46(нет)-58-59-60-61-62-63-64.
5 РАСЧЁТ МЕТРИКИ ДЖИЛБА
CL=11,
cl=CL/кол-во всех операторов=11/51=0,216
1. Максимальный уровень вложенности условного оператора CLI = 2
6 РАСЧЁТ МЕТРИКИ ГРАНИЧНЫХ ЗНАЧЕНИЙ
Граф: G=(E,V)
Абсолютная граничная сложность программы Sa:
Sa=119
Относительная граничная сложность программы So:
So = 1 - −1 =l – 0,529=0,471
7 РЕЗУЛЬТАТЫ РАСЧЕТОВ МЕТРИК
Свойства |
|
|
|
|
|
|
|
|
Номер вершины выбора |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||||
подграфов |
|
|
|
|
|
6 |
|
|
|
|
8 |
|
|
16 |
|
17 |
24 |
|
|
26 |
|
35 |
|
|
37 |
|
|
46 |
48 |
|
51 |
|||||||||||||||||||
программы |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
Номера |
|
|
вершин |
7, |
|
|
|
|
9, |
|
17, |
18, |
25, |
|
27, |
|
36, |
|
|
38, |
|
47, |
49, |
|
52, |
|||||||||||||||||||||||||
перехода |
|
|
|
|
|
|
|
|
12 |
|
|
|
11 |
|
22 |
|
20 |
33 |
|
|
29 |
|
43 |
|
|
41 |
|
|
58 |
56 |
|
55 |
||||||||||||||||||
Скорректированная |
6 |
|
|
|
|
3 |
|
|
6 |
|
|
4 |
|
9 |
|
|
3 |
|
8 |
|
|
4 |
|
|
|
12 |
8 |
|
4 |
|||||||||||||||||||||
сложность |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
вершины выбора |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||
Номера |
|
|
вершин |
7- |
|
|
|
|
9- |
|
17- |
18- |
25- |
|
27- |
|
36- |
|
38- |
|
47- |
49- |
|
52- |
||||||||||||||||||||||||||
подграфа |
|
|
|
|
|
|
|
|
12 |
|
|
|
11 |
|
22 |
|
21 |
33 |
|
|
29 |
|
43 |
|
|
41 |
|
|
58 |
56 |
|
55 |
||||||||||||||||||
Номер |
|
|
нижней |
12 |
|
|
|
11 |
|
22 |
|
20 |
33 |
|
|
29 |
|
43 |
|
|
41 |
|
|
58 |
56 |
|
55 |
|||||||||||||||||||||||
границы подграфа |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||
|
|
|
Скорректированные сложности вершин графа программы (рис. 1) |
|||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
Номер вершины |
|
1 |
|
2 |
|
|
|
3 |
|
4 |
|
|
5 |
|
6 |
7 |
|
8 |
|
9 |
|
10 |
|
11 |
|
12 |
13 |
14 |
|
15 |
||||||||||||||||||||
графа программы |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||
Скорректированная |
1 |
|
1 |
|
|
|
1 |
|
1 |
|
|
1 |
|
6 |
1 |
|
3 |
|
1 |
|
1 |
|
1 |
|
1 |
|
|
1 |
1 |
|
1 |
|||||||||||||||||||
сложность |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
вершины графа |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
16 |
17 |
|
18 |
19 |
|
20 |
|
21 |
|
22 |
|
|
23 |
|
24 |
|
|
25 |
|
26 |
|
27 |
|
|
|
28 |
29 |
|
|
30 |
||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
6 |
4 |
|
1 |
1 |
|
1 |
|
|
1 |
|
|
|
1 |
|
|
|
|
1 |
|
|
9 |
|
|
1 |
|
|
3 |
|
1 |
|
|
|
1 |
|
1 |
|
|
1 |
||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||
31 |
|
32 |
|
|
33 |
|
34 |
|
|
35 |
|
|
|
36 |
|
37 |
|
38 |
39 |
|
|
40 |
|
41 |
|
|
42 |
|
|
43 |
44 |
|
45 |
|||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||
1 |
|
1 |
|
|
1 |
|
1 |
|
|
8 |
|
|
|
|
1 |
|
|
4 |
|
|
1 |
|
1 |
|
|
1 |
|
1 |
|
|
1 |
|
|
|
1 |
1 |
|
1 |
||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||
46 |
|
47 |
|
|
48 |
|
49 |
|
50 |
|
|
|
51 |
|
|
52 |
53 |
54 |
|
55 |
|
56 |
|
|
57 |
|
|
58 |
59 |
|
60 |
|||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||
12 |
|
|
1 |
|
|
|
8 |
|
|
1 |
|
|
1 |
|
|
|
|
4 |
|
|
1 |
|
|
1 |
|
1 |
|
|
1 |
|
|
1 |
|
|
|
1 |
|
|
|
1 |
1 |
|
1 |
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
61 62 63 64
1 |
1 |
1 |
0 |
Sa = 119
Итоговая таблица:
Метрики сложности потока |
Схемы алгоритмов |
управление |
Вариант 16 |
Метрика Маккейба Z(G) |
11 |
Абсолютная сложность программы |
11 |
CL по метрике Джилба |
|
Относительная сложность |
0,216 |
программы cl по метрике Джилба |
|
Максимальный уровень |
2 |
вложенности условного оператора |
|
CLI по метрике Джилба |
|
Метрика граничных значений |
119 |
(абсолютная граничная сложность |
|
программы) Sa |
|
Метрика граничных значений |
|
(относительная граничная |
0,471 |
сложность программы) Sо |
|