Вычисление чисел Фибоначчи: различия между версиями

 

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

//Внимание: функция имеет экспоненциальное время выполнения и неэффективно использует стэк.

//Функция возвращает n-e число Фибоначчи по данному n.

return fib(n - 1) + fib(n - 2);

}

 

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

 

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

//возвращает n-e число Фибоначчи

int fib_n(int n)

return dp[n];

}

 

Код функции на Python, возвращающий последовательность чисел с помощью списка:

def fibo(n):

f = [0, 1]

n = 10

fibo(n) # [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55]

 

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

 

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

//возвращает n-е число Фибоначчи

int fib_n(int n)

return y;

}

 

Приведем Python — код:

# возвращает последовательность чисел

def fibo(n):

n = 10

fibo(n) # 0 1 1 2 3 5 8 13 21 34 55

 

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

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

 

//возвращает n-е число Фибоначчи

int fib(int n)

return rc;

}

 

То же на языке Python:

#возвращает n-е число Фибоначчи

def fib(n):

n >>= 1 #Уменьшаем степень вдвое

return rc

{{Темы|Программирование|Математический анализ}}