Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

C++ में N-ary ट्री को पार करने के तरीकों की संख्या


एक N-ary ट्री दिया गया है और हमें इस ट्री को पार करने के कुल तरीकों की संख्या निकालने का कार्य दिया गया है, उदाहरण के लिए -

C++ में N-ary ट्री को पार करने के तरीकों की संख्या

उपरोक्त ट्री के लिए, हमारा आउटपुट 192 होगा।

इस समस्या के लिए, हमें कॉम्बिनेटोरिक्स के बारे में कुछ ज्ञान होना चाहिए। अब इस समस्या में, हमें बस हर पथ के लिए सभी संभावित संयोजनों की जांच करने की आवश्यकता है और यह हमें हमारा उत्तर देगा।

समाधान खोजने का दृष्टिकोण

इस दृष्टिकोण में, हमें बस एक लेवल ऑर्डर ट्रैवर्सल करने की आवश्यकता है और प्रत्येक नोड के बच्चों की संख्या जांचें और फिर बस उसके फैक्टोरियल को उत्तर से गुणा करें।

उदाहरण

उपरोक्त दृष्टिकोण के लिए C++ कोड

#include<bits/stdc++.h> using namespace std; struct Node{ // हमारे नोड की संरचना     char key;     vector<Node *> child; }; Node *createNode(int key){ // नया नोड इनिशियलाइज़ करने का फंक्शन     Node *temp = new Node;     temp->key = key;     return temp; } long long fact(int n){     if(n <= 1)         return 1;     return n * fact(n-1); } int main(){     Node *root = createNode('A');     (root->child).push_back(createNode('B'));     (root->child).push_back(createNode('F'));     (root->child).push_back(createNode('D'));     (root->child).push_back(createNode('E'));     (root->child[2]->child).push_back(createNode('K'));     (root->child[1]->child).push_back(createNode('J'));     (root->child[3]->child).push_back(createNode('G'));     (root->child[0]->child).push_back(createNode('C'));     (root->child[2]->child).push_back(createNode('H'));     (root->child[1]->child).push_back(createNode('I'));     (root->child[2]->child[0]->child).push_back(createNode('N'));     (root->child[2]->child[0]->child).push_back(createNode('M'));     (root->child[1]->child[1]->child).push_back(createNode('L'));     queue<Node*> q;     q.push(root);     long long ans = 1;     while(!q.empty()){         auto z = q.front();         q.pop();         ans *= fact(z -> child.size());         cout << z->child.size() << " ";         for(auto x : z -> child)            q.push(x);    }    cout << ans << "\n";    return 0; }

आउटपुट

4 1 2 2 1 0 0 1 2 0 0 0 0 0 192

उपरोक्त कोड की व्याख्या

इस दृष्टिकोण में, हम BFS (ब्रेडथ-फर्स्ट सर्च) या लेवल ऑर्डर ट्रैवर्सल लागू करते हैं और प्रत्येक नोड के बच्चों की संख्या जांचते हैं। फिर, उस संख्या के फैक्टोरियल को अपने उत्तर से गुणा करते हैं।

निष्कर्ष

यह ट्यूटोरियल N-ary ट्री को पार करने के कई तरीकों को कॉम्बिनेटोरिक्स और BFS लागू करके ढूंढता है। हमने इस समस्या के लिए C++ प्रोग्राम और पूरा दृष्टिकोण भी सीखा जिसे हमने हल किया।

हम यही प्रोग्राम C, Java, Python, और अन्य भाषाओं में भी लिख सकते हैं। आशा है आपको यह ट्यूटोरियल उपयोगी लगा होगा।

  1. C++ में स्ट्रिंग के सबस्ट्रिंग्स की संख्या निकालना C++ में स्ट्रिंग के सबस्ट्रिंग्स की संख्या निकालना

    इस लेख में, आप एक दी गई स्ट्रिंग में बनने वाले सबस्ट्रिंग्स (गैर-खाली) की संख्या निकालने के दृष्टिकोण के बारे में जानेंगे।इनपुट: string = moon आउटपुट: 10 व्याख्या: सबस्ट्रिंग्स हैं m, o, o, n, mo, oo, on, moo, oon और moon। इनपुट: string = yellow आउटपुट: 21समाधान खोजने का दृष्टिकोणमान लें स्ट्रिंग की

  1. C++ का उपयोग करके स्टॉपिंग स्टेशनों की संख्या ज्ञात करें C++ का उपयोग करके स्टॉपिंग स्टेशनों की संख्या ज्ञात करें

    बिंदु X और Y के बीच n संख्या में इंटरमीडिएट ट्रेन स्टेशन हैं। उन विभिन्न तरीकों की गणना करें जिनसे ट्रेनों को s स्टेशनों पर रुकने के लिए व्यवस्थित किया जा सकता है जैसे कि कोई दो स्टेशन एक-दूसरे के बगल में न हों। तो इस लेख में, हम स्टॉपिंग स्टेशनों की संख्या ज्ञात करने के लिए हर संभव दृष्टिकोण की व्य

  1. C++ का उपयोग करके एक सेट पर रिफ्लेक्सिव रिलेशंस की संख्या ज्ञात करें C++ का उपयोग करके एक सेट पर रिफ्लेक्सिव रिलेशंस की संख्या ज्ञात करें

    इस लेख में, हम एक सेट पर रिफ्लेक्सिव रिलेशंस की संख्या ज्ञात करने के दृष्टिकोणों की व्याख्या करेंगे। इस समस्या में, हमें संख्या n दी गई है, और n प्राकृतिक संख्याओं के एक सेट पर, हमें रिफ्लेक्सिव रिलेशंस की संख्या निर्धारित करनी है।रिफ्लेक्सिव रिलेशन - एक सेट A में एक रिलेशन को रिफ्लेक्सिव कहा जाता ह