Курсова робота на тему:«АЛГОРИТМИ ПОШУКУ ТА ЇХ РЕАЛІЗАЦІЯ»

Зміст

Вступ    3

Лінійний пошук    4

Двійковий пошук    5

Помилки в реалізації    6

Двійковий пошук на C++    7

Двійковий пошук на Java    8

Двійковий пошук на OCaml    8

Перевірка роботи    9

Пошук за ключем у масиві    10

Лінійний пошук    10

Дихотомічний пошук    11

Алгоритми пошуку даних    13

Простий алгоритм    14

Алгоритм Рабина-Карпа    15

Алгоритм Кнута-Морріса-Пратта    19

Висновки    22

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

 

  1. Вступ

  2. Одна з дій, що найчастіше зустрічаються в програмуванні – пошук. Він же є ідеальною задачею, на якій можна випробовувати різні структури даних у міру їх появи. Існує декілька основних “варіацій цієї теми”, і для них створено багато різних алгоритмів. При подальшому розгляді ми виходимо з такого принципового припущення: група даних, в якій необхідно відшукати заданий елемент, фіксована. Вважатимемо, що множина з N елементів задана, скажімо, у вигляді такого масиву:
  3. а: ARREY [0..N-1] OF item;

    Звичайно тип item описує запис з деяким полем, що виконує роль ключа.
    Задача полягає в пошуку елементу, ключ якого рівний заданому “аргументу пошуку” х. Одержаний в результаті індекс i, що задовольняє умові а[i].key=х, забезпечує доступ до інших полів знайденого елементу. Оскільки нас цікавить в першу чергу сам процес пошуку, а не знайдені дані, то ми вважатимемо, що тип item включає тільки ключ, тобто він є ключ (kеу).

  4. Лінійний пошук

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

  5. Елемент знайдений, тобто аі= х.
  6. Весь масив проглянутий і збігу не знайдено.

    Це дає нам лінійний алгоритм:

    і:=0;

    WHILE (i<N) & (a[i] # x) DO i:=i+1 END;

    Зверніть увагу, що порядок елементів в логічному виразі має вагоме значення. Інваріант циклу, тобто умова, що виконується перед кожним збільшенням індексу і, виглядає так:

    (0≤i<N) & (Ak:0≤k<i:аk≠x).

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

    ((i=N)OR(аі=x)) & (Ak:0≤k<i:аk≠x).

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

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

    Ясно, що на кожному кроці вимагається збільшувати індекс і обчислювати логічний вираз. А чи можна цю роботу спростити і таким чином прискорити пошук? Єдина можливість -спробувати спростити сам логічний вираз, адже він складається з двох членів. Отже, єдиний шанс на шляху до простішого рішення – сформулювати просту умову еквівалентну нашій складній. Це можна зробити, якщо ми гарантуємо, що збіг завжди відбудеться. Для цього достатньо в кінець масиву помістити додатковий елемент зі значенням х. Назвемо такий допоміжний елемент бар’єром, адже він охороняє нас від переходу за межі масиву. Тепер масив буде описаний так:

    a:ARREY[0..N] OF INTEGER

    і алгоритм лінійного пошуку з бар’єром виглядає таким чином:

    a[N]:=x; i:=0;

    WHILE a[i] #×DO i:=i+1 END;

    Результуюча умова, виведена з того ж інваріанта, що і раніше:

    і=x) & (Ak:0≤k<i:аk≠x).

    Очевидно, рівність i=N свідчить про те, що збігу (якщо не рахувати збігу з бар’єром) не було.

    ЗАВАНТАЖИТИ

    Для скачування файлів необхідно або Зареєструватись

    Algor Poschuku (145.0 KiB, Завантажень: 7)

Сторінка: 1 2 3 4 5
завантаження...
WordPress: 23.53MB | MySQL:26 | 0,524sec