এই সমস্যায়, আমাদের একটি পূর্ণসংখ্যা n দেওয়া আছে যা উপাদান সংখ্যা নির্দেশ করে। আমাদের কাজ হল একটি প্রোগ্রাম তৈরি করা যা এসোসিয়েটিভ অপারেশন দিয়ে n উপাদান গুণ করার পদ্ধতির সংখ্যা গণনা করবে।
এসোসিয়েটিভ অপারেশন সংখ্যাগুলো যেভাবে সাজানো হোক না কেন একই ফলাফল ফেরত দেয়।
একটি উদাহরণ নিয়ে সমস্যাটি বুঝি,
ইনপুট
3
আউটপুট
12
ব্যাখ্যা
(x*(y*z)), (x*(z*y)), (y*(x*z)), (y*(z*x)), (z*(x*y)), (z*(y*x)), ((x*y)*z), ((y*x)*z), ((x*z)*y), ((z*x)*y), ((z*y)*x), ((y*z)*x).
এই সমস্যাটি সমাধান করতে, আমরা চেষ্টা করব কোনো সম্পর্ক বা সিরিজ আছে কিনা যা তৈরি করা যায় যাতে আমরা আমাদের ফলাফল সাধারণীকরণ করতে পারি। অপারেটরের সংখ্যা ভিত্তিক করে এসোসিয়েটিভ অপারেশনের সংখ্যা দেখি -
1 => 1 2 => 2 3 => 12
এখন, গণনার সাধারণীকরণ চেষ্টা করি। ধরা যাক, n উপাদানের জন্য এসোসিয়েটিভ অপারেশন তৈরি করছি। তবে, আমরা n-1 গুণ অপারেটর এবং n-1 প্যারেনথেসিস রাখতে পারি।
এখানে, আমরা এগুলো দুটি পদ্ধতিতে সাজাব -
(n-1) পর্যন্ত গুণ করার পদ্ধতিগুলো বিবেচনা করে। এবং তারপর শেষ উপাদানটি অ্যাসোসিয়েশনের যেকোনো শেষে যোগ করব। এটি n-1 সংখ্যার জন্য n অপারেটরের জন্য 2*2*(n-2) অ্যাসোসিয়েশন তৈরি করবে।
তারপর আমরা (a1, a2, … a(n-1))-এর গুণ বিবেচনা করব এবং an কে বাম বা ডানে গুণ করব যা অ্যাসোসিয়েশন তৈরি করার অতিরিক্ত দুটি পদ্ধতি দেবে।
উপরের ক্ষেত্রগুলো যোগ করে n অপারেটরের জন্য মোট অ্যাসোসিয়েশন পাই।
ass(n) = ((2*2*(n-2))(ass(n-1))) + 2*(ass(n-1)) ass(n) = (4n-8)(ass(n-1)) + 2*(ass(n-1)) ass(n) = (4n-6)(ass(n-1))
এই সম্পর্কটি ছদ্ম ক্যাটালান নম্বারের মতো, যার একই সূত্র এবং একই প্রাথমিক মান রয়েছে।
তাই, আমরা এখানে ছদ্ম ক্যাটালান নম্বারের সাধারণ সূত্র প্রয়োগ করতে পারি,
ass(n) = (2*n-2)!/(n-1)!
n = 5-এর জন্য আমাদের সূত্রের কাজকর্ম দেখি।
ass(10) = (2*5 - 2)!/ (5-1)! ass(10) = 8!/4! = 40320/24 = 1680
এসোসিয়েটিভ অপারেশন দিয়ে n উপাদান গুণ করার পদ্ধতির সংখ্যা খুঁজে বের করার প্রোগ্রাম
// এসোসিয়েটিভ অপারেশন দিয়ে n উপাদান গুণ করার পদ্ধতির সংখ্যা খুঁজে বের করার প্রোগ্রাম -
উদাহরণ
#include<iostream> using namespace std; long int calcFactorial(int n){ if (n == 0 || n == 1) return 1 ; return n*calcFactorial(n-1); } long int calcWays ( int n ){ int N = 2*n - 2 ; int R = n - 1 ; return (calcFactorial((2*n)-2)/calcFactorial(n-1)); } int main(){ int n = 7; cout<<"এসোসিয়েটিভ অপারেশন দিয়ে "<<n<<" উপাদান গুণ করার পদ্ধতির সংখ্যা : "<<calcWays(n); return 0 ; }
আউটপুট
এসোসিয়েটিভ অপারেশন দিয়ে ৭ উপাদান গুণ করার পদ্ধতির সংখ্যা : 665280
