सी ++ में एक सहयोगी ऑपरेशन के साथ एन तत्वों को गुणा करने के तरीके

इस समस्या में, हमें एक पूर्णांक n दिया गया है जो तत्वों की संख्या है। हमारा काम एक ऐसा प्रोग्राम बनाना है जो साहचर्य संचालन के साथ n तत्वों को गुणा करने के तरीकों की संख्या की गणना करता है।

सहयोगी संचालन संख्याओं को व्यवस्थित करने के तरीके पर ध्यान दिए बिना वही परिणाम लौटाएं।

समस्या को समझने के लिए एक उदाहरण लेते हैं,

इनपुट

आउटपुट

स्पष्टीकरण

(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)) और गुणक a से बाएँ या दाएँ के गुणन पर विचार करेंगे जो साहचर्य बनाने के अतिरिक्त दो तरीके देता है।

आइए उपरोक्त मामले का उपयोग करके 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<<"The ways to multiply "<<n<<" elements with an associative operation : "<<calcWays(n);
   return 0 ;
}

आउटपुट

The ways to multiply 7 elements with an associative operation : 665280