GV

GeezerVison

The World Wide Web, restored to 800 pixels of glory.

Home|About|Gaming cabinet|Archives|How it works|Starter sites

On this site

  • Sign in
  • ActionsCI/CD and automation
  • CodespacesCloud development environments
  • All Features
  • Documentation
  • Training
  • Certifications
  • Build with Copilot
  • Customize Copilot
  • Integrations
  • Trending repos
  • GitHub Sponsors
  • Developer articles
  • Enterprises

This view

  • Original page
  • New address

GeezerVison is showing github.com — algorithms/algorithms/dp/fib.py at master · oldmonad/algorithms

Expand file tree

/

fib.py

Copy path
More file actions
More file actions

Latest commit

 

History

History
History
72 lines (55 loc) · 1.48 KB
/

fib.py

Copy path

File metadata and controls

72 lines (55 loc) · 1.48 KB
Raw
Copy raw file
Download raw file
Open symbols panel
Edit and raw actions
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
64
65
66
67
68
69
70
71
72
def fib_recursive(n):
"""[summary]
Computes the n-th fibonacci number recursive.
Problem: This implementation is very slow.
approximate O(2^n)
Arguments:
n {[int]} -- [description]
Returns:
[int] -- [description]
"""
# precondition
assert n >= 0, 'n must be a positive integer'
if n <= 1:
return n
else:
return fib_recursive(n-1) + fib_recursive(n-2)
# print(fib_recursive(35)) # => 9227465 (slow)
def fib_list(n):
"""[summary]
This algorithm computes the n-th fibbonacci number
very quick. approximate O(n)
The algorithm use dynamic programming.
Arguments:
n {[int]} -- [description]
Returns:
[int] -- [description]
"""
# precondition
assert n >= 0, 'n must be a positive integer'
list_results = [0, 1]
for i in range(2, n+1):
list_results.append(list_results[i-1] + list_results[i-2])
return list_results[n]
# print(fib_list(100)) # => 354224848179261915075
def fib_iter(n):
"""[summary]
Works iterative approximate O(n)
Arguments:
n {[int]} -- [description]
Returns:
[int] -- [description]
"""
# precondition
assert n >= 0, 'n must be positive integer'
fib_1 = 0
fib_2 = 1
sum = 0
if n <= 1:
return n
for _ in range(n-1):
sum = fib_1 + fib_2
fib_1 = fib_2
fib_2 = sum
return sum
# print(fib_iter(100)) # => 354224848179261915075
You are visitor 01402520 — GeezerVison does not store the pages you look up.
Best viewed with Netscape Navigator 4.7 or Internet Explorer 6 at 800×600. No cookies required.