Cari bilangan cara untuk melintasi pokok N-ary menggunakan C++

Memandangkan pokok N-ary, tugas kita adalah untuk mencari jumlah cara untuk melintasi pokok itu, cth.

Untuk masalah ini, kita memerlukan sedikit pengetahuan tentang kombinatorik. Sekarang dalam masalah ini kita hanya perlu menyemak semua kemungkinan kombinasi setiap laluan dan ini akan memberi kita jawapannya.

Kaedah untuk mencari penyelesaian

Dalam kaedah ini, kita hanya perlu melakukan traversal tahap, semak bilangan anak yang ada pada setiap nod, dan kemudian darabkan secara berfaktor dengan jawapan.

Contoh

C++ kod kaedah di atas

#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(&#39;A&#39;);
    (root->child).push_back(createNode(&#39;B&#39;));
    (root->child).push_back(createNode(&#39;F&#39;));
    (root->child).push_back(createNode(&#39;D&#39;));
    (root->child).push_back(createNode(&#39;E&#39;));
    (root->child[2]->child).push_back(createNode(&#39;K&#39;));
    (root->child[1]->child).push_back(createNode(&#39;J&#39;));
    (root->child[3]->child).push_back(createNode(&#39;G&#39;));
    (root->child[0]->child).push_back(createNode(&#39;C&#39;));
    (root->child[2]->child).push_back(createNode(&#39;H&#39;));
    (root->child[1]->child).push_back(createNode(&#39;I&#39;));
    (root->child[2]->child[0]->child).push_back(createNode(&#39;N&#39;));
    (root->child[2]->child[0]->child).push_back(createNode(&#39;M&#39;));
    (root->child[1]->child[1]->child).push_back(createNode(&#39;L&#39;));
    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;
}

Output

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

Penjelasan kod di atas

Dalam kaedah ini kami menggunakan BFS (Breadth First Number Search) dan tiada traversal hierarki setiap anak nod. Kemudian, darabkan faktorial kuantiti itu dengan jawapan kita.

Kesimpulan

Tutorial ini memperkenalkan beberapa kaedah merentasi gabungan pokok N-ary dan BFS yang digunakan. Kami juga mempelajari program C++ dan kaedah lengkap untuk menyelesaikan masalah ini.

Kami boleh menulis program yang sama dalam bahasa lain seperti C, Java, Python dan bahasa lain. Harap anda mendapati tutorial ini membantu.

Atas ialah kandungan terperinci Cari bilangan cara untuk melintasi pokok N-ary menggunakan C++. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!