Home > C++ | バグ | プログラム | 聞いて欲しい独り言 > 簡単なことが実はできてない

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

例えば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;
}

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

以上

Comments:0

Comment Form
Remember personal info

Trackbacks:0

Trackback URL for this entry
http://red-treasure.com/report/wp-trackback.php?p=282
Listed below are links to weblogs that reference
簡単なことが実はできてない from コスミー報告書[社外秘]

Home > C++ | バグ | プログラム | 聞いて欲しい独り言 > 簡単なことが実はできてない

Search
Feeds
Meta
 合計:016022
 今日:0020 昨日:0168

Return to page top