ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ РФ
УФИМСКИЙ ГОСУДАРСТВЕННЫЙ АВИАЦИОННЫЙ УНИВЕРСИТЕТ
Кафедра: ВМиК
Лабораторная работа №3
Метрики сложности программ
Выполнил:
студент группы ПО - 335т
Проверил:
преподаватель
Уфа 2012
Содержание
1. Задание на лабораторную работу 3
2. Описание алгоритма поискового дерева 4
3. Листинг программы 6
4. Метрики сложности программ 7
4.1. Метрики размера программ 7
4.2. Метрики сложности потока управления программ 8
4.2.1. Цикломатическое число Маккейба 8
4.2.2. Метрика Майерса 10
4.2.3. Метрика Джилба 11
4.3. Метрики сложности потока данныхМетрика Чепина 12
5. Вывод 12
1. Задание на лабораторную работу
Выбрать для оценки готовую программу, для которой имеются исходные тексты, и определить её сложность согласно метрикам размера программ, сложности потока управления программ, сложности потока данных.
2. Описание алгоритма поискового дерева
В качестве примера была рассмотрена программа построения поискового дерева. Поисковым деревом называется дерево, для каждой вершины 
которого справедливо утверждение: все ключи левого поддерева вершины меньше или равны ключа , а все ключи правого поддерева больше
Алгоритм построения поискового дерева с прямым методом обхода:
1) Генерируем с помощью датчика случайные трёхзначные числа.
2) Записываем эти числа в элемент StringGrid1.
3) Берем число из первой ячейки StringGrid1 и определяем его как корень дерева.
4) Берем следующее число и сравниваем его со значением корня:
- если оно < или = значению корня, то записываем его в левую ветвь;
- если оно > значения корня, то записываем его в правую ветвь.
5)Каждое следующее число из последовательности сначала сравнивается с корнем, а затем с узлами либо левой, либо правой ветви.
6) Отображаем полученное дерево в компоненте Image1.
3. Листинг программы
unit Trees;
interface
uses
Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
Dialogs, Grids, StdCtrls, ExtCtrls, ComCtrls, XPMan;
type
tree=^node; // создаем указатель
node=record // создаем запись
data:Integer; // название вершины поддерева
left:tree; // левое поддерево
right:tree; // правое поддерево
end;
TForm1 = class(TForm)
StringGrid1: TStringGrid;
Button1: TButton;
Button2: TButton;
Edit1: TEdit;
GroupBox1: TGroupBox;
Image1: TImage;
Label1: TLabel;
XPManifest1: TXPManifest;
procedure Button1Click(Sender: TObject);
procedure Button2Click(Sender: TObject);
procedure Draw_Tree(t:tree; xn, yn, sdvig:integer);
procedure Destroy_Tree(var t:tree);
private
{ Private declarations }
public
{ Public declarations }
end;
var
Form1: TForm1;
a:array[1..100]of Integer; // массив, хранящий сгенерированные элементы-вершины
My_Tree:tree; // дерево
nom:integer; // количество элементов в строящемся дереве
n:integer; // количество элементов в дереве
implementation
{$R *.dfm}
procedure TForm1.Button1Click(Sender: TObject); // кнопка генерации элементов
var i, j,x:integer;
label label_a; //метка перехода
begin
nom:=1; // количество уровней
n:=strtoint(Edit1.Text); // записывам количество вершин будущего дерева
StringGrid1.Width:=n*(StringGrid1.DefaultColWidth+1)+3; // задаем ширину StringGrid1 для вывода сгенерированной последовательности чисел-вершин
StringGrid1.ColCount:=n; // задаем размер элементов в StringGrid1
if My_Tree <>nil then Destroy_Tree(my_tree); // если дерево уже не пустое, то вызываем функцию его очистки
Randomize;
i:=1;
while i<=n do // цикл по n
begin
label_a: //метка перехода
x:=100+random(900); // генерируются трехзначные числа (random(90)- числа от 0 до 89)
for j:=1 to i do // цикл, проверяющий совпадения
if x=a[j] then goto label_a; // если совпало, возвращаемся по метке и генерируем новое число
a[i]:=x; // если не совпало, записываем число
StringGrid1.Cells[i-1,0]:=inttostr(a[i]); //выводим число
inc(i) // увеличиваем счетчик цикла
end;
Button2.Visible:=True; // отобразим кнопку
StringGrid1.Visible:=True; // отобразим таблицу
GroupBox1.Visible:=True; // отобразим элемент
end;
procedure Build_Tree(var t:tree; nom1: integer); // генерация дерева
begin
if t=nil then
begin // если число вершин дерева больше числа необходимых для генерации вершин, то выходим из процедуры
New(t); // выделяем память под поддерево
t^.data:=a[nom1]; // создаем вершину дерева и записываем туда число из сгенерированнной последовательности
t^.left:=nil; // указатель на левое поддерево
t^.right:=nil; // указатель на правое поддерево
end
else // увеличиваем счетчик вершин
if a[nom1]<t^.data then Build_Tree(t^.left, nom1) // если ещё остались незаполненные вершины слева, то рекурсивно вызываем процедуру
else Build_Tree(t^.right, nom1); // если ещё остались незаполненные вершины справа, то рекурсивно вызываем процедуру
end;
procedure TForm1.Draw_Tree(t:tree; xn, yn, sdvig:integer);
// процедура прорисовки дерева Xn и Yn - определяют точку начала рисования главной вершины, sdvig - определяет интервалы между вершинами
begin
Image1.Canvas. ellipse(xn-5,yn-8,xn+25,yn+22); // прорисовываем окружность
Image1.Canvas. TextOut(xn, yn, IntToStr(t^.data)); // выводим номер вершины внутрь окружности
if t^.left<>nil then // если указатель на левую ветвь не пуст, то рисуем её
begin
Image1.Canvas. MoveTo(xn+2,yn+20); // перемещаем "перо" на нижний левый край окружности
Image1.Canvas. lineto(xn-sdvig+5,yn+47); // рисуем прямую от нижнего левого края верхней окружности до верхнего края будущей нижней окружности
Draw_Tree(t^.left, xn-sdvig, yn+50,Round(sdvig/2)); // рекурсивно вызываем процедуру прорисовки
end;
if t^.right<>nil then // если указатель на правую ветвь не пуст, то рисуем её
begin
Image1.Canvas. MoveTo(xn+18,yn+20); // перемещаем "перо" на правый нижний край окружности
Image1.Canvas. lineto(xn+sdvig+15,yn+47); // рисуем прямую от нижнего левого края верхней окружности до верхнего края будущей нижней окружности
Draw_Tree(t^.right, xn+sdvig, yn+50,Round(sdvig/2)); // рекурсивно вызываем процедуру прорисовки
end;
end;
procedure TForm1.Destroy_Tree(var t:tree); // очищение дерева
begin
t:=nil; // зануляем указатель на дерево
nom:=1; // количество вершин дерева делаем равным 1
Image1.Canvas. Brush. Color := clBtnFace; // устанавливаем цвет - белым
Image1.Canvas. FillRect(Canvas. ClipRect); // заполняем поле Canvas белым цветом
end;
procedure TForm1.Button2Click(Sender: TObject); // кнопка построения дерева
var i:integer;
begin
for i:=1 to n do
Build_Tree(My_tree, i); // функция построения дерева
Draw_Tree(My_tree,420,50,210); // функция прорисовки дерева
end;
end.
4. Метрики сложности программ
4.1. Метрики размера программ
Для подсчета характеристик размера программ используется метрика Холстеда
По итогам подсчетов имеем:
- число уникальных операторов, появляющихся в данной реализации;
- число уникальных операндов, появляющихся в данной реализации;
- словарь
- общее число операторов, появляющихся в данной реализации;
- общее число операндов, появляющихся в данной реализации;
- длина реализации.
- объем программы
бит
4.2. Метрики сложности потока управления программ
4.2.1. Цикломатическое число Маккейба
Программа представляется в виде управляющего ориентированного графа G=(V, E), где V-вершины, соответствующие операторам, а E-дуги, соответствующие переходам.
Для вычисления цикломатического числа Маккейба применяется формула:
Z(G)=e-v+2p,
где e – число дуг ориентированного графа G;
v – число вершин;
p – число компонентов связности графа.
Параметры данной программы:
е = 25;
v = 18;
p = 3;
Z(G) = e – v + 2p = 25 – 18 + 2 = 9
Ориентированный граф G программы построения поискового дерева имеет вид:
 |
