mozok.click » Інформатика » Допоміжні алгоритми
Інформація про новину
  • Переглядів: 9620
  • Автор: admin
  • Дата: 18-09-2017, 10:53
18-09-2017, 10:53

Допоміжні алгоритми

Категорія: Інформатика

12.1. Загальні відомості про допоміжні алгоритми і підпрограми

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

Допоміжний алгоритм — це заздалегідь розроблений алгоритм, до якого можна звертатися неодноразово з основного алгоритму в процесі розв'язування конкретної задачі.

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

У мовах програмування допоміжні алгоритми реалізуються за допомогою підпрограм.

Із підпрограмами ви вже зустрічалися раніше у процесі розробки програм обчислення значень арифметичних та інших виразів, не акцентуючи увагу саме на цьому терміні. Наприклад, використовувалися функції обчислення кореня квадратного — sqrt(x), абсолютного значення виразу abs(x) та ін. Функції можуть використовуватися в одній програмі багаторазово у різних місцях цієї програми. Перелічені та інші функції і є підпрограмами. Але вони вбудовані в саму мову програмування і тому їх називають стандартними підпрограмами. Для їх використання достатньо вказати ім’я функції і значення аргументу.

Крім стандартних підпрограм сучасні мови програмування надають можливість програмісту самому створювати підпрограми. Головні переваги використання підпрограм наведено на рис. 1.

Сутність використання підпрограм продемонстровано на рис. 2.

Рис. 2. Організація звернення до підпрограм

Підпрограми користувача обов'язково слід описати у розділі опису, дотримуючись встановленого синтаксису. Опис містить заголовок підпрограми і тіло підпрограми. У заголовку оголошується ім'я підпрограми й у круглих дужках параметри (якщо вони є).

Тіло підпрограми слідує безпосередньо за її заголовком. Під час звернення до підпрограм їм передаються конкретні дані для опрацювання.

Результат обчислення підпрограмою повертається в основну програму.

Катерина Логвинівна Ющенко написала перші програми для першої ЕОМ, створеної у НАН України під керівництвом С. О. Лебедєва. За 40 років роботи в Інституті кібернетики ім. В. М. Глушкова НАН України нею створена широковідома в Україні і за кордоном наукова школа теоретичного програмування.

Із рис. 2 видно, що основна програма містить оператори s1-s10. Перший раз звернення до підпрограми здійснюється з оператора s2. Після завершення виконання підпрограми управління передається оператору основної програми, розташованому безпосередньо за оператором s2, тобто оператору s3. Другий раз звернення до підпрограми здійснюється з оператора s9, а повертається управління до оператора s10 основної програми. З основної програми можна неодноразово звертатися до багатьох підпрограм.

Отже, підпрограма — це логічно завершений фрагмент програми з наданим іменем, який має строго визначене призначення і до якого можна неодноразово звертатися з основної програми.

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

Одна підпрограма може містити опис інших підпрограм. Це означає, що з однієї підпрограми можна звертатися до декількох інших підпрограм.

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

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

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

Передавання аргументів формальним параметрам здійснюється у процесі виклику підпрограми. Наприклад, у підпрограмі обчислення квадратного кореня — sqrt(x) змінна x — це формальний параметр. Після виклику цієї підпрограми змінна х набуде конкретного значення, наприклад 23, тобто воно є аргументом, з якого слід обчислити квадратний корінь.

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

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

Структура процедур і функцій аналогічна структурі програми. Як і основна програма, вони мають складатися із заголовка й операторів, розміщених між ключовими словами begin і end. Цю групу операторів називають тілом процедури (функції). Процедура (функція) завершується словом end, після якого ставиться символ крапки з комою.

Запитання для перевірки знань

Що називають допоміжним алгоритмом?

Які переваги дає використання підпрограм?

Які змінні називають глобальними й локальними?

Поясніть область дії локальних і глобальних змінних.

Поясніть сутність формальних і фактичних параметрів.

Які різновиди підпрограм існують у середовищі Lazarus?

Яка основна відмінність підпрограм-функцій від підпрограм-процедур?

Наведіть означення підпрограми.

Завдання для самостійного виконання

Основна програма займає 5 Кбайтів пам'яті, а підпрограма — 0,75 Кбайта. Із різних місць основної програми здійснюється звернення до підпрограми 6 разів. Визначте, на скільки орієнтовно більше пам'яті займала б ця програма за умови відсутності підпрограми.

