C ++のシリーズ1、3、6、10…（三角数）の合計

この問題では、級数1、3、6、10…（三角数）の要素のnが与えられる数nが与えられます。私たちの仕事は、級数の合計を計算するプログラムを作成することです。

合計を計算する前に、三角数についてブラッシュアップしましょう。

三角数は、三角形の形で表すことができる数です。

三角形は、最初の行に1つのポイントがあり、2番目の行に2つのポイントがある、というように形成されます。

例

問題を理解するために例を見てみましょう

入力

n = 4

出力

説明 − 合計=T1+ T2 + T3 + T4 =1 + 3 + 6 + 10 =20

この問題を解決する簡単な方法は、n個の三角数をすべて見つけることです。そして、それらを合計変数に1つずつ追加します。

アルゴリズム

Initialise sum = 0.
Step 1: loop for i = 0 to n. And follow steps 2 and 3
Step 2: for each value of i, calculate the triangular numbers using the formula, t[i] = ∑ i = i*(i+1)/2.
Step 3: Update sum value, sum += t[i].
Step 4: return sum.

例

ソリューションの動作を説明するプログラム

#include <iostream>
using namespace std;
int calcSeriesSum(int n) {
   int sum = 0;
   for (int i=1; i<=n; i++)
   sum += i*(i+1)/2;
   return sum;
}
int main() {
   int n = 6;
   cout<<"Sum of the series 1, 3, 6, 10 ... (Triangular Numbers) is "<<calcSeriesSum(n);
   return 0;
}

出力

Sum of the series 1, 3, 6, 10 ... (Triangular Numbers) is 56

O（n）、時間計算量がかかるため、これは最も効果的なソリューションではありません。

より効果的な解決策は、合計に直接式を使用することです。

Tiがi番目の三角数の場合。次に、

T1 =1

T2 =3

T3 =6

Tn =n *（n + 1）/ 2

すべての三角数の合計は

sum = 1 + 3 + 6 + 10 + …
sum = T1 + T2 + T3 + … + Tn
sum = ∑ (Ti) , i -> 0 to n
sum = ∑ (n)(n+1)/2
sum = ½ ∑ n2 + n
sum = ½ ∑n^2 + ∑ n
sum = ½ [ (n*(n+1)*(2n+1)/6) + (n*(n+1)/2) ]
sum = ½ (n*(n+1)/2)*[ (2n+1)/3 + 1 ]
sum = ¼ [n*(n+1)]*[(2n+1+3)/3]
sum = ¼ [n*(n+1)]*[(2n+4)/3]
sum = ¼ [n*(n+1)]*[2(n+2)/3]
sum= ⅙ [n*(n+1)*(n+2)]

これは、三角数の合計の一般式です。

例

ソリューションの動作を説明するプログラム

#include <iostream>
using namespace std;
int calcSeriesSum(int n) {
   return ( ( n*(n + 1)*(n + 2) )/6);
}
int main() {
   int n = 6;
   cout<<"Sum of the series 1, 3, 6, 10 ... (Triangular Numbers) is "<<calcSeriesSum(n);
   return 0;
}

出力

Sum of the series 1, 3, 6, 10 ... (Triangular Numbers) is 56