C++でn変数の線形方程式の解の個数を求める方法

問題の概要

この問題では、次のような形式で表されるn個の変数を持つ線形方程式が与えられます。

coeff1(var1) + coeff2(var2) + … + coeffn(varn) = value

この線形方程式の解が全部でいくつ存在するのかを求めるのが目的です。

入出力例で問題を理解する

まずは具体的な例を見てみましょう。

入力

coeff[] = {3, 1}, value = 4

出力

1

説明

方程式：3x + y = 4
解：x = 0, y = 4

解法のアプローチ

最もシンプルな解き方は、方程式の値を段階的に評価していく方法です。各係数をvalueから順に引いていき、再帰的に処理を進めます。valueがちょうど0になった時点で、それは有効な解が1つ見つかったことを意味します。それ以外の場合は、残りの係数をvalueから差し引きながら再帰呼び出しを続けます。

この手法は「組み合わせの総数を数える」という考え方に基づいており、同じ係数を繰り返し使える点が特徴です。計算量は係数の数とvalueの値に依存して指数的に増えるため、小規模な入力に適したアプローチです。

プログラム例

以下は、この解法の動作を示すC++プログラムです。

#include<iostream>
using namespace std;
int countSolutionsEq(int coeff[], int start, int end, int value) {
    if (value == 0)
        return 1;
    int coefCount = 0;
    for (int i = start; i <= end; i++)
        if (coeff[i] <= value)
            coefCount += countSolutionsEq(coeff, i, end, value - coeff[i]);
    return coefCount;
}
int main() {
    int coeff[] = {3, 5, 1, 2};
    int value = 6;
    int n = sizeof(coeff) / sizeof(coeff[0]);
    cout<<"The number of solutions of the linear equation is "<<countSolutionsEq(coeff, 0, n - 1, value);
    return 0;
}

実行結果

The number of solutions of the linear equation is 8

まとめ

この記事では、n変数の線形方程式における解の個数を、再帰的な探索によって求める方法を紹介しました。valueが0になるまで係数を減算しながら再帰を深めていくことで、すべての有効な解の組み合わせを効率よく数え上げることができます。動的計画法などを用いればさらに高速化できるため、大規模な入力への拡張も検討してみると良いでしょう。