Материал: Інформатика_1 (методи побудови алгоритмівта та їх аналіз)

5. Зробити письмовий аналіз завдання 4.

111

else if a[m]<x

then L := m + 1 else R := m - 1 end; if flag then writeln ('Шуканий елемент знайдено') else writeln ('Шуканий елемент не знайдено');

Чи не можна дещо вдосконалити цей алгоритм? Виявляеть-ся, можна, помінявши місцями вкладені умовні оператори: пе-ревірку на рівність шуканого елемента і «середнього» вико-нувати в останню чергу, оскільки вона при виконанні нашого алгоритму трапиться лише один раз і приведе до завершения алгоритму. А може статися і така ситуація, що ця умова жод-ного разу не виконається. Перевіряючи умову a[m] = х остан-ньою, ми таким чином запобігаємо зайвим перевіркам умов, які найчастіше не дають позитивного результату:

if a[m]<x then L := m + 1 else if a[m] > x

then R := m - 1

else flag := true;

Можна запропонувати інший варіант цього самого алго­ритму, але з використанням повторения з післяумовою:

L:=1;R:=N; repeat

m:=(L+R)div2; if х > a[m]

then L := m + 1 else if x<a[m]

then R : = m - 1 until (a[m] = x) or (L = R); if a[m] = x then writeln ('Шуканий елемент знайдено')

else writeln ('Шуканий елемент не знайдено');

Суттєвішим удосконаленням алгоритму буде, як і при ліній-ному пошуку, таке, яке передбачило б логічне завершения ал­горитму без зайвої перевірки умови not flag у першому варіанті та a[m] = х у другому. Адже виконання цих умов можливе лише один раз або навіть жодного разу не відбудеться нротягом вико­нання всього алгоритму. I справді, відмова від перевірки збі-гання значения шуканого елемента з поточним значениям ♦ центрального» елемента масиву значно покращуе виграш ефективності алгоритму: на кожному кроці втрати від швидко-го визначення результату виконання алгоритму значно менші, ніж переваги відмови від зайвих порівнянь.

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

112

L:=1;R:=N; while (L<R) do begin

m:=(L + R)div2; if a[m] < x then L := m + 1 else R := m end; if a[R] = x then writeln ('Шуканий елементзнайдено')

else writeln ('Шуканий елемент не знайдено');

Залишилося лише проаналізувати умову визначення ре­зультату пошуку a[R] = х. Умовою виходу з циклу є L > R. Однак умова L > R ніколи не буде досяжною, оскільки проміжок [L; R] завжди зменшується за умови, що або L := m + 1, або R := т. При цьому завершения алгоритму відбудеться лише за умови L = R. Але зрозуміло, що виконання умови L = R зовсім не свідчить про те, що шуканий елемент знайдено. Це говорить лише про те, що ми зменшували проміжок пошуку в масиві і зійшлися на одному елементі (L = R). Чому саме перевіряється на збігання елемент масиву з індексом R, а не L? Проаналізуємо оператор розгалуження, який використовується для знаходження певного елемента:

if a[m]<x

then L := m + 1 else R := m;

Якщо шуканого елемента в масиві немає, то ми весь час від-кидаємо ліву половину масиву, тим самим просуваючи значен­ия L до R. При цьому значения R не змінюється, тобто зали-шається R = N. Якщо ж шуканий елемент у масиві присутній, то найімовірніше, що протягом виконання алгоритму відбу-валося відкидання як правої, так і лівоїчастин. Тому перевірка на наявність шуканого елемента в масиві зводиться до пере-вірки умови, чи є елемент, на якому ми зійшлися, шуканим: a[R] = х. Якщо ж ця умова не виконується, то це означатиме, що шуканого елемента в масиві немає. Особливим випадком є ситуація, коли шуканий елемент знаходиться на N-му місці в масиві. Але і при цьому знайдемо правильну відповідь.

Оцінкою ефективності виконання алгоритму бінарного по­шуку є значения 0(log₂N), оскільки саме стільки порівнянь бу­де виконано в запропонованому алгоритмі. Детально це питан­ия розглядалося при ознайомленні з визначенням оцінки ефек-тивності роботи розроблених алгоритмів у першому розділі.

113

/ Запитання для самоконтролю

1. Навєдіть алгоритм пошуку необхідної інформації у словнику.

Рекурсивний бінарний пошук

У класичній літературі, що розглядає питания алгоритмі-зації, рекурсивні алгоритми ще називаються алгоритмами з поверненням.

114

Для пояснения використання рекурсивності в пошукових алгоритмах сформулюємо таку задачу.

