इस समस्या में, हमें एक पूर्णांक 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 संख्याओं के लिए 2*2*(n-2) एसोसिएशन बनाएगा n ऑपरेटर्स के लिए।
फिर हम (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(5) = (2*5 - 2)! / (5-1)! ass(5) = 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;
}
आउटपुट
एसोसिएटिव ऑपरेशन के साथ 7 तत्वों को गुणा करने के तरीके: 665280