A Fibonacci sequence is a sequence in which the first two terms are 0, 1 and every subsequent term is the sum of the two terms immediately preceding it. ([Wikipedia](https://en.wikipedia.org/wiki/%E3%83%95%E3%82%A3%E3%83%9C%E3%83%8A%E3%83%83%E3% From 83% 81% E6% 95% B0))
Fibonacci sequence
0
1
1 （0 + 1）
2 （1 + 1）
3 （1 + 2）
5 （2 + 3）
8 （3 + 5）
13 （5 + 8）
When finding the nth term of this sequence, if it is implemented as it is, it will be like this.
def fib(n):
"""
Find the nth Fibonacci number starting from 0.
"""
if n == 0:
return 0
if n == 1:
return 1
return fib(n-1) + fib(n-2)
print(fib(7)) # -> 13
When you actually run it, you can see that it is ** very slow **. For example, even n = 100 takes a considerable amount of time.
The reason is that, although details are omitted, ** the same calculation is performed many times **. For example, fib (8) can be obtained by finding fib (7) and fib (6), and then adding them together. However, in order to find fib (7), it is necessary to find fib (6) anew. There is.
Let's speed up with the keyword ** "Do not do the same calculation twice" **. We will introduce two algorithms, ** memoization ** and ** dynamic programming **.
Save the result of the calculation once. If it works, use it, if not, calculate it anew and save the result for future use.
MAX_N = 100
MEMO = [None] * (MAX_N + 1) #Array to save the calculation result
def fib(n):
if n == 0:
return 0
if n == 1:
return 1
#Calculated?
if MEMO[n]:
return MEMO[n]
r = fib(n-1) + fib(n-2)
MEMO[n] = r #Save calculation result
return r
print(fib(100))
Even when n = 100, the result came back immediately.
The Fibonacci number can be calculated from the smaller n without using a recursive function.
MAX_N = 100
DP = [None] * (MAX_N + 1) #Array to save the calculation result
DP[0] = 0 #From the definition
DP[1] = 1 #From the definition
def fib(n):
#Find the Fibonacci number in order from 2 to n
for i in range(2, n + 1):
DP[i] = DP[i-1] + DP[i-2]
return DP[n]
print(fib(100))
See reference material for dynamic programming.
Recommended Posts