teratail header banner
teratail header banner
質問するログイン新規登録

回答編集履歴

1

nCr

2017/11/11 16:51

投稿

swordone
swordone

スコア20675

answer CHANGED
@@ -1,3 +1,9 @@
1
1
  オーバーフローしているものと思われます。
2
2
  階乗計算は数の増加が早く、12! = 479001600の時点で符号付32ビット整数が表せる整数の範囲を超え、
3
- 21! = 51090942171709440000で符号付64ビット整数の範囲を超えます。
3
+ 21! = 51090942171709440000で符号付64ビット整数の範囲を超えます。
4
+
5
+ 二項係数は要はnCrなので、乗算が少なくなるように工夫すればいいのです。
6
+ 階乗を使わず、
7
+ n(n-1)(n-2)...(n-r+1)/r(r-1)(r-2)...1
8
+ として計算します。
9
+ rがnの半分より大きい場合は、nCr = nCn-rを使えば乗算回数を減らせます。