var S : array[1..10000] of char;

P : array[1..10000] of word; {масив, в якому зберігаються значення префікс-функції}

i,k : longint;

m : longint;

…

Procedure Prefix; {процедура, що знаходить префікс-функцію}

Begin

P[1]:=0; {префікс рядка із одного символу має нульову довжину}

k:=0;

for i:=2 to m do {обраховуємо для префіксів рядки довжиною від 2 до m символів}

begin

while (k>0) and (S[k+1]<>S[i]) do

k:=P[k]; {значення функції може бути отримане із обчислень, проведених раніше}

if S[k+1]=S[i] then

k:=k+1;

P[i]:=k; {присвоєння префікс-функції}

end;

End;

Давайте тепер розглянемо дану функцію, і перевіримо, чи правильно обраховується префікс-функція. Використовується наступна ідея: якщо префікс (він же суфікс) рядка довжиною і довший одного символу, то він же одночасно і префікс підрядка довжиною і-1. Таким чином, ми перевіряємо префікс попереднього підрядка, якщо ж він не підходить, то префікс її префікса і т.д. Діючи таким способом, ми знаходимо найбільший шуканий префікс. Наступне питання, на який потрібно відповісти: чому час роботи процедури ми вказали лінійний, якщо в ній присутній вкладений цикл? Ну, по-перше, присвоєння префікс-функції виконується чітко m раз, решта часу міняється змінна k. Так як в циклі while вона зменшується (P[k]<k), але не стає меншою 0, то зменшуватися вона може не частіше, чи зростати. Змінна k зростає на 1 не частіше m раз. Значить, змінна k міняється всього не більше як 2m разів. Звідки слідує, що час роботи всієї процедура рівний O(m).

Розглянемо всю программу, що шукає рядок в тексті.

Program KnutMorrisPrattSearch;

…

