Python高效计算斐波那契数列

实现功能：计算斐波那契数列的第n项

以下是用 Python 编写的递归方法实现斐波那契数列：

def fibonacci(n):
if n <= 0:
return "输入必须为正整数"
elif n == 1:
return 0
elif n == 2:
return 1
else:
return fibonacci(n – 1) + fibonacci(n – 2)

# 示例调用
n = 10
print(f"斐波那契数列的第{n}项是: {fibonacci(n)}")

迭代方法优化

递归方法在 n 较大时效率较低，可以使用迭代方法优化：

def fibonacci_iterative(n):
if n <= 0:
return "输入必须为正整数"
a, b = 0, 1
for _ in range(2, n):
a, b = b, a + b
return b if n > 1 else a

# 示例调用
n = 10
print(f"斐波那契数列的第{n}项是: {fibonacci_iterative(n)}")

动态规划方法

使用动态规划存储中间结果，避免重复计算：

def fibonacci_dp(n, memo={}):
if n <= 0:
return "输入必须为正整数"
if n in memo:
return memo[n]
if n == 1:
return 0
elif n == 2:
return 1
memo[n] = fibonacci_dp(n – 1, memo) + fibonacci_dp(n – 2, memo)
return memo[n]

# 示例调用
n = 10
print(f"斐波那契数列的第{n}项是: {fibonacci_dp(n)}")

公式法（Binet公式）

对于大数计算，可以使用数学公式近似计算：

import math

def fibonacci_formula(n):
if n <= 0:
return "输入必须为正整数"
sqrt5 = math.sqrt(5)
phi = (1 + sqrt5) / 2
return round((phi ** n – (-phi) ** (-n)) / sqrt5)

# 示例调用
n = 10
print(f"斐波那契数列的第{n}项是: {fibonacci_formula(n)}")

以上方法可根据实际需求选择，递归适合小规模计算，迭代和动态规划适合高效计算，公式法适用于大数近似计算。