Нет Да 
 |
 |
Нет
 |  |
Нет Да
Да
Нет Нет Да
 |
 |
Нет Да
4.2.2. Метрика Майерса
Суть подхода Майерса состоит в представлении метрики сложности программ в виде интервала [Z(G),Z(G)+h].Для простого предиката h=0, а для n-местных предикатов h=n-1.
Параметры данной программы:
Для 1-го оператора:
h = 1-1 = 0 -> [9, 9]
Для 2-го оператора:
h = 10 – 1 = 9 -> [9, 9 + 9] = [9, 18]
Для 3-го оператора:
h = 2 – 1 = 1 -> [9, 18 + 1] = [9, 19]
Для 4-го оператора:
h = 1 – 1 = 0 -> [9, 19]
Для 5-го оператора:
h = 10 – 1 = 9 -> [9, 19 + 9] = [9, 28]
Для 6-го оператора:
h = 2 – 1 = 1 -> [9, 28 + 1] = [9, 29]
Для 7-го оператора:
h = 6 – 1 = 5 -> [9, 29 + 5] = [9, 34]
Для 8-го оператора:
h = 6 – 1 = 5 -> [9, 34 + 5] = [9, 39]
Для 9-го оператора:
h = 2 – 1 = 1 -> [9, 39 + 1] = [9, 40]
4.2.3. Метрика Джилба
Согласно этой метрике логическая сложность программы определяется как насыщенность программы выражениями типа IF-THEN-ELSE. При этом вводятся две характеристики:
CL - абсолютная сложность программы, характеризующаяся количеством операторов условия;
cl - относительная сложность программы (определяется как отношение CL к общему числу операторов).
Параметры данной программы:
CL = 7
4.3. Метрики сложности потока данных
4.3.1. Метрика Чепина
Суть метода состоит в оценке информативной прочности отдельно взятого модуля с помощью анализа характера использования переменных из списка ввода-вывода
Все множество переменных, составляющих список ввода-вывода, разбивается на четыре функциональные группы:
1.Р – вводимые переменные для расчетов и для обеспечения вывода.
2.М – модифицируемые или создаваемые внутри программы переменные.
3.С – переменные, участвующие в управлении работой программного модуля.
4.Т – неиспользуемые в программе переменные.
Далее вводится значение метрики Чепина: Q=a1 Р + a2 М + a3С + a4Т,
где а1=1.а2=2, а3=3, а4=0.5 – весовые коэффициенты.
Параметры данной программы:
P = 15;
M = 12;
C = 10;
T = 0;
Вывод: в данной лабораторной работе проводились расчеты по таким метрикам сложности программ, как метрики размера программ, метрики сложности управления программ, метрики сложности потока данных. В метриках сложности управления программ был построен ориентированный граф, описывающий функционирование программы создания поискового дерева.
