重みが正確にXであり、C++で重みMの少なくとも1つのエッジを持つパスの数をカウントします。

無限のレベルを持つことができるツリー、ノードが持つことができる子の数を格納する可変の子、パスに関連付けられた重みを格納する可変の重み、およびパスとタスクを格納する可変のパスが与えられます。 Xに等しい重みを持つパスの数を計算し、指定された重みを持つエッジが少なくとも1つ存在する必要があります。

例

入力- int child =4、weight =4、path =4;

出力- 重みが正確にXであり、重みMの少なくとも1つのエッジを持つパスの数は次のとおりです。1

説明- 4つの子が4つのパスに接続されており、パスに4の重みが関連付けられているノードが与えられているためです。したがって、重みが4、つまり1〜4のパスは1つしか存在できないため、カウントは1であることがわかります。

入力- int child =3、weight =2、path =4;

出力- 重みが正確にXであり、重みMの少なくとも1つのエッジを持つパスの数は次のとおりです。4

説明- 3つの子が4つのパスに接続されており、パスに2の重みが関連付けられているノードが与えられているためです。したがって、重みが2の4つのパス、つまり1-1、1-2、2-1、および2-1が存在する可能性があることがわかります。したがって、カウントは4です。

以下のプログラムで使用されているアプローチは次のとおりです

• 変数の子、重み、およびパスの各パスに関連付けられている子、パス、および重みの総数をそれぞれ入力します。
• 指定されたサイズの配列を宣言します。
• 配列のサイズになるまで、iから0までのループFORを開始します。ループ内で、jから0までの別のループFORを開始し、jが2未満になるまで、arr[i][j]を-1に設定します。
• ここで、path、0、weight、child、およびarrを関数の引数として渡して、関数total_weight（）を呼び出します。
• 関数内
  • 結果を格納するための一時変数カウントを宣言します。
  • 0未満のIFパスを確認してから、0を返します
  • IFパスが0に等しいことを確認してから、iを返します
  • arr [path] [i]が1に等しくないかどうかを確認してから、arr [path] [i]
  を返します。
  • jから子までのループFORを開始します。ループ内で、path-j、1、weight、child、およびarrを引数として関数に渡すことにより、関数total_weight（）関数への再帰呼び出しとしてifjがsetcountよりも重みに等しいことを確認します。
  • それ以外の場合は、path-j、i、weight、child、およびarrを引数として関数に渡すことにより、関数total_weight（）関数への再帰呼び出しとしてcountを設定します。
  • arr[path][i]をカウントとして設定します
• return arr [path] [i]
• 結果を印刷します。

例

#include <bits/stdc++.h>
using namespace std;
#define size 4
#define col 4
int total_weight(int path, int i, int weight, int child, int arr[size + 1][col]) {
   int count = 0;
   if (path < 0) {
      return 0;
   }
   if (path == 0) {
      return i;
   }
   if (arr[path][i] != -1) {
      return arr[path][i];
   }
   for (int j = 1; j <= child; j++) {
      if (j == weight) {
         count += total_weight(path - j, 1, weight, child, arr);
      } else {
         count += total_weight(path - j, i, weight, child, arr);
      }
   }
   arr[path][i] = count;
   return arr[path][i];
}
int main() {
   int child = 4, weight = 4, path = 4;
   int arr[size + 1][col];
   for (int i = 0; i <= size; i++) {
      for (int j = 0; j < 2; j++) {
         arr[i][j] = -1;
      }
   }
   cout << "Count of number of paths whose weight is exactly X and has at-least one edge of weight M are: " << total_weight(path, 0, weight, child, arr);
}

上記のコードを実行すると、次の出力が生成されます-

出力

Count of number of paths whose weight is exactly X and has at-least one edge of weight M are: 1