5.2. Приклад алгоритму та програми

Одним із найпростіших прикладів рекурсії – це функція обчислення факторіала. Нагадаємо, що факторіалом n! натурального числа n називається добуток усіх цілих чисел від одиниці до n. Вважають також, що 0!=1. Обчислення факторіала зводиться до багаторазового застосування рекурентної формули n! = (n  1)!· n. Ця формула є рекурсивною, оскільки означує «факторіал через факторіал». Рекурсивне обчислення n! низхідним: «обчислити (n – 1)! і отримане значення помножити на n». При обчисленні (n – 1)! застосоване те саме правило: «обчислити (n – 2)! і отримане значення помножити на n – 1». Рекурсія являє нескінченний цикл, для її переривання необхідно визначити умову завершення рекурсії. Такою умовою буде рівність n нулеві.

Повне рекурсивне означення факторіала:

//ex4_9.cpp. Обчислення факторіала числа #include<iostream> using namespace std; int x; //число, факторіал якого необхідно обчислити int Factorial(int n) //оголошення функції { if (n==0) return 1; else return Factorial(n-1)*n; //рекурсивний виклик функції } int main() //головна функція { cout<<"calculate factorial"<<endl; cout<<"Enter x "<<endl; cin>>x; cout<<"x!="<<Factorial(x)<<endl; system("pause"); }

5.3. Варіанти завдань

1. Знайти суму цифр натурального числа n та значення глибини рекурсії, використовуючи рекурентне означення функції f(n):

Підказка. Умова продовження рекурсії: сума цифр числа дорівнює останній цифрі плюс сума цифр числа без останньої цифри (числа, що ділиться без остачі на 10). Умова закінчення рекурсії: якщо число дорівнює 0, то сума його цифр дорівнює 0.

2. Знайти кількість одиниць в двійковому представленні числа n та значення глибини рекурсії, використовуючи рекурентне означення функції f(n) (& - операція побітового логічного множення):

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

= ,

використовуючи рекурентне співвідношення:

Визначити глибину рекурсії.

4. Знайти значення функції Аккермана A(m, n), використовуючи рекурентне співвідношення:

Визначити глибину рекурсії.

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

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

Підказка. Використати рекурсію, визначивши рекурентне співвідношення:

7. Визначити рекурсивні функції зображення натурального числа у двійковій, вісімковій системах числення та у системі числення з основою N > 1 та глибину рекурсії. Числа у десятковій системі числення вводити з клавіатури.

8. Визначити рекурсивну функцію обчислення найбільшого спільного дільника НСД{п,т) натуральних чисел, яка ґрунтується на співвідношенні НСД(п,т) = НСД(т,r), де r -залишок від ділення п на т.

9. Визначена рекурсивна функцію через рекурентне співвідношення:

Визначити глибину рекурсії та обчислити функції за заданими значеннями :

10. Визначити рекурсивну функцію обчислення степеня дійсного числа з цілим показником , згідно з рекурентним співвідношенням:

11. Коефіцієнти розкладання бінома (a+b)ⁱ, тобто біноміальні коефіцієнти, утворюють і-й рядок трикутника Паскаля. Кожне число в трикутнику, крім перших трьох, є сумою чисел, розташованих над ним у попередньому рядку. Число в i-му рядку (i = 0, 1, 2, …) на j-му місці (j = 0, 1, …, i), задається формулою . «Верхівка» трикутника має наступний вигляд.

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

12. Написати рекурсивну функцію, яка методом ділення відрізання навпіл (методом дихотомії) знаходить з точністю корінь рівняння на відрізку (). Згідно з методом дихотомії, якщо i мають різні знаки, то між точками існує корінь . Нехай – середня точка в інтервалі . Якщо , то корінь . Якщо , то або і мають різні знаки, або і мають різні знаки. Якщо , то корінь лежить в інтервалі Інакше він лежить в інтервалі Процес продовжується доти, поки інтервал не стане менший . Визначити глибину рекурсії під час обчислення кореня рівняння.

13. Реалізувати генератор послідовності псевдовипадкових чисел {Vi} на основі рекурентного співвідношення V_i = (aV_i–1 + bV_i–2 + c) mod m, де a, b, c, m — довільні натуральні параметри. Перші два значення, V₁ і V₂, задаються випадково. Підібрати значення параметрів, за яких послідовність є схожою на випадкову.

14. Довести, що для перших чисел послідовності Фібоначчі справедлива формула: ,

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

Числа Фібоначчі визначаються рекурентним співвідношенням:

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

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

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

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

Підказка. З алгоритмом Карацуби початкові операнди множення подаються як вирази , де для 32-бітних процесорів, визначається як половина розміру (в 32-бітових словах) мінімального по довжині множника. Таким чином, початкові множники розбиваються на молодшу і старшу частині. Після розбиття операндів виконується розрахунок проміжних значень:

Результуючий добуток розраховується за формулою:

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

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

Підказка. Використати рекурентне співвідношення для чисел Фібоначчі.

20. Довести, що рекурсивна послідовність

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

21. Задані натуральні числа а, c, m. Визначити рекурсивну функцію та глибину рекурсії для обчислення за формулою:

, де

- залишок від ділення на 10.

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

23. По заданим b, p, m обчислити значення виразу . Обчислення виконати, використовуючи алгоритм, що базується на двійковому розкладанні показника степені p:

24. Функція f визначена так:

Обчислити значення , якщо

5.4 Контрольні запитання

1. Що таке рекурсивне визначення і рекурсивний об’єкт?

2. Визначити поняття рекурсії. Що таке рекурсивна підпрограма?

3. Як визначається глибина рекурсії?

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

5. Коли рекурсія неефективна і коли її необхідно уникати?

6. Чим викликається переповнення стеку під час рекурсії?

Покажчики Лабораторна робота 6

Мета роботи.

• ознайомитися з особливостями посилальних типів даних;

• опанувати технологію застосування посилальних типів даних;

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

6.1 Теоретичні відомості

6.1.1. Основні поняття

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

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