用C++求解斐波那契数列的第n项值和前n项的和 |21xrx.com

用C++求解斐波那契数列的第n项值和前n项的和

2023-07-11 12:43:23 深夜i 20 0

C++ 斐波那契数列第n项值前n项的和

斐波那契数列是一种非常常见的数列，其规律为每个数都是前两个数的和，即F(n) = F(n-1) + F(n-2)，其中F(0) = 0，F(1) = 1。

在C++中，可以用递归或迭代的方式求解斐波那契数列的第n项值和前n项的和。

首先看递归方法，代码如下：

int fibonacci(int n) {
  if (n <= 0) return 0;
  if (n == 1) return 1;
  return fibonacci(n - 1) + fibonacci(n - 2);
}

这里用了递归的思想，将问题不停地分解为规模更小的子问题，直到问题变得足够简单，然后再逐层返回答案。但是递归方法的时间复杂度为指数级别，当n较大时会造成很大的时间开销，因此不太适用于求解较大的n。

接下来看迭代方法，代码如下：

int fibonacci(int n) {
  if (n <= 0) return 0;
  if (n == 1) return 1;
  int f1 = 0, f2 = 1, f3;
  for (int i = 2; i <= n; i++) {
    f3 = f1 + f2;
    f1 = f2;
    f2 = f3;
  }
  return f3;
}

这里用了循环的方式，从前往后依次计算每个斐波那契数列的项，直到求得第n项。迭代方法的时间复杂度为线性级别，比较快速且适用于求解较大的n。

除了求解斐波那契数列的第n项值之外，还有求解前n项的和。这里有一个简单的方法，代码如下：

int fibonacciSum(int n) {
  if (n <= 0) return 0;
  if (n == 1) return 1;
  int f1 = 0, f2 = 1, f3, sum = 1;
  for (int i = 2; i <= n; i++) {
    f3 = f1 + f2;
    f1 = f2;
    f2 = f3;
    sum += f3;
  }
  return sum;
}

这里在求解斐波那契数列的第n项值的过程中，顺便累加每个数的值，最后得到的就是前n项的和。

无论是求解斐波那契数列的第n项值还是前n项的和，都需要注意数据类型的选择，当n较大时需注意是否会超出数据类型的范围。同时还需要注意边界条件的判断，尤其是n <= 0和n == 1的情况。

上一篇: idea打包java可执行jar包

下一篇: 如何下载C++2015

评论区

相似文章