Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Параметри алгоритму. Правило безпосереднього переробленя
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Електронні обчислювальні машини
Інформація про роботу
Рік:
2004
Тип роботи:
Лабораторна робота
Предмет:
Алгоритми та методи обчислень
Група:
КI
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти і науки України
Національний університет „Львівська політехніка”
Кафедра ЕОМ
Звіт
з лабораторної роботи №3
на тему: ”Параметри алгоритму. Правило безпосереднього переробленя”.
з предмету „Алгоритми та методи обчислень”.
Підготував: ст. гр. КІ-3
Львів 2004
Тема: Параметри алгоритму. Правило безпосереднього перероблення.
Мета: Аналіз впливу параметру „Правила безпосередньогоперероблення” на складність алгоритму.
Теоретичні відомості:
Завдання:
Знайти найбільший спільний дільник (НСД) двох чисел методом Евкліда.
I. Теоритична частина.
Основні поняття та визначення
Параметри алгоритму.
Характеристики алгоритму.
II. Практична частина
Знайти найбільший спільний дільник (НСД) двох чисел методом Евкліда.
Скласти блок-схеми алгоритму.
Порівняти часову складність алгоритмів повного перебору (лабораторна робота № 2) і Евкліда.
Порівняти програмну складність алгоритмів повного перебору (лабораторна робота № 2) і Евкліда.
III. Лабораторна робота
Скласти програму (Pascal , C) знаходження найбільшого спільного дільника (НСД) двох чисел за методом
Евкліда. Вхідні дані : 400 пар випадкових чисел в діапазоні від 100*X до 200+X., де Х – Ваш порядковий номер в списку підгрупи.
Відобразити за допомогою графіка часову складність алгоритму для кожноі пари чисел.
Визначити часову складність алгоритму в “найгіршому випадку” для чисел заданого діпазону
Відобразити на графіку функцію Y= log2N, де N- менше число з кожної пари вхідних даних.
Варіант №23
Початок
Ввід даних
i= 400 пар випадкових чисел
i!=0
Random a, b
a < b
c=a
а=b
b=c
c = a % b
c=0
Вивід НДС=b
а=b
b=c
Кінець
i--
Програмна реалізація даного методу:
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <conio.h>
#define random(num)(int)(((long)rand()*(num))/(RAND_MAX+1))
void main()
{int f,i,n,*a,*b,c,d,NSD,l=0;
int min=2023,max=2300;
clrscr();
printf("\n\tEnter the kilkist par chysel: ");
scanf("%d",&n);
l++;
getchar();
a=(int*)malloc(n*sizeof(int));
b=(int*)malloc(n*sizeof(int));
l++;
for(i=1;i<=n;i++)
{
l++;
srand(max);
l++;
a[i]=min+((long)rand()*b[i-1])%(max-min);
l++;
b[i]=min+((long)rand()*a[i-1])%(max-min);
l++;
if (a[i]>b[i])
{
c=a[i];
l++;
d=b[i];
}
else
{
d=a[i];
c=b[i];
l++;
}
while(c%d!=0)
{
l++;
f=d;
d=c%d;
c=f;
}
l++;
printf("\n\ta=%d ",a[i]);
printf(" b=%d ",b[i]);
printf(" NSD=%d",d);
l++;
printf(" l=%d",l);
}
getchar();
}
Висновок: порівнюючи часову і програмну складність алгоритму методу перебору та алгоритму Евкліда ми чітко бачимо, що алгоритм Евкліда і по програмній і по часовій складності швидший за алгоритми перебору.
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора