M_CI_5

Приклад 5.6.

1: #include <stdio.h>

2:

3: void up_to_down(int);

4:

5:void main(void)

6:{

7:up_to_down(1);

8:}

9:

10:void up_to_down(int n)

11:{

12:printf("Рівень %d\n", n);

13:if(n<4)

14:up_to_down(n+1);

15:printf("Рівень %d-дубль\n", n);

16:}

При виконанні програма виведе на екран:

Рівень 1 Рівень 2 Рівень 3 Рівень 4 Рівень 4-дубль Рівень 3-дубль Рівень 2-дубль Рівень 1-дубль

Для ознайомлення з роботою рекурсії давайте прослідкуємо послідовність викликів в програмі. На початку функція main() викликає функцію up_to_down() з аргументом 1. В результаті формальний аргумент n в функції up_to_down() приймає значення 1, і оператор виведення в рядку 12 виводить рядок Рівень 1. Потім, оскільки n менше 4, функція up_to_down() (рівня 1) викликає функцію up_to_down() (рівня 2) з аргументом n+1. В результаті параметру в виклику рівня 2 (рядок 14) присвоюється значення 2 і оператор виведення в рядку 12 виводить рядок Рівень 2. Аналогічно наступні два виклики призведуть до виведення рядків Рівень 3 і Рівень 4.

При досягненні рівня 4 параметр n має значення 4, тому умова в операторі if дає значення FALSE (0). Функція up_to_down() більше не викликається. Замість цього виклик рівня 4 переходить до оператора виведення в рядку 15, який виводить рядок Рівень 4-дубль. Потім потік програми досягає оператора return (неявного, його замінює фігурна дужка }) в функції up_to_down(). В цьому місці виклик рівня 4 завершується і управління передається назад функції, яка його викликала – в даному випадку виклику функції up_to_down() рівня 3. Останнім оператором, який виконувався, в виклику рівня 3, було звертання до виклику 4 в операторі if. Таким чином, виконання перерваного рівня 3 буде продовжено з наступного оператора, яким є оператор виведення в рядку 15. Цей оператор виводить рядок Рівень 3-дубль. Потім рівень 3 завершується, передаючи управління рівню 2, який виводить рядок Рівень 2-дубль, і т.д.

Для того, щоб краще зрозуміти, як працює попередній приклад, уявіть собі, що ми маємо ланцюжок викликів функцій, якому fun_1() викликає fun_2(), fun_2() викликає fun_3(), а fun_3() викликає fun_4(). Коли функція fun_4() завершується, вона повертає управління функції fun_3(). Коли функція fun_3() завершується, вона повертає управління функції fun_2(). А коли функція fun_2() завершується, вона повертає

76

управління функції fun_1(). Рекурсія працює таким же чином, за виключенням того, що fun_1(),fun_2(), fun_3() і fun_4()– одна і та ж функція.

Для розуміння механізму рекурсії потрібно розглянути кілька вузлових моменти.

Кожен рівень виклику функції має свої власні змінні. Це значить, що змінна n Рівня 1 (приклад 5.6) відрізняється від змінної n Рівня 2. Таким чином програма створює чотири окремих змінні, кожна з яких називається n, але має своє значення.

Кожному виклику відповідає код повернення функції. Коли потік програми досягає оператора return в кінці останнього рівня рекурсії, управління передається попередньому

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

Оператори в рекурсивній функції, які розміщені перед рекурсивним викликом, виконуються в тому ж порядку, в якому викликаються функції (дивіться приклад 5.6).

Оператори в рекурсивній функції, які розміщені після рекурсивного виклику, виконуються в зворотному порядку по відношенню до порядку виклику функцій (дивіться там же).

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

Коли рекурсивний виклик функції стоїть перед оператором return (або перед }), то

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

Розглянемо іще кілька прикладів використання рекурсії – функцію обчислення цілої степені дійсного ненульового числа (приклад 5.7) та обчислення факторіалу додатного цілого числа (приклад 5.8):

Приклад 5.7

1:long fact(int n)

2:{

3:if(n < 0) return 0;

4:if(n == 0) return 1;

5:return n*fact(n-1);

6:}

Вфункції використовується той факт, що n! = n*(n-1)! . Формальний параметр не може приймати значення більше 15, тому що факторіал такого числа не розміститься в long. Для таких чисел функція fact() повинна мати тип double (факторіал 15!=2004310016).

