In the previous article we explored the LCM Concept and two different ways we can obtain them, now we will look at what the Fibonacci numbers are and how they can be obtained or the way in which Fibonacci Numbers in Python are implemented. Let us look at a problem involving Fibonacci numbers:
There are n stairs, a person standing at the bottom wants to reach the top. The person can climb either 1 stair or 2 stairs at a time. Count the number of ways, the person can reach the top. We are given in this case a staircase with 4 stairs, we can jump one stair a time or we can traverse the stairs one by one. Or we can go to second stair directly, followed by third stair and fourth stair. So there are multiple ways to reach the top of fourth stair. We need to count total number of ways in which we can reach the fourth stair.
There are a total of 5 ways in which we can reach the fourth stair:
- 1st stair-> 2nd Stair -> 3rd Stair-> 4th Stair
- 1st Stair->2nd Stair -> 4th Stair
- 1st Stair->3rd Stair-> 4th Stair
- 2nd Stair -> 3rd Stair ->4th Stair
- 2nd Stair->4th Stair
Suppose we had only three stairs like in the below image:
There would be three ways of reaching the last stair:
1st Stair->2nd Stair->3rd Stair
2nd Stair-> 3rd Stair
1st Stair-> 3rd Stair
Count ways to reach n-number of stairs
Count Ways(3 stairs) = 3
Count Ways(4 stairs) = 5
Count Ways(5 Stairs) =?
There lies a hidden relation between the result obtained for three stairs and the result for four stairs that will enable us to count the number of ways we can reach the final stair in the case of five.
The answer for count of ways in(5 stairs) is equal to: => Count Ways(4 stairs) + Count Ways(3 stairs)
=> 5 + 3
Therefore the total number of ways in which we can reach the 5th step is equal to 8 different ways. We can always obtain the result for the current number of stairs by adding the number of ways for the previous two cases.
n=int(input("Enter n : ")) if n ==0: print(1) elif n==1: print(1,1) else: print(1,1,end =" ") a=1 b=1 for i in range(2,n+1): c=a+b print(c, end =" ") a=b b=c
Output: Enter n : 5 1 1 2 3 5 8
The pattern relation above matches a common number sequence occurence that is referred to or known as the Fibonacci Sequence
1, 1, 2 , 3, 5, 8 , 13, 21……and so on.
Thus we have seen the implementation of Fibonacci series in Python in the next article we will look at how we check for prime numbers in Python.