Розроблено програму, яка займає 4 Кбай-ти пам'яті. Потім виникла необхідність у цій програмі тричі обчислити квадрат числа і двічі — модуль числа. Який орієнтовно обсяг пам'яті буде займати така програма, якщо кожного разу обчислювати ці значення безпосередньо у цій програмі?



12.2. Процедури

Що називають допоміжним алгоритмом і підпрограмою? Поясніть загальний принцип звернення до підпрограм. Які змінні називають глобальними й локальними? Поясніть сутність формальних і фактичних параметрів. Які різновиди підпрограм існують у середовищі Lazarus?

Загальна структура опису процедури має такий вигляд:

У структурі опису процедури обов'язковими є ключове слово procedure, ім'я процедури, ключові слова begin, end і тіло процедури. Інші складові використовуються за необхідності. Найчастіше процедура оголошується у розділі опису основної програми або іншої процедури.

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

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

В оголошенні можуть використовуватися і var-параметри.

Службове слово var перед змінними у списку формальних параметрів свідчить про те, що ці змінні можуть набувати нові значення в процесі роботи підпрограми. Їх називають параметрами-змінними, а змінні без службового слова var — параметрами-значеннями (приклад 2).

Для звернення до процедури використовується оператор виклику такої структури:

ім'я процедури [(список фактичних параметрів)];

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

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

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

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

Приклад 2. Обчислити об’єми двох циліндрів за відомими радіусами (г) і висотами (Л) за умови, що r, h — цілі числа. Об’єм циліндра збережемо у змінній V.

Алгоритм обчислення об’єма циліндрів з використанням допоміжного алгоритму може бути таким.

Для реалізації алгоритму розмістимо на формі 4 компоненти TEdit, 2 компоненти TLabel і компонент TButton. Встановимо такі значення властивості Text: об’єкта Editl — 2, об’єкта Edit2 — 3, об’єкта Edit3 — 4, об’єкта Edit4 — 5. Об’єкти Labell і Label2 використаємо для виведення результатів обчислення об’ємів циліндрів. Для об’єкта Buttonl обираємо подію onclick. Для обчислення об’єму циліндра

використаємо процедуру obem і глобальні змінні. Результат обчислення об’єму циліндра надається змінній V. Звернення до процедури здійснюється з основної програми двічі. Варіант програмного коду реалізації алгоритму зображено на рис. 1.

Результат виконання програми подано на рис. 2.

Рис. 1. Програмний код з процедурою без параметрів

На рис. З зображено ще один варіант програмного коду реалізації того самого алгоритму. У цьому варіанті процедура obem міститься за межами обробника події об’єкта Buttonl.

Разом із тим, вона розміщена вище за те місце програмного коду, де здійснено звернення до цієї процедури.

Рис. 3. Програма з процедурою без параметрів за межами обробника подій

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

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


Приклад 3. Розробити програму обчислення об’єму двох циліндрів за відомими висотою і радіусом основи з використанням процедури з параметрами. До процедури обчислення об’єму циліндра величину v (шуканий об’єм) передамо як параметр-змінну, а величини г і h (радіус і висоту циліндра) — як параметри-значення.

Варіант програми обчислення об’єму циліндра зображено на рис. 4.

Результат виконання програми подано на рис. 5.

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

Рис. 4. Програма з процедурою з параметрами усередині обробника подій

Рис. 6. Програма з процедурою з параметрами за межами обробника подій

Запитання для перевірки знань

Яка інформація міститься в заголовку процедури?

Які різновиди формальних параметрів використовуються у процедурах?

Як здійснюється виклик процедур?

Які компоненти є обов'язковими в описі процедури?

Наведіть правила запису формальних параметрів процедури.

Наведіть загальну структуру опису процедури.

Яка різниця між параметрами-змінним і па-раметрами-значеннями?

Як пов'язані формальні і практичні параметри процедури?

Завдання для самостійного виконання

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

Складіть програму з використанням підпрограми, яка визначала б день тижня за його номером (1 — понеділок, 2 — вівторок і т. д.).

У банк поклали s грн під k % річних. Розробіть алгоритм і програму обчислення накопиченої суми через n років. У програмі використайте дві процедури без параметрів. За допомогою першої процедури вводяться вихідні дані, а за допомогою другої — обчислюється і виводиться накопичена сума.

12.3. Функції

У структурі опису функції обов'язковими є ключове слово function, ім'я функції, ключові слова begin, end і тіло функції. Інші складові використовуються за необхідності. Найчастіше функція оголошується у розділі опису основної програми або іншої підпрограми.

Загальний опис функції складається із заголовка функції, розділу опису, тіла функції і має таку структуру:

Розглянемо приклади використання функцій у програмах.

Приклад 2. Розробити алгоритм і програму обчислення значення виразу

для двох пар значень змінних а і Ь з використанням підпрограми-функції.

Алгоритм розв’язування цієї задачі можна подати так.

Яку загальну структуру має процедура? Які складові цієї структури є обов'язковими? Поясніть сутність термінів «параметри-змінні» та «параметри-значення». Як здійснюється звернення до процедур?

Як і в процедурі, обов’язковим тут є заголовок і тіло функції. Заголовок починається службовим словом function (приклад 1). Список формальних параметрів функції відповідає списку формальних параметрів процедури. Він містить імена формальних параметрів і їхні типи. Тип результату — це тип значення, що повертає функція. Повертатися можуть скалярні значення цілого, дійсного, логічного, символьного і посилального типів.

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

Для реалізації алгоритму на формі розміщено об’єкти, наведені у таблиці.

Рис. 1. Програмний код із функцією

Рис. 2. Результати виконання програми з двома зверненнями до функції

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

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

Для розв’язання цієї задачі розробимо основний алгоритм і два допоміжні: у першому

допоміжному алгоритмі будемо визначати умову можливості існування трикутника, а у другому — обчислювати площу трикутника. Фактичні довжини відрізків позначимо змінними а, Ь, с, а формальні — відповідно ЗМІННИМИ X, у І 2.

Алгоритм розв’язування задачі можна подати так.

Для реалізації алгоритму розмістимо на формі компонент TEdit, 7 компонентів TLabel і компонент TButton. Об’єкт Editl призначений для виведення повідомлення Сторони трикутника, об’єкт Labell — для виведення повідомлення х=, об’єкт Label2 — для виведення повідомлення у=, об’єкт Label3 — для виведення повідомлення z=, об’єкт Label4 — для введення

значення змінної а, об’єкт Label5 — для введення значення змінної Ь, об’єкт Label6 — для введення значення змінної с, об’єкт Label7 — для виведення результату, об’єкт Buttonl — для надання події onclick.

Програму реалізації алгоритму подано на рис. 3. Результат виконання програми зображено на рис. 4.

Рис. 3. Програмний код із двома функціями

Інколи процедури або функції здійснюють взаємне звернення одна до одної. У такому випадку використовується випереджальний опис (приклад 4).

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

Запитання для перевірки знань

Для чого використовується змінна Result?

Яку структуру має заголовок функції?

Як повертається результат функції у програму, що його викликала?

Які компоненти в описі функції є обов'язковими?

Наведіть загальну структуру опису функції. Наведіть приклад опису функції.

Завдання для самостійного виконання

Дано дві групи цілих чисел: al, a2, a3 і Ь1, b2, Ь3. Розробіть алгоритм і програму визначення мінімального числа у кожній групі,

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

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

12.4. Використання масивів як формальних параметрів підпрограм

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

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

Відкритими називають масиви, які оголошуються у розділах var або type без діапазону індексів, вказується лише тип елементів.

Профільний IT-ресурс DOU.UA провів у 2017 році опитування щодо популярності мов програмування, в якому взяли участь 8 тисяч спеціалістів, із яких 90 % проживає в Україні. Найпопулярнішими виявилися такі мови: Java, javascript, С#, РНР, Python, C++.

Відкриті масиви оголошуються за такою структурою: var <ім'я масиву>: array of <тип>; (приклад 1).

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

Розмір відкритих масивів можна задавати і змінювати під час виконання програми.

Виділення пам’яті масиву здійснюється за допомогою функції SetLength, яка має таку структуру:

