fibonacci

def fibonacci(n):
    if (n==1) or (n==2):
        return 1
    return fibonacci(n-1)+fibonacci(n-2)
print (fibonacci(10))

以 set 來表示

memo1={1:1,2:1}
def fibonacci(n):
    if n in memo1:
        return memo1[n]
    memo1[n]=fibonacci(n-2)+fibonacci(n-1)
    return memo1[n]
print(fibonacci(6))

以 list 呈現

def fibonacci(n):
    fib=[1,1]
    for i in range(2,n):
        fib.append(fib[i-2]+fib[i-1])
    return fib[n-1]
print(fibonacci(6))

上小節驗算

fib=[1,1]
for i in range(2,6):
    fib.append(fib[i-2]+fib[i-1])
    print(fib)