Fibonacci numbers list
Fibonacci numbers problem
Write a program to compute the Fibonacci sequence number of a given integer. Your algorithm must run in linear time ie O(N).
What is the fibonacci sequence
Definition: Fibonacci number of (N) is the sum of Fibonacci numbers of (N-1) and (N-2). In other words, the fibonacci numbers list formula:
|
1 |
Fibonacci(N) = Fibonacci(N-1) + Fibonacci(N-2) |
where
|
1 |
Fibonacci(0) = Fibonacci(1) = 1 |
Fibonacci code
The easiest way to solve this problem is by recursion due to the recursive nature of the problem however a recursive solution has an exponential time complexity function of (N). The reason why a recursive solution is very slow is because it recomputes values whenever needed from the scratch and does not utilize the fact that some numbers need not be recomputed every single time as long as we can save and reuse later. Such technique is called memoization which is an optimization technique used to speed up programs by having function calls avoid repeating the calculation of results for previously computed values. For more information you can search for the topic Dynamic Programming. So how can we solve this problem in linear time using memoization. Here is how we will solve this problem: if (N) is zero just return zero otherwise save the first two Fibonacci numbers needed for the calculation of the third Fibonacci number. Keep updating those two numbers as you loop to (N) for example if you need to calculate Fibonacci(5) then Fibonacci(3) and Fibonacci(4) should be calculated along the way while looping to (5)
Fibonacci numbers C++
Here is an example fibonacci number calculator algorithm:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 |
//Includes #include <iostream> using namespace std; int Fibonacci (int); void main() { cout << "Fibonacci(4) = " << Fibonacci(4) << endl; } // N = 0 1 2 3 4 5 6 7 // Fibonacci (N) = 0 1 1 2 3 5 8 13 int Fibonacci (int N) { //Initial case is 0 by definition if (N == 0) { return 0; } //Save the first two Fibonacci numbers int x = 1; int y = 1; //Keep updating the last two Fibonacci numbers //to calculate the next one for (int i = 3; i <= N; i++) { int sum = x + y; x = y; y = sum; } return y; } |
I hope fibonacci numbers got explained in an easy way. Comments ? questions ? pease use the comments section below. Thanks for reading.
About Author
Mohammed Abualrob
Software Engineer @ Cisco