Нехай автомат, який щохзилини виготовляє деталі, мае пристрій, що фіксує їх виготовлення та виводить на друк від-повідний протокол. Якщо протягом робочої зміни автомат працював без збоїв, то порядковий номер останньої виготов-леної деталі збігатиметься з останніми числовими даними про­токолу. Але пристрій був не дуже якісний і в деякі моменти часу його «заїдало». Тому фіксація нових виготовлених де­талей тимчасово припинялася і в протоколі повторювалося значения порядкового номера останньої деталі перед збоєм. Через деякий час робота пристрою сама собою відновлювалася і лічба виготовлених деталей продовжувалася, починаючи з останнього зафіксованого значения. У результаті дані при­строю наприкінці зміни не збігалися з реальною кількістю виготовлених деталей.

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

Наведемо приклад. Якщо дані пристрою під час виготовлен­ня 10 деталей були такими:

122344456 7,

то можна зробити висновок, що збої пристрою відбувалися на 3-й, 6-й і 7-й хвилинах.

Ознакою відсутності збою між двома сусідйіми значениями є виконання умови a[k + 1] - a[k] = 1, а між /г-им та Z-им значен­иями відповідно (k < I) а[1] - a[k] - I - k.

Якби було відомо, що під час роботи пристрою відбувся ли­ше один збій, то його пошук можна було б здійснити за допомо-гою алгоритму бінарного пошуку. Цей алгоритм за зазначених вище умов виглядатиме так:

L:=1;R:=N; while (L<R) do begin

m:=(L+R)div2; if a[m] - a[L] = m - L then L := m + 1 else R := m end; if a[R] = x then writeln ('Шуканий елемент знайдеио')

else writeln ('Шуканий елемент не знайдено');

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

115

матимсмо змоги ііадолі визначити всі збої. Щоб на настуПНИХ кроках перегляду заданої послідовності збоїв була можливість поверыутися до тих її частин, що відкидаються методом бі-нарного пошуку, треба застосувати рекурсивне повернення до них на наступних кроках алгоритму.

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

Рекурсивна процедура, що здійснює пошук збоі'в системи в послідовності даних, може бути такою:

procedure Bin_Recur (L, R: byte); var m: byte; begin

ifL+1 OR then begin

m:=(L+R)div2;

if a[m] - a[L] <> m - L

then BinRecur (L, m); if a[R] - a[m] <> R - m then Bin_Recur (m, R); end else writein (f_out, R) end;

Виклик процедури для послідовності з п елементів буде та­ким: Bin_Recur(l, n).

Проаналізуємо деякі фрагмента наведено!' процедури ре­курсивного пошуку.

Мабуть, у вас відразу ж виникло запитання щодо параметрів виклику рекурсивно']' процедури для лівої Bin_Recur(L, m) i правої' Bin_Recur(m, R) частин поточного проміжку. Справді, на відміну від наведеного вище алгоритму, який розглядає ли­ше один збій нашої лічильної системи, у даному випадку гра-ничний елемент з номером т включається як у праву частину, так і в ліву. Це пояснюється тим, що в нашій задачі необхідно весь час контролювати два сусідні елементи. Розглянемо такий конкретний приклад. У випадку послідовності 12 2 2 3 відразу видно, що збої відбулися на 3 та 4 кроках. Центральним еле-ментом цієї послідовності при т = 3 буде а[3] = 2. Якщо ж ми поділимо дану послідовність на такі дві частили: 1 2 2 і 2 3, то аналіз лівої дасть відповідь 3, а правої не визначить жодних збої'в. Таким чином, на цьому прикладі добре видно, що цент-ральний елемент необхідно включати як у праву, так і в ліву частини при поділі навпіл поточної послідовності.

1. Сформулюйте задачу пошуку заданого елемента в упорядкова­ному масиві.

2. Запишіть алгоритм бінарного пошуку.

2. Як визначається «центральний» елемент масиву, з яким відбу-вається порівняння при бінарному пошуку?

3. Як відбувається «відкидання» правоі та лівої частин масиву при бінарному пошуку?

4. Запишіть алгоритм і текст Pascal-програми бінарного пошуку інформації, при виконанні якого використовується логічна змінна як ознака завершения алгоритму.

5. Як можна вдосконалити алгоритм, наведений у попередньому пункті? Обґрунтуйте свою відповідь.

6. Запишіть найефективніший варіант алгоритму бінарного по­шуку. Обґрунтуйте ефективність окремих фрагментів цього алгоритму.

7. Проаналізуйте умову завершеності алгоритму, наведеного в попередньому пункті.

10. Якою є оцінка ефективності роботи бінарного пошукового алго­ритму?

Завдання

1. Реалізувати алгоритм бінарного пошуку заданого елемен­та в упорядкованому масиві, перевіряючи його на збігання з елементом, що мае порядковий номер т мовою Pascal. Визна-чити кількість порівнянь, необхідних для виконання цього ал­горитму.

