C++で級数「1+2+2+3+3+3+…+n」の総和を求めるプログラム

問題概要

この問題では、級数の第n項を表す整数nが与えられます。私たちの課題は、C++で級数 1 + 2 + 2 + 3 + 3 + 3 + … + n の総和を求めるプログラムを作成することです。

問題の説明 ― この級数では、第k項が「数kをk回加えた値」になっています。言い換えると、これは平方数（1×1、2×2、3×3…）を順番に加えていく級数です。

入出力例

まず、具体例で問題を確認しましょう。

入力：

n = 4

出力：

30

説明： 第4項までの総和は 1 + 2 + 2 + 3 + 3 + 3 + 4 + 4 + 4 + 4 = 30 となります。

解法アプローチ

最も効率的な解法は、級数の総和を求める一般公式を利用することです。ここでは、思いつきうる複数の解法を段階的に比較しながら見ていきましょう。

解法1：単純な二重ループ（時間計算量 O(n²)）

最もシンプルな解法は、第n項までの数値を素直に足し合わせる方法です。外側のループで各項を処理し、内側のループでその項に含まれる個々の値を加算するため、二重ループが必要になります。

アルゴリズム

初期化： sumVar = 0;

• ステップ1 ― i を 1 から n までループする。
  • ステップ1.1 ― j を 1 から i までループする。
    • ステップ1.1.1 ― sumVar += i; として sumVar を更新する。
• ステップ2 ― sumVar を出力する。

実装例

#include <iostream>
using namespace std;
int calcSeriesSum(int n){
    int sumVar = 0;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= i; j++){
            sumVar += i;
        }
    }
    return sumVar;
}
int main(){
    int n = 7;
    cout<<n<<"までの級数の総和は "<<calcSeriesSum(n);
    return 0;
}

出力：

7までの級数の総和は 140

この解法は理解しやすい反面、二重ループを使用しているため時間計算量が O(n²) となり、nが大きくなると非効率です。

解法2：乗算を利用した一重ループ（時間計算量 O(n)）

より効率的なアプローチは、「ある数を自分自身にn回加えることは、その数同士の掛け算と同じ」という性質を利用することです。

たとえば、5 + 5 + 5 + 5 + 5 = 5 × 5 ですね。そこで、内側のループを乗算に置き換えることで、計算を大幅に簡略化できます。

アルゴリズム

初期化： sumVal = 0;

• ステップ1 ― i を 1 から n までループする。
• ステップ2 ― sumVal += (i * i); として sumVal を更新する。

実装例

#include <iostream>
using namespace std;
int calcSeriesSum(int n){
    int sumVar = 0;
    for(int i = 1; i <= n; i++){
        sumVar += (i*i);
    }
    return sumVar;
}
int main(){
    int n = 7;
    cout<<n<<"までの級数の総和は "<<calcSeriesSum(n);
    return 0;
}

出力：

7までの級数の総和は 140

この解法はループが一つだけで済むため、時間計算量は O(n) に改善されます。しかし、後述するようにO(1)で求められるため、これが最善というわけではありません。

解法3：数学の公式を利用（時間計算量 O(1)）― 最も効率的

最も効果的な解法は、与えられた級数の総和に対する一般公式を使うことです。まず、級数を変形してみましょう。

1 + (2+2) + (3+3+3) + … + (N+N+…+N)
= 1×1 + 2×2 + 3×3 + … + N×N
= 1² + 2² + 3² + … + N²

つまり、この級数の総和は「1からNまでの平方数の総和」（Σ k²）と等しくなります。そして、平方数の総和には次の有名な公式が成り立ちます。

総和 = n × (n + 1) × (2n + 1) / 6

この公式を使えば、ループを一切使わずに定数時間で答えを求められます。なお、nが大きい場合はオーバーフローを避けるため、long long 型の使用を検討してください。

実装例

#include <iostream>
using namespace std;
int calcSeriesSum(int n){
    int sumVar = ((n * (n + 1) * (2 * n + 1)) / 6);
    return sumVar;
}
int main(){
    int n = 7;
    cout<<n<<"までの級数の総和は "<<calcSeriesSum(n);
    return 0;
}

出力：

7までの級数の総和は 140

まとめ：各解法の比較

級数の構造を見抜いて数式に変換できれば、O(1)の最速解法にたどり着けます。競技プログラミングや実務においても、まずは規則性を数式で表せないかを検討することが重要です。