对于输入同样的非负整数n,用迭代、递归、显示公式 及矩阵4种方法计算第n个Fibonacci数,并比较上述4种 方法基本操作的执行次数; 2)设计可供用户选择算法的交互式菜单(放在相应的 主菜单下)。 python编写。注释
时间: 2024-05-08 09:18:54 浏览: 17
好的,我明白了。让我来回答你的问题。
1)计算第n个Fibonacci数的四种方法及基本操作的执行次数:
迭代法:
```python
def fib_iter(n):
if n == 0:
return 0
elif n == 1:
return 1
else:
fib_n_2, fib_n_1 = 0, 1
for i in range(2, n + 1):
fib_n = fib_n_2 + fib_n_1
fib_n_2 = fib_n_1
fib_n_1 = fib_n
return fib_n
```
迭代法的基本操作执行次数:$O(n)$
递归法:
```python
def fib_rec(n):
if n == 0:
return 0
elif n == 1:
return 1
else:
return fib_rec(n - 2) + fib_rec(n - 1)
```
递归法的基本操作执行次数:$O(2^n)$
显示公式:
$$
F_n = \frac{1}{\sqrt{5}}\Bigg(\bigg(\frac{1 + \sqrt{5}}{2}\bigg)^n - \bigg(\frac{1 - \sqrt{5}}{2}\bigg)^n\Bigg)
$$
显示公式法的基本操作执行次数:$O(1)$
矩阵法:
$$
\begin{pmatrix} F_n \\ F_{n-1} \end{pmatrix} = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^n \begin{pmatrix} 1 \\ 0 \end{pmatrix}
$$
代码实现:
```python
import numpy as np
def fib_matrix(n):
if n == 0:
return 0
else:
A = np.array([[1, 1], [1, 0]], dtype=np.object)
F = np.array([[1], [0]], dtype=np.object)
A_n = np.linalg.matrix_power(A, n)
return np.dot(A_n, F)[0]
```
矩阵法的基本操作执行次数:$O(\log n)$
2)设计菜单的代码如下所示:
```python
def select_algorithm():
algorithms = {
1: ('迭代法', fib_iter),
2: ('递归法', fib_rec),
3: ('显示公式法', lambda n: int((((1 + 5 ** 0.5) / 2) ** n - ((1 - 5 ** 0.5) / 2) ** n) / 5 ** 0.5)),
4: ('矩阵法', fib_matrix)
}
print('请选择计算Fibonacci数的算法:')
for idx, algorithm in algorithms.items():
print(f'{idx}: {algorithm[0]}')
selection = int(input('请选择算法序号:'))
if selection not in algorithms:
print('输入有误,请重新选择')
return select_algorithm()
return algorithms[selection][1]
```
以上代码实现了一个简单的交互式菜单,用户可以从中选择计算Fibonacci数的算法。
希望这些能够对你有帮助。如果你有其他问题,随时可以继续提问。