The Algorithms logoThe Algorithms
AboutDonate
"""
This is a pure Python implementation of Dynamic Programming solution to the fibonacci
sequence problem.
"""


class Fibonacci:
    def __init__(self, N=None):
        self.fib_array = []
        if N:
            N = int(N)
            self.fib_array.append(0)
            self.fib_array.append(1)
            for i in range(2, N + 1):
                self.fib_array.append(self.fib_array[i - 1] + self.fib_array[i - 2])
        elif N == 0:
            self.fib_array.append(0)
        print(self.fib_array)

    def get(self, sequence_no=None):
        """
        >>> Fibonacci(5).get(3)
        [0, 1, 1, 2, 3, 5]
        [0, 1, 1, 2]
        >>> Fibonacci(5).get(6)
        [0, 1, 1, 2, 3, 5]
        Out of bound.
        >>> Fibonacci(5).get(-1)
        [0, 1, 1, 2, 3, 5]
        []
        """
        if sequence_no is not None:
            if sequence_no < len(self.fib_array):
                return print(self.fib_array[: sequence_no + 1])
            else:
                print("Out of bound.")
        else:
            print("Please specify a value")


if __name__ == "__main__":
    print("\n********* Fibonacci Series Using Dynamic Programming ************\n")
    print("\n Enter the upper limit for the fibonacci sequence: ", end="")
    try:
        N = int(input().strip())
        fib = Fibonacci(N)
        print(
            "\n********* Enter different values to get the corresponding fibonacci "
            "sequence, enter any negative number to exit. ************\n"
        )
        while True:
            try:
                i = int(input("Enter value: ").strip())
                if i < 0:
                    print("\n********* Good Bye!! ************\n")
                    break
                fib.get(i)
            except NameError:
                print("\nInvalid input, please try again.")
    except NameError:
        print("\n********* Invalid input, good bye!! ************\n")

    import doctest

    doctest.testmod()

Fibonacci Numbers

In mathematics, the Fibonacci numbers commonly denoted F(n), form a sequence, called the Fibonacci sequence, such that each number is the sum of the two preceding ones, starting from 0 and 1. The Sequence looks like this:

[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...]

Applications

Finding N-th member of this sequence would be useful in many Applications:

  • Recently Fibonacci sequence and the golden ratio are of great interest to researchers in many fields of

science including high energy physics, quantum mechanics, Cryptography and Coding.

Steps

  1. Prepare Base Matrice
  2. Calculate the power of this Matrice
  3. Take Corresponding value from Matrix

Example

Find 8-th member of Fibonacci

Step 0

| F(n+1)  F(n)  |
| F(n)    F(n-1)|

Step 1

Calculate matrix^1
| 1 1 |
| 1 0 |

Step 2

Calculate matrix^2
| 2 1 |
| 1 1 |

Step 3

Calculate matrix^4
| 5 3 |
| 3 2 |

Step 4

Calculate matrix^8
| 34 21 |
| 21 13 |

Step 5

F(8)=21

Implementation

Video URL

Others