フィボナッチ数列

ここによると,動的計画法の基礎は以下の三つに分かれるらしい. ビデオの中にも出て来たアルゴリズムを試してみた. フィボナッチ数列のプログラムを書くのは何年ぶりだろう.
例のごとく,ここにプログラムは置いている.source

# lazy
def fib(n):
    if n <= 2: f = 1
    else: f = fib(n-1) + fib(n-2)
    return f

# memorization
memo = {}
def fib1(n):
    if n in memo: return memo[n]
    if n <= 2: f = 1
    else: f = fib(n-1) + fib(n-2)
    memo[n] = f
    return f

# buttom up    
def fib2(n):
    fib = {}
    for k in range(1, n+1):
        if k <= 2: f = 1
        else: f = fib[k-1] + fib[k-2]
        fib[k] = f
    return fib[n]

if __name__ == '__main__':
    from time import time
    N = 35
    start = time()
    print fib(N)
    print time() - start

    start = time()
    print fib1(N)
    print time() - start

    start = time()
    print fib2(N)
    print time() - start

コメントを残す

以下に詳細を記入するか、アイコンをクリックしてログインしてください。

WordPress.com ロゴ

WordPress.com アカウントを使ってコメントしています。 ログアウト / 変更 )

Twitter 画像

Twitter アカウントを使ってコメントしています。 ログアウト / 変更 )

Facebook の写真

Facebook アカウントを使ってコメントしています。 ログアウト / 変更 )

Google+ フォト

Google+ アカウントを使ってコメントしています。 ログアウト / 変更 )

%s と連携中