Файл: Понятия рекурсии. Рекурсивные функции по дисциплине Алгоритмы и структуры данных.docx
Добавлен: 21.11.2023
Просмотров: 22
Скачиваний: 1
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
ФЕДЕРАЛЬНОЕ АГЕНТСТВО СВЯЗИ
ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ОБРАЗОВАНИЯ
«САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ТЕЛЕКОММУНИКАЦИЙ ИМ. ПРОФ. М.А. БОНЧ-БРУЕВИЧА»
(СПбГУТ)
Кафедра безопасности информационных систем
ОТЧЁТ
по практической работе №5 на тему:
«Понятия рекурсии. Рекурсивные функции»
по дисциплине «Алгоритмы и структуры данных»
Выполнил: студент группы ИБ-92вп Кадамов Ш.Ф.
«15» апреля 2021 г. ___________/Кадамов Ш.Ф./
Принял: к.ф.-м.н., доцент, И.А. Моисеев
«ХХ» апреля 2021 г. ___________/ И.А. Моисеев /
САНКТ-ПЕТЕРБУРГ
2021
Цель работы
Цель работы: изучить понятия рекурсии, рекурсивные функции в программировании, приемы построения рекурсивной триады при решении задач, научиться применять рекурсивные методы в решении задач на языке С++.
Задачи:
Задача 1.
Определите закономерность формирования членов последовательности. Найдите n -ый член последовательности: 1, 1, 2, 3, 5, 8, 13, ...
Задача 2.
Разработать алгоритм и программу вычисления числа сочетаний из n элементов по m:
Числа n и m вводятся с клавиатуры (n
m). Решить задачу рекурсивно, выразив вычисление 
через
Задача 3.
Найдите наибольший общий делитель двух натуральных чисел с помощью алгоритма Евклида, используя рекурсивный и не рекурсивный (итерационный) алгоритмы. Определить оценку сложности и провести сравнительный анализ двух алгоритмов
Задача 4.
Дано натуральное число, кратное 3. Получите сумму кубов цифр этого числа, затем сумму кубов получившегося числа и т.д. Проверьте на нескольких примерах, что любая такая последовательность чисел сходится к числу 153. Определить зависимость между вводимыми числами и количеством итераций.
21=>8+1=9=>729=>343+8+729=1080=1+512=513=>153
Задача 5.
Исполнитель умеет выполнять два действия: "+1", "*2". Составьте рекурсивную функцию для программы получения из числа 1 числа 100 за наименьшее количество операций. Определить количество операций.
Результаты выполнения работы
Задача 1
#include
using namespace std;
int main()
{
setlocale(LC_ALL, "Russian");
int it;
int f0 = 0;
int f1 = 1;
int f;
cout << "Введите количество итераций:\n";
cin >> it;
cout << f0 + f1 << " ";
for (int i = 1; i < it; i++)
{
cout << f0 + f1 << " ";
f = f1;
f1 += f0;
f0 = f;
}
cout << "\nn -ый член последовательности = " << f1 << endl;
}
Скриншот 1:
Задача 2
#include
using namespace std;
int CB(int n, int m)
{
int c;
if (m > n / 2) m = n - m;
if (m == 1) return n;
if (m == 0) return 1;
if (n + m >= 90)
{
c = CB(n - 1, m);
c += CB(n - 1, m - 1);
}
else
{
c = 1;
for (int i = 1; i <= m; ++i)
{
c *= n - m + i;
c /= i;
}
}
return c;
}
int main()
{
setlocale(LC_ALL, "Russian");
int n, m;
cout << "Введите n: ";
cin >> n;
cout << "Введите m: ";
cin >> m;
if (n >= m)
cout << "\nКоличество сочетаний: " << CB(n, m) << endl;
}
Скриншот 2:
Задача 3
#include
using namespace std;
int recurs(int a, int b)
{
if (a != 0 && b != 0)
{
if (a > b)
{
a %= b;
recurs(a, b);
}
else
{
b %= a;
recurs(a, b);
}
}
else
{
return a + b;
}
}
int iter(int a, int b)
{
for (int i = 0; i < a + b; i++)
{
if (a != 0 && b != 0)
{
if (a > b)
{
a %= b;
}
else
{
b %= a;
}
}
else
{
return a + b;
}
}
}
int main()
{
setlocale(LC_ALL, "Russian");
int n, m;
cout << "Введите первое натуральное число: ";
cin >> n;
cout << "Введите второе натуральное число: ";
cin >> m;
cout << "\nНОД с помощью рекурсивного алгоритма = " << recurs(n, m) << endl;
cout << "НОД с помощью итерационного алгоритма = " << iter(n, m) << endl;
}
Скриншот 3:
Задача 4
#include
using namespace std;
int kub(int n)
{
int C = 0;
if (n >= 10)
{
C += kub(n / 10);
}
int a = n % 10;
C += a * a * a;
return C;
}
int main()
{
setlocale(LC_ALL, "Russian");
int b;
cout << "Введите число кратное 3-ём: ";
cin >> b;
cout << endl << b;
if ((b % 3) == 0)
{
while (b != 153)
{
b = kub(b);
cout << " --> " << b;
}
}
cout << endl;
}
Скриншот 4:
Скриншот 5:
Скриншот 6:
Задача 5
#include
using namespace std;
int recurs(int a)
{
int b = 1;
if (a != 1)
{
if ((a % 2) == 0)
{
a /= 2;
b += recurs(a);
}
else
{
a -= 1;
b += recurs(a);
}
}
return b;
}
int main()
{
setlocale(LC_ALL, "Russian");
int c;
c = recurs(100);
cout << "Количество операций = " << c << endl;
}
Скриншот 7:
Выводы
Цель работы была - изучить понятия рекурсии, рекурсивные функции в программировании, приемы построения рекурсивной триады при решении задач, научиться применять рекурсивные методы в решении задач на языке С++, считаю, что 5 задач по этой теме помогли мне с этим, всё работает исправно, значит, цель была достигнута.