Курсовая работа: Порівняльний аналіз ефективності та складності алгоритмів пошуку елементів у масивах

Рис. 2. Дерево Фібоначе порядку 6

Ефективність даного метода вища за ефективність методу бінарного дерева в тому, що метод Фібоначе включає в себе тільки такі арифметичні операції, як додавання і віднімання, немає необхідності в діленні на 2, тим самим економиться процесорний час. Адже, як відомо виконання операцій віднімання і додавання проходить на порядок швидше ніж операція множення чи ділення.

Даний метод був винайдений в 60-ті роки.

Реалізація алгоритму на Turbo Pascal. Нехай дано впорядкований масив N елементів цілочисельного типу, знайти заданий елемент і вивести його позицію у масиві використовуючи метод Фібоначе.

Program Seach_1_3;

Uses Crt;

Var a:array [1..200] of integer;

i,n,k,j,l,x,y,z,tmp,q,p:integer;

Begin

ClrScr;

Write('Vvedit kilkist chleniv poslidovnocti');

readln(n);

for j:=1 to 3 do

begin

l:=1;x:=1;y:=0;

While l<trunc(n/2)+1-j do

begin

z:=x; l:=l+1;

x:=x+y; y:=z;

end;

Case j of

1:i:=x;

2:p:=x;

3:q:=3;

end;

end;

Writeln('-----------------------------');

For i:=1 to n do

Readln(A[i]);