Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Оцінка складності алгоритмів
Інформація про навчальний заклад
ВУЗ:
Тернопільський національний економічний університет
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Не вказано
Інформація про роботу
Рік:
2010
Тип роботи:
Лабораторна робота
Предмет:
Теорiя алгоритмiв i математичнi основи представленння знань
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
ТЕРНОПІЛЬСЬКИЙ НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ
імені Івана Пулюя
Кафедра комп’ютерних наук
ЛАБОРАТОРНА РОБОТА №6
з предмету
Теорія алгоритмів та математичні основи представлення знань
Тема: Оцінка складності алгоритмів
Тернопіль-2010
Мета роботи: Вивчення теоретичних та практичних методів оцінки cкладності алгоритмів.
Завдання до роботи
Порівняльна таблиця виконання програми лабораторних робіт №3, №4, №5
Кількість відліків = 10
№
Лабораторної
Кількість відліків
Кількість додавань
Кількість множень
Час виконання
3
20
60
120
3 мс
50
150
300
7 мс
100
300
600
26 мс
4
20
40
80
4 мс
50
100
200
5 мс
100
200
400
21 мс
5
20
210
231
6 мс
50
510
561
11 мс
100
1010
1111
33 мс
Код програми Лабораторна №3
unit Unit1;
interface
uses
Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
Dialogs, StdCtrls, ComCtrls, ExtCtrls, TeeProcs, TeEngine, Chart, Series;
type
TForm1 = class(TForm)
Button1: TButton;
Chart1: TChart;
Series1: TFastLineSeries;
Button2: TButton;
Label1: TLabel; Label2: TLabel; Label3: TLabel;
Label4: TLabel; Label5: TLabel; Label6: TLabel;
Label7: TLabel;
procedure Button1Click(Sender: TObject);
function Mnogenia(m1:real; m2:extended): extended;
function Dodavania(d1:extended; d2:extended): extended;
procedure Button2Click(Sender: TObject);
private
{ Private declarations }
public
{ Public declarations }
end;
const
n=20;
var
Form1: TForm1;
k_dod, k_mnog:integer;
i:integer;
x1,x2,x3,x4,x5:extended;
inx: array[1..n] of real;
outx: array[1..n] of extended;
implementation
{$R *.dfm}
procedure TForm1.Button1Click(Sender: TObject);
begin
x1:=0; x2:=0; x3:=0; x4:=0; x5:=0;
k_dod:=0; k_mnog:=0;
inx[1]:=1;
for i:=2 to n do
inx[i]:=0;
for i := 1 to n do
begin
outx[i]:=x5;
x5:= x4;
x4:=Dodavania(Mnogenia(12.3,x2),Dodavania(Mnogenia(4,x3),-x5));
x3:=x2;
x2:= Dodavania(Mnogenia(-2,x3),Dodavania(Mnogenia(11,x5),x1));
x1:=inx[i];
end;
Form1.Label1.Caption:='x1='+ floattostr(x1);
Form1.Label2.Caption:='x2='+ floattostr(x2);
Form1.Label3.Caption:='x3='+ floattostr(x3);
Form1.Label4.Caption:='x4='+ floattostr(x4);
Form1.Label5.Caption:='x5='+ floattostr(x5);
Form1.Label6.Caption:='Функція додавання викликалася '+ inttostr(k_dod);
Form1.Label7.Caption:='Функція множення викликалася '+ inttostr(k_mnog);
series1.Clear;
for i:=1 to n do
begin
Series1.Add(outx[I]) ;
end;
end;
procedure TForm1.Button2Click(Sender: TObject);
begin
close;
end;
function TForm1.Dodavania(d1:extended; d2:extended): extended;
begin
k_dod:= k_dod+1;
Dodavania:=d1+d2;
end;
function TForm1.Mnogenia(m1:real; m2:extended):extended;
begin
k_mnog:= k_mnog+1;
Mnogenia:=m1*m2;
end;end.
Код програми Лабораторна №4
unit Unit1;
interface
uses
Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
Dialogs, StdCtrls, ComCtrls, ExtCtrls, TeeProcs, TeEngine, Chart, Series;
type
TForm1 = class(TForm) Button1: TButton; Chart1: TChart; Series1: TFastLineSeries;
Button2: TButton; Label6: TLabel; Label7: TLabel;
procedure Button1Click(Sender: TObject);
function Mnogenia(m1:real; m2:extended): extended;
function Dodavania(d1:extended; d2:extended): extended;
procedure Button2Click(Sender: TObject);
private
{ Private declarations }
public
{ Public declarations }
end;
const
n=20;
var
Form1: TForm1;
k_dod, k_mnog:integer;
i:integer;
x1,x2,x3,x4,x5:extended;
inx: array[1..n] of real;
outx: array[1..n] of extended;
implementation
{$R *.dfm}
procedure TForm1.Button1Click(Sender: TObject);
begin
inx[1]:=1;
for i:=2 to n do
begin
inx[i]:=0;
end;
for i:=1 to n do
begin
outx[i]:= Dodavania(Dodavania(Mnogenia(12.3,inx[i]),+Mnogenia(4,inx[i-1])),Mnogenia(132,outx[i-1]))-Mnogenia(46,outx[i-2]);
end;
Form1.Label6.Caption:='Функція додавання викликалася '+ inttostr(k_dod);
Form1.Label7.Caption:='Функція множення викликалася '+ inttostr(k_mnog);
series1.Clear;
for i:=1 to n do
begin
Series1.Add(outx[I]) ;
end;
end;
procedure TForm1.Button2Click(Sender: TObject);
begin
close;
end;
function TForm1.Dodavania(d1:extended; d2:extended): extended;
begin
k_dod:= k_dod+1;
Dodavania:=d1+d2;
end;
function TForm1.Mnogenia(m1:real; m2:extended):extended;
begin
k_mnog:= k_mnog+1;
Mnogenia:=m1*m2;
end;end.
Код програми Лабораторна №5
unit Unit1;
interface
uses
Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
Dialogs, StdCtrls, ComCtrls, ExtCtrls, TeeProcs, TeEngine, Chart, Series;
type
TForm1 = class(TForm) Button1: TButton; Chart1: TChart;
Series1: TFastLineSeries; Button2: TButton; Label6: TLabel; Label7: TLabel;
procedure Button1Click(Sender: TObject);
function Mnog(m1:real; m2:extended): extended;
function Dod(d1:extended; d2:extended): extended;
procedure Button2Click(Sender: TObject);
private
{ Private declarations }
public
{ Public declarations }
end;
const
n=20;
var
Form1: TForm1;
k_dod, k_mnog:integer;
i,s, d:integer;
x2,x3,x5:real;
x1:array[1..n] of real;
a:array[0..n] of real;
y:array[1..n] of real;
x:array[1..n] of real;
implementation
{$R *.dfm}
procedure TForm1.Button1Click(Sender: TObject);
begin
x1[1]:=1; for i:=2 to n do
begin
x1[i]:=0;
end;
x1[1]:=1; for i := 1 to n do
begin
x5:=a[i-1]*a[i]; a[i]:=x1[i-1]*12.3*x2+4*x3-x5; x3:=x2; x2:=-2*x3+11*x5+x1[i];
end;
x[i]:=1; for i:=0 to n do
begin
y[i]:=Dod(Dod(Dod(Dod(Dod(Dod(Dod(Dod(Dod(Dod(Mnog(a[0],x[i]),Mnog(a[1],x[i+1])),Mnog(a[2],x[i+2])),Mnog(a[3],x[i+3])),Mnog(a[4],x[i+4])),Mnog(a[5],x[i+5])),Mnog(a[6],x[i+6])),Mnog(a[7],x[i+7])),Mnog(a[8],x[i+8])),Mnog(a[9],x[i+9])),Mnog(a[10],x[i+10]));
end;
Form1.Label6.Caption:='Функція додавання викликалася '+ inttostr(k_dod);
Form1.Label7.Caption:='Функція множення викликалася '+ inttostr(k_mnog);
series1.Clear;
for i:=1 to n do
begin
Series1.Add(y[I]) ; end;end;procedure TForm1.Button2Click(Sender: TObject);
begin
close;
end;
function TForm1.Dod(d1:extended; d2:extended): extended;
begin
k_dod:= k_dod+1; Dod:=d1+d2;
end;
function TForm1.Mnog(m1:real; m2:extended):extended;
begin
k_mnog:= k_mnog+1; Mnog:=m1*m2;
end;end.
Результат роботи Лабораторної роботи №3
Результат роботи Лабораторної роботи №4
Результат роботи Лабораторної роботи №5
Висновок: Під час виконання лабораторної роботи я порівнював програми трьох лабораторних робіт і зробив висновок: найшвидше працює програми 4-ї лабораторної роботи, яка реалізована в канонічній формі. Найменше викликів функції додавання в четвертій лабораторні роботі. Найменше викликів функції множення також в четвертій лабораторні роботі. Найдовше працює програма реалізована за допомогою не рекурсивного алгоритму у ній найбільша кількість виклику функцій додавання і множення.
07.02.2013 19:02-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора