C++で数列の総和を求めるプログラム：連続する整数の積の和を効率的に計算する方法

この問題では、数列を定義する2つの整数 n と k が与えられます。私たちのタスクは、C++ を使って次の形式で表される数列の総和を求めるプログラムを作成することです。

(1×2×3×…×k) + (2×3×…×k×(k+1)) + (3×4×…×(k+1)×(k+2)) + … + ((n−k+1)×(n−k+2)×…×n)

各項は「連続する k 個の整数の積」で構成されており、隣接する項どうしは開始位置が1つずつずれていきます。ここでは、与えられた k の値に基づいて、この数列の総和を計算します。

入力例と出力例

入力

n = 4, k = 3

出力

30

説明

数列：(1×2×3) + (2×3×4) = 6 + 24 = 30

n = 4、k = 3 の場合、数列は「1×2×3」と「2×3×4」の2つの項から構成され、その合計は 30 になります。

解法①：二重ループによる素朴なアプローチ

最も直感的な方法は、反復処理によって総和を求めるものです。外側のループで各項の開始位置を1つずつ進めながら、内側のループで「連続する k 個の整数の積」を計算し、その値を順に加算していきます。

サンプルコード

#include <iostream>
using namespace std;

int findSeriesSum(int n, int k){
    int sumVal = 0, term = 1;
    for(int i = 1; i <= (n - k + 1); i++){
        term = 1;
        for(int j = i; j < (k + i); j++){
            term *= j;
        }
        sumVal += term;
    }
    return sumVal;
}

int main(){
    int n = 4, k = 3;
    cout << "The sum of series is " << findSeriesSum(n, k);
    return 0;
}

出力

The sum of series is 30

このプログラムは正しい結果を返しますが、二重ループを必要とするため時間計算量は O(n²) のオーダーとなり、n が大きくなるほど処理が遅くなるという欠点があります。

解法②：一般公式を使った効率的なアプローチ

この数列には便利な数学的性質があり、総和は次の一般公式から一気に求められます。

総和 = (n＋1) × n × (n−1) × (n−2) × … × (n−k＋1) ÷ (k＋1)

この公式を使えば、ループは1つだけでよく、時間計算量は O(k) まで削減できます。実際に検証すると、n = 4、k = 3 の場合は (5 × 4 × 3 × 2) ÷ 4 = 120 ÷ 4 = 30 となり、確かに一致します。

サンプルコード

#include <iostream>
using namespace std;

int findSeriesSum(int n, int k){
    int sumVal = 1;
    for(int i = n + 1; i > n - k; i--)
        sumVal *= i;
    sumVal /= (k + 1);
    return sumVal;
}

int main(){
    int n = 4, k = 3;
    cout << "The sum of series is " << findSeriesSum(n, k);
    return 0;
}

出力

The sum of series is 30

まとめ

連続する整数の積からなる数列の総和は、二重ループでも O(n²) で求められますが、一般公式を活用すれば O(k) で効率的に計算できます。なお、n や k が大きい場合は積が急激に増大し、int 型ではオーバーフローが発生する恐れがあるため、実運用では long long 型などより大きなデータ型の使用を検討してください。数列の数学的な性質を見抜いてアルゴリズムを改良できるかどうかは、競技プログラミングや実務の両面で重要なスキルといえます。