斐波那契数列:1,1,2,3,5,8......求第n项。
时间: 2024-04-30 12:17:40 浏览: 136
计算斐波那契数列的第n项
斐波那契数列是指每一项都是前两项之和,因此可以使用递归的方式来求解。具体算法如下:
1. 当n等于1或2时,斐波那契数列的第n项为1;
2. 当n大于2时,斐波那契数列的第n项为前两项之和。
根据上述算法,可以写出如下的递归函数来求解斐波那契数列的第n项:
```python
def fib(n):
if n <= 2:
return 1
else:
return fib(n-1) + fib(n-2)
```
这个函数的时间复杂度是指数级的,因为它会重复计算很多次相同的值。如果要计算比较大的n,这个函数的效率会非常低下。可以使用动态规划的方法来优化这个函数,避免重复计算。
阅读全文