【C++】階乗を使って組み合わせ（nCr）を計算するプログラム

組み合わせ（コンビネーション）とは、n個の異なる要素の中からr個を選び出すときの選び方の総数を表す概念で、数学では次の式で定義されます。

nCr = n! / (r! × (n − r)!)

ここで「!」は階乗を意味し、例えば 5! = 5 × 4 × 3 × 2 × 1 = 120 となります。以下は、この公式を階乗の計算によって実装したC++プログラムの例です。

サンプルコード

#include <iostream>
using namespace std;
int fact(int n) {
    if (n == 0 || n == 1)
    return 1;
    else
    return n * fact(n - 1);
}
int main() {
    int n, r, result;
    cout<<"Enter n : ";
    cin>>n;
    cout<<"\nEnter r : ";
    cin>>r;
    result = fact(n) / (fact(r) * fact(n-r));
    cout << "\nThe result : " << result;
    return 0;
}

実行結果

Enter n : 10
Enter r : 4
The result : 210

プログラムの解説

階乗を求める fact() 関数

上記のプログラムでは、数値の階乗を計算する処理が fact() 関数内に実装されています。

if (n == 0 || n == 1)
return 1;
else
return n * fact(n - 1);

この関数は再帰的に動作します。引数 n が 0 または 1 の場合は 1 を返し、それ以外の場合は n × fact(n − 1) を返すことで、階乗を順番に計算していきます。

main() 関数での組み合わせの計算

cout<<"Enter n : ";
cin>>n;
cout<<"\nEnter r : ";
cin>>r;
result = fact(n) / (fact(r) * fact(n-r));

main() 関数では、ユーザーから組み合わせの計算に必要な2つの整数 n と r を入力として受け付けます。その後、変数 result に、fact() 関数で求めた階乗の値をもとに計算した組み合わせの結果を格納し、画面へ出力します。

なお、階乗の値は急激に大きくなるため、n が大きい場合は int 型ではオーバーフローが発生するおそれがあります。実用的なプログラムでは long long 型を使用する、あるいは掛け算と割り算を交互に行うなどの工夫が必要です。