Добавлен: 09.01.2024
Просмотров: 87
Скачиваний: 1
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
МИНИСТЕРСТВО ЦИФРОВОГО РАЗВИТИЯ, СВЯЗИ И МАССОВЫХ КОММУНИКАЦИЙ РОССИЙСКОЙ ФЕДЕРАЦИИФедеральное государственное бюджетное образовательное учреждение высшего образования «Санкт-Петербургский государственный университет телекоммуникаций им. проф. М. А. Бонч-Бруевича»(СПбГУТ)Факультет Информационных систем и технологийКафедра Безопасности информационных системОтчетПо предмету «Алгоритмы и структуры данных»о практической работе №2:«Понятие рекурсии. Рекурсивные функции» Выполнил студент гр. ИСТ-022:Волков Кирилл // //оценка Проверил: Бородянский Ю.М. // //ПодписьЗадача работыИзучить понятия рекурсии, рекурсивные функции в программировании, научиться применять рекурсивные методы в решении задач на языке С++, разработать программу по вычислению суммы кубов цифр числа и доказать, что, независимо от входного числа, результат работы программы сводится к числу 153. Приобрести навыки и умения анализа алгоритма и всего кода разработанной программы в Big-O-нотации.Ход работыСуть разработанного алгоритма: на входе даётся число, далее проверяется условие кратности трём, затем в случае «true», вызывается рекурсивная функция с вычислением суммы кубов цифр полученного числа, до тех пор, пока число не будет равно 153.Блок-схема
Рассчет сложности Big-OОтвет: общая сумма сложности двух функций O(1) + O(n^2) = O(n^2)Рекурсивная триада:Параметр: число( numb )База рекурсии: 1305Декомпозиция: два цикла whileРезультат работы программы
Время работы с рекурсией
Время работы линейного алгоритма
ВыводВ результате работы была разработана программа, которая вычисляет сумму цифр куба числа, а затем повторяет вычисление с полученной суммой, и доказывает, что любое число при таком алгоритме сводится к 153.На практике были применены знания о рекурсивных функциях.В результате вычислений разных чисел, не была выявлено конкретной зависимости количества итераций от числа. В большинстве случаев – чем больше число, тем больше итераций.Была проведена работа по анализу программного кода и была вычислена сложность в нотации Big-O.Код программы смотрите в приложении 1Приложение 1#include
#include
#include
using namespace std;
int count_ = 0;
int f_recurs(int numb){
int cube=0;
count_ += 1;
cout<<"\nИтерация №"<
while (numb != 0){
cube += (numb%10) * (numb%10) * (numb%10);
numb = numb / 10;
}
cout<<"\nСумма кубов цифр числа = "<
numb = cube;
if ( numb != 153)
f_recurs(numb);
return 0;
}
int main()
{
SetConsoleOutputCP(1251);
SetConsoleCP(1251);
int numb;
cout<<"Введите натуральное число :";
cin>>numb;
if(numb%3==0)
{
f_recurs(numb);
}
else
cout<<"Число не кратно трём";
return 0;
}
г. Санкт-Петербург
2021
Рассчет сложности Big-OОтвет: общая сумма сложности двух функций O(1) + O(n^2) = O(n^2)Рекурсивная триада:Параметр: число( numb )База рекурсии: 1305Декомпозиция: два цикла whileРезультат работы программы
Время работы с рекурсией
Время работы линейного алгоритма ВыводВ результате работы была разработана программа, которая вычисляет сумму цифр куба числа, а затем повторяет вычисление с полученной суммой, и доказывает, что любое число при таком алгоритме сводится к 153.На практике были применены знания о рекурсивных функциях.В результате вычислений разных чисел, не была выявлено конкретной зависимости количества итераций от числа. В большинстве случаев – чем больше число, тем больше итераций.Была проведена работа по анализу программного кода и была вычислена сложность в нотации Big-O.Код программы смотрите в приложении 1Приложение 1#include #include
#include
using namespace std;
int count_ = 0;
int f_recurs(int numb){
int cube=0;
count_ += 1;
cout<<"\nИтерация №"<
while (numb != 0){
cube += (numb%10) * (numb%10) * (numb%10);
numb = numb / 10;
}
cout<<"\nСумма кубов цифр числа = "<
numb = cube;
if ( numb != 153)
f_recurs(numb);
return 0;
}
int main()
{
SetConsoleOutputCP(1251);
SetConsoleCP(1251);
int numb;
cout<<"Введите натуральное число :";
cin>>numb;
if(numb%3==0)
{
f_recurs(numb);
}
else
cout<<"Число не кратно трём";
return 0;
}
г. Санкт-Петербург
2021