Міністерство освіти і науки України Національний університет „Львівська політехніка” Кафедра ЕОМ Звіт з лабораторної роботи №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(); } Висновок: порівнюючи часову і програмну складність алгоритму методу перебору та алгоритму Евкліда ми чітко бачимо, що алгоритм Евкліда і по програмній і по часовій складності швидший за алгоритми перебору.