組み合わせの数を計算する
プログラミングの問題を解いてると、組み合わせの数を計算する必要が出てきたので、調査した内容をメモ。
組み合わせの数とは
高校数学なんかで習った記憶は微かにあるが、大分忘れてるので勉強しなおし。
こちらのサイトの説明が非常に丁寧でした。
実装
一通り理解したところで実装してみる。因みに言語はJava。
//組み合わせの数nCrを計算 int calcNumOfCombination(int n, int r){ return factorial(n) / (factorial(r) * factorial(n-r)); } //nの階乗を計算 int factorial(int n){ int answer = 1; while(n > 1){ answer *= n; n--; } return answer; }
実行して見た結果
テストを走らせたところ、一部ケースが通ったが組み合わせがでかいケースで結果がおかしくなることが判明!
そりゃそーだ。桁あふれしてますやーん(T_T)
改良版実装
こちらが、(ある程度)桁あふれ対策した改良版。おとなしく先人の知恵を拝借することに。
C言語で数値計算(1)順列・組み合わせの「組み合わせ」(漸化式のループ処理による実装) - Qiita
//組み合わせの数nCrを計算 int calcNumOfCombination(int n, int r){ int num = 1; for(int i = 1; i <= r; i++){ num = num * (n - i + 1) / i; } return num; }