Вычисление чисел Фибоначчи
Постановка задачи
правитьВычислить , где — -е число Фибоначчи, задаваемое рекуррентным соотношением:
- , n > 2
Рекурсивное решение
правитьЕсли напрямую написать решение этой задачи, переписав рекурсию в код, то получим экспоненциальное время выполнения, ведущее себя примерно как , где — золотое сечение.
Приведем C++ — код этой функции:
//Функция возвращает n-e число Фибоначчи по данному n.
int fib(unsigned int n)
{
if (n < 2) return n;
return fib(n - 1) + fib(n - 2);
}
Как недостаток, функция имеет экспоненциальное время выполнения и неэффективно использует стек, и при больших n возможно переполнение стека (англ. stack overflow).
Решение с помощью динамического программирования
правитьВ данном случае организовать запоминание перекрывающихся подзадач очень легко — заведем массив dp, dp[i] будет значением . В этой задаче легко организовать восходящее ДП, так как мы знаем, что для вычисления понадобятся и . Асимптотическая сложность алгоритма будет O(n) время и O(n) памяти.(Требуется массив и один проход по массиву).
Код функции, реализующий восходящее ДП:
//возвращает n-e число Фибоначчи
int fib_n(int n)
{
if (n < 2) return n;
int dp[n];
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)
int x = 1;
//F(n-1)
int y = 0;
for (int i = 0; i < n; i++)
{
x += y;
y = x - y;
}
return y;
}
Приведем 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;
}
То же на языке Python:
#возвращает n-е число Фибоначчи
def fib(n):
a = 1
b = 1
c = 1
rc = 0
d = 0
rd = 1
while n>0:
if n%2!=0: #Если степень нечетная
# Умножаем вектор 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