1 1 2 3 5 8 13 etc.
Series of numbers found a lot in nature:
– Number of petals in a flower,
– The number of spirals on a sunflower or pineapple tend to be a Fibonacci number
When we make squares with those widths, we get a nice spiral.
Simple series of numbers where n is composed of n-1 + n-2.
The Fibonacci Sequence is the series of numbers: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, …
The next number is found by adding up the two numbers before it.
01
012 = 3
0123 = 5
01235 = 8
012358 …
1+1 = 2
1+2 = 3
2+3 = 5
3+5 = 8
5+8 = 13
Here is the list of the first 50th Fibonacci numbers:
1
1
2
3
5
8
13
21
34
55
89
144
233
377
610
987
1597
2584
4181
6765
10946
17711
28657
46368
75025
121393
196418
317811
514229
832040
1346269
2178309
3524578
5702887
9227465
14930352
24157817
39088169
63245986
102334155
165580141
267914296
433494437
701408733
1134903170
1836311903
47th: 2971215073 (2 971 215 073) <<< beyond int32 with signed bit: 2 2^31 = 147 483 648
48th: 4807526976 (4 807 526 976) <<<< beyond int32 unsigned! 2^32=4 294 967 296
49th: 7778742049
50th: 12 586 269 025
Storing them in an int32 will overflow as of the 47th element.
Int32 can hold 2^32= 4 billions of values but from [-2b, +2b].
To solve this problem, you can change Fibonacci() to return Int64 or long.
There are many solutions to implement the Fibonacci algo and it’s often used as an introduction to Dynamic Programming:
//--------------- iterative version ---------------------
static int FibonacciIterative(int n)
{
if (n == 0) return 0;
if (n == 1) return 1;
int prevPrev = 0;
int prev = 1;
int result = 0;
for (int i = 2; i <= n; i++)
{
result = prev + prevPrev;
prevPrev = prev;
prev = result;
}
return result;
}
As pointed out in this post, the iterative approach is the fastest.
https://www.codeproject.com/Articles/21194/Iterative-vs-Recursive-Approaches
Time Complexity: O(N)
Space Complexity: O(N)
//--------------- naive recursive version ---------------------
static int FibonacciRecursive(int n)
{
if (n == 0) return 0;
if (n == 1) return 1;
return FibonacciRecursive(n - 1) + FibonacciRecursive(n - 2);
}
Time Complexity?
O(N) ? Nope.
Look at the recursive tree.
Each node of the recursive tree has 2 children.
This is because we call 2 times F per F.
The depth is 5.
2^5 –> 2^N which is an exponential time that looks like that:
The Recursive version is slower than the iterative.
https://www.codeproject.com/Articles/21194/Iterative-vs-Recursive-Approaches
Recursive Tree
F(5)
F(4) F(3)
F(3) F(F2) F(2) F(1)
F(2)F(1)
etc..
Recursive, optimized solution (memoised)
//--------------- optimized recursive version ---------------------
static Dictionary<int> resultHistory = new Dictionary<int>();
static int FibonacciRecursiveOpt(int n)
{
if (n == 0) return 0;
if (n == 1) return 1;
if (resultHistory.ContainsKey(n))
return resultHistory[n];
int result = FibonacciRecursiveOpt(n - 1) + FibonacciRecursiveOpt(n - 2);
resultHistory[n] = result;
return result;
}
Sources
https://leetcode.com/problems/fibonacci-number/submissions/
http://www.numberempire.com/fibonaccinumbers.php
Fibo Generator: https://www.browserling.com/tools/fibonacci-numbers
http://www.geeksforgeeks.org/program-for-nth-fibonacci-number/
From: https://www.mathsisfun.com/numbers/fibonacci-sequence.html
The magic of Fibonacci numbers | Arthur Benjamin
Leave a Reply
Want to join the discussion?Feel free to contribute!