/
AirLexa
/
03
Обзор
Документация
Войти
/
AirLexa
/
03
Код
Запросы
0
Задачи
Вики
Пакеты
0
Релизы
0
CI/CD
Аналитика
Безопасность
master
Lesson_02/Task2/Task_2.cpp
37 строк
2 KB
AirLexa
создали Lesson_02/Task2/Task_2.cpp
27 дек 2025, 10:47
27 дек 2025, 10:47
568debe
Код
Авторство
О чём код?
#include <iostream> #include <windows.h> int fib(int n, int pred_2, int pred_1, int& count) { count++; if (n == 0) return pred_2; if (n == 1) return pred_1; return fib(n - 1, pred_1, pred_2 + pred_1, count); } void print_fib(int num) { int count = 0; std::cout << num << "-e число Фибоначчи равно " << fib(--num, 0, 1, count) << ". Количество вызовов fib = " << count << std::endl; } int main() { SetConsoleCP(1251); SetConsoleOutputCP(1251); for (int i = 1; i < 21; i++) print_fib(i); return 0; } // Очевидно, что для вычисления текущего числа Фибоначчи нам достаточно // знать два предыдущих значения чисел, ибо результат - это их сумма. // Т.о. можно запоминать эти 2 предыдущих значения и передавать их в // следующую рекурсию как параметры функции. Этим мы добьемся того, что // все предыдущие числа Фибоначчи будут вычисляться только один раз. // Поэтому, как видно из работы данной программы, при увеличении числа Фибоначчи // в два раза, количество итераций возрастает тоже примерно в два раза, // что говорит нам о линейной зависимости О(n) по скорости. // Сложность алгоритма по памяти тоже будет линейна О(n), ибо дерево ветвлений // рекурсии не меняется.