C++でn個の変数の線形方程式の解の数を見つけます

この問題では、次の形式のn変数の線形方程式が与えられます。

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

n個の変数の線形方程式の解の数を見つけます。

問題を理解するために例を見てみましょう

入力

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

出力

1

説明

Equation : 3x + y = 4.
Solution, x = 0, y = 4.

ソリューションアプローチ

この問題の簡単な解決策は、方程式の値を評価することです。次に、再帰的に呼び出して値を更新します。値が0の場合、ソリューションカウントは1です。それ以外の場合は、係数値を減算して値を繰り返します。

ソリューションの動作を説明するプログラム

例

#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