2. Реалізувати алгоритм бінарного пошуку заданого елемен­та в упорядкованому масиві, не перевіряючи його на збігання з елементом, що мае порядковий номер т мовою Pascal.

3. Порівняти виконання алгоритмів щодо кількості викона-них порівнянь у завданнях 1,2, протестувавши їх для випад-ків, коли шуканий елемент розміщений:

1. на початку масиву;

2. у кінці масиву;

3. посередині масиву.

4. Зробити письмовий аналіз завдання 3.

РЕКУРСИВШ ПОШУКОВІ АЛГОРИТМИ

116

Ще одне питания може виникнути щодо умови продовжепня виклику рекурсивного пошуку L + 1 о R, оскільки в по-передньому варіанті бінарного пошуку ця умова виглядала так: L < R. Чим це пояснюється? Справа в тому, що в задачі бінарно-го пошуку одного елемента в заданій послідовності ми ділили навпіл нашу послідовність до того часу, поки не зупинилися на одному елементі, що визначалося саме умовою L < R. У задачі рекурсивного бінарного попіуку кількох шуканих елементів ми повинні зупинитися на двох сусідніх елементах і проана-лізувати їхні значения, звужуючи при цьому проміжок, що розглядається. Таким чином, номери лівого і правого елемен-тів відрізнятимуться на 1: L + 1 = R.

Проведемо порівняльний аналіз алгоритму звичайного бі-нарного пошуку та рекурсивного бі парного пошуку.

Зрозуміло, що перший із них дуже ефективно знаходить лише один необхідний елемент у заданій послідовності. Тому в такому випадку немає потреби в застосуванні рекурсивності.

У разі, коли шуканих елементів у послідовності може бути декілька, то виникає потреба у перегляді всіх частин послідов-ності. Звичайний алгоритм бінарного пошуку, на жаль, такої можливості не надає, оскільки завжди відкидає одну з двох частин поточної послідовності. Тому в такому випадку може допомогти лише рекурсивний перегляд усіх частин послідов-ності. Але й у цьому разі треба знати міру. Наприклад, коли шуканих елементів у послідовності дуже багато і сама послі-довність велика, то рекурсивний алгоритм може «захлинути-ся»: не вистачить стекової пам'яті для розміщення незавер-шених рекурсивних процедур. Та й щодо часу виконання рекурсивного алгоритму є проблеми: треба визнати, що рекурсивний виклик потребуе додаткового часу. Тому у випад­ку, коли в задачі передбачається наявність великої кількості шуканих елементів у великій послідовності, то варто застосу-вати звичайний лінійний пошук.

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

3 огляду на проведений аналіз алгоритму рекурсивного бі-нарного пошуку визначимо оцінки його ефективності. На ма-люнку 37 зображено дерево пошуку розв'язку задачі для п = 8. У термінальних вершинах дерева вказані самі елементи меси­ву, серед яких можуть бути шукані елементи. В інших вер­шинах дерева вказано рівень поділу задачі на підзадачі: у ко-реневій - 1, оскільки це перший поділ, у наступних - 2, бо на цьому рівні йде поділ ще на дві підзадачі і т. д.

117

Мал. 37

Для найкращого випадку, коли кількість шуканих елемен-тів k у масиві значно менша, ніж самих елементів масиву п, тобто k « п, то оцінкою буде величина 0(log₂n) + С{п) + D(n).

Для випадку наявності двох шуканих елементів у вхідному масиві, тобто при k = 2 (на мал. 37 ці елементи виділено), мож-на зробити такі обчислення. До елемента а_л можна дійти за log₂n кроків, до елемента а₄ - за log₂(n/2) кроків, оскільки до нього можна прийти, повернувшись на рівень 2. Тому отри-маемо результат обчислення:

log₂n + log₂(ra/2) = log₂n + log₂n - log₂2 = 21og₂n -1 - log₂n.

Тобто за наявності невелико!' кількості шуканих елементів у заданому масиві оцінка даного алгоритму залишається 0(log₂n) + С(га) + D(n).

У найгіршому випадку, тобто коли таких елементів багато, тобто k - п, оцінкою буде О(п) + С(п) + D(n), оскільки за алго­ритмом визначення оцінки роботи рекурсивних алгоритмів треба обчислити кількість викликів підзадач, на які буде поділено задачу. Таких поділів буде - п. Як бачимо, додаткові затрати часу на поділ задачі на підзадачі під час виклику ре­курсивних процедур і об'єднання отриманих результатів робо­ти рекурсивних процедур у кінцевий результат мають зміст ли­ше при великих п і малих k.