Fibonacci Sequence 斐波那契序列

fib = 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ......

方法一：模拟

n = int(input())
fib = [0, 1]
for _ in range(2, n+1):
        fib.append(sum(fib[-2:]))
print(fib[:n+1])

方法二：迭代

n = int(input())
fib = []
a = 0
b = 1
while n >= 0:  # n次
    fib.append(a)
    tem = a
    a = b
    b = a + tem
    # a, b = b, a + b  # 滚动赋值
    n -= 1
print(fib)

方法三：递归

def f(n):
    if n < 2:
        return n
    else:
        return f(n-1) + f(n-2)

n = int(input())
fib = [f(i) for i in range(0, n+1)]
print(fib)

方法四：动态规划（DP）

n = int(input())
dp = [i for i in range(n+1)] # 初始化数组dp (0-n的升序，含初始条件：dp[0]=0；dp[1]=1)
for i in range(2, n+1):
        dp[i] = dp[i-1] + dp[i-2] # 转移方程
print(dp)

方法五：矩阵快速幂

# 需要安装第三方库numpy （Terminal: pip install numpy）
# 导入numpy模块
import numpy as np
n = int(input())
M = np.matrix([[1,1],[1,0]])
A = np.matrix([[0,1]])
fib = []
for N in range(0,n+1):
    F = M**N * A.T
    fib.append(F[0,0])
print(fib)

n为无穷是，fib前项和后项之比ratio为黄金分割数

方法六：公试法

n = int(input())
fib = [int(1/(5**0.5) * ((0.5*(1+5**(0.5)))**N - (0.5 * (1 - 5**0.5))**N)) for N in range(n+1)]
print(fib)