-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy path1.fibonacci_sequence.py
More file actions
63 lines (41 loc) · 1.05 KB
/
Copy path1.fibonacci_sequence.py
File metadata and controls
63 lines (41 loc) · 1.05 KB
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
56
57
58
59
60
61
62
63
"""
Here is the one and only "Fibonacci sequence"
where the result of the current number is the sum of the previous 2
"""
# Fibonacci:
def fib(n):
if n == 0:
result = 0
elif (n == 1) or (n == 2):
result = 1
# this step calls fib for the previous two elements
else:
result = fib(n-1) + fib(n-2)
return result
# Memoization: runs above algorithm, with a notebook writting
# down every result from fib(n) up to fib(n-1)
def fib2(n, memo):
if memo[n]:
return memo[n]
elif n == 0:
result = 0
elif (n == 1) or (n == 2):
result = 1
else:
result = fib(n-1) + fib(n-2)
memo[n] = result
return result
def memo(n):
memo = [None] * (n + 1)
return fib2(n, memo)
def fib_bottom_up(n):
if n == 0:
return 0
elif (n == 1) or (n == 2):
return 1
bottom_up = [None] * (n+1)
bottom_up[1] = 1
bottom_up[2] = 1
for i in range(3, n+1):
bottom_up[i] = bottom_up[i-1] + bottom_up[i-2]
return bottom_up[n]