Розв'язання задач на використання рекурсивних алгоритмів
Автор: Anonim Nkzk • Май 1, 2023 • Лабораторная работа • 1,736 Слов (7 Страниц) • 225 Просмотры
Лабораторна робота №6
Розв'язання задач на використання рекурсивних алгоритмів
Мета роботи: вивчити рекурсивні алгоритми та основні схеми розв'язання задач рекурсивними способами, навчитися застосовувати рекурсивні алгоритми під час вирішення завдань.
Загальні вказівки
Під час виконання лабораторної роботи для кожного завдання потрібно написати програму мовою С++ (або Python), яка отримує на вході числові дані, виконує їх обробку відповідно до вимог завдання та виводить результат на екран. Для обробки даних потрібно реалізувати рекурсивну функцію. Введення даних здійснюється з клавіатури з урахуванням вимог до вхідних даних, що містяться у постановці. Введення даних супроводжуйте діалогом.
Теоретичні відомості.
Ознайомтеся із матеріалом лекцій.
Завдання до лабораторної роботи.
Виконайте наведені нижче завдання.
1. Знайдіть суму факторіалів перших n натуральних чисел. Вирішіть двома способами: через безпосереднє обчислення факторіалів (за допомогою рекурсивного алгоритму) та за допомогою наближеної функції.
[pic 1]
Оцініть трудомісткість розрахунків для кожного алгоритму (обчисливши час виконання програми для різних n).
- Код програми на мові С++ для обчислення суми факторіалів перших n натуральних чисел за допомогою безпосереднього обчислення факторіалів:
#include <iostream>
using namespace std;
// функція обчислення факторіалу числа n
int factorial(int n) {
if (n <= 1) {
return 1;
}
return n * factorial(n-1);
}
int main() {
int n, sum = 0;
cout << "Введіть натуральне число n: ";
cin >> n;
// обчислення суми факторіалів перших n натуральних чисел
for (int i = 1; i <= n; i++) {
sum += factorial(i);
}
cout << "Сума факторіалів перших " << n << " натуральних чисел: " << sum << endl;
return 0;
}
Даний код на мові C++ обчислює суму факторіалів перших n натуральних чисел.
Спочатку програма отримує введення від користувача натурального числа n за допомогою функції cin.
Далі, для обчислення суми факторіалів перших n натуральних чисел використовується цикл for. На кожній ітерації циклу обчислюється факторіал поточного числа i за допомогою функції factorial. Отриманий факторіал додається до змінної sum, яка зберігає суму факторіалів перших n натуральних чисел.
Функція factorial обчислює факторіал числа n рекурсивно. Якщо введене число n менше або дорівнює 1, функція повертає 1 (так як факторіал 0 та 1 дорівнює 1). В іншому випадку, функція повертає n помножене на факторіал (n-1).
Нарешті, програма виводить отриману суму факторіалів перших n натуральних чисел на екран за допомогою функції cout.
- Код програми на мові С++ для обчислення суми факторіалів перших n натуральних чисел за допомогою наближеної функції:
#include <iostream>
#include <cmath>
using namespace std;
// функція обчислення наближеної функції для факторіалу числа n
double approx_factorial(int n) {
if (n == 0) {
return 1.0;
}
double x = n + 1.0;
return sqrt(2.0 * M_PI * x) * pow((x/M_E), x) * exp(1.0/(12.0*x));
}
int main() {
int n;
double sum = 0.0;
cout << "Введіть натуральне число n: ";
cin >> n;
// обчислення суми факторіалів перших n натуральних чисел за допомогою наближеної функції
for (int i = 1; i <= n; i++) {
sum += approx_factorial(i);
}
cout << "Сума факторіалів перших " << n << " натуральних чисел: " << sum << endl;
return 0;
}
Основна функція програми main містить наступні кроки:
- Об'являється змінна n, яка буде містити значення натурального числа, введеного користувачем.
- Об'являється змінна sum, яка буде містити суму факторіалів перших n натуральних чисел.
- Користувачеві виводиться повідомлення, щоб він ввів натуральне число n.
- Користувач вводить натуральне число n.
- За допомогою циклу for обчислюється сума факторіалів перших n натуральних чисел за допомогою наближеної функції approx_factorial.
- Результат обчислень виводиться на екран.
Функція approx_factorial обчислює наближене значення факторіалу числа n за допомогою наступного алгоритму:
...