Параметри алгоритму. Правило безпосереднього переробленя. Лабораторна робота з Алгоритми та методи обчислень. Робота № 200103

Параметри алгоритму. Правило безпосереднього переробленя

Інформація про навчальний заклад

ВУЗ:

Національний університет Львівська політехніка

Інститут:

Не вказано

Факультет:

Не вказано

Кафедра:

Електронні обчислювальні машини

Інформація про роботу

Рік:

2015

Тип роботи:

Лабораторна робота

Предмет:

Алгоритми та методи обчислень

Група:

К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(); } Висновок: порівнюючи часову і програмну складність алгоритму методу перебору та алгоритму Евкліда ми чітко бачимо, що алгоритм Евкліда і по програмній і по часовій складності швидший за алгоритми перебору.

Лабораторна робота Алгоритми та методи обчислень

2015

Коментарі

Ви не можете залишити коментар. Для цього, будь ласка, або зареєструйтесь.

Ділись своїми роботами та отримуй миттєві бонуси!

поділитись