सी++ का उपयोग करके एन-आरी ट्री को पार करने के तरीकों की संख्या ज्ञात करें

एक एन-आरी पेड़ को देखते हुए और हमें इस पेड़ को पार करने के कुल तरीकों को खोजने का काम सौंपा गया है, उदाहरण के लिए -

उपरोक्त पेड़ के लिए, हमारा उत्पादन 192 होगा।

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

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

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

उदाहरण

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

#include<bits/stdc++.h>
using namespace std;
struct Node{ // structure of our node
    char key;
    vector<Node *> child;
};
Node *createNode(int key){ // function to initialize a new node
    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

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

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

निष्कर्ष

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

हम उसी प्रोग्राम को अन्य भाषाओं जैसे सी, जावा, पायथन और अन्य भाषाओं में लिख सकते हैं। हमें उम्मीद है कि आपको यह ट्यूटोरियल मददगार लगा होगा।