Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- function fib(n)
- if n = 0 or n = 1
- return 1
- return fib(n − 1) + fib(n − 2)
- fib(5)
- fib(4) + fib(3)
- (fib(3) + fib(2)) + (fib(2) + fib(1))
- ((fib(2) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))
- (((fib(1) + fib(0)) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))
- >>> def fib_to(n):
- ... fibs = [0, 1]
- ... for i in range(2, n+1):
- ... fibs.append(fibs[-1] + fibs[-2])
- ... return fibs
- ...
- >>> fib_to(20)
- [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765]
- >>> fib_to(40)[17]
- 1597
- >>> def fib(n, computed = {0: 0, 1: 1}):
- ... if n not in computed:
- ... computed[n] = fib(n-1, computed) + fib(n-2, computed)
- ... return computed[n]
- >>> fib(400)
- 176023680645013966468226945392411250770384383304492191886725992896575345044216019675
- import functools
- @functools.lru_cache(None)
- def fib(n):
- if n < 2:
- return n
- return fib(n-1) + fib(n-2)
- >>> def fib(n):
- ... a, b = 0, 1
- ... for _ in range(n):
- ... a, b = b, a+b
- ... return a
- cache = {}
- def fib(n):
- if n <= 1:
- return n
- if n not in cache:
- cache[n] = fib(n-1) + fib(n-2)
- return cache[n]
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement