Home »
Python »
Python programs
Python | Program to calculate n-th term of a Fibonacci Series
Here, we are going to learn how to calculate the n-th term of a Fibonacci series using python program?
Submitted by Sanjeev, on March 30, 2019
Python program to calculate n-th term of Fibonacci series with the help to two approaches (there are many approaches to calculate n-th term).
Description:
- First Approach: Dynamic Programming
In this approach, we calculate all the terms of Fibonacci series up to n and if we need to calculate any other term which is smaller than n, then we don’t have to calculate it again.
- Second Approach: By Formula
In this approach we calculate the n-th term of Fibonacci series with the help of a formula.
Formula:
phi = ( 1 + sqrt(5) ) / 2
An = phin/ sqrt(5)
Example:
Input:
for n = 5
for n = 8
Output:
a5 = 5
a8 = 21
Procedure: Dynamic Programming Approach
L[0] = 0, L[1] = 1
For loop from 2 to n+1
L[i] = L[i-1] + L[i -2]
End of for
As you may observe that we are also storing each calculated value, so we can also use them later if necessary.
This is the benefit of Dynamic Programming over Recursion.
Python code to calculate n-th term of a Fibonacci series
def dynamic_fibonacci(n):
'''
This function will calculate fobonacci
series with the help of dynamic
programming.
'''
l = [0]*(n+1)
l[0] = 0
l[1] = 1
for i in range(2, n+1):
l[i] = l[i-1] + l[i-2]
return l
# Time complexity O(n)
def fibonacci_by_formula(n):
'''
This function will calculate n-th
term of fibonacci series with the
help of a formula.
'''
from math import sqrt
phi = (1 + sqrt(5))/2
fib = round(pow(phi, n)/sqrt(5))
return fib
# Time complexity O(1)
def main():
n = 8
lst = dynamic_fibonacci(n)
x = fibonacci_by_formula(n)
print('By Dynamic Programming:',lst[n])
print()
print('By Formula:',x)
main()
Output
By Dynamic Programming: 21
By Formula: 21
TOP Interview Coding Problems/Challenges