Вычисление чисел Фибоначчи

Постановка задачи

Вычислить $F_{n}$, где $F_{n}$ — $n$-е число Фибоначчи, задаваемое рекуррентным соотношением:

• $F_{1}=1$
• $F_{2}=1$
• $F_{n}=F_{n-1}+F_{n-2}$, n > 2

Рекурсивное решение

Если напрямую написать решение этой задачи, переписав рекурсию в код, то получим экспоненциальное время выполнения, ведущее себя примерно как $\Phi ^{n}$, где $\Phi$ — w:золотое сечение.

Приведем C++ — код этой функции:

//Внимание: функция имеет экспоненциальное время выполнения и неэффективно использует стэк.
//Функция возвращает n-e число Фибоначчи по данному n.
int fib(int n)
{
    if (n <= 2) return 1;
    else
    {
       return fib(n - 1) + fib(n - 2);
    }
}

Решение с помощью динамического программирования

В данном случае организовать запоминание перекрывающихся подзадач очень легко — заведем массив dp, dp[i] будет значением $F_{i}$. В этой задаче легко организовать восходящее ДП, так как мы знаем, что для вычисления $F_{n}$ понадобятся $F_{n-1}$ и $F_{n-2}$. Асимптотическая сложность алгоритма будет O(n) время и O(n) памяти.(Требуется массив и один проход по массиву).

Код функции, реализующий восходящее ДП:

//возвращает n-e число Фибоначчи
int fib_n(int n)
{
    if (n <= 2) return 1;
    std::vector<int> dp(n + 1);
    dp[1] = 1; dp[2] = 1;
    for (int i = 3; i <= n; i++)
    {
       dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
}

Элегантное решение

Приведем ещё одно решение — оно использует также как и динамическое программирование O(n) времени, но обходится всего O(1) памяти. Решение основывается на том, что для вычисления следующего числа нужно помнить всего 2 предыдущих, а не все предыдущие.

Приведем С++ — код:

//возвращает n-е число Фибоначчи
int fib_n(int n)
{
	if (n <= 2) return 1;
	//F(n-2)
	int x = 1;
	//F(n-1)
	int y = 1;
	//F(n)
	int ans = 0;
	for (int i = 3; i <= n; i++)
	{
		ans = x + y;
		x = y;
		y = ans;
	}
	return ans;
}