斐波拉契数列c++算法
时间: 2024-06-08 09:06:35 浏览: 9
斐波那契数列是一个经典的数学问题,可以使用递归或迭代两种算法来求解。下面分别介绍这两种算法的实现。
1. 递归算法:
递归算法是最直观的一种实现方法,根据斐波那契数列的定义,可以将问题划分为两个子问题:求解第n-1项和第n-2项的值,然后将它们相加得到第n项的值。
```c
int fibonacci(int n) {
if (n <= 0) {
return 0;
} else if (n == 1) {
return 1;
} else {
return fibonacci(n - 1) + fibonacci(n - 2);
}
}
```
这种方法的缺点是在计算较大的斐波那契数列时效率较低,因为会有很多重复的计算。
2. 迭代算法:
迭代算法通过循环的方式计算斐波那契数列,避免了重复计算的问题。
```c
int fibonacci(int n) {
if (n <= 0) {
return 0;
} else if (n == 1) {
return 1;
} else {
int a = 0;
int b = 1;
for (int i = 2; i <= n; i++) {
int temp = a + b;
a = b;
b = temp;
}
return b;
}
}
```
这种方法的效率较高,时间复杂度为 O(n)。
以上是两种常见的斐波那契数列的求解算法,你可以根据实际需求选择合适的方法来使用。