C++で和の方程式 x + y + z = n の非負整数解の個数を求める方法

このチュートリアルでは、和の方程式の非負整数解の個数を求めるプログラムをC++で作成します。

扱う方程式は x + y + z = n です。数値 n が与えられたとき、この方程式を満たす非負整数解(x, y, z がすべて 0 以上の整数)がいくつ存在するかを求めます。まずは具体例を見てみましょう。

入力

2

出力

6

この場合の解は以下の6通りです。

0 0 2
0 1 1
0 2 0
1 0 1
1 1 0
2 0 0

アルゴリズム

• 数値 n を初期化します。

• 解の個数を数える変数 count を 0 に初期化します。

• 3つの数値のすべての組み合わせを調べるため、三重のネストしたループを記述します。

  • 現在の組み合わせが方程式を満たすかどうかを判定します。

  • 方程式を満たしていれば、count を 1 増やします。

• 最後に count を返します。

実装

以下は、上記のアルゴリズムをC++で実装したコードです。

#include <bits/stdc++.h>
using namespace std;
int getEquationSolutionCount(int n) {
    int count = 0;
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= n - i; j++) {
            for (int k = 0; k <= n - i - j; k++) {
                if (i + j + k == n) {
                    count++;
                }
            }
        }
    }
    return count;
}
int main() {
    int n = 10;
    cout << getEquationSolutionCount(n) << endl;
    return 0;
}

出力

上記のコードを実行すると、次の結果が得られます。

66

計算量について

このアプローチは三重ループを使用するため、時間計算量は O(n³) となります。n が小さい範囲では十分に高速ですが、n が大きくなると処理時間が増加します。

なお、この問題には数学的な性質も利用できます。x + y + z = n の非負整数解の個数は「重複組合せ」の公式 C(n+2, 2) = (n+1)(n+2)/2 で一意に求められるため、O(1) で計算することも可能です。ただし、全探索による実装はロジックの理解に役立つため、学習目的としては非常に有効です。