C++で三角数の級数（1、3、6、10…）の合計を求める方法

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

合計を計算する前に、まず三角数についておさらいしておきましょう。

三角数とは？

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

三角形は、1行目に1個の点、2行目に2個の点、3行目に3個の点…というように配置することで構成されます。このとき、点の総数が三角数となります。

具体例で問題を理解しよう

入力：

n = 4

出力： 20

説明： sum = T1 + T2 + T3 + T4 = 1 + 3 + 6 + 10 = 20

方法1：ループを使ったシンプルな解法

この問題を解く最もシンプルなアプローチは、n 個の三角数をすべて求め、それらを1つずつ合計変数に加えていく方法です。

アルゴリズム

sum = 0 で初期化する。
Step 1: i = 1 から n までループし、Step 2 と Step 3 を実行する。
Step 2: 各 i の値に対して、公式 t[i] = i*(i+1)/2 を使って三角数を計算する。
Step 3: sum の値を更新する（sum += t[i]）。
Step 4: 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<<"級数 1, 3, 6, 10 ...（三角数）の合計は "<<calcSeriesSum(n);
    return 0;
}

出力

級数 1, 3, 6, 10 ...（三角数）の合計は 56

この解法は正しい結果を返しますが、時間計算量が O(n) となるため、最も効率的な方法とは言えません。

方法2：直接公式を使った効率的な解法

より効率的な解法は、級数の合計を求める直接公式を利用することです。

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 は 1 から n まで
sum = Σ n(n+1)/2
sum = ½ Σ n² + Σ n
sum = ½ Σn² + Σ 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)]

これが三角数の合計を求める一般公式です。つまり、級数の合計は n(n+1)(n+2)/6 で表されます。この公式を使えば、時間計算量 O(1) で答えを求められます。

実装例

#include <iostream>
using namespace std;
int calcSeriesSum(int n) {
    return ( ( n*(n + 1)*(n + 2) )/6);
}
int main() {
    int n = 6;
    cout<<"級数 1, 3, 6, 10 ...（三角数）の合計は "<<calcSeriesSum(n);
    return 0;
}

出力

級数 1, 3, 6, 10 ...（三角数）の合計は 56

まとめ

三角数の級数の合計は、ループで順番に足し合わせる方法（O(n)）でも求められますが、直接公式 n(n+1)(n+2)/6 を使えば定数時間で計算でき、はるかに効率的です。大きな n を扱う場合には、公式を使った解法を推奨します。