কম্পিউটার টিউটোরিয়াল

C++ দিয়ে N-ary ট্রি ট্রাভার্স করার উপায়ের সংখ্যা বের করা

একটি N-ary ট্রি দেওয়া আছে এবং আমাদের এই ট্রি ট্রাভার্স (traverse) করার মোট উপায়ের (number of ways) সংখ্যা বের করতে হবে। উদাহরণ −

C++ দিয়ে N-ary ট্রি ট্রাভার্স করার উপায়ের সংখ্যা বের করা

উপরের ট্রির জন্য আউটপুট হবে ১৯২।

এই সমস্যা সমাধানের জন্য কৌম্বিনেট্রিক্স (Combinatorics) সম্পর্কে জ্ঞান প্রয়োজন। এই সমস্যায় আমরা সহজে প্রতিটি পথের সব সম্ভাব্য কম্বিনেশন চেক করব এবং সেটিই উত্তর দেবে।

সমাধানের পদ্ধতি

এই পদ্ধতিতে, আমরা সিম্পলি লেভেল অর্ডার ট্রাভার্সাল (level order traversal) করব এবং প্রতিটি নোডের কতটি চাইল্ড (child) আছে সেটি চেক করব এবং তার ফ্যাক্টোরিয়াল (factorial) কে আন্সারের সাথে গুণ করব।

উদাহরণ

উপরোক্ত পদ্ধতির 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 (Breadth-First Search) বা লেভেল অর্ডার ট্রাভার্সাল প্রয়োগ করি এবং প্রতিটি নোডের চাইল্ড সংখ্যা চেক করি। তারপর সেই সংখ্যার ফ্যাক্টোরিয়ালকে আন্সারের সাথে গুণ করি।

উপসংহার

এই টিউটোরিয়ালে N-ary ট্রি ট্রাভার্স করার উপায়ের সংখ্যা বের করা হয়েছে কৌম্বিনেট্রিক্স এবং BFS প্রয়োগ করে। আমরা এই সমস্যার C++ প্রোগ্রাম ও সম্পূর্ণ পদ্ধতি দেখেছি। একই প্রোগ্রাম C, Java, Python ইত্যাদি ভাষায়ও লিখা যায়। আশা করি আপনি এই টিউটোরিয়ালটি সহায়ক পাবেন।

  1. C++ ব্যবহার করে পেন্টাগোনাল পিরামিডাল সংখ্যা নির্ণয় করুন

  2. C++ দিয়ে একটি স্ট্রিংয়ের সাবস্ট্রিং-এর সংখ্যা বের করা

  3. C++-এ ট্রেন স্টপেজ স্টেশন সংখ্যা বের করুন

  4. C++-এ সেটে রিফ্লেক্সিভ রিলেশন সংখ্যা বের করুন