47
правок
Вычисление чисел Фибоначчи: различия между версиями
Перейти к навигации
Перейти к поиску
откат вандализма
Нет описания правки |
Drawiz (обсуждение | вклад) (откат вандализма) |
||
|
== Постановка задачи ==
Вычислить <math>F_n</math>, где <math>F_n</math> — <math>n</math>-е [[w:Числа Фибоначчи|число Фибоначчи]], задаваемое [[w:Рекуррентная последовательность|рекуррентным]] соотношением:
* <math> F_1 = 1 </math>
* <math> F_2 = 1 </math>
* <math> F_n = F_{n - 1} + F_{n - 2}</math>, n > 2
== Рекурсивное решение ==
Если напрямую написать решение этой задачи, переписав рекурсию в код, то получим экспоненциальное время выполнения, ведущее себя примерно как <math> \Phi^n </math>, где <math> \Phi </math> — [[w:золотое сечение]].
Приведем [[C++]] — код этой функции:
<source lang="cpp">
//Внимание: функция имеет экспоненциальное время выполнения и неэффективно использует стэк.
//Функция возвращает n-e число Фибоначчи по данному n.
int fib(int n)
{
if (n <= 2) return 1;
else
{
return fib(n - 1) + fib(n - 2);
}
}
</source>
== Решение с помощью динамического программирования ==
В данном случае организовать запоминание перекрывающихся подзадач очень легко — заведем массив dp, dp[i] будет значением <math> F_i </math>. В этой задаче легко организовать восходящее [[Динамическое программирование|ДП]], так как мы знаем, что для вычисления <math>F_n</math> понадобятся <math>F_{n-1}</math> и <math>F_{n-2}</math>. Асимптотическая сложность алгоритма будет [[O-большое|O]](n) время и O(n) памяти.(Требуется массив и один проход по массиву).
Код функции, реализующий восходящее ДП:
<source lang="cpp">
//возвращает 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];
}
</source>
== Элегантное решение ==
Приведем ещё одно решение — оно использует также как и динамическое программирование O(n) времени, но обходится всего O(1) памяти. Решение основывается на том, что для вычисления следующего числа нужно помнить всего 2 предыдущих, а не все предыдущие.
Приведем С++ — код:
<source lang="cpp">
//возвращает 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;
}
</source>
| |||