हमें एक ट्री दिया गया है जिसमें अंतहीन स्तर हो सकते हैं, एक वेरिएबल child जो एक नोड के बच्चों की संख्या संग्रहीत करेगा, एक वेरिएबल weight जो पथ से जुड़े वजन को संग्रहीत करेगा और एक वेरिएबल path जो पथ को संग्रहीत करेगा और कार्य उन पथों की संख्या की गणना करना है जिनका वजन X के बराबर है और कम से कम एक एज दिए गए वजन के साथ होनी चाहिए।
उदाहरण के लिए
इनपुट - int child = 4, weight = 4, path = 4;
आउटपुट - वजन X वाले और कम से कम एक एज वजन M वाले पथों की संख्या: 1
व्याख्या - जैसा कि हमें 4 बच्चों वाला नोड दिया गया है जो 4 पथों से जुड़े हैं और पथ से जुड़ा वजन 4 है। तो, हम देख सकते हैं कि वजन 4 वाला केवल एक पथ हो सकता है यानी 1 - 4 इसलिए गिनती 1 है।
इनपुट - int child = 3, weight = 2, path = 4;
आउटपुट - वजन X वाले और कम से कम एक एज वजन M वाले पथों की संख्या: 4
व्याख्या - जैसा कि हमें 3 बच्चों वाला नोड दिया गया है जो 4 पथों से जुड़े हैं और पथ से जुड़ा वजन 2 है। तो, हम देख सकते हैं कि वजन 2 वाले चार पथ हो सकते हैं यानी 1-1, 1 - 2, 2-1 और 2-1 इसलिए, गिनती 4 है।
नीचे दिए गए प्रोग्राम में उपयोग किया गया दृष्टिकोण
- कुल बच्चों की संख्या, पथ और प्रत्येक पथ से जुड़े वजन को वेरिएबल child, weight और path में इनपुट करें।
- दिए गए आकार की एक सरणी घोषित करें।
- i से 0 से सरणी के आकार तक FOR लूप शुरू करें। लूप के अंदर, j से 0 से j 2 से कम तक एक और FOR लूप शुरू करें और फिर arr[i][j] को -1 सेट करें।
- अब path, 0, weight, child और arr को तर्क के रूप में पास करके total_weight() फ़ंक्शन को कॉल करें।
- फ़ंक्शन के अंदर,
- परिणाम संग्रहीत करने के लिए एक अस्थायी वेरिएबल count घोषित करें।
- चेक करें IF path 0 से कम है तो 0 लौटाएं
- चेक करें IF path 0 के बराबर है तो i लौटाएं
- चेक करें IF arr[path][i] 1 के बराबर नहीं है तो arr[path][i] लौटाएं
- j से 1 से child तक FOR लूप शुरू करें। लूप के अंदर, चेक करें IF j weight के बराबर है तो count को total_weight() फ़ंक्शन के पुनरावर्ती कॉल के रूप में सेट करें path-j, 1, weight, child और arr को तर्क के रूप में पास करके।
- अन्यथा, count को total_weight() फ़ंक्शन के पुनरावर्ती कॉल के रूप में सेट करें path-j, i, weight, child और arr को तर्क के रूप में पास करके।
- arr[path][i] को count के रूप में सेट करें और
- 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
