/
fib.py
57 lines (41 loc) · 1.33 KB
/
fib.py
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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
# fib(n) -> 1, 1, 2, 3, 5, 8, 13, 21, ...
# n -> 0, 1, 2, 3, 4, 5, 6, 7
import sys
sys.setrecursionlimit(3000)
# MEMOIZATION (MEMOIZAÇÃO)
memo = {}
def fib(n):
result_from_memo = memo.get(n) # O(1)
if result_from_memo is not None: # O(1)
return result_from_memo # O(1)
if n <= 1:
return 1
result = fib(n-1) + fib(n-2)
memo[n] = result # anota no memo o resultado para este valor de n
return result
for i in range(2001):
print i, "-->", fib(i)
# fib(40)
# quantas vezes fib(40) ? 1 = fib(0)
# quantas vezes fib(39) ? 1 = fib(1)
# quantas vezes fib(38) ? 2 = fib(2)
# quantas vezes fib(37) ? 3 = fib(3)
# quantas vezes fib(36) ? 5 = fib(4)
# quantas vezes fib(35) ? 8 = fib(5)
# ....
# quantas vezes fib(1) ? fib(39) vezes!!!!
######
#
# 40
# / \
# 39 38*
# / \
# 38 37*
# / \
# 37 36*
# / \
# 36 35*
# / \
# 35 34*
#
#