求Fibonacci数列第n项
时间: 2023-12-31 16:53:24 浏览: 76
Fibonacci数列是指从0和1开始,后面每一项都是前面两项的和,即:0、1、1、2、3、5、8、13、21、34、……。第n项的值可以通过递归或循环的方式求解。以下是两种不同的实现方式:
递归实现:
```python
def fibonacci(n):
if n <= 1:
return n
else:
return fibonacci(n-1) + fibonacci(n-2)
```
循环实现:
```python
def fibonacci(n):
if n <= 1:
return n
else:
a, b = 0, 1
for i in range(2, n+1):
c = a + b
a, b = b, c
return b
```
两种方式的时间复杂度都是O(n),但递归的方式会造成大量的重复计算,因此循环的方式更加高效。
相关问题
求斐波那契数列第n项
斐波那契数列是指:1、1、2、3、5、8、13、21、34、55、89、144……,它的递推公式为 f(n) = f(n-1) + f(n-2),其中 f(1) = f(2) = 1。
因此,斐波那契数列的第n项可以通过递归或循环的方式求解。
递归方式:
```
int fibonacci(int n) {
if (n == 1 || n == 2) {
return 1;
}
return fibonacci(n-1) + fibonacci(n-2);
}
```
循环方式:
```
int fibonacci(int n) {
if (n == 1 || n == 2) {
return 1;
}
int a = 1, b = 1, c;
for (int i = 3; i <= n; i++) {
c = a + b;
a = b;
b = c;
}
return c;
}
```
其中,递归方式虽然简单易懂,但是当n较大时会导致栈溢出的问题,而循环方式则可以有效避免这个问题。
c语言求斐波那契数列第n项
以下是用 C 语言实现求斐波那契数列第n项的代码:
```c
#include <stdio.h>
// 求斐波那契数列的第n项
int fibonacci(int n)
{
if (n <= 0)
return 0;
else if (n == 1)
return 1;
else
return fibonacci(n - 1) + fibonacci(n - 2);
}
int main()
{
int n;
printf("请输入一个正整数:");
scanf("%d", &n);
printf("斐波那契数列的第%d项为:%d\n", n, fibonacci(n));
return 0;
}
```
在这个程序中,我们使用递归的方式来求解斐波那契数列的第n项。在递归函数中,如果n小于等于0,我们返回0;如果n等于1,我们返回1;否则我们返回前两项的和。在主函数中,我们通过scanf函数获取用户输入的n,然后调用fibonacci函数来求解斐波那契数列的第n项。最后,我们输出结果。
阅读全文