Структури алгоритмів
Міністерство освіти і науки України
Тернопільський національний технічний університет
імені Івана Пулюя
Кафедра комп’ютерних наук
ЛАБОРАТОРНА РОБОТА №2
з дисципліни “Теорія алгоритмів”
Тема роботи: Структури алгоритмів.
Виконав:
студент групи СНс-33
Михалевич М.М.
Перевірив:
викладач Фалендиш В.В.
Тернопіль – 2010
Лабораторна робота №2
Тема роботи: Структури алгоритмів.
Мета роботи: Вивчення основних елементів структури обчислювальних алгоритмів.
Теоретичні відомості
Часто в інженерній практиці виникає необхідність порівняння технічних об’єктів. У цих випадках опис технічного об’єкта необхідно звести до таких математичних об’єктів як числа, вектори, матриці або функції. У цьому випадку порівнюютбся вже не самі об`єкти, а іх математичні представлення.
У таких випадках характерисртикою об’єктів є поняття норми, а самі об’єкти розглядають у відповідних метричних просторах, наприклад . Нормою в називається дійснозначна функція (позначають -норма Х), яка задовільняє такі умови:
для будь-якого , причому тільки якщо ;
для кожного і ;
для кожного ;
Найбільш поширені слідуючі норми:
для дійсних чисел: модуль числа ;
для комплексних чисел:
модуль комплексного числа
для векторів :
- норма (норма Чебишева) ;
- норма (Евклідова норма) ;
- норма ;
для матриць:
норма Фробеніуса ;
l1- норма ,
де - j-ий стовбець матриці X
для функцій:
, де T – интервал задання функції X(t).
Порівняння норм здійснюється так само як порівняння дійсних чисел.
|
В деяких випадках виникає необхідність
|
|
|
391
|
299
|
|
Знаходження спільної міри кількох об`єктів. У
|
|
|
299
|
1
|
|
цьому випадку поріввнюються значення
|
|
299
|
92
|
|
|
норми, а для знаходження найбільшого
|
|
276
|
3
|
|
|
спільного дільника (НСД) використовується
|
92
|
23
|
|
|
|
алгоритм Евкліда. Приклад знаходження НСД
|
92
|
4
|
|
|
|
за алгоритмом Евкліда представлено на рис.1. У цьому прикладі шукають НСД чисел
|
0
|
|
|
|
|
391 і 299. Значення НСД буде рівне останньому дільнику, після ділення на який остача рівна 0, тобто НСД рівне 23.
|
Рис.1
|
Для знаходження НСД трьох і більше чисел спочатку знаходять НСД будь-яких двох чисел а потім – знайденого НСД і одного з чисел що залишилися.
Завдання до лабораторної роботи.
- Згідно заданого варіанту завдань написати програму на мові ПАСКАЛЬ або С++ і реалізувати її на ЕОМ.
- Представити результати роботи програми.
- Оформити звіт по виконаній роботі.
|
7
|
Знайти спільну міру відстані між точками А1(345,921), А2(7209,2923) i B1(-987,352), B2(2685,1423).
|
Текст програми
unit Unit1;
interface
uses
Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
Dialogs, StdCtrls, ExtCtrls;
type
TForm1 = class(TForm)
Memo1: TMemo;
Button1: TButton;
Button4: TButton;
Edit1: TEdit;
Label1: TLabel;
procedure Button1Click(Sender: TObject);
procedure Button4Click(Sender: TObject);
private
{ Private declarations }
public
{ Public declarations }
end;
var
Form1: TForm1;
i,k:real;
x,y:integer;
kil:integer;
L:array [1..2,1..4] of real;
d:array [1..2,1..4] of real;
implementation
{$R *.dfm}
procedure TForm1.Button1Click(Sender: TObject);
begin
form1.Memo1.Visible:=true;
form1.Button4.Enabled:=true;
form1.Memo1.Lines.text:=' I:';
begin
L[1,1]:=345;
L[1,2]:=921;
L[1,3]:=7209;
L[1,4]:=2923;
d[2,1]:=-987;
d[2,2]:=352;
d[2,3]:=2685;
d[2,4]:=1423;
k:=sqrt((L[1,1]*L[1,1])+(L[1,2]*L[1,2])+(L[1,3]*L[1,3])+(L[1,4]*L[1,4]));
i:=sqrt((d[2,1]*d[2,1])+(d[2,2]*d[2,2])+(d[2,3]*d[2,3])+(d[2,4]*d[2,4]));
y:=round(k);
x:=round(i);
form1.Memo1.Lines.Add('1: ' +floattostr(L[1,1]));
form1.Memo1.Lines.Add('2: ' +floattostr(L[1,2]));
form1.Memo1.Lines.Add('3: ' +floattostr(L[1,3]));
form1.Memo1.Lines.Add('4: ' +floattostr(L[1,4]));
form1.Memo1.Lines.Add(' ');
form1.Memo1.Lines.Add(' : ' +floattostr(y));
form1.Memo1.Lines.Add(' ');
form1.Memo1.Lines.Add(' ');
form1.Memo1.Lines.add(' II:');
form1.Memo1.Lines.Add('1: ' +floattostr(d[2,1]));
form1.Memo1.Lines.Add('2: ' +floattostr(d[2,2]));
form1.Memo1.Lines.Add('3: ' +floattostr(d[2,3]));
form1.Memo1.Lines.Add('4: ' +floattostr(d[2,4]));
form1.Memo1.Lines.Add(' ');
form1.Memo1.Lines.Add(' : ' +floattostr(x));
end;
end;
procedure TForm1.Button4Click(Sender: TObject);
begin
while (x<>0) and (y<>0) do
begin
if (x>=y) then
x:= x mod y
else
begin
y:=y mod x;
end;
kil:=y+x;
end;
form1.Edit1.Text:=floattostr(kil);
end;
end.
Результати роботи
Висновок: на цій лабораторній роботі я вивчив основні елементи структури обчислювальних алгоритмів.
Кінець
Вивід
ні
так
kil:=y+x
ні
так
y:=y mod x
x:= x mod y
if (x>=y)
while (x<>0) and (y<>0) do
k:=sqrt((L[1,1]*L[1,1])+(L[1,2]*L[1,2])+(L[1,3]*L[1,3])+(L[1,4]*L[1,4]));
i:=sqrt((d[2,1]*d[2,1])+(d[2,2]*d[2,2])+(d[2,3]*d[2,3])+(d[2,4]*d[2,4]));
Генерація масиву
масиву
Початок
Структури алгоритмів