つぎの式に、数字の前後順序を変えないで、計算の順番をはっきりさせる、括弧のつけ方は最大何通りあるか。
 1+2+3 ⇒ (1+2)+3  1+(2+3) 2通り
 1+2+3+4 ⇒ ((1+2)+3)+4  (1+2)+(3+4)  (1+(2+3))+4
         1+((2+3)+4)  1+(2+(3+4)) 計5通り

一般に、N+1個の数字を、前後の順序を変えずに結合の組合せを算出する関数は カタラン数(Catalan number) という。

カタラン数 Cnは以下の漸化式で求められる。
   C0 = 1
   Cn = Cn-1 * 2*(2n-1)/(n+1)

 C[0] = 1
 C[1] = 1
 C[2] = 2
 C[3] = 5
 C[4] = 14
 C[5] = 42
 C[6] = 132
 C[7] = 429
 C[8] = 1430
 C[9] = 4862
 C[10] = 16796
 C[11] = 58786
 C[12] = 208012
 C[13] = 742900
 C[14] = 2674440
 C[15] = 9694845
 C[16] = 35357670
 C[17] = 129644790
 C[18] = 477638700
 C[19] = 1767263190
 C[20] = 6564120420
 C[21] = 24466267020
 C[22] = 91482563640
 C[23] = 343059613650
 C[24] = 1289904147324
 C[25] = 4861946401452
 C[26] = 18367353072152
 C[27] = 69533550916004
 C[28] = 263747951750360
 C[29] = 1002242216651368
 C[30] = 3814986502092304
 C[31] = 14544636039226909
 C[32] = 55534064877048198
 C[33] = 212336130412243110
 C[34] = 812944042149730764
 C[35] = 3116285494907301262

以下はカタラン数を計算するC言語プログラム。オーバフローにならぬよう、計算途中、分母と分子との最大公約数をうまく取り除く工夫をしてある。

#include <stdio.h>
typedef unsigned long long ullong;
ullong gcd(ullong n1, ullong n2)
{
    if (n2 == 0) return n1;
    return gcd(n2, n1 2);
}
int main(void) { int i; ullong c; ullong r, bo, si;
c = 1; printf("C[0] = 1\n"); for (i = 1; i <= 35; i++) { si = c; bo = i+1; if ((r = gcd(si, bo)) > 1) { si /= r, bo /= r; } c = si*2*(2*i-1)/bo; printf("C[-655927664] = 225550331424\n", i, c); } return 0; }

さて、演算子が2種類ある場合に、話はすこしややこしくなる。
  1+2+3*4 ⇒ (1+2)+(3*4)  1+(2+3*4) 計2通り
  1*2+3*4 ⇒ (1*2)+(3*4) 1通り
と、だいぶ少なくなる。しかし、計算順位の高い演算子同士にぞれぞれの組合せを考え、さらに計算順位の低い演算子とあわせて考えると、計算結果は得られやすい。

例: 1+1+1+1+2*2+1*2*2*2+1+1+1+1*2+1 について考える。
解答: まず乗算の部分を考える
     2*2 1通り
     1*2*2*2 5通り
     1*2 1通り
つぎに、加算と合わせて考える。
      1+1+1+1+○+○+1+1+1+○+1 C9=16796通り
ただし、○は乗算の部分を表す。
それで、全体的に 1x5x1x16796=83980 通りの正しい結果が得られる。

ACM問題 #10454 Trexpression が本題に当たる。細かい説明は抜きにするが、解答プログラムを置いておく。

<数式の木表現の組合せ数を算出するプログラム> p10454.c

Comments are closed.

Post Navigation