回答編集履歴
3
リンク先変更
answer
CHANGED
|
@@ -1,4 +1,4 @@
|
|
|
1
|
-
[入山徳夫氏によるnCrを高速に求めるアルゴリズム](http://
|
|
1
|
+
[入山徳夫氏によるnCrを高速に求めるアルゴリズム](http://d.hatena.ne.jp/kadzus/20081211/1229023326)(追記：リンク先変更)
|
|
2
2
|
人間が手計算でnCrを計算するとき、約分して分母を消して、残った分子を掛けますが、
|
|
3
3
|
それをそのまんま再現したようなアルゴリズムです。
|
|
4
4
|
|
2
実装について追記
answer
CHANGED
|
@@ -4,4 +4,7 @@
|
|
|
4
4
|
|
|
5
5
|
もしくはパスカルの三角形を使って加算だけで求める手もあります。
|
|
6
6
|
|
|
7
|
-
どっちが速いかは知らないので早かった方をお使い下さい
|
|
7
|
+
どっちが速いかは知らないので早かった方をお使い下さい
|
|
8
|
+
|
|
9
|
+
あと実装は自分でやって下さい。
|
|
10
|
+
リンク先をRubyにただ翻訳すればいいと思います。
|
1
パスカルの三角形について加筆
answer
CHANGED
|
@@ -1,3 +1,7 @@
|
|
|
1
1
|
[入山徳夫氏によるnCrを高速に求めるアルゴリズム](http://usonko.xtr.jp/blog/?p=289)
|
|
2
2
|
人間が手計算でnCrを計算するとき、約分して分母を消して、残った分子を掛けますが、
|
|
3
|
-
それをそのまんま再現したようなアルゴリズムです。
|
|
3
|
+
それをそのまんま再現したようなアルゴリズムです。
|
|
4
|
+
|
|
5
|
+
もしくはパスカルの三角形を使って加算だけで求める手もあります。
|
|
6
|
+
|
|
7
|
+
どっちが速いかは知らないので早かった方をお使い下さい
|