Just relax, take it easy..

0%

Fibonacci number(Recursive, DP and Decorator)

发表于

I found a fatastic video about Dynamic Programming, it can be used to solve Fibonacci number problem efficiently. Decorater can also be used to make code elegent ^o^

Fibonacci number: 1, 1, 2, 3, 5, 8, 13...

Original recursive implementation

1
2
3
4
5
def fib(n):
    if n<=2: f = 1
    else: f = fib(n-1) + fib(n-2)

    return f

Improvement: memoization

  • Reuse solutions to sub-problems to solve the problem
  • So time = #sub-problems * O(sub-problem) 
    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
    #!/usr/bin/python3
    from collections import defaultdict
    import sys

    n = int(sys.argv[1])
    mem = defaultdict(lambda: 0)

    def fib(n):
        global mem
        # print(n)
        if mem[n]:
            return mem[n]

        if n<=2: f = 1
        else: f = fib(n-1) + fib(n-2)

        mem[n] = f
        print(f)
        return f


    def fib_con(n):
        mem = {}
        for k in range(1, 1+n):
            if k<=2:
                mem[k] = 1
            else:
                mem[k] = mem[k-1] + mem[k-2]

            print(mem[k])
        return mem[n]

    fib(n)
    fib_con(n)

Video link: https://www.youtube.com/watch?v=OQ5jsbhAv_M
DP = recursion + memorization + guessing

Problem of the improvement above:

The disadvantage of this method is that the clarity and the beauty of the original recursive implementation is lost.
So we use a helper function to handle the fib() function, the idea of . 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def memoize(f):
    memo = {}

    def helper(x):
        if x not in memo:
            memo[x] = f(x)
        return memo[x]

    return helper


def fib(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fib(n - 1) + fib(n - 2)


fib = memoize(fib)
print(fib(40))

That is Decorator: @memoize
U can check this website for more information:
http://www.python-course.eu/python3_memoization.php 

1
2
3
4
5
@memoize
def fib(n):
    ...

print(fib(40))

Generator version

1
2
3
4
5
6
7
8
def fib(n):
    a, b = 0, 1
    for _ in range(n):
        yield a
        a, b = b, a+b

for i in fib(10):
    print(i)