Приклад 5.8

1:double expo(double x, int n)

2:{

3:if(n == 0) return 1;

4:if(x == 0.0) return 0;

6:if(n < 0) return x*expo(x, n+1)/x;

7:}

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

77

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

5.8. Модифікатори функцій.

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

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

static void Get_Float(void);

Крім того, ви можете оголосити функцію зовнішньою, використовуючи ключове слово extern. Наприклад:

extern void Get_Float(void);

Функції є зовнішніми по замовчанню, тому модифікатор extern є необов`язковим. Іншими модифікаторами функцій є:

5.9.Робоче завдання.

Увiдповiдностi з завданням скласти i вiдпрацювати програму. Пояснити структуру пiдлеглостi підпрограм i механiзм дiї параметрiв. Протокол оформити у відповідності до вимог, приведених у Додатку А. Інформація про бібліотечні функції знаходиться в додатку Б.

1. Описати i використати в програмi функцію ReadInteger, яка дозволяє органiзувати введення цiлого числа I в межах вiд Min до Max, з органiзацiєю запиту. Процедура повинна мiстити в собi пiдлеглу логiчну функцiю VirnVvod, яка дозволяє визначити, чи введене число попадає в дiапазон Min...Max. Вихiд з функції ReadInteger повинен здiйснюватись тiльки при умовi вiрного введення.

2. Є довжини A, B, C сторiн трикутника. Знайти медiани трикутника, довжини сторiн якого дорiвнюють довжинам медiан початкового трикутника. В програмi визначити логiчну функцiю IsTriangle(L1,L2,L3), яка визначає, чи iснує трикутник з сторонами L1, L2, L3, i функцію Medians(L1,L2,L3,M1,M2,M3), яка по довжинаx сторiн трикутника L1, L2, L3 визначає його медiани. Довжина медiани, що проведена до сторони L1 дорiвнює sqrt(2*L2**2 + 2*L3**2 - L1**2)/2.

78

3.Є довжини вiдрiзкiв A, B, C, D. Для кожної трiйки цих вiдрiзкiв, з якої можна побудувати трикутник, вивести на екран площу трикутника. В програмi використати логiчну функцiю IsTriangle(L1,L2,L3), яка визначає чи iснує трикутник з довжинами сторiн L1,L2,L3, а також функцію AreaOfTriangle(L1,L2,L3), яка по довжинах сторiн трикутника L1, L2, L3 визначає i виводить на екран його площу.

4.Три прямi на площинi задаються рiвняннями Ai*X+Bi*Y=Ci, (i=1, 2, 3). В програмi визначити функцію, яка дозволяє по коефiцiєнтах характеристичних рiвнянь двох прямих визначити перетинаються вони чи нi, i якщо вони перетинаються - розрахувати координати точки перетину Coord(A1,B1,C1,A2,B2,C2,X,Y), i функцiю розрахунку площі трикутника по координатах його вершин AreaOfTriangle(X1,Y1,X2, Y2,X3,Y3).

5.Є координати двох трiйок точок на площинi X11,Y11, X12, Y12, X13, Y13 i X21, Y21, X22, Y22, X23, Y23. Якщо через цi точки можна провести два трикутника, визначити який з них має бiльшу площину. В програмi визначити логiчну функцiю IsTriangle (X1, Y1, X2, Y2, X3, Y3), яка визначає чи iснує трикутник з координатами вершин X1, Y1, X2, Y2, X3, Y3 i функцію обчислення площини трикутника по координатам його вершин AreaOfTriangle(X1, Y1, X2, Y2, X3, Y3, S).

6.Є дiйснi числа X1, Y1, X2, Y2,..., X10, Y10. Знайти периметр десятикутника, вершини якого мають координати (X1, Y1), (X2, Y2), (X3, Y3), ..., (X10, Y10). В програмi визначити функцiю розрахунку вiдстанi мiж двома точками, якi заданi своїми координатами Vidstan (X1, Y1, X2, Y2) i функцію визначення i виводу на екран значення периметра десятикутника

Area (L1, L2, L3, L4, L5, L6, L7, L8, L9, L10).

7.Є координати двох трiйок точок на площинi X11, Y11, X12, Y12, X13,Y13 i X21, Y21, X22, Y22, X23, Y23. З'ясувати, чи лежить один трикутник повнiстю всерединi iншого. Якщо це так - розрахувати рiзницю площ бiльшого i меншого трикутника. В програмi визначити логiчну функцiю TrianInTrian(X11,Y11, X12, Y12, X13, Y13, X21, Y21, X22, Y22, X23, Y23),

яка визначає чи лежить один трикутник повнiстю всерединi iншого, i функцію обчислення площі трикутника по координатах його вершин AreaOfTrian(X1, Y1, X2, Y2, X3, Y3, S).

8.Хай елементами прямокутного рівнобедреного трикутника є катет а (елемент номер 1), гіпотенуза b (елемент номер 2), висота h, проведена з вершини прямого кута на гіпотенузу (елемент номер 3), радіус вписаного кола r (елемент номер 4). Скласти програму, яка по заданому номеру одного із елементів трикутника обчислювала значення всіх інших його елементів. В програмі потрібні обчислення елементів трикутника провадити за допомогою функції (функцій) та передбачити введення даних (номера елемента та його значення) з клавіатури та виведення результатів розрахунків з коментарями на екран.

9.Написати програму, яка б визначала б значення n!. Введення числа (n ≥ 0) провадити

уфункції main(), а визначення факторіалу у функції рекурсивній функції fFactorial().

10.Написати програму, яка б розпізнавала повні квадрати, степені п’ятірки та прості числа. Введення числа провадити у функції main(), а розпізнавання повних квадратів, степенів п’ятірки та простих чисел у відповідних функціях, які мають логічний тип.

11.Пряма на площинi задається рiвнянням Ax + By + C = 0. Рівняння параболи

задається рівнянням Dx2 + Ex + F = 0. Написати програму, яка б запитувала з клавіатури значення коефіцієнтів рівнянь, визначала б за допомогою функції Intersect_Parab(), чи перетинає пряма у двох точках параболу, і якщо перетинає, то за допомогою функції Arial_Parab() визначала б площу замкнену між прямою та параболою. В кінці програма повинна вивести значення коефіцієнтів, повідомлення про перетин прямої та параболи і вирахувану площу.

12. Написати програму яка б визначала, парне чи непарне введене ціле число. Введення числа провадити у функції main(), а розпізнавання парності-непарності числа виконувати за допомогою функції у функції iEvenOrOdd(), яка має логічний тип.

79

13. Дано: натуральне n, дійсні a1, a2, K, an . Потрібно знайти наближені корені рівнянь

0.5(ai x)4 −cos(x)= 0 (i =1, 2, K, n). Кожне із рівнянь потрібно розв’язати методом ділення відрізка навпіл (дивіться приклад алгоритму 4.14. і приклад програми 4.15.в розділі 4). Корні потрібно шукати на відрізку [0, π 2], точність рішення і-го рівняння дорівнює ε =110n . В програмі:

описати функцію f (t, x)= 0.5(t x)4 −cos(x);

функцію root(t, eps) для знаходження кореню рівняння f(t, x)=0;

14. Написати програму обчислення синуса кута. В програмі передбачити:

формул приведення тригонометричних функцій обчислювати на sin(х) проміжку [−∞, + ∞].

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

ε =10−5 .

5.10.Контрольнi запитання.

1.Для чого в Сі iснують пiдпрограм? Що таке пiдпрограма ? Якi типи пiдпрограм є в Сі?

2.Оголошення функцій. Прототипи функцій.

3.Модифікатори типів змінних у функціях. Локальні змінні.

4.Модифікатори типів змінних у функціях. Глобальні змінні.

5.Модифікатори типів змінних у функціях. Зовнішні змінні.

6.Модифікатори типів змінних у функціях. Статичні змінні.

7.Параметри і аргументи функцій. Навести приклади.

8.Рекурсивні функції. Приклади.

9.На прикладах пояснiть використання стандартних математичних функцiй abs(X), fabs(X), log(X), exp(X), і log10(X).

10.На прикладах пояснiть використання стандартних математичних функцiй tan(X), cos(X), sin(X).

11.Наприкладахпояснiтьвикористаннястандартнихматематичнихфункцiйalog(X), clog(X).

12.Чи можна в головному програмному модулі використовувати iдентифiкатори, якi описанi в підпрограмі? Пояснiть, чому?

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

80