Cho một cây N-ary và chúng tôi có nhiệm vụ tìm tổng số cách để đi qua cây này, chẳng hạn -
Đối với cây trên, sản lượng của chúng ta sẽ là 192.
Đối với bài toán này, chúng ta cần có một số kiến thức về tổ hợp. Bây giờ trong vấn đề này, chúng tôi chỉ cần kiểm tra tất cả các kết hợp có thể có cho mọi đường dẫn và điều đó sẽ cho chúng tôi câu trả lời của chúng tôi.
Phương pháp tiếp cận để tìm giải pháp
Trong cách tiếp cận này, chúng ta chỉ cần thực hiện duyệt qua thứ tự cấp và kiểm tra số nút con mà mỗi nút có và sau đó chỉ cần nhân giai thừa của nó với câu trả lời.
Ví dụ
Mã C ++ cho phương pháp tiếp cận trên
#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;
} Đầu ra
4 1 2 2 1 0 0 1 2 0 0 0 0 0 192
Giải thích về Quy tắc trên
Trong cách tiếp cận này, chúng tôi áp dụng BFS (Breadth-First Search) hoặc duyệt theo thứ tự mức độ và kiểm tra số lượng nút con mà mỗi nút có. Sau đó, nhân giai thừa của số đó với câu trả lời của chúng tôi.
Kết luận
Hướng dẫn này tìm một số cách để duyệt qua các tổ hợp cây N-ary và bằng cách áp dụng BFS. Chúng tôi cũng đã học chương trình C ++ cho vấn đề này và cách tiếp cận hoàn chỉnh mà chúng tôi đã giải quyết.
Chúng ta có thể viết cùng một chương trình bằng các ngôn ngữ khác như C, java, python và các ngôn ngữ khác. Chúng tôi hy vọng bạn thấy hướng dẫn này hữu ích.