Рисунок 1. График результатов линейного поиска

Вывод: Из рисунка 2 видно, что график линейного поиска имеет линейный характер. Теоретическое время незначительно отличается от практического, что означает правильность результатов выполнения линейного поиска.

Данный метод удобен для массивов с малой длиной, но использование его для больших массивов занимает много времени.

5.2 Двоичный поиск

Анализ двоичного поиска был проведен на примере числового одномерного массива длиной в 16, 128, 512, 1024 элементов. В качестве искомых элементов были взяты числа, расположенные в первой, средней, последней и произвольной позициях. Для двоичного поиска теоретическое время поиска определяется по формуле Tтеор.=[время сравнения]Ч log2N

Результаты приведены в таблице, которая приведена ниже.

Таблица 3. Результаты двоичного поиска

Ниже приведен график зависимости времени поиска от количества элементов массива.

Рисунок 2. График результатов двоичного поиска

Вывод: Из рисунка 2 видно, что график двоичного поиска имеет логарифмический характер. Теоретическое время незначительно отличается от практического, что означает правильность результатов выполнения двоичного поиска.

Данный метод удобен для массивов с большой длиной, но его использование возможно только в упорядоченных массивах.

5.3 Анализ сортировки деревом

Анализ сортировки деревом был проведен на примере массива длиной в 16, 128, 512, 1024 элементов.

Результаты представлены в виде нижеследующей таблицы.

Таблица 6. Результаты сортировки

Ниже приведен график сортировки деревом.

Рисунок 3. График сортировки деревом.

Вывод: Организация массива в виде двоичного дерева требует несколько больших затрат как на организацию массива, так и на поиск в нем нужного элемента, чем это минимально необходимо. Впрочем, это увеличение не столь существенно. Этот метод оптимален по порядку роста трудоемкости поиска в зависимости от размера массива.

Сортировка деревом не является минимальной по памяти, так как на построения дерева необходимы большие затраты памяти, но процесс сортировки с помощью данного метода занимает мало времени.

Заключение

В процессе выполнения данного курсового проекта изучены и разработаны алгоритмы нечисленной обработки данных: линейный и двоичный поиск заданного элемента, а также упорядочение массива методом сортировки дерева. Был проведен анализ результатов программы, который подтвердил правильность составления и отладки программы. Для наглядности результатов работы программы построены графики и составлены таблицы.

Список литературы

1. Лорин Г. Сортировка и системы сортировки. М.: Наука, 1983г.

2. Лавров С.С, Гончаров Л.И. Автоматическая обработка данных. Хранение информации в памяти ЭВМ. М.: Наука, 1971г.

3. Попов В.Б. Turbo Pascal. М.: Финансы и статистика, 2007г.

Приложение А

Таблицы идентификаторов

Таблица А.1: Идентификаторы основной программы

Таблица А.2: Идентификаторы процедуры VVod

Таблица А.3: Идентификаторы процедуры Vivod

Таблица А.4: Идентификаторы процедуры Save_To_File

А.5 Идентификаторы процедуры Lin_Poisk

Таблица А.6 Идентификаторы процедуры Dv_Poisk

Таблица А.7: Идентификаторы процедуры Tree

Таблица А.8: Идентификаторы процедуры TreeSort

Приложение Б

Текст программы

Program Fariza_Kurs;

uses crt;

type

mas= array [1..1024] of integer;

mas2= array [1..1024, 1..5] of integer;

var n,i,j,x: integer;

a: mas;

b,b1: mas2;

f, f1: text;

Procedure Vvod(n: integer; Var a: mas);

var i: integer;

begin

if n<=16 then

begin

writeln('Vvedite elementy massiva');

for i:=1 to n do read(A[i]);

end

else

for i:=1 to n do

A[i]:=random(1000);

writeln(f,'Ishodnii masssiv');

for i:=1 to n do write(f,a[i]:4);

end;

Procedure Vivod(n: integer; a: mas);

var i: integer;

begin

for i:=1 to n do write(a[i], ' ');

end;

{zapis v fail}

Procedure Save_To_File(var f:text; n: integer; a: mas; m:integer);

var i1: integer;

begin

if n<=16 then

