Який висновок можна зробити з наведено!' формули? А він такий: використовувати рекурсивні алгоритмы є сенс лише тоді, коли накладні витрати D(N) та C(N) значно менші, ніж час виконання самого алгоритму. А це може статися лише за великих значень N. Для малих N краще застосовувати прямі методи розв'язування задачі.

Повернемося до задачі і спробуємо оцінити час виконання рекурсивно! версії Гї розв'язування. Оскільки граничним зна­чениям N є 1, то гілка then виконається лише один раз. Тому можна вважати, що в тілі цієї підпрограми фактично весь час виконується гілка else, а саме: Factorial := N * * Factorial(N - 1). У цьому арифметичному виразі використовується лише одна операція множення значения змінної N на результат виконан­ня функції, що не залежить від інтервалу, на якому обчис-люється значения факторіала [l..iV], [1..JV - 1], ..., [1..1]. Тому

можна вважати, що 71— =1.

Що ж являе собою операція віднімання, яка використовуєть-ся при виклику функції? Саме вона необхідна для поділу задачі на підзадачі. Таких підзадач буде N, оскільки саме стільки звер-нень буде до функції Factorial. Тобто в нашому випадку а = N.

Поділ нашої загальної задачі на підзадачі полягає в тому, що на кожному наступному кроці довжина інтервалу [l..iV] змен-шується на 1: [1..N], [1..N - 1], ..., [1..1]. А це означав, що поділів буде N і витрати часу на них складатимуть відповідно D(N) та C(N).

Отже, можна визначитися з формулою для обчислення за-гального часу виконання рекурсивного алгоритму Factorial(N):

0(N) = N-1+ D(N) + C(N).

18

Отриманий результат показує, що для даної задачі краще використовувати звичайний алгоритм накопичення добутку, який використовуе час на виконання лише N операцій множен-ня, оскільки часові витрати на рекурсивний виклик функції D(N) та «збирання» результатів ЇЇ виконання C(N) збільшують загальний час роботи алгоритму втричі.

А.

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

1. На які класи поділяються всі алгоритми? За якою ознакою відбу-вається такий поділ?

2. У чому полягає важливість вибору моделі для розв'язування поставлено! задачі?

3. У чому полягає важливість вибору структури даних для роз­в'язування поставлено! задачі?

4. Якими можуть бути критері! оптимальності алгоритму?

5. Яким критеріям при розробці алгоритму задачі надається пріоритет, а якими можна знехтувати?

6. Що називається деревом розв'язків задачі? Наведіть власний приклад.

7. Як за допомогою дерева розв'язків задачі можна визначити оцінку оптимальності алгоритму?

8. Які дії, виконувані алгоритмами, традиційно вважаються опера-ціями?

9. Яку роль при виконанні алгоритму відіграють вхідні дані?

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

11. Які вхідні дані вважаються найгіршим випадком? Наведіть влас­ний приклад обчислення часу роботи алгоритму в найгіршому випадку.

12. Які вхідні дані вважаються середнім випадком? Наведіть влас­ний приклад обчислення часу роботи алгоритму в середньому випадку.

13. Які алгоритми слід порівнювати при визначенні оцінки їх ефек-тивності?

14. Що вважається критеріями ефективності виконання алгоритму? Чим можна знехтувати при обчисленні ефективності виконання алгоритму?

15. Що називається порядком росту часу роботи алгоритму? Наве-діть приклад обчислення порядку росту часу роботи алгоритму.

16. Як позначасться порядок росту часу роботи алгоритму?

17. Як обчислюсться порядок росту часу роботи алгоритмів типу «розділяй і володарюй»? Наведіть власний приклад.

19

Налагодження алгоритму

Планування, покрокова деталізація та представления алгоритму

Налагодження алгоритму - це процес, який складається з декількох кроків. Коли обрано математичну модель, що відпо-відає умові задачі, визначено методи, які треба застосувати для її реалізації, починається розробка самого алгоритму. Оскіль-ки не завжди доводиться розв'язувати такі прості задачі, як упорядкування заданої послідовності чисел за зростанням, тому й не відразу вдається розробити алгоритм у його кінцевій, остаточній формі.

Як і будь-яка інша робота, розробка алгоритму повинна по-чинатися з планування роботи над ним. Розібравшись з умовою задачі, визначаємося не тільки з методами ЇЇ розв'язування, а й з представлениям вхідних та вихідних даних, тобто з їх струк­турами. Від вибору таких структур певним чином залежить і побудова алгоритму.

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

Для прикладу розглянемо алгоритм Евкліда, який дає змогу визначити найбільший спільний дільник двох натуральних чи­сел. На першому кроці покрокової деталізації сформуємо дію повторения, яка дасть змогу визначити результат алгоритму:

while n <> m do

<замінюємо більше число на різницю більшого і меншого чисел>;

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

while nOmdo if n >m

then Оамінюємо число n> else Оамінюємо число m>;

Тепер залишилося зробити останній крок у деталізації алго­ритму - записати дії заміни відповідних значень mam:

