Вправи і задачі з теми "Рекурсія"

РЕКУРСІЯ

Задачі і вправи

Вправа І.

1. Опишіть процедуру пошуку найбільшого і найменшого елементів у масиві. За допомогою цієї процедури складіть програму, що визначає, чи співпадають найбільший і найменший елементи двох масивів А [1..n] і В [1..n].
   
2. Опишіть процедури пошуку середнього за величиною елемента у масиві А [1..2n+1] і середнє арифметичне елементів цього масиву. За допомогою цих процедур складіть програму, яка порівнює середнє за величиною і середнє арифметичне у масиві А [1..99].
   
3. Опишіть процедуру пошуку найбільшого і найменшого елементів у масиві А[1..n]. За допомогою цієї процедури складіть програму, що визначає координати вершин найменшого прямокутника зі сторонами, паралельними осям координат, який містить в собі множину точок Т1(X1,Y1), ... , Tn(Xn,Yn).
   
4. Опишіть процедуру перевірки розкладення натурального числа в суму двох квадратів. Складіть програму, яка вибирає з даного масиву ті і тільки ті числа, які розкладаються в суму двох квадратів.
   
5. Опишіть функцію перевірки простоти числа. Опишіть функцію перевірки числа на розкладність в суму виду 1+2а. Складіть програму, яка вибирає з даного масиву чисел ті і тільки ті його елементи, які задовольняють обом властивостям.
   
6. Опишіть процедуру перетворення цілого числа з десяткової системи в p-ічну систему числення. Опишіть процедуру перетворення правильного десяткового дробу в p-ічний з заданою кількістю розрядів. Складіть програму перетворення довільного дійсного числа з 10-вої в p-ічну систему числення.
   
7. Опишіть процедуру пошуку найменшого елемента в рядку матриці. Опишіть функцію перевірки на максимальність даного елемента в стовпці матриці. Складіть програму пошуку сідлової точки матриці.
   

Вправи II.

1. Опишіть функцію f(x) - найбільший власний дільник числа х. Складіть програму пошуку всіх власних дільників числа N.
   
2. Опишіть функцію y = arcsin(x). Складіть програму розв’язку рівняння sin(ax+b) = c.
   
3. Опишіть функцію f(x) - число, яке отримується з натурального числа x пере¬становкою цифр у зворотному порядку. Складіть програму, яка роздруковує симетричні числа з масиву натуральних чисел.
   

Задачі.

1. Перечислити всі вибірки по K елементів у масиві A з N елементів. Масив містить перші N натуральних чисел: A[i] = i. Знайти їх кількість і оцінити складність алгоритму.
   
2. Перечислити всі підмножини множини (масиву A) з задачі 1. Знайти їх кількість і оцінити складність алгоритму.
   
3. Дано масив A[1..n] цілих додатних чисел і ціле число b. Перечислити всі набори індексів j1, j2, ..., jk такі, що A[j1] + A[j2] + ... + A[jk] = b. Оцінити складність алгоритму.
   
4. Дано масив A[1..n] цілих чисел і ціле число b. Перечислити всі набори індексів j1, j2, ... , jk такі, що A[j1] + A[j2] + ... + A[jk] = b. Оцінити складність алгоритму.
   
5. Відома в теорії алгоритмів функція Акермана А(x, y) визначена на множні натуральних чисел рекурсивно:
   

A(0, y) = y + 1,
A(x, 0) = A(x - 1, 1),
A(x, y) = A(x - 1, A(x, y - 1));
a) Опишіть функції A(1, y), A(2, y), A(3, y), A(4, y) явним чином;
б) Реалізуйте рекурсивну програму обчислення A(x, y);
в) Реалізуйте програму обчислення A(x, y) без рекурсії.

Джерело: Гуржій Андрій Миколайович, 
Львов Михайло Сергійовий, 
Співаковський Олександр Володимирович

Основи програмування 
355 с.:іл.