Лабораторна робота № 2 Побудова|шикування| рекурсивних функцій

Мета. Отримати тримати практичні навички навички побудови рекурсивних функцій

на С++.

Короткі теоретичні відомості

Функції в С++ служать для запису програмного коду безпосередньо вирішуваних|рішати| підзадач. Виконання програми завжди починається з функції main(). Коли при виконанні програми зустрічається ім'я функції, відбувається|походить| звернення до цієї функції, тобто управління передається функції. Після того, як функція виконала свою роботу, управління повертається в те місце, звідки функція була викликана|спричинена|.

У С/С++ код, що описує, роботу функції, називається визначенням функції і має вигляд:

Заголовок_функции

{

оператор

}

Заголовок функції містить

тип_функции имя_функции(список аргументів)

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

return значення;

В тому випадку, якщо функція не повертає жодного значення, її тип визначається ключовим|джерельним| словом void, і оператор return не використовується.

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

тип_функции имя_функции (список аргументів)

{

.

<умова завершення рекурсії>

}

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

Приклад. Написати рекурсивні функції визначення n! і .

#include <iostream.h>

#include <conio.h>

unsigned factor_n(int ); // прототип функції визначення n!

// опис функції визначення xn

float multy_x_n(float x, int n)

{

if(n>1) // умова продовження рекурсії

return x*multy_x_n(n-1); // рекурсивний виклик функції

else // умова зупинки рекурсії

return x; //повернення значення при останньому виклику функцією

//самої себе

}

// головна функція

void main(void)

{ int n;

float x;

cout<<"\nВведіть значення n для визначення n!:";

cin>>n;

cout<<"n!= "<<factor_n(n)<<endl;

cout<<" Введіть|запровадьте| значення х і n для визначення x^n: ";

cin>>x>>n;

cout<<"x^n= "<<multy_x_n(x,n);

getch();

}

//опис функції обчислення|підрахунку| n!

unsigned long factor_n(int n)

{ if(n>1) return n*factor_n(n-1);

else return 1;

}

Завдання до лабораторної роботи № 2

1. Вивчити правила побудови рекурсивних функцій на прикладі програм, що розглянуті в п.п. «Короткі теоретичні відомості» та «Приклад виконання лабораторної роботи №2». Перевірити роботу наведених програм.

2. |задачі|Написати програму, що дозволяє вирішити поставлену в індивідуальному завданні задачу з використанням рекурсивної функції.

Приклад виконання лабораторної роботи №2

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

Представимо операцію множення в загальному вигляді через операцію додавання:

, (2.1)

або в рекурсивному вигляді:

(2.2)

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

Формула (2.2) є підґрунтям для написання рекурсивної функції. В якості параметрів функції виступатимуть значення k та n. Тип функції визначається типом множника k, оскільки виходячи з умов задачі n є цілим. Використаємо більш загальний випадок, коли k має тип float. Тоді визначення рекурсивної функції має вигляд:

float dobutok(int n, float k)

{ if (n>0) //умова продовження рекурсії

return dobutok(n-1,k)+k; //визначення рекурсивної суми

else //умова припинення рекурсії

return 0;

}

Визначення рекурсивної суми проводиться в два етапи: спочатку виконується виклик рекурсивної функції dobutok() з параметром n, який зменшено на одиницю, після цього визначається рекурсивна сума як результат додавання до значення, отриманого в результаті рекурсивного виклику, значення параметра k .

2. Приклад побудови головної функції та виклику рекурсивної.

#include<iostream.h>

float dobutok(int n, float k);

void main()

{ float k;

int n;

cout<<”\nВведіть значення n та k”;

cin>>n>>k;

cout<<”\nЗначення n*k= ”<<dobutok(n,k); //виклик рекурсивної функції

}

Заголовок рекурсивної функції, який наведено в другому рядку програми, дозволяє компілятору визначити тип функції та список параметрів, але не саму функцію. За правилами мови C/C++ заголовок функції необхідно навести до її використання, що в даному випадку виконано. Опис самої функції, який наведено в попередньому пункті, можна навести після головної функції або в окремому файлі за умов його коректного підключення.

Зміст|вміст,утримання| звіту до лабораторної роботи №2

1. Титульний лист|аркуш|: назва дисципліни; номер і найменування роботи; прізвище, ім'я, по батькові студента; дата виконання.

2. Постановка завдання|задачі|.