while n <> m do

if n > m

20

then n := n - m else m :=m-n;

Зрозуміло, наведений приклад є одним з найпростіших, на яких продемонстровано принцип покрокової деталізації.

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

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

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

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

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

Допоміжні задачі

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

Спосіб створення алгоритму з широким використанням до-поміжних алгоритмів називається структурным підходом до побудови алгоритмів.

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

Якщо поставлена перед вами задача є серйозним великим завданням, то важливість поділу алгоритму на окремі модулі

21

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

Нині можна вже говорити про сформовану індустрію виго-товлення програм. 3 цією метою створюються різноманітні технологи програмування, які увібрали в себе ідеї структурно!' побудови алгоритмів, що базуються на модульному підході до їх створення. При такій побудові алгоритм складається з ок-ремих модулів, що виконують унікальні у даному алгоритмі функції з обробки даних. Зібрані в одну схему модулі із зазначенням усіх переходів між ними й утворюють загальний вигляд алгоритму. Яким чином може йти робота над розробкою алгоритму, що використовує технологію структурного програ­мування? Існують два варіанти: або спочатку розробити каркас алгоритму без деталізації окремих його фрагментів, або надати перевагу розробці окремих модулів, з яких поступово буде фор-муватися основний алгоритм.

Ознайомимося з цими варіантами детальніше.

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

Програмування «знизу-вгору», або висхідне програмуван­ня, засноване на протилежному процесі. Спочатку пишуться і налагоджуються частини задачі, модул і. які розв'язують ок-ремі підзадачі, тобто програми нижчого рівня. а потім поступо-во з них збираються крупніші блоки. Цей процес завершиться тоді, коли вся програма буде повністю зібрана і налагоджена.

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

22

У випадку роботи над алгоритмом цілої групп програмістів найчастіше використовується принцип висхідного програму-вання. Керівник групи розробляє загальну схему алгоритму з визначенням усіх необхідних модулів та обумовленням струк-тури вхідних і вихідних даних для кожного з них. Останній фактор є дуже важливим для наступного стикування модулів у єдине ціле. Розробка модулів доручається окремим членам творчої групи і на кінцевому етапі роботи над алгоритмом усі модулі «збираються» згідно з наперед розробленою схемою.

Реалізація алгоритму мовою програмування

Вибір мови програмування залежить як від уподобань кож­ного, так і від вимог самої задачі. Оскільки алгоритми, які бу-демо розглядати, не вимагають використання можливостей комп'ютера на низькому машинному рівні, тому зупинимо свій вибір на мові програмування Pascal. Хоча слід зазначити, що всі алгоритми, які розглядатимуться далі, можна реалізувати і будь-якою іншою мовою програмування.

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

Для прикладу задачі з пошуком заданого елемента в послі-довності з N елементів вхідними даними повинні бути:

• послідовність, у якій шуканий елемент знаходиться на першому місці;

• послідовність, у якій шуканий елемент знаходиться на останньому місці;

• послідовність, у якій шуканий елемент знаходиться в середині;

• послідовність, у якій шуканий елемент відсутній.

Для прикладу задачі з сортуванням за зростанням послідов-ності з N елементів вхідними даними повинні бути:

• зростаюча послідовність;

• спадна послідовність;

• послідовність, у якій елементи розташовані випадковим чином;

• послідовність, у якій одна половина елементів утворює зростаючу підпослідовність, а решта елементів розташовані ви-падково;

ЯЗ

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

При тестуванні програм бажано враховувати і перевірку ча-сової складності розробленого алгоритму. Тому ці тести треба виконати для різних значень N. Наприклад, для N = 10, 100, 1000,10 000. Знаючи оцінку ефективності роботи розробленого алгоритму, молена таким чином підтвердити чи спростувати його правильність.

Для фіксації часу роботи програм, що реалізують на ком-п'ютері розроблений алгоритм, можна застосувати таку змінну:

var timer: longint absolute $40: S6c;

Призначенням змінної timer є звернення за адресою $40: $6с. Саме там розміщена чотирибайтова ціла змінна, до

якої раз за с апаратно додається 1. Якщо ми опишемо в

18,2

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

Шд час тестування програм варто фіксувати «чистий» час їх роботи, тобто не враховувати введения вхідної інформації та виведення результату. Тому рекомендується на початку тієї частини програми, яка безпосередньо реалізує сам алгоритм, зафіксувати значения, яке міститься за адресою $40: $6с, а те­ля ЇЇ завершения визначити реальний час виконання програми, знову звернувшись по інформацію за тією самою адресою:

timeold := timer;

<програма>

writeln ((timer - timeold)/18.2);

Для складних і громіздких алгоритмів може застосовува-тися методика використання «заглушок». Тобто замість пере-вірки виконання окремих частин алгоритму тимчасово вико-ристовуються значения, які мають бути отримані в результаті їх виконання. Пізніше, після аналізу основних частин алго­ритму, можна повернутися до пропущених фрагментів і переві-рити їх коректність.

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

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