簡単なことが実はできてない

例えばnCrをどうやって計算するか。私は素直なので以下のようにやってしまいます。

int nPr(int n, int r)
{
    int retval = 1;
    if (n < r) return 0;
    for (int i = n; i > (n-r); i--) {
        retval *= i;
    }
    return retval;
}

int nCr(int n, int r)
{
    return nPr(n, r)/nPr(r, r);
}

数学的には上のような感じでいいはず(nとかrの不正値について無視すれば)。でもこれだとオーバーフローするらしいのです。速攻で。まあ、そりゃそうかも。階乗だし。例えばrを10にしたら分母のnPr(r,r)がもうオーバーフローします。なのでnCr(10,10)なんて簡単に1になることが分かるのに、計算できないわけです。まあ、この例ならnCr(10,10)=nCr(10,0)=1って計算しろよ、なんですが、まあすぐオーバーフローすると。で、どうしたらいいかというと漸化式で計算すればいいらしいです。

int nCr(int n, int r)
{
    int retval = 1;
	for (int i = 1; i < r; i++) {
		retval = retval * (n-i+1)/i;
	}
	return retval;
}

プログラムって微妙に数学と違うところが難しい。

以上