3. Пояснення можливості використання рекурсії в поставленому завданні. Визначення основних змінних та функцій з|із| коментарями.

4. Реалізація функцій.

5. Лістинг основної програми, в якому повинно бути вказано, в якому місці і яка функція викликається|спричиняються|.

Варіанти завдань до лабораторної роботи №2

1. Написати рекурсивну функцію для знаходження біноміальних| коефіцієнтів, користуючись їх визначенням:

2. Задано ненегативні числа n і m. Необхідно обчислити|обчисляти,вичислити| функцію A(n, m), де

3. Задано натуральні числа с|із| і m. Необхідно обчислити|обчисляти,вичислити| функцію f(m)

де g(m) – залишок|остача| від ділення|поділки,розподілу,поділу| (m +c) на 10.

4. Обчислити|обчисляти,вичислити| функцію f(m), яка визначається для цілих позитивних чисел таким чином:

5. Обчислити|обчисляти,вичислити| числа Фібоначі, якщо відомо, що два перші числа F₁=F₂=1, а значення подальших|наступних| чисел дорівнює сумі двох попередніх чисел ( F_k=F_k-1+F_k-2 ): 1,1,2,3,5,8 і т.і.

6. Для заданого натурального числа n з'ясувати, чи можна представити|уявити| n! у вигляді добутку|добутку| трьох послідовних цілих чисел, тобто перевірити істинність виразу|вираження| n!= j(j+1)(j+2), знайшовши деяке число j.

7. Серед чисел 1.. n (n - ціле позитивне число  25) знайти все такі, запис яких співпадає|збігається| з|із| останніми цифрами запису їх квадрата (наприклад: 6²=36, 25²=625).

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

9. Для заданого цілого числа n обчислити|обчисляти,вичислити| .

10. Для заданого цілого числа n обчислити|обчисляти,вичислити| .

11. Для заданого цілого числа n обчислити|обчисляти,вичислити| .

12. Для заданого цілого числа n обчислити|обчисляти,вичислити| .

13. Для заданого цілого числа n обчислити|обчисляти,вичислити| .

14. Для заданого цілого числа n обчислити |обчисляти,вичислити|, де max5(x, у|в,біля|)-функція, що визначає більше з|із| двох значень х і у. Більшим з двох чисел вважається те|в,біля|, чий залишок|остача| від ділення|поділки,розподілу,поділу| на 5 є більшим.

15. Для заданого цілого числа n обчислити|обчисляти,вичислити| .

16. Для заданого цілого числа n обчислити|обчисляти,вичислити| .

17. Для заданого цілого числа n обчислити|обчисляти,вичислити|

18. Для заданого ненегативного числа n обчислити|обчисляти,вичислити|

19. Написати рекурсивну функцію, яка визначає максимальне число з|із| вхідної послідовності чисел х (умову завершення вводу чисел вибрати самостійно).

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

21. Написати рекурсивну функцію, яка визначає добуток |добуток| введених|запроваджених| негативних|заперечних| дійсних чисел х (умовою завершення обчислень|підрахунків| вважати|лічити| введення позитивного числа).

22. Написати рекурсивну функцію, яка визначає суму введених|запроваджених| дійсних чисел х, порядковий номер яких у вхідній послідовності кратний двом (умовою завершення обчислень|підрахунків| вважати|лічити| введення позитивного числа).

23. Обчислити|обчисляти,вичислити| величину , де х1, х2..,х_n (x_i2) – послідовність позитивних дійсних чисел, кількість яких наперед|заздалегідь| невідома (умову завершення вводу чисел вибрати самостійно).

24. Для введеного|запровадженого| цілого n обчислити|обчисляти,вичислити| a_02⁰+ a_12¹+ a_32³+.+ a_n2ⁿ, де а₀, а₁, а₃., а_n – приймають значення –1, 0,1 по черзі, тобто –1,0,1,-1,0,1, і т.д.

25. Написати рекурсивну функцію переводу|переведення,переказу| десяткового числа в двійкову систему шляхом ділення|поділки,розподілу,поділу| його на 2 і видачі залишку|остачі| в зворотній послідовності.

26. Для довільного цілого n визначити кількість чисел і їх суму в десятковому записі числа n!.

27. Визначити значення , де x_i – ненегативні числа (умову завершення вводу чисел вибрати самостійно).

28. Для довільного цілого n вивести на екран в зворотному порядку|ладі| проходження|дотримання| всі числа в десятковому записі значення n!.

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

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