ให้ต้นไม้ N-ary และเราถูกมอบหมายให้ค้นหาจำนวนวิธีที่จะข้ามต้นไม้นี้ ตัวอย่างเช่น −
สำหรับแผนภูมิด้านบน ผลลัพธ์ของเราคือ 192
สำหรับปัญหานี้ เราต้องมีความรู้เกี่ยวกับ combinatorics บ้าง ในปัญหานี้ เราเพียงแค่ต้องตรวจสอบชุดค่าผสมที่เป็นไปได้ทั้งหมดสำหรับทุกเส้นทาง และนั่นจะให้คำตอบแก่เรา
แนวทางในการหาแนวทางแก้ไข
ในแนวทางนี้ เราเพียงแค่ต้องทำการข้ามผ่านลำดับระดับ และตรวจสอบจำนวนลูกที่แต่ละโหนดมี จากนั้นเพียงคูณแฟคทอเรียลกับคำตอบ
ตัวอย่าง
รหัส 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
คำอธิบายของโค้ดด้านบน
ในแนวทางนี้ เราใช้ BFS(Breadth-First Search) หรือการข้ามผ่านลำดับระดับ และตรวจสอบจำนวนชายน์ที่แต่ละโหนดมี จากนั้นคูณแฟกทอเรียลของจำนวนนั้นกับคำตอบของเรา
บทสรุป
บทช่วยสอนนี้พบหลายวิธีในการสำรวจ N-ary tree combinatorics และโดยการใช้ BFS นอกจากนี้เรายังได้เรียนรู้โปรแกรม C++ สำหรับปัญหานี้และแนวทางทั้งหมดที่เราแก้ไข
เราสามารถเขียนโปรแกรมเดียวกันในภาษาอื่นๆ เช่น C, java, python และภาษาอื่นๆ เราหวังว่าคุณจะพบว่าบทช่วยสอนนี้มีประโยชน์
