1+ '''
2+ Nth Fibonacci Number
3+
4+ The Fibonacci numbers are the numbers in the following integer sequence.
5+ 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144...
6+ Given a number n, print n-th Fibonacci Number.
7+
8+ Input: 8
9+ Output: 34
10+
11+ =========================================
12+ Many solutions for this problem exist, I'll show 6 different solutions,
13+ starting from the worst to the best.
14+
15+ The simplest recursive solution.
16+ Time Complexity: O(2^N) , actually ~1.6^N, the golden ratio
17+ Space Complexity: O(N) , because of the recursion stack
18+ Recursion with memoizing.
19+ Time Complexity: O(N)
20+ Space Complexity: O(N)
21+ Dynamic programming.
22+ Time Complexity: O(N)
23+ Space Complexity: O(N)
24+ Space optimized dynamic programming. (don't need a whole array, only 2 variables are needed)
25+ Time Complexity: O(N)
26+ Space Complexity: O(1)
27+ Matrix multiplication. (matrix power)
28+ start matrix: | 1 1 |
29+ | 1 0 |
30+
31+ result matrix: | Fn+1 Fn |
32+ | Fn Fn-1 |
33+
34+ result * start = | Fn+1 * 1 + Fn * 1 Fn+1 * 1 + Fn * 0 |
35+ | Fn * 1 + Fn-1 * 1 Fn * 1 + Fn-1 * 0 |
36+
37+ = | Fn+1 + Fn Fn+1 |
38+ | Fn + Fn-1 Fn |
39+
40+ = | Fn+1 + Fn Fn+1 |
41+ | Fn+1 Fn |
42+ Time Complexity: O(N)
43+ Space Complexity: O(1)
44+ Optimized matrix multiplication. (faster power function, using divide and conquer approach)
45+ Time Complexity: O(LogN)
46+ Space Complexity: O(LogN) , because of the recursion stack
47+ '''
48+
49+
50+ ##############
51+ # Solution 1 #
52+ ##############
53+
54+ def fibonacci_1 (n ):
55+ if (n == 0 ) or (n == 1 ):
56+ return n
57+ return fibonacci_1 (n - 1 ) + fibonacci_1 (n - 2 )
58+
59+
60+ ##############
61+ # Solution 2 #
62+ ##############
63+
64+ fib = {0 : 0 , 1 : 1 }
65+
66+ def fibonacci_2 (n ):
67+ if n in fib :
68+ return fib [n ]
69+ fib [n ] = fibonacci_2 (n - 1 ) + fibonacci_2 (n - 2 )
70+ return fib [n ]
71+
72+
73+ ##############
74+ # Solution 3 #
75+ ##############
76+
77+ def fibonacci_3 (n ):
78+ dp = [0 for i in range (max (2 , n + 1 ))]
79+ dp [0 ] = 0
80+ dp [1 ] = 1
81+
82+ for i in range (2 , n + 1 ):
83+ dp [i ] = dp [i - 1 ] + dp [i - 2 ]
84+
85+ return dp [n ]
86+
87+
88+ ##############
89+ # Solution 4 #
90+ ##############
91+
92+ def fibonacci_4 (n ):
93+ a , b = 1 , 0
94+
95+ while n > 0 :
96+ a , b = a + b , a
97+ n -= 1
98+
99+ return b
100+
101+
102+ ##############
103+ # Solution 5 #
104+ ##############
105+
106+ def fibonacci_5 (n ):
107+ fib = [[1 , 1 ], [1 , 0 ]]
108+ res = [[1 , 1 ], [1 , 0 ]]
109+
110+ for i in range (n ):
111+ res = [
112+ [
113+ res [0 ][0 ]* fib [0 ][0 ] + res [0 ][1 ]* fib [1 ][0 ],
114+ res [0 ][0 ]* fib [0 ][1 ] + res [0 ][1 ]* fib [1 ][1 ]
115+ ],
116+ [
117+ res [1 ][0 ]* fib [0 ][0 ] + res [1 ][1 ]* fib [1 ][0 ],
118+ res [1 ][0 ]* fib [0 ][1 ] + res [1 ][1 ]* fib [1 ][1 ]
119+ ]
120+ ]
121+
122+ return res [1 ][1 ] # Fn-1 (or change the range(n-1) and use res[0][1] or res[1][0])
123+
124+
125+ ##############
126+ # Solution 6 #
127+ ##############
128+
129+ def fibonacci_6 (n ):
130+ fib = [[1 , 1 ], [1 , 0 ]]
131+
132+ # send the matrix by reference
133+ matrix_pow (fib , n + 1 )
134+
135+ return fib [1 ][1 ] # return Fn-1
136+
137+ def matrix_pow (fib , n ):
138+ # divide and conquer power function
139+ if (n == 0 ) or (n == 1 ):
140+ return
141+
142+ # split on 2, because matrix^k = matrix^(k/2) * matrix^(k/2)
143+ matrix_pow (fib , n // 2 )
144+
145+ matrix_mult (fib , fib )
146+ if n % 2 == 1 :
147+ # multiply by the start matrix if odd power
148+ matrix_mult (fib , [[1 , 1 ], [1 , 0 ]])
149+
150+ def matrix_mult (a , b ):
151+ a0 = [
152+ a [0 ][0 ]* b [0 ][0 ] + a [0 ][1 ]* b [1 ][0 ],
153+ a [0 ][0 ]* b [0 ][1 ] + a [0 ][1 ]* b [1 ][1 ]
154+ ]
155+ a1 = [
156+ a [1 ][0 ]* b [0 ][0 ] + a [1 ][1 ]* b [1 ][0 ],
157+ a [1 ][0 ]* b [0 ][1 ] + a [1 ][1 ]* b [1 ][1 ]
158+ ]
159+ # don't lose the reference of 'a'
160+ # and don't multiply directly because 'a' has same reference as 'b'
161+ a [0 ] = a0
162+ a [1 ] = a1
163+
164+
165+ ###########
166+ # Testing #
167+ ###########
168+
169+ # Test 1
170+ # Correct result => 21
171+ print (fibonacci_1 (8 ))
172+ print (fibonacci_2 (8 ))
173+ print (fibonacci_3 (8 ))
174+ print (fibonacci_4 (8 ))
175+ print (fibonacci_5 (8 ))
176+ print (fibonacci_6 (8 ))
0 commit comments