Вычисление чисел Фибоначчи: различия между версиями
Iniquity (обсуждение | вклад) доп тема |
|||
Строка 145: | Строка 145: | ||
</source> |
</source> |
||
{{Темы|Программирование}} |
{{Темы|Программирование|Математический анализ}} |
||
[[Категория:Математический анализ]] |
Версия от 21:01, 6 марта 2016
Постановка задачи
Вычислить , где — -е число Фибоначчи, задаваемое рекуррентным соотношением:
- , n > 2
Рекурсивное решение
Если напрямую написать решение этой задачи, переписав рекурсию в код, то получим экспоненциальное время выполнения, ведущее себя примерно как , где — золотое сечение.
Приведем C++ — код этой функции:
//Внимание: функция имеет экспоненциальное время выполнения и неэффективно использует стэк.
//Функция возвращает n-e число Фибоначчи по данному n.
int fib(int n)
{
if (n == 0) { return 0; }
else
{
if ((n == -1) || (n == 1)) { return 1; }
else
{
if (n > 0) { return fib(n - 1) + fib(n - 2); }
else { return fib(n + 2) - fib(n + 1); }
}
}
}
Решение с помощью динамического программирования
В данном случае организовать запоминание перекрывающихся подзадач очень легко — заведем массив dp, dp[i] будет значением . В этой задаче легко организовать восходящее ДП, так как мы знаем, что для вычисления понадобятся и . Асимптотическая сложность алгоритма будет 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];
}
Код функции на Python, возвращающий последовательность чисел с помощью списка:
def fibo(n):
f = [0, 1]
for i in range(2, n + 1):
f.append(f[i-1] + f[i-2])
print(f)
n = 10
fibo(n) # [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55]
Элегантное решение
Приведем ещё одно решение — оно использует также как и динамическое программирование O(n) времени, но обходится всего O(1) памяти. Решение основывается на том, что для вычисления следующего числа нужно помнить всего 2 предыдущих, а не все предыдущие.
Приведем С++ — код:
//возвращает n-е число Фибоначчи
int fib_n(int n)
{
//F(n-2)
int x = 1;
//F(n-1)
int y = 0;
//F(n)
int ans;
for (int i = 2; i <= n; i++)
{
ans = x + y;
x = y;
y = ans;
}
return ans;
}
Приведем Python — код:
# возвращает последовательность чисел
def fibo(n):
a = 0
b = 1
print(a, b, end=' ')
for i in range(2, n + 1):
c = a + b
a, b = b, c
print(c, end=' ')
n = 10
fibo(n) # 0 1 1 2 3 5 8 13 21 34 55
Решение быстрым возведением матрицы в степень
Существует более эффективное решение данной задачи с помощью быстрого возведения матрицы в степень. Оно основано на следующем тождестве:
Для удобства обозначим матрицу, возводимую в степень, как P:
Без учета затрат на реализацию длинной арифметики этот алгоритм требует времени и памяти.
Ниже этот алгоритм реализован на языке С. Будем считать, что:
- — временная матрица, используемая в алгоритме возведения в степень. Инициализируется матрицей .
- — вектор результатов (вторая строка матрицы ), инициализируется как вторая строка единичной матрицы.
//возвращает n-е число Фибоначчи
int fib(int n)
{
int a = 1, ta,
b = 1, tb,
c = 1, rc = 0, tc,
d = 0, rd = 1;
while (n)
{
if (n & 1) // Если степень нечетная
{
// Умножаем вектор R на матрицу A
tc = rc;
rc = rc*a + rd*c;
rd = tc*b + rd*d;
}
// Умножаем матрицу A на саму себя
ta = a; tb = b; tc = c;
a = a*a + b*c;
b = ta*b + b*d;
c = c*ta + d*c;
d = tc*tb+ d*d;
n >>= 1; // Уменьшаем степень вдвое
}
return rc;
}