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

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

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

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

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

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

Приведем 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] будет значением $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 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

Решение быстрым возведением матрицы в степень

Существует более эффективное решение данной задачи с помощью быстрого возведения матрицы в степень. Оно основано на следующем тождестве:

${\begin{pmatrix}1&1\\1&0\end{pmatrix}}^{n}={\begin{pmatrix}F_{n+1}&F_{n}\\F_{n}&F_{n-1}\end{pmatrix}}.$

Для удобства обозначим матрицу, возводимую в степень, как P:

$P={\begin{pmatrix}1&1\\1&0\end{pmatrix}}.$

Без учета затрат на реализацию длинной арифметики этот алгоритм требует $O(log(n))$ времени и $O(1)$ памяти.

Ниже этот алгоритм реализован на языке С. Будем считать, что:

$A={\begin{pmatrix}a&b\\c&d\end{pmatrix}}$ — временная матрица, используемая в алгоритме возведения в степень. Инициализируется матрицей $P$.

$R={\begin{pmatrix}rc&rd\end{pmatrix}}$ — вектор результатов (вторая строка матрицы $P^{n}$), инициализируется как вторая строка единичной матрицы.

//возвращает 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