Анализ и построение алгоритмов

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Міністерство освіти та науки України

Запорізький національний технічний університет

Кафедра комп'ютерних систем та мереж

№ зал.кн. 3.06.07.5.049

Контрольна робота

“Аналiз та побудова алгоритмiв”

Виконав студент

групи ІОТз-527

Мельнiчук О.В.

Прийняв викладач

Пiнчук В.П.

м. Запоріжжя

2011 р.

Задача 4

Выполнить упорядочивание (сортировку) одномерного массива значений по возрастанию. Тип элемента массива - целое число.

Алгоритм: метод слияния.

Описание алгоритма

В основе этого алгоритма лежат две вещи: возможность быстрого объединения двух упорядоченных массивов в один (эта процедура линейна по времени) и последовательное деление исходного массива на части с помощью рекурсии. Подробнее см. в лекциях по АПА.

Построение программы А

Программа А должна решать задачу упорядочивания массива методом слияния и служить доказательством правильности построенного (выбранного) алгоритма. Алгоритм реализуется в виде двух процедур (функций)

sort (int* A, int p, int q, int r) и p_sort(int* A, int n, int p, int r),

где n - размер исходного массива, А - имя массива (указатель на массив), . Для проверки правильности алгоритма и его реализации используются массив со случайными цифрами.

#include <syst.h>

void sort (int* A, int p, int q, int r)

{ int i,j,k, L= r-p+1;

int* x= new int[L];

i=p; j=q+1;

for (k=0;k<L;k++) { if (j>r) { x[k]= A[i]; i++; continue; }

if (i>q) { x[k]= A[j]; j++; continue; }

if (A[i]<=A[j]) { x[k]= A[i]; i++; }

else { x[k]= A[j]; j++; }

}

for (k=0;k<L;k++) A[p+k]=x[k];

delete[] x;

}

void p_sort(int* A, int n, int p, int r)

{ int q;

if (p<r) { q= (p+r)/2;

p_sort(A,n,p,q);

p_sort(A,n,q+1,r);

sort (A,p,q,r);

}

}

void main()

{ const int n = 8;

int a[n]= {8,3,5,2,3,4,5,1};

p_sort(a,n,0,n-1);

for (int i=0;i<8;i++) printf("%d ",a[i]);

puts(""); puts("Press any key..."); getch();}

массив алгоритм рекурсия сортировка

Построение программы В

Программа вычисляет таблицу функции сложности и, решает соответствующую задачу аппроксимации, определяет порядок алгоритма, т.е. порядок полинома, который соответствует функции t = F(n). Программа вычисляет таблицу функции сложности (времени выполнения) исследуемого алгоритма, выводит ее на экран и, далее, решая соответствующую задачу аппроксимации данных, находит порядок алгоритма. При этом предполагается, что алгоритм является полиномиальным, т.е. его функция сложности t = F(n) представляет собой полином относительно n порядка p, где p - порядок алгоритма.

#include <syst.h>

void merge(int* A, int p, int q, int r)

{ int i,j,k, L= r-p+1;

int* x= new int[L];

i=p; j=q+1;

for (k=0;k<L;k++) { if (j>r) { x[k]= A[i]; i++; continue; }

if (i>q) { x[k]= A[j]; j++; continue; }

if (A[i]<=A[j]) { x[k]= A[i]; i++; } // по возраст.

else { x[k]= A[j]; j++; }

}

for (k=0;k<L;k++) A[p+k]=x[k];

delete[] x;

}

void merge_sort(int* A, int n, int p, int r)

{ int q;

if (p<r) { q= (p+r)/2;

merge_sort(A,n,p,q); // рекурсивные вызовы

merge_sort(A,n,q+1,r); // функции merge_sort

merge(A,p,q,r);

}

}

const int M=8;

void main()

{ randomize();

int i,k,n=65536;

double t;

double x[M],y[M];

int* a;

for (k=0;k<M;k++)

{ a= new int[n];

for (i=0;i<n;i++) a[i]= random(1000000);

runtimer();

merge_sort(a,n,0,n-1);

t=timer();

x[k]=log2(n); y[k]=log2(t);

printf("k=%d n=%6d t=%f \n", k,n,t);

n*=2;

delete[] a;

}

double a0,a1;

linappr(M,x,y,a0,a1);

printf("\n p = %6.4f \n",a1);

delete[] a;

printf("\7"); pause;

}

p=1.1203

Результаты выполнения.

n=	65536	t=	0,015000
n=	131072	t=	0,015000
n=	262144	t=	0,063000
n=	524288	t=	0,125000
n=	1048576	t=	0,281000
n=	2097152	t=	0,594000
n=	4194304	t=	1,203000
n=	8388608	t=	2,484000



Задача12

Решить систему линейных уравнений порядка n. Для вычислений используется тип double.

Алгоритм Гаусса.

Описание алгоритма

Задача решается в два этапа. Вначале матрица системы приводится к верхней треугольной форме, затем вычисляются искомые величины, начиная с последней. Время выполнения первого этапа равно O(n3), время выполнения второго O(n2). Функция сложности алгоритма Гаусса в целом соответствует асимптотическому классу:

Ft(n) = O(n3) .

Построение программы А

С использованием библиотеки dalmat.h, алгоритм программы сводится к созданию матрицы, вектора правых частей и вектора решений, далее все вычисления производит функция gauss().

#include <dalmat.h>

void main()

{ int n;

printf("n = "); scanf("%d",&n);

dmatrix A(n); A.rand(0,1);

dvector B(n); B.rand(0,1);

dvector X(n);

gauss(A,B,X);

for (int i=0;i<n;i++){

printf ("X[%d] = %f", i,X[i]);

printf("\n");

}

pause;

}

Построение программы В

Программа вычисляет таблицу функции сложности (времени выполнения) исследуемого алгоритма, выводит ее на экран и, далее, решая соответствующую задачу аппроксимации данных, находит порядок алгоритма.

#include <dalmat.h>

const int M=6;

void main()

{ int k, n=256;

double t;

dmatrix A;

dvector B,X;

double x[M],y[M];

FILE* f= fopen("12_B.txt","w");

if (f==0) { puts("Cannot open the File!");

pause;

exit(0); }

fprintf(f,"%2d \n",M);

for (k=0;k<M;k++)

{ A= dmatrix(n); A.rand(0,1);

B= dvector(n); B.rand(0,1);

X= dvector(n);

runtimer();

gauss(A,B,X);

t=timer();

printf("%d. n=%2d t=%f \n",k,n,t);

fprintf(f,"%d. n= %2d t= %f \n",k,n,t);

x[k]=log2(n); y[k]=log2(t);

n=round(n*sqrt(2));

}

double a0,a1;

linappr(M,x,y,a0,a1);

fprintf(f,"\na0=%f a1=%f \n",a0,a1);

printf("\na0=%f a1=%f \n",a0,a1);

fclose(f);

puts("END\7");

pause;

}

Результаты выполнения.

n=	256	t=	0.032000
n=	362	t=	0.093000
n=	512	t=	0.250000
n=	724	t=	0.718000
n=	1024	t=	2.062000
n=	1448	t=	6.000000

Размещено на Allbest.ru