Файл: Понятия рекурсии. Рекурсивные функции по дисциплине Алгоритмы и структуры данных.docx
Добавлен: 21.11.2023
Просмотров: 85
Скачиваний: 2
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
ФЕДЕРАЛЬНОЕ АГЕНТСТВО СВЯЗИФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ОБРАЗОВАНИЯ«САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ТЕЛЕКОММУНИКАЦИЙ ИМ. ПРОФ. М.А. БОНЧ-БРУЕВИЧА»(СПбГУТ)Кафедра безопасности информационных системОТЧЁТпо практической работе №5 на тему: «Понятия рекурсии. Рекурсивные функции»по дисциплине «Алгоритмы и структуры данных»Выполнил: студент группы ИБ-92вп Кадамов Ш.Ф.«15» апреля 2021 г. ___________/Кадамов Ш.Ф./ Принял: к.ф.-м.н., доцент, И.А. Моисеев «ХХ» апреля 2021 г. ___________/ И.А. Моисеев /САНКТ-ПЕТЕРБУРГ2021
Числа 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 за наименьшее количество операций. Определить количество операций.
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 задач по этой теме помогли мне с этим, всё работает исправно, значит, цель была достигнута.
Цель работы
Цель работы: изучить понятия рекурсии, рекурсивные функции в программировании, приемы построения рекурсивной триады при решении задач, научиться применять рекурсивные методы в решении задач на языке С++.Задачи:Задача 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#includeusing 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 задач по этой теме помогли мне с этим, всё работает исправно, значит, цель была достигнута.