組み合わせ
最終更新日27 Mar 2015 09:48
texコード
{}_n\mathrm{C}_x
異なるn個のものから、異なるm個を選ぶ場合の組み合わせの総数は？
(1)\begin{align} nCr=\frac{n!}{r!(n-r)!}\\ \end{align}
常に$n>r$である。
(2)\begin{align} nCr=\frac{n(n-1)(n-2)....(r+1)r!}{r!(n-r)!}\\ \end{align}
これを約分するとこうなる
(3)\begin{align} nCr=\frac{n(n-1)(n-2)....(r+1)}{(n-r)!}\\ \end{align}
(4)
\begin{align} nCr=\frac{\prod_{i=(r+1)}^n i}{(n-r)!} \end{align}
この定義通りにコードを書くとこうなるが
int combination(int _n,int _r){ unsigned long long numerator=1;//分子 unsigned long long denominator=1;//分母 for(int i=_n;i>=_r+1;i--){ numerator*=i; } for(int i=_n-_r;i>0;i--){ denominator*=i; } if(numerator<denominator){cout<<"失敗"<<endl;return -1;} return (int)(numerator/denominator); }
大きな数の時、失敗してしまうのだ。
$32C6$で既にアウトだ。
なので、コンピュータに計算させるなら、漸化式にした方がいいみたい。(5)
\begin{align} {}_n\mathrm{C}_{r}=\frac{n-r+1}{r}{}_n\mathrm{C}_{r-1} \end{align}
欠点
これは数学的解法。
何か例外が発生した場合柔軟に対処できないのが問題。
これをコンピュータにやらせるぐらいだったら、
動的計画法やメモ化再帰を使った方がいいらしいぞ。
