C++で結合演算を用いてn個の要素を掛け合わせる方法の総数を求める

問題概要

この問題では、要素の個数を表す整数 n が与えられます。求めるのは、結合演算（associative operation）を用いて 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).

3つの要素 x, y, z を掛け合わせる場合、括弧の付け方と順序の組み合わせによって、全部で12通りの方法が存在することが分かります。

解き方のアプローチ

まず、一般的な規則性や級数が見つけられないかを調べてみましょう。演算子の個数ごとの結合方法の数は次のようになっています。

1 => 1
2 => 2
3 => 12

次に、この個数を一般化することを考えます。n 個の要素に対する結合を作る場合、乗算の演算子は n−1 個、括弧も n−1 個配置できると考えられます。

ここで、結合の作り方を次の2つのケースに分けて数えます。

• ケース1：n−1 個までの掛け方を基準にし、そこへ最後の要素 an を挿入します。n−1 個の要素の場合、演算子は n−2 個あるため、各演算子の左右どちらの側にも挿入可能であり、これにより 2×2×(n−2) 通りの組み合わせが生まれます。

• ケース2：(a1, a2, …, a(n−1)) の掛け算全体に対して、an を左または右から掛けることを考えると、さらに2通りの方法が追加されます。

以上の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))

この漸化式は擬似カタラン数（pseudo Catalan Number）と同じ関係式であり、初期値も一致しています。

したがって、擬似カタラン数の一般公式をそのまま適用できます。

ass(n) = (2*n-2)!/(n-1)!

n = 5 のときにこの公式が正しく機能するか確認してみましょう。

ass(5) = (2*5 - 2)! / (5-1)!
ass(5) = 8!/4! = 40320/24 = 1680

C++での実装例

以下は、結合演算を用いて n 個の要素を掛け合わせる方法の総数を求めるC++プログラムです。階乗を再帰的に計算し、その比から答えを求めています。

#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

注意点

階乗の値は急激に大きくなるため、n がある程度大きくなると long int の範囲を超えてオーバーフローが発生する可能性があります。大きな n を扱う場合は、多倍長整数型や任意精度演算ライブラリの利用を検討してください。また、計算量は階乗計算の再帰に依存し、O(n) で求められるため非常に効率的です。