或るプログラマの開発日記

日々の勉強したことの備忘録なんかに使っていきます

組み合わせの数を計算する

プログラミングの問題を解いてると、組み合わせの数を計算する必要が出てきたので、調査した内容をメモ。

組み合わせの数とは

高校数学なんかで習った記憶は微かにあるが、大分忘れてるので勉強しなおし。
こちらのサイトの説明が非常に丁寧でした。

組み合わせの公式~計算方法と練習問題~:ビジュアル数学(数学A:場合の数)

実装

一通り理解したところで実装してみる。因みに言語は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;
    }