C++で漸化式を使って組み合わせ（nCr）を計算するプログラムの解説

本記事では、漸化式（再帰関係）を利用して組み合わせ nCr を求める C++ プログラムを紹介します。組み合わせとは、n 個の要素から r 個を選ぶときの選び方の総数のことであり、数学的には次の公式で定義されます。

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

この公式をそのまま階乗で計算すると数が巨大化しやすいため、本プログラムでは次のような漸化式の性質を利用して再帰的に計算を行います。

nCr = (n / r) × (n−1)C(r−1)

アルゴリズム

Begin
    function CalCombination():
        引数：n, r
        関数の処理内容：
        漸化式 nCr = (n/r) × (n-1)C(r-1)
        を用いて組み合わせを再帰的に計算する
End

サンプルコード

#include<iostream>
using namespace std;
float CalCombination(float n, float r) {
    int i;
    if(r > 0)
        return (n/r)*CalCombination(n-1,r-1);
    else
        return 1;
}
int main() {
    float n, r;
    int res;
    cout<<"Enter the value of n: ";
    cin>>n;
    cout<<"Enter the value of r: ";
    cin>>r;
    res = CalCombination(n,r);
    cout<<"\nThe number of possible combinations are: nCr = "<<res;
}

実行結果

Enter the value of n: 7
Enter the value of r: 6
The number of possible combinations are: nCr = 2

プログラムの解説

関数 CalCombination() は、引数として受け取った n と r を用いて再帰呼び出しを行います。r が 0 より大きい間は「(n / r) × (n−1)C(r−1)」という漸化式に従って自分自身を呼び出し続け、r が 0 になった時点で 1 を返すことで再帰を終了します。

例えば n = 7、r = 6 の場合、7C6 の値は 7! / (6! × 1!) = 7 ではなく、実際には 7 通りの選び方が存在するため注意が必要です。ただし、このプログラムでは戻り値を int 型変数 res に格納しているため、小数点以下が切り捨てられて誤差が生じる可能性があります。正確な結果を得たい場合は、戻り値や変数の型を見直すことをおすすめします。

まとめ

このように、漸化式と再帰関数を組み合わせることで、大きな階乗の計算を避けながら簡潔に組み合わせを求めることができます。再帰の仕組みを理解する練習問題としても非常に有用なサンプルです。