{Опис процедури Prefix і пов'язаних з нею змінних}

…

var n : longint;

T : array[1..40000] of char;

Begin

{Ввід тексту і зразку}

…

Prefix; {Обчислення префікс-функції}

k:=0; {кількість символів, що співпадають на даний час}

for i:=1 to n do

begin

while (k>0) and (S[k+1]<>T[i]) do

k:=P[k];

if S[k+1]=T[i] then

k:=k+1;

if k=m then {якщо співпали всі символи}

begin

writeln('Зразок входить в текст починаючи з ',i-m+1,'-ого символу');

k:=P[k];

end;

end;

End.

Довести, що ця програма працює за лінійний проміжок часу, можна аналогічно доведенню, наведеному вище для процедури Prefix. Отже, загальний час роботи програми рівний O(n+m), тобто лінійний час.

Алгоритм Кнута-Морріса-Пратта більш громіздкий ніж наведені вище, проте час роботи із великими об'ємами даних є набагато меншим, тобто він більш швидше працює із великими об'ємами тексту ніж решта алгоритмів.

Реалізація алгоритму на Turbo Pascal. Нехай маємо рядок і підрядок, що складаються лише з літер англійського алфавіту, використовуючи метод Кнута-Морріса-Пратта знайти позицію першого входження даного підрядка в рядок.

Program Seach_2_3;

Uses Crt;

var

n : longint;

T : array[1..40000] of char;

S : array[1..1000] of char;

P : array[1..1000] of word; {масив, в якому зберігаються значення префікс-функції}

i,k : longint;

m : longint;

{---------------------------------------------------------}

Procedure Prefix; {процедура, що знаходить префікс-функцію}

Begin

P[1]:=0; {префікс рядка із одного символу має нульову довжину}

k:=0;

for i:=2 to m do {обраховуємо для префіксів рядки довжиною від 2 до m символів}

begin

while (k>0) and (S[k+1]<>S[i]) do

k:=P[k]; {значення функції може бути отримане із обчислень, проведених раніше}

if S[k+1]=S[i] then

k:=k+1;

P[i]:=k; {присвоєння префікс-функції}

end;

End;

{---------------------------------------------------------------------------------}

Begin

ClrScr;

Randomize;

Writeln(` Vvedit dovguny texty n');

Readln(n);

Writeln(` Vvedit dovguny pidradka m, m<n');

Readln(m);

for i:=1 to n do

begin

T[i]:=chr(97+random(26));

write(T[i]);

end;

Writeln;

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

Writeln(`Vvedit pidrjadok sumvolu a..z');

I:=1;

While i<=m do

Begin

C:=readkey;

If (ord(c)>96)and(ord(c)<123)then begin

S[i]:=c;

Write(s[i]);

Inc(i);

End;

End;

Writeln;

Prefix; {Обчислення префікс-функції}

k:=0; {кількість символів, що співпадають на даний час}

for i:=1 to n do

begin

while (k>0) and (S[k+1]<>T[i]) do

k:=P[k];

if S[k+1]=T[i] then

k:=k+1;

if k=m then {якщо співпали всі символи}

begin

writeln('Зразок входить в текст починаючи з ',i-m+1,'-ого символу');

k:=P[k];

end;

end;

Readln;

End.

Висновки

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

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

У відповідності до мети та завдання курсової роботи були виконані наступні кроки:

1. Було проведено детальний аналіз літератури та Інтернет джерел за темою "Пошук елементів у масиві", що дало змогу сформувати як теоретичні основи понять лінійного пошуку, пошуку за допомогою дерева так і визначено основні алгоритми реалізації пошуку елементів. У курсовій роботі наведено графічне представлення деревоподібного пошуку для більшої наглядності і проведено детальний розгляд кожного кроку алгоритмів.

2. Було проаналізовано застосування методів пошуку на практиці, що дало змогу визначити, в яких цілях і з якою метою є їх найбільш доцільну використання. Було показано, що на даний час існує ряд специфічних задач і областей застосування, де без використання алгоритмів пошуку обійтись не можливо. Як наслідок, це дало змогу поставити завдання для реалізації конкретних завдань з допомогою мови програмування високого рівня - Turbo Pascal, вибір даної мови програмування був обумовлений тим, що вона найбільш підходить для навчальних цілей. Оскільки в школах і вузах початки програмування і алгоритмізацію показуються саме з допомогою Turbo Pascal. Вибір цієї мови програмування був зумовлений ще і її гнучкістю і простотою в застосуванні і розумінні. Всі програми, які показані в курсовій роботі відповідним чином названі у відповідності до розділу, до якого вони належать. У програмах було зроблено коментарі, які роблять їх більш зрозумілими для розуміння;

3. В своїй роботі ми розбили матеріал на дві окремі частини, в першій частині ми провели розгляд найбільш використовуваних методів пошуку елементів на прикладі одновимірного масиву, знаючи ці алгоритми, досить просто перенести їх для пошуку елементів у багатовимірних масивах, структурах. В другій частині роботи ми більшу увагу приділили більш сучасним алгоритмам пошуку підрядка в тексті, які набувають більшої популярності в нас час, коли практично будь-яку текстову інформацію можна знайти в мережі Інтернет.

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

Виконуючи курсову роботу, ми дійшли висновку, що використання одних алгоритмів пошуку у відношенню до інших може бути мінливе навіть не в залежності від швидкості дій, а в залежності від поставленої мети. Так, наприклад, швидкість виконання алгоритму лінійним пошуком елемента в масиві N- невеликої кількості більш прийнятна, ніж застосування пошуку "бінарним деревом", оскільки затрати на реалізацію даного методу не оправдовують його застосування.

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

Література

1. Turbo Pascal - Издательская група К.: ВНV, 2000. - 320 с.

2. Абрамов В. Г. Введение в язык Pascal: Учебное пособие для студентов вузов по специальности Прикладная математика. - М.: Наука, 1988. - 200 с.

3. Абрамов С. А., Зима Е. В. Начала программирования на языке Pascal. - М.: Наука, 1987. - 126 с.

4. Андреева Е., Фалина И. Системы счисления и компьютерная арифметика. М.: Лаборатория базовых знаний, 2000. - 201 с.

5. Ахо А.А., Хопкрофт Д.Э., Ульман Д.Д. Структуры данных и алгоритмы. М.: "Вильямс", 2000. - 163 с.

6. Вирт Н. Алгоритмы и структуры данных. M.: Мир, 1989. - 142 с.

7. Власик А.П. Практикум з програмування в середовищі Turbo Pascal. Ч 1.- Рівне: НУВГП, 2005. - 179 с.

8. Грис Д. Наука программирования. M.: Мир, 1984. - 230 с.

9. Д. Кнут "Искусство программирования для ЭВМ", 1978г, издательство "МИР", том 3 "Сортировка и поиск". - 530 с.

10. Джонс Ж., Харроу К. Решение задач в системе Турбо Паскаль. М, 1991. - 709 с.

11. Зуев Е. А. Язык программирования Турбо Паскаль 6.0, 7.0. - М.: Радио и связь, 1993. - 150 с.

12. Клюшин Д. А. Полный курс С++. Москва: Санкт-Петербург, 2004. - 668 с.

13. Кнут Д.Э. Искуство програмирования, том 3. Поиск и сортировка, 3-е изд.: Пер. с англ.: Уч. Пос. - М.:Издательский дом "Вильямс", 2000. - 750 с.

14. Ковалюк Т.В. Основи програмування. Київ: Видавнича група ВНV, 2005. - 385 с.

15. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы. Построение и анализ. М.: МЦНМО, 2000. - 93 с.

16. Культин Н. Б. Программирование в TurboPascal 7.0 и Delphi. - Санкт- петербург,1999. - 120 с.

17. Культин Н. Б. С/С++ в задачах и примерах. - М., 2002. - 288 с.

18. Кучеренко В. Язык программирования С++ для начинающих и не только. - М.: Майор, 2001. - 160 с.

19. Львов М. С., Співаковський О. В. Основи алгоритмізації та програмування. Херсон, 1997. - 240 с.

20. Марченко А.И., Марченко Л.А. Программирование в среде Turbo Pascal 7.0. К.: ВЕК, 2000. - 441 с.

21. Окулов С.M. Сортировка и поиск. "Информатика", №35, 2000. - 73 с.

22. Окулов С.М. Основы программирования. "Информатика", №27, 2001. - 430 с.

23. Перминов О. Н. Программирование на языке Паскаль. - М.: Радио и связь, 1988. - 97 с.

24. Перминов О. Н. Язык программирования Pascal. - М.: Радио и свіязь,1989. - 205 с.

25. Популярные лекции по математике, выпуск №6. 1969г. Издательство "Наука" Н.Н. Воробьев. "Числа Фибоначчи" - 105 с.

26. Шень А. Программирование: теоремы и задачи. М.: МЦНМО. - 205 с.

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