SetLength (<ім'я відкритого масиву>, <розмір масиву>); Звільнення пам’яті, виділеної для відкритого масиву, здійснюється за допомогою команди:

<ім'я відкритого масиву>:=пф

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

Нумерація елементів відкритого масиву завжди починається з нуля. За допомогою функції high можна визначити індекс останнього елемента масиву (high=Length—1).

Перший індекс відкритого масиву дорівнює нулю, а останній можна отримати за допомогою стандартної функції: high <ім'я відкритого масиву>;

Параметром функції high є ім’я відкритого масиву, а результатом — індексний номер останнього елемента масиву.

Наприклад, якщо виділено пам’ять для 100 елементів відкритого масиву, то функція high поверне число 99 (оскільки індексація починається з 0, і, відповідно, індекс останнього елемента масиву дорівнюватиме 99).

Відкриті масиви найчастіше використовуються як параметри підпрограм (процедур або функцій). Разом із тим їх можна використовувати й у звичайних програмах.

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

На формі розміщено такі об’єкти: Labell, властивість Caption якого має значення Довжина масиву; Label2, властивість Caption якого має значення Значення елементів масиву; Label3 призначений для виведення результату;

ListBoxI — для виведення значень елементів створеного масиву; Buttonl — для встановлення події onclick. Програму обчислення суми значень елементів масиву подано на рис. 1. Масив формується випадковими числами.

Результат виконання програми зображено на рис. 2.

Рис. 1. Програма з відкритим масивом

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

Найчастіше у підпрограмах як формальні параметри використовують стандартні типи даних (integer, char та ін.). Але можна використовувати і нестандартні типи даних. У такому разі їх необхідно оголосити раніше оголошення підпрограм. Тип масиву оголошується за такою структурою:

type <тип масиву>=аггау [список індексів] of <тип елементів>;

Наприклад:

type skan = array [1..8] of byte;

Опис підпрограми, наприклад процедури, у якій як параметр використовується відкритий масив, має такий вигляд:

procedure <ім'я процедури> <ім'я масиву>: <тип масиву>;

Наприклад:

procedure proc_1 (vas_3: skan);

Джеймс Гослінг, автор мови програмування Java, творець віконної системи NeWS, Gos-lingEmacs, один із розробників StarSeve. Наразі входить в команду відомого українського стартапа Jelastic як незалежний директор.

Приклад 4. На рис. З наведено програму, в якій оголошено два масиви: masl і mas2. Формальними параметрами процедури ргос є відкритий масив mas типу integer. Звернення до процедури з основної програми здійснюється двічі. Перший раз формальним параметрам процедури передаються значення масиву masl завдовжки 5, а у процесі другого звернення передаються значення масиву mas2 завдовжки 4. Під час першого звернення до процедури обчислюється кількість елементів масиву masl, що дорівнює 4, а під час другого

звернення — кількість елементів масиву mas2, що також дорівнює 4. Отже, за допомогою однієї процедури опрацьовуються два різні за довжиною і змістом масиви, але їхні типи збігаються з типом відкритого масиву процедури. На формі розташовано об’єкти Labell і Label2, за допомогою їхніх властивостей Caption здійснюється виведення результатів звернення до процедури. Для об’єкта Buttonl обрано подію onclick.

Результат виконання програми зображено на рис. 4.

Рис. 3. Програма з процедурою, формальним параметром якої є масив

Запитання для перевірки знань

Які масиви називають відкритими?

Для чого призначена функція SetLength?

Як можна звільнити пам'ять, виділену під відкритий масив?

За якою структурою оголошуються відкриті масиви?

Наведіть приклад оголошення відкритого масиву.

Як можна визначити максимальний індекс масиву?

Як викликається процедура, у якій параметрами є відкриті масиви?

Завдання для самостійного виконання

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

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

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

12.5. Поняття рекурсії. Рекурсивні алгоритми

У всіх розглянутих раніше прикладах підпрограми викликалися з основної програми. А чи можуть, на ваш погляд, підпрограми викликати самі себе?

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

Макс Левчін (нар. 1975 р. в м. Києві) є автором багатьох стартапів, співзасновником та головним інженером PayPal, віце-президентом з розробки в компанії Google.

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

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

Зазначимо, що рекурсивні обчислення в багатьох випадках є неефективними і тому часто замінюються рекурентними обчисленнями. Метод рекурентного обчислення потребує меншого обсягу пам’яті й реалізується швидше за рекурсивний. Для свідомого розуміння такого висновку розглянемо детальніше сутність рекурентного і рекурсивного обчислень.

Нагадаємо, що рекурентне обчислення значення математичного виразу на кожному кроці здійснюється через його значення на попередньому кроці. Наприклад, алгоритм обчислення значення виразу y=xn можна подати так.

Отже, після того як вираз i<=n із кроку 6 набуде значення false, виконання алгоритму завершується і змінна y буде містити результат обчислення. Для рекурсивного обчислення значення xn (n — додатне ціле, x — може бути дійсне) потрібно обчислити значення xn-1, оскільки xn=xn-1 • x. У свою чергу, для обчислення xn-1 потрібно обчислити xn-2, оскільки

xn-1 = xn-2 • x і т. д. Процес обчислення слід припинити після обчислення x0, оскільки воно має значення 1. Але результат ще не отримано, отримано лише опорне значення функції. Для отримання кінцевого значення функції потрібно реалізувати зворотний процес обчислення, що міститься у стеку. Пояснимо сутність і необхідність цього процесу на прикладі обчислення значення виразу xn. Рекурсивна функція його обчислення має такий зміст:

function st (x, n:integer): integer;

begin

if n=0 then st:=1 else st:=st(x, n-1)*x;

end;

Ця рекурсивна підпрограма виконується у такій послідовності.

Перший раз вона викликається з основної програми, наприклад, за допомогою команди z=st(2, 3); (отже, x = 2 і n = 3). У результаті цього виклику в стеку виділяється перший блок пам'яті (вершина стека) й управління передається умовному оператору.

Нагадаємо, що у вершину стека записується адреса команди основної пам'яті, до якої слід повернутися після всіх звернень до процедури. Оскільки на цьому етапі вираз n = 0 набуває значення false, то виконується гілка else. Тут у виразі st:=st(x, n-1)*x робиться спроба обчислити значення st(2,2), тобто в дійсності виконується звернення до самої функції st з новими значеннями параметрів. Тому обчислення переривається.

Викликається другий раз функція st, але вже з параметрами st(2, 2). У стеку також виділяється наступний блок пам'яті, а в умовному операторі виконується гілка else і робиться спроба обчислити значення функції st з параметрами st(2, 1).

Третій раз викликається функція st з параметрами st(2, 1). У стеку також виділяється блок пам'яті і знову виконується гілка else з параметрами st(2, 0).

Четвертий раз виклик виконується з параметрами st(2, 0). У стеку виділяється четвертий блок пам'яті, але виконується гілка then, а функція st набуває значення 1. У результаті функція st рекурсивно більше не викликається і здійснюється повернення в основну програму, яка викликала цю підпрограму.

У процесі повернення до основної програми виконуються такі дії. Зі стека вибирається опорне значення st(2, 0)=1, оскільки у стеку реалізується принцип «останній прийшов — перший вийшов». На наступному кроці обчислюється значення st(2, 1)=1*2, потім — st(2, 2)=2*2, нарешті — st(2, 3)=2*4=8. Це значення передається змінній z в основну програму.

Динаміку описаного процесу «заглиблення» і виходу зі стека для описаної функції наведено в таблиці.

Таблиця. ДИНАМІКА ВИКОНАННЯ РЕКУРСІЇ

Класичним варіантом рекурсивної функції є обчислення факторіала заданого числа n, яке виконується за формулою n! = n• (n - 1)!, якщо n > 0 і n! = 1, якщо n=0. Програму обчислення факторіала з використанням рекурсивної функції зображено на рис. 1.

Результат виконання програми наведено на рис. 2.

Рис. 1. Програма обчислення факторіала

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

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

ґрунтується на використанні алгоритму Ев-кліда. Програму реалізації цього алгоритму з використанням рекурсивної функції наведено на рис. 3. Функція має ім’я evk, а числа, для яких обчислюється найбільший спільний дільник, позначені змінними п і т.

Результат виконання програми зображено на рис. 4.

Рис. 3. Програмний код обчислення найбільшого спільного дільника

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

Запитання для перевірки знань

Що називають рекурсією у програмуванні?

З якою метою у тілі рекурсії передбачається умовний оператор?

На якій структурі даних ґрунтується реалізація рекурсивних підпрограм?

Які недоліки має рекурсивне обчислення?

Поясніть сутність «заглиблення» й виходу зі стека у процесі реалізації рекурсії.

Завдання для самостійного виконання

Розробіть рекурсивну функцію для обчислення n перших членів заданої геометричної прогресії.

Дано десяткове натуральне число а. Розробіть рекурсивну функцію обчислення кількості цифр у цьому числі.

Розробіть програму з використанням рекурсивної функції для визначення мінімального елемента одновимірного числового масиву.

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

Розробіть програму з використанням рекурсивної функції обчислення добутку значень елементів одновимірного числового масиву.


Практична робота № 23

Тема. Розробка алгоритмів з використанням допоміжних алгоритмів користувача та їх реалізація у вигляді програм.

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

Обладнання: комп'ютер із встановленою програмою — середовищем програмування.

Хід роботи

Під час роботи з комп’ютером дотримуйтесь правил безпеки. Виберіть один із варіантів завдань самостійно або за вказівкою вчителя. (У разі успішного виконання одного варіанта, виконайте інший.)

Розробіть алгоритм розв’язування завдання.

Розробіть програмний код реалізації алгоритму.

Уведіть код програми в комп’ютер і ви-правте всі синтаксичні помилки.

Виконайте програму для заданих початкових даних і доведіть, що програма функціонує правильно.

Виконайте програму для інших початкових даних і переконайтеся, що отримано правильний результат.

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

Практична робота № 24

Тема. Розробка алгоритмів з використанням масивів як формальних параметрів і реалізація у вигляді програм.

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

Варіант

Завдання

Початкові дані

1

Дано масив цілих чисел a[1], a[2], ..., a[n]. Знайдіть у ньому кількість додатних і кількість від'ємних чисел.

43, -5, 0, 21, 23, -321, -66, 7, -59

2

На змаганнях у стрибках у воду з вишки спортсмена оцінюють 7 суддів. Максимальна і мінімальна оцінки не враховуються. Якщо максимальних або мінімальних оцінок декілька, не враховується по одній оцінці. Знайдіть середній бал виступу спортсмена.

9.5, 9.4, 9.5, 9.2, 9.5, 9.3, 9.2

3

Дано рядок символів. Знайдіть номери, на яких розташований символ s.

subscription

Обладнання: комп'ютер із встановленою програмою — середовищем програмування.

Хід роботи

Під час роботи з комп’ютером дотримуйтесь правил безпеки.

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

Розробіть у вигляді блок-схеми або у словесній формі алгоритм розв’язування завдання.

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

Уведіть код програми в комп’ютер. Спробуйте виконати компіляцію програми. Виправте всі синтаксичні помилки.

Виконайте програму для заданих початкових даних і доведіть, що програма функціонує правильно.

Виконайте програму для інших початкових даних і переконайтеся, що отримано правильний результат.

Зробіть висновок: чим принципово відрізняється опрацювання двовимірних масивів від одновимірних.

Практична робота № 25

Тема. Розробка рекурсивних алгоритмів та їх реалізація у вигляді програм.

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

Варіант

Завдання

Початкові дані

1

Дано рядок, який містить n символів. Розміс-

n=7

тіть символи у зворотному порядку.

рядок: abcdefg

2

Дано n-розрядне ціле число. Розмістіть цифри

n=6

числа у зворотному порядку.

654321

3

У першому квадраті розташовано два прямокутники, сторони яких паралельні осям координат. Відомі координати вершин прямокутників. Визначте загальну площу обох прямокутників.

Вершини першого квадрата: x1 =20, y1 =120, x2=120, y2=120, x3=120, y3=40, x4=20, y4=40 Вершини другого квадрата: x1 =10, y1 =90, x2=100, y2=90, x3=100, y3=10, x4=10, y4=10

Обладнання: комп'ютер із встановленою програмою — середовищем програмування.

Хід роботи

Під час роботи з комп’ютером дотримуйтесь правил безпеки.

Виберіть один із варіантів завдань самостійно або за вказівкою вчителя. (У разі успішного виконання одного варіанта, виконайте інший.)

Проаналізуйте умову завдання. Визначте загальний порядок розв’язання.

Розробіть у словесній формі алгоритм розв’язування завдання.

Розробіть програмний код реалізації алгоритму.

Уведіть програму в комп’ютер. Виконайте компіляцію програми і виправте синтаксичні помилки.

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

Виконайте програму для початкових даних, наведених у таблиці. Доведіть, що результат є правильним.

Зробіть висновок: чи можна було виконати завдання за допомогою рекурентного обчислення.

 

Це матеріал з підручника Інформатика 9 клас Руденко (поглиблений рівень)

 






^