এই আর্টিকেলে, আমাদের একটি প্রশ্ন দেওয়া আছে যেখানে পয়েন্ট A থেকে B-এ যাওয়ার মোট পথের সংখ্যা বের করতে হবে, যেখানে A এবং B ফিক্সড পয়েন্ট, অর্থাৎ A হলো গ্রিডের টপ-লেফট (top-left) পয়েন্ট এবং B হলো গ্রিডের বটম-রাইট (bottom-right) পয়েন্ট। উদাহরণস্বরূপ:
Input : N = 5 Output : 252 Input : N = 4 Output : 70 Input : N = 3 Output : 20
দেওয়া সমস্যায়, আমরা সহজ পর্যবেক্ষণ দিয়ে উত্তরটি ফর্মুলাইজ করতে পারি এবং ফলাফল পেতে পারি।
সমাধানের পদ্ধতি
এই পদ্ধতিতে, আমরা প্রদত্ত সমস্যার জন্য একটি সূত্র তৈরি করি পর্যবেক্ষণ দিয়ে যে গ্রিডে A থেকে B-এ যাওয়ার জন্য আমাদের ডান দিকের দিকে n বার এবং নিচের দিকে n বার ট্রাভেল করতে হবে, তাই মানে আমাদের এই পথগুলোর সব কোম্বিনেশন (combination) বের করতে হবে, যা আমাদের (n+n) এবং n-এর কোম্বিনেশন ফর্মুলা দিয়ে দেয়।
উদাহরণ
#include<bits/stdc++.h> using namespace std; int fact(int n){ // ফ্যাক্টোরিয়াল ফাংশন if(n <= 1) return 1; return n * fact(n-1); } int main() { int n = 5; // দেওয়া n int answer = 0; // আমাদের উত্তর answer = fact(n+n); // 2*n-এর ফ্যাক্টোরিয়াল বের করুন answer = answer / (fact(n) * fact(n)); // (2*n)! / (n! + n!) cout << answer << "\n"; }
আউটপুট
252
উপরোক্ত কোডের ব্যাখ্যা
এই কোডে, আমরা 2*n কে n-এ কোম্বিনেশন ফর্মুলা ক্যালকুলেট করি কারণ আমরা জানি যে পয়েন্ট A থেকে B-এ যাওয়ার জন্য আমাদের ঠিক ২*n অপারেশন লাগবে দুটি ডাইরেকশনে, অর্থাৎ এক ডাইরেকশনে n অপারেশন এবং অন্য ডাইরেকশনে n অপারেশন। তাই আমরা এই অপারেশনগুলোর সব সম্ভাব্য কোম্বিনেশন বের করি, অর্থাৎ (2*n)! / (n! * n!)。 এই প্রোগ্রামের ওভারঅল টাইম কমপ্লেক্সিটি O(1) অর্থাৎ আমাদের কমপ্লেক্সিটি দেওয়া n-এর ওপর নির্ভর করে না।
উপসংহার
এই আর্টিকেলে, আমরা একটি গ্রিডে একটি পয়েন্ট থেকে অন্য পয়েন্টে যাওয়ার পথের সংখ্যা বের করার সমস্যা আলোচনা করেছি। আমরা এই সমস্যার জন্য C++ প্রোগ্রাম এবং সম্পূর্ণ পদ্ধতি শিখেছি। একই প্রোগ্রামটি C, Java, Python এবং অন্যান্য ভাষায়ও লিখা যায়। আশা করি আপনি এই আর্টিকেলটিকে উপকারী পাবেন।
