Python Program for n-th Fibonacci Number

Nth Term of a Fibonacci Series: In this tutorial, we will learn how to calculate the Nth term of a Fibonacci series using Python program? By Sanjeev Last updated : April 14, 2023

Different Approaches to Find n-th Fibonacci Number in Python

The following are the two approaches to find the N-th term of a Fibonacci Number:

  1. Using Dynamic Programming
  2. Using Formula

1. Using 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.

Procedure:

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 find n-th Fibonacci number using dynamic programming approach

# This function will calculate fobonacci
# series with the help of dynamic
# programming.

def dynamic_fibonacci(n):
    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 main():
    n = 8
    lst = dynamic_fibonacci(n)
    print("By Dynamic Programming:", lst[n])

main()

Output

By Dynamic Programming: 21

2. Using 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)

Python code to find n-th Fibonacci number using formula

# This function will calculate n-th
# term of fibonacci series with the
# help of a formula.

def fibonacci_by_formula(n):
    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
    x = fibonacci_by_formula(n)
    print("By Formula:", x)

main()

Output

By Formula: 21

Python Basic Programs »


Related Programs



Comments and Discussions!

Load comments ↻





Copyright © 2024 www.includehelp.com. All rights reserved.