C++ 找到序列1*2*3 + 2*3*4 + 3*4*5 + . . . + n*(n+1)*(n+2)的和

序列的和是给定序列中所有项按照特定模式相加的值。这里给出的模式的形式是：

∑ (n*(n+1)*(n+2))，其中(n*(n+1)*(n+2))是给定模式中的最后一项。以下文章详细讨论了3种不同时间和空间复杂度的方法来求解给定序列的和。

问题陈述

现在，让我们看看如何计算序列1*2*3 + 2*3*4 + 3*4*5 + . . . + n*(n+1)*(n+2)的和。

示例

让我们通过一个示例来理解这个问题。

输入-

n = 12

输出 −

8190

解释 −

1*2*3 + 2*3*4 + 3*4*5 + 4*5*6 + 5*6*7 + 6*7*8 + 7*8*9 + 8*9*10 + 9*10*11 + 10*11*12 + 11*12*13 + 12*13*14
= 6 + 24 + 60 + 120 + 210 + 336 + 504 + 720 + 990 + 1320 + 1716 + 2184
= 4290

输入 −

n = 7

输出 −

1260

解释 −

1*2*3 + 2*3*4 + 3*4*5 + 4*5*6 + 5*6*7
= 6 + 24 + 60 + 120 + 210 + 336 + 504
= 1260

输入 −

n = 21

输出 −

63756

解释： −

1*2*3 + 2*3*4 + 3*4*5 + 4*5*6 + 5*6*7 + . . . + 21*22*23
= 6 + 24 + 60 + 120 + 210 + 336 + 504 + . . . + 10626
= 63756

问题说明

让我们尝试理解问题并找到其解决方案。我们有两种选项来解决上述问题。一种解决方案可以通过使用递归来完成，而第二种解决方案可以通过使用迭代方法（通过循环来帮助）来实现。

我们将逐个查看这两个解决方案。

解决方案1 使用最后一项的蛮力解决方案

通过使用表达式的最后一项即 n*(n+1)*(n+2) 的递归代码

#include<bits/stdc++.h>
using namespace std;
// Define a recursive function to calculate the sum of the series.  Here we have used long long int to avoid the situation of overflow for large values of the output data
long long int SeriesSum(int n){
   // Base case
   if(n==0)return 0;
   // store each value in a variable m
   long long int m= (n*(n+1)*(n+2));
   // making a recursive call
   return m+ SeriesSum(n-1);
}
// main function
int main(){
   int num=5;
   // Declare a variable ‘num’ Call the function to get the output
   cout<< "The sum of the series is: " << SeriesSum(num);
   return 0;
}

输出

The sum of the series is: 420

递归代码的复杂性

• 时间复杂性 – O(1)；无论输入的大小如何，该代码执行固定数量的计算。

• 空间复杂性 – O(1)；无论输入的大小如何，该代码使用固定数量的变量来存储输入值和结果。

迭代方法

#include<bits/stdc++.h>
using namespace std;
// main function
int main(){
   int num=5;
   // Declare a variable ‘num’
   long long int ans=0;
   // Iteration process for getting required answer using the last term
   for(int i=1;i<=num;i++){
      ans += (i*(i+1)*(i+2)); 
   }
   // Print the output
   cout<< "The sum of series is: " << ans;
   return 0;
}

输出

The sum of series is: 420

迭代代码的复杂性

• 时间复杂性- O(n); 这段代码执行了一定数量的计算(迭代)，这取决于输入，循环将运行n次，其中n是输入。

• 空间复杂性- O(1); 代码使用一定数量的变量来存储输入值和结果，不管输入的大小如何。

解决方案2

通过使用可以通过使用求和的属性派生出的公式进行方法

我们可以通过使用求和的属性和使用已知项的求和来推导出公式。

找出公式- (n*(n+1)*(n+2)*(n+3))/4

1*2*3 + 2*3*4 + 3*4*5 + . . . + (n*(n+1)*(n+2))/4
=> Σ (n*(n+1)*(n+2))/4
=> Σ n*(n^2 + 3n +2) 
=> Σ n^3 + Σ 3n^2 + Σ 2n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Equation 1

正如我们已经知道的那样，

Σ n^3 = ((n*(n+1))/2) ^2;
Σ n^2 = (n*(n+1)*(2n+1))/6;
Σ n = (n*(n+1))/2;

将所有这些值代入方程式1中，

=> (n*(n+1)^2/4 + (3 * (n*(n+1)*(2n+1))/6) + (2 * (n*(n+1))/2)
=> (n*(n+1))^2/4 + ((n*(n+1)*(2n+1))/2) + (2 * (n*(n+1))/2)
=> (n*(n+1))/2 * {(n*(n+1)/2) + (2n+1) + (2)}
=> (n*(n+1))/2 * {(n^2+n) + (4n+2) + (4))/2}
=> (n*(n+1))/4 * {(n^2 +5n+6)}
=> (n*(n+1))/4 * {(n+2)*(n+3)}
=> (n*(n+1)*(n+2)*(n+3))/4

示例：使用直接公式的代码

因此，可以通过这个公式直接解决这个问题。

#include <bits/stdc++.h>
using namespace std;
// Function to calculate the sum of series.
// We just need to derive the formula, we can directly put the value of n in the formula to get our answer.
int SeriesSum(int n){
   // Here to avoid the situation of an overflow of data we are doing step-wise calculations by dividing (n*(n+1)) and ((n+2)*(n+3)) separately by 2 as  (n*(n+1)) must be divisible by 2 and ((n+2)*(n+3)) is also divisible by 2
   return ((n * (n + 1))/2) * (((n + 2) * (n + 3))/ 2);
}
// main function
int main(){
   // Declare a variable 'n'
   int n=5;
   cout<< "The number n is given as "<< n << endl;
   // Call the function to get the output
   cout<< "The sum of the series is: " << SeriesSum(n);
   return 0;
}

输出

The number n is given as 5
The sum of the series is: 420

对于以上代码的复杂性

• 时间复杂度−O(1); 此代码仅使用输入n来执行计算。

• 空间复杂度−O(1); 代码使用固定数量的变量来存储输入值和结果，不管输入的大小如何。

结论

在本文中，我们学习了解决相同问题的级数求和的3种不同方法。我们还学习了如何使用求和性质直接推导出级数求和的公式，以编写代码并节省时间和空间。我们还看到了如何避免输入值问题的溢出情况。