Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Алгоритм, властивості, параметри та характеристики складності алгоритму
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
ІКТА
Факультет:
КН
Кафедра:
Кафедра ЕПМС
Інформація про роботу
Рік:
2014
Тип роботи:
Лабораторна робота
Предмет:
Алгоритми та методи обчислень
Варіант:
7
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти і науки України
Національний університет «Львівська політехніка»
Кафедра ЕОМ
/
ЗВІТ
З лабораторної роботи №1
з дисципліни:
«Алгоритми та методи обчислень»
на тему:
«Алгоритм, властивості, параметри та характеристики складності алгоритму»
Мета роботи: засвоїти основні поняття та визначення теорії алгоритмів, проаналізувати вплив параметрів алгоритму на характеристики складності алгоритму
Теоретична частина
Опис алгоритму
Маючи два натуральні числа a та b:
якщо b=0, то a є шуканим НСД,
інакше повторюємо обчислення для пари b та залишку від ділення a на b (тобто a mod b).
Версія ітераційна:
НСД( a, b)
поки b ≠ 0
c := остача від ділення a на b
a := b
b := c
поверни a
Версія рекурсивна:
НСД( a, b)
якщо b = 0
поверни a
інакше
поверни НСД( b, остача від ділення a на b)
Для того, щоб довести ефективність алгоритму, потрібно порівняти його з таким, який
приймається за неефективний. Прикладом такого неефективного алгоритму є процедура послідовного перебору можливих розв’язань задачі. Будемо вважати, що алгоритм перебору утворений в результаті структурного синтезу, на основі вхідних даних та намагання знайти серед всіх допустимих чисел такє, що є найбільшим дільником двох заданих чисел.
Ефективність, як правило, визначається такою характеристикою як часова складність, що вимірюється кількістю операцій, необхідних для розв’язання задачі.
Дослідимо розв’язання задачі знаходження найбільшого спільного дільника двох цілих чисел (N1>0,N2 >0, N1≥N2 ) алгоритмом перебору і алгоритмом Евкліда.[10] Алгоритм перебору заснований на операції інкременту змінної (n) від одиниці до меншого (N2) з двох заданих чисел і перевірці, чи ця змінна є дільником заданих чисел. Якщо це так, то значення змінної запам’ятовується і операції алгоритму продовжуються. Якщо ні, то операції алгоритму продовжуються без запам’ятовування. Операції алгоритму закінчуються видачею з пам’яті знайденого останнім спільного дільника. Блок-схема алгоритму приведена на рис.2(а).
a) б)
Рис2. Блок-схема алгоритму перебору (а) і Евкліда (б).
Послідовність виконання роботи
Користуючись програмою Lab_NSD.exe знайшли два числа з діапазону [1, 150], для яких часова складність алгоритму Евкліда найбільша, L=7, це числа 129 і 49.
Текст програми:
#include <iostream>
using namespace std;
int NSD1(int N1,int N2,int L2)
{
if(N2==0){
cout<<"L2="<<L2<<endl;
return N1;}
else
{L2++;
return NSD1(N2, N1%N2,L2);}
cout<<"L2="<<L2<<endl;
}
int main()
{
int N1,a,b,N2,k,i,NSD,r,n,L1=0,L2=0,L3=0,f,s;
char r1='l';
cout<<"Diapazon:";
cin>>a;cout<<endl;cin>>b;cout<<endl;
while(1){
char r1='l';
N1=a+rand()%(b-a);
N2=a+rand()%(b-a);
cout<<"First number: "<<N1<<endl<<"Second number: "<<N2<<endl;
k=min(N1,N2);
i=1;
NSD=i;
do{
i++;
if (((N1%i)==0) & ((N2%i)==0))
NSD=i;L1=L1+1;
} while(i<=k);
cout<<"NSD za I metodom:"<<NSD<<endl<<"L1="<<L1<<endl;
cout<<"NSD za II metodom:"<<NSD1(N1,N2,L2)<<endl;
n=max(N1,N2);
NSD=k;
while(1){
r=n%k;
if(r==0) {cout<<"NSD za III metodom:"<<NSD<<endl<<"L3="<<L3<<endl;break;}
else
{NSD=r;L3++;}
n=k;
k=r;}
f=max(L1,L2);
s=max(f,L3);
cout<<"MAX:"<<s<<endl;
cin>>r1;
if(r1=='k') break;}
}
Результи виконання програми:
/
Висновок. Я засвоїла основні поняття та визначення теорії алгоритмів, проаналізувала вплив параметрів алгоритму на характеристики складності алгоритму
27.05.2014 22:05-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора