पथों की संख्या की गणना करें जिनका वजन बिल्कुल X है और C++ में वजन M का कम से कम एक किनारा है

हमें एक पेड़ दिया जाता है जिसमें अंतहीन स्तर हो सकते हैं, एक चर बच्चा जो एक नोड के बच्चों की संख्या को संग्रहीत करेगा, एक चर वजन जो पथ से जुड़े वजन को संग्रहीत करेगा और एक चर पथ जो पथ और कार्य को संग्रहीत करेगा। पथों की संख्या की गणना करने के लिए जिनका वज़न X के बराबर है और दिए गए वज़न के साथ कम से कम एक किनारा होना चाहिए।

उदाहरण के लिए

इनपुट - इंट चाइल्ड =4, वज़न =4, पथ =4;

आउटपुट - पथों की संख्या जिनका वजन ठीक X है और जिनका वजन M का कम से कम एक किनारा है:1

स्पष्टीकरण - जैसा कि हमें 4 पथों से जुड़े 4 बच्चों वाले नोड के साथ दिया गया है और पथ से जुड़े 4 का वजन है। तो, हम देख सकते हैं कि वजन के साथ केवल एक ही पथ हो सकता है 4 यानी 1 - 4 इसलिए गिनती 1 है।

इनपुट - इंट चाइल्ड =3, वज़न =2, पथ =4;

आउटपुट - पथों की संख्या जिनका वजन ठीक X है और जिनका वजन M का कम से कम एक किनारा है:4

स्पष्टीकरण - जैसा कि हमें नोड के साथ दिया गया है जिसमें 4 पथ से जुड़े 3 बच्चे हैं और पथ से जुड़े 2 का वजन है। तो, हम देख सकते हैं कि 2 के रूप में वजन के साथ चार पथ हो सकते हैं अर्थात 1-1, 1 - 2, 2-1 और 2-1 इसलिए, गिनती 4 है।

नीचे दिए गए प्रोग्राम में इस्तेमाल किया गया तरीका इस प्रकार है

• चर के बच्चे, वजन और पथ में प्रत्येक पथ से जुड़े बच्चों की कुल संख्या, पथ और वजन क्रमशः इनपुट करें।
• दिए गए आकार की एक सरणी घोषित करें।
• एक सरणी के आकार तक i से 0 तक के लिए लूप प्रारंभ करें। लूप के अंदर, एक और लूप FOR j से 0 तक j से 2 से कम तक शुरू करें और फिर arr[i][j] को -1 के रूप में सेट करें।
• अब फ़ंक्शन के तर्क के रूप में पथ, 0, वज़न, चाइल्ड और एआर पास करके फंक्शन Total_weight() को कॉल करें।
• समारोह के अंदर,
  • परिणाम संग्रहीत करने के लिए एक अस्थायी चर गणना घोषित करें।
  • जांचें IF पथ 0 से कम है और फिर 0 लौटाएं
  • जांचें कि क्या पथ 0 के बराबर है, फिर मैं वापस आ जाता हूं
  • जांचें IF arr[path][i] 1 के बराबर नहीं है तो वापस arr[path][i]
  • जे से 1 तक बच्चे के लिए लूप शुरू करें। लूप के अंदर, जाँच करें कि IF j, फंक्शन के लिए रिकर्सिव कॉल के रूप में सेट काउंट की तुलना में वज़न के बराबर है, कुल_वेट () फ़ंक्शन को पथ-जे, 1, वज़न, चाइल्ड और एरर को तर्क के रूप में पास करके जाँचें।
  • अन्यथा, फ़ंक्शन के लिए एक पुनरावर्ती कॉल के रूप में सेट करें total_weight() फ़ंक्शन पथ-जे, i, वजन, बच्चे को पास करके और फ़ंक्शन को तर्क के रूप में गिरफ्तार करें।
  • गिरफ्तारी [पथ] [i] को गिनती के रूप में सेट करें और
• रिटर्न एआर [पथ] [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