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

Writeln('Vvedit k');

Readln(k);

while a[i]<>k do

begin

if k<a[i] then begin i:=i-q; tmp:=q; q:=p-q;p:=tmp;end

else begin i:=i+q; p:=p-q; q:=q-p; end;

end;

Writeln('element ',k,' mae index ',i);

Readln;

End.

1.4 Метод екстраполяції

Даний метод в деякій мірі подібний до "методу дихотомії", наведеного вище. Проте, щоб краще зрозуміти даний метод, давайте представимо собі, що нам потрібно взнати, як перекладається на українську мову англійське слово treasure. Тобто в нас задача – знайти це слово в словнику.

По суті, всі наші дії будуть нічим іншим, як реалізацією деякого алгоритму пошуку. Масив значень – це словник, всі значення в ньому відсортовані за алфавітом. Шукане слово нам відомо. Тобто будемо проводити пошук в відсортованому масиві. З першого погляду стає зрозумілим, що ми не будемо перебирати всі слова словника, як і не будем ділити книгу навпіл, дивитися що там в середині і відраховувати в одну і другу сторону рівно ¼ сторінок словника і т.д. (за умови що словник великий). Тобто метод дихотомії і лінійний пошук буде проігноровано.

Більш ніж вірно що ми спочатку відкриємо словник дещо дальше ніж на середині (літера t за серединою латинського алфавіту). Якщо відкрили на літері R , ясно, що шукати потрібно в другій частині словника, а на скільки відступити? На половину? "Навіщо ж на половину, це більше, чим потрібно", скажете ви і будете праві. Адже нам не просто відомо, в якій частині масиву шукане значення, ми володіємо ще і інформацією про те наскільки далеко потрібно зробити наступний крок!

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

Якщо при пошуку по бінарному дереву за кожний крок масиву пошуку зменшується з N до значення N/2 , то при цьому методі за кожен крок зона зменшується з N значення до кореня квадратного з N . Якщо K лежить в межах Kn і Km , то наступний крок робимо від n на величину (n - m)*(K - Kn)/(Km - Kn). Швидкість екстраполяційного методу розпочинає суттєво перевершувати швидкість метода половинного ділення при великих значеннях.

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

Program Seach_1_ 4 ;

Uses Crt;

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

i,j,n,k,l,r:integer;

Begin

ClrScr;

Write('Vvedit kilkist chleniv poslidovnocti = ');

readln(n);

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

For i:=1 to n do Readln(A[i]);

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

Writeln('Vvedit k');