C++で最初のn個の自然数のm番目の合計を求める方法

問題概要

この記事では、2つの整数 m と n が与えられたときに、最初のn個の自然数のm番目の合計を求める方法を解説します。

ここでいう「m番目の合計」とは、n個の自然数の合計をm回繰り返し計算する操作のことです。合計は次の漸化式で定義されます。

m > 1 の場合：

sum(n, m) = sum( sum(n, m-1), 1 )

m = 1 の場合：

sum(n, 1) = n個の自然数の合計 = n × (n + 1) / 2

入出力例

入力： m = 4、n = 2

出力： 231

計算過程：

sum(2, 4) = sum( sum(2, 3), 1 )
          = sum( sum( sum(2, 2), 1 ), 1 )
          = sum( sum( sum( sum(2, 1), 1 ), 1 ), 1 )
          = sum( sum( sum(3, 1), 1 ), 1 )   // sum(2,1) = 2×3/2 = 3
          = sum( sum(6, 1), 1 )             // sum(3,1) = 3×4/2 = 6
          = sum(21, 1)                      // sum(6,1) = 6×7/2 = 21
          = 231                             // sum(21,1) = 21×22/2 = 231

解決アプローチ

最も単純な解法は二重ループを使う方法です。外側のループでm回の繰り返しを制御し、内側のループで現在のn個の自然数の合計を計算します。各周回でnの値を直前の合計値で更新しながら処理を進めていきます。

より効率的なのが再帰呼び出しを活用するアプローチです。再帰のたびに前回の合計値をもとに新しい合計を計算することで、簡潔なコードでm段階の累積合計を求められます。

アルゴリズムの手順

1. ステップ1： m > 1 のとき、sum = sum(n, m-1) × (sum(n, m-1) + 1) ÷ 2 として合計値を更新する。
2. ステップ2： m = 1 のとき、sum = n × (n + 1) ÷ 2 を返す。
3. ステップ3： 最終的な合計値 sum を返す。

C++による実装例

#include <iostream>
using namespace std;

int calcSumN(int n, int m) {

    // m == 1 のときは、通常の自然数の合計を返す
    if (m == 1)
        return (n * (n + 1) / 2);

    // 前段階の合計を再帰的に求め、さらにその合計を取る
    return (calcSumN(n, m-1) * (calcSumN(n, m-1) + 1) / 2);
}

int main() {

    int n = 4;
    int m = 6;
    cout<<m<<"-th summation of first "<<n<<" natural numbers is "<<calcSumN(n, m);
    return 0;
}

実行結果

6-th summation of first 4 natural numbers is 125230148

コードの解説と注意点

関数 calcSumN(n, m) は、m が 1 になるまで自分自身を再帰的に呼び出します。各段階で「1からnまでの自然数の合計 n×(n+1)/2」を前段階の結果に適用していくことで、m段階の累積合計が求まります。

パフォーマンス改善のヒント： 上記の実装では return 文内で calcSumN(n, m-1) を2回呼び出しているため、計算量が O(2^m) と指数関数的に増加します。次のように一度変数に保存すれば、O(m) まで削減できます。

int prev = calcSumN(n, m - 1);
return prev * (prev + 1) / 2;

オーバーフローへの注意： m や n が大きくなると結果は爆発的に増大し、int 型（最大約21億）の範囲をすぐに超えてしまいます。実際、上記の実行結果 125230148 はオーバーフロー発生後の値です。大きな入力を扱う場合は、long long 型や多倍長整数ライブラリの利用を検討しましょう。