とくにあぶなくないRiSKのブログ

危ないRiSKのブログだったかもしれない。本当はRiSKだけどググラビリティとか取得できるIDの都合でsscriskも使ったり。

Cパズルプログラミング-再帰編(3)

Karetta|Cパズルプログラミング-再帰編|組合せ
続いて組合せ。

comb1.c

Karetta|Cパズルプログラミング-再帰編|comb1.c


int comb(int m,int n){return m>n&&n>0?comb(m-1,n-1)+comb(m-1,n):1;}
#include<stdio.h>
int main(void){
int i,j;
for(i=0;i<5;++i)for(j=0;j<=i;++j)printf("comb(%d,%d) = %d\n",i,j,comb(i,j));
}

comb3.c

Karetta|Cパズルプログラミング-再帰編|comb3.c

int comb(int m,int n){
int r=1,i;
for(i=0;i<=n;r/=++i)r*=m--;
return r;
}
#include<stdio.h>
int main(void){
int i,j;
for(i=0;i<5;++i)for(j=0;j<=i;++j)printf("comb(%d,%d) = %d\n",i,j,comb(i,j));
}

組合せの定義

組合せの定義ってどうやって導くのだろう。関数に値を渡せば正しい結果を返すけど,そうなる理由が分からないんで腑に落ちない。ってことで,プログラムを書いて表にしてみた。

   n ->
 m 1    0    0    0    0    0    0    0    0    0    0    0    0    0    0
   1    1    0    0    0    0    0    0    0    0    0    0    0    0    0
 | 1    2    1    0    0    0    0    0    0    0    0    0    0    0    0
 V 1    3    3    1    0    0    0    0    0    0    0    0    0    0    0
   1    4    6    4    1    0    0    0    0    0    0    0    0    0    0
   1    5   10   10    5    1    0    0    0    0    0    0    0    0    0
   1    6   15   20   15    6    1    0    0    0    0    0    0    0    0
   1    7   21   35   35   21    7    1    0    0    0    0    0    0    0
   1    8   28   56   70   56   28    8    1    0    0    0    0    0    0
   1    9   36   84  126  126   84   36    9    1    0    0    0    0    0
   1   10   45  120  210  252  210  120   45   10    1    0    0    0    0
   1   11   55  165  330  462  462  330  165   55   11    1    0    0    0
   1   12   66  220  495  792  924  792  495  220   66   12    1    0    0
   1   13   78  286  715 1287 1716 1716 1287  715  286   78   13    1    0
   1   14   91  364 1001 2002 3003 3432 3003 2002 1001  364   91   14    1

m>nじゃないところは便宜上0にしてみたが*1,きれいな*2パスカルの三角形ができていることが分かると思う。パスカルの三角形は上の段の2つの数を足すことで下の段の値を求めることができる。
この上の段の2つの数こそ comb(m-1,n-1) と comb(m-1,n) であり,これを足すことで組合せ( comb(m,n) )を求めることができるのだと納得した*3

*1:「組み合わせられない」という組合せがあるから1なのかもしれないが,詳細は分からない。誰か分かりやすく教えて。

*2:斜めってるけど。

*3:つもりになった。だって,なぜパスカルの三角形が現れるのか分からないんだもん。なんせ数学の基本が分からないんで,こういうところで躓くんだよね。orz