begin

writeln(f,m,'-yi shag:');

for i1:=1 to n do

write(f,A[i1]:4);

writeln(f);

end;

if (n>16) and (m mod 10=0) then

begin

writeln(f,m,'-yi shag:');

for i1:=1 to n do

write(f,A[i1]:4);

writeln(f);

end;

end;

{metod lineinogo poiska}

Procedure Lin_Poisk(n: integer; a: mas; x: integer);

var i,k: integer;

begin

writeln('Metod lineinogo poiska:');

k:=0;

for i:=1 to n do

if a[i]=x then begin k:=i; break;

end;

if k<>0 then Writeln('Element naiden. Sravnenii - ',k)

else writeln('Element ne naiden');

end;

{========metod dvoichnogo poiska ================}

procedure Dv_Poisk(n:integer;a:mas; x:integer);

var k,ni,vi, sri:integer;

f:boolean;

begin

writeln('Metod dvoichnogo poiska:');

vi:=N;

ni:=1;

k:=0;

f:=FALSE;

repeat

sri:=( (ni+vi) div 2);

k:=k+1;

if a[sri] = X then f:=TRUE

else if X > a[sri] then ni:=sri else vi:=sri;

until (k>trunc(ln(n)/ln(2))) or (f=true);

if f=true then writeln('Element naiden, Index= ', sri,'. Sravnenii ',k)

else writeln('Element ne naiden');

end;

{predstavlenie massiva A v vide dereva}

Procedure Tree(a:mas; n: integer; var b: mas2 );

label l;

var i,j,s,k: integer;

begin

b[1,3]:=0;

b[1,4]:=0;

b[1,5]:=0;

for i:=1 to n do begin

b[i,1]:=a[i];

b[i,2]:=a[i];

end;

for i:=2 to n do

begin

k:=1;

l: if b[i,1]<b[k,1] then j:=3 else j:=4;

s:=b[k,j];

if s<>0 then begin

k:=s;

goto l;

end;

b[k,j]:=i;

b[i,3]:=0;

b[i,4]:=0;

b[i,5]:=k;

end;

end;

{sortirovka derevom}

procedure Tree_Sort(b: mas2; var b1: mas2; n: integer);

label l1,l2,l3;

var k,m,i1: integer;

begin m:=0;

for i:=1 to n do

for j:=1 to 5 do

b1[i,j]:=b[i,j];

i:=1;

k:=0;

l1:

if b[i,3]<>0 then

begin

i:= b[i,3];

goto ll;

end;

m:=m+1;

for i1:=1 to n do A[i1]:=b1[i1,1];

savetofile(f1,n,a,m);

l2:

k:=k+1;

b1[k,1]:=b[i,1];

b1[k,2]:=b[i,2];

if b[i,4]<>0 then

begin

i:=b[i,4];

goto ll;

end;

m:=m+1;

for i1:=1 to n do A[i1]:=b1[i1,1];

savetofile(f1,n,a,m);

l3:

j:=i;

i:=b[i,5];

if i<>0 then

begin

if b[i,1]> b[j,1] then goto lm else goto ln;

end;

m:=m+1;

for i1:=1 to n do A[i1]:=b1[i1,1];

savetofile(f1,n,a,m);

writeln('Otsortirovanii massiv');

Vivod(n,a);

readln;

writeln('Kolichestvo perestanovok=',m);

end;

BEGIN

writeln(' VVedite 4islo elementov massiva N<=1024');

readln(n);

assign (f, 'd:\dan.txt');

rewrite(f);

Vvod(n,a);

close(f);

writeln('Ishodnii massiv:');

Vivod(n,a);

{====================lineinii poisk===============}

writeln;

writeln('Vvedite element dla poiska');

readln(x);

LinPoisk(n,a,x);

{========sortirovka============}

assign (f1, 'd:\res.txt');

rewrite(f1);

tree(a,n,b);

Treesort(b,b1,n);

writeln(f1, 'Otsortirovannyi massiv:');

for i:=1 to n do write(f1, A[i]:4);

close(f1);

{========dvoichnii poisk===========}

DvPoisk(n,a,x);

end.

Страницы: 1, 2, 3