C++で結合演算を使用してn個の要素を乗算する方法

この問題では、要素の数である整数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個の括弧を配置できます。

ここでは、2つの方法でそれらを配置します-

• （ n-1 まで乗算する方法を検討する ）。そして、最後の要素を関連付けの任意の端に挿入できます。これは、n-1の数の場合、n個の演算子の2 * 2 *（n-2）の関連付けから得られます。

• 次に、（a1、a2、…a（n-1））の乗算と、左または右への乗算を検討します。これにより、関連付けを作成する2つの方法が追加されます。

上記のケースを使用して、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