Посчитать количество раз выполнения функции

@Snaces · Регистрация: 03.11.2019

Author24 — интернет-сервис помощи студентам

Программист Вася написал вычисление ��-ого числа Фибоначчи с помощью рекурсивной функции,
которая выглядит следующим образом:

Python

def fibonacci(n):
    if n < 3:
        return 1
    else:
        return fibonacci(n - 1) + fibonacci(n - 2)

Сколько раз запустится эта функция прежде, чем будет получено значение?
На вход программе подаётся одно натуральное число. Программа должна вывести одно
натуральное число — ответ на вопрос задачи. Гарантируется, что ответ не превосходит 10^18
Мой код:
Выдаёт ошибку превышено максимальное время работы, подскажите пожалуйста как исправить

C++

#include <string>
#include <iostream>
 
unsigned long int fibonacci(int n);
int main()
{
    int n;
    std::cin >> n;
    std::cout << fibonacci(n);
    return 0;
}
/////////////////
unsigned long int count = 1;
unsigned long int fibonacci(int n)
{
    if (n < 3)
    {
        return count;
    }
    else
    {
        count += 2;
        fibonacci(n - 1) + fibonacci(n - 2);
    }
}

Vourhey · 17.11.2019, 21:41

Сообщение от Snaces

std::cout << fibonacci(n);

А что здесь выводить, если функция fibonacci ничего не возвращает? Допустим, я ввел 10. Возврат count делают только вложенные вызовы.

@Snaces · 17.11.2019, 21:49 **[ТС]**

Vourhey, да ты ввёл 10, выведет 109, количество раз вызова функции Fibonacci. У меня ошибка из за большого времени работы, а так алгоритм же правильный

Vourhey · 17.11.2019, 21:57

Сообщение от Snaces

а так алгоритм же правильный

Нет, неправильный. Если я введу 10, то никакого return в самом первом вызове функции у меня не будет, потому что n<3 для 10 не случится. Не суть.
По поводу того, сколько раз запустится, я думаю, что задача подразумевает не имитацию рекурсивных вызовов. Ты должен вывести формулу по Васиному коду, как посчитать кол-во вызовов. А не переписать Васин же код с подсчетом.

@Snaces · 17.11.2019, 22:02 **[ТС]**

Vourhey, можешь тогда помочь с формулой и кодом, потому что я туплю если честно

Vourhey Почетный модератор 7393 / 2639 / 281 Регистрация: 29.07.2006 Сообщений: 13,696
	17.11.2019, 21:41	2
	Сообщение от Snaces std::cout << fibonacci(n); А что здесь выводить, если функция fibonacci ничего не возвращает? Допустим, я ввел 10. Возврат count делают только вложенные вызовы. 0

@Snaces 0 / 0 / 0 Регистрация: 03.11.2019 Сообщений: 36
	17.11.2019, 21:49 [ТС]	3
	Vourhey, да ты ввёл 10, выведет 109, количество раз вызова функции Fibonacci. У меня ошибка из за большого времени работы, а так алгоритм же правильный 0

Vourhey Почетный модератор 7393 / 2639 / 281 Регистрация: 29.07.2006 Сообщений: 13,696
	17.11.2019, 21:57	4
	Сообщение от Snaces а так алгоритм же правильный Нет, неправильный. Если я введу 10, то никакого return в самом первом вызове функции у меня не будет, потому что n<3 для 10 не случится. Не суть. По поводу того, сколько раз запустится, я думаю, что задача подразумевает не имитацию рекурсивных вызовов. Ты должен вывести формулу по Васиному коду, как посчитать кол-во вызовов. А не переписать Васин же код с подсчетом. 1

@Snaces 0 / 0 / 0 Регистрация: 03.11.2019 Сообщений: 36
	17.11.2019, 22:02 [ТС]	5
	Vourhey, можешь тогда помочь с формулой и кодом, потому что я туплю если честно 0