C言語での組み合わせの問題について

質問

(環境はmacで, gcc 4.0.1を用いています)

#include <stdio.h>

main(void)
{
int n, k, nck;

printf("n = ");
scanf("%d", &n);

printf(" k nCk\n");

k = 0;
nck = 1;
printf("%12d%12d\n", k, nck);

for(k=1; k <= n; k++) {
nck = nck * (n-k+1)/k;

printf("%12d%12d\n", k, nck);
}
}

とした場合, 入力した値n=29までは正しい答えが得られるのですが
n=30以降では途中から答えが狂い始めます.
この現象はなぜ起こるのでしょうか?

回答No.3

akayoroshi · ベストアンサー

この方法で、この環境だと、n=30, k=14 までは正しく求めることができます。
30C14=145,422,675に(30-15+1)=16を掛けると、intで取り扱うことができる最大の数値(2の31乗よりも1小さい値:2,147,483,647)よりも大きくなってしまいます（オーバーフローです）。以降は正しくないnckの値を使って次の値を求めているので当然正しい値は得られません。
#1の回答の「(n-k+1)/kは恒に整数か？」は何を指摘されているのかわかりません。nck*(n-k+1)は、オーバーフローしない限り、kで割り切れます。
また、「nckの最大値は？」については、n≦33であればnCkの値がintの最大値を超えることはありません。

お礼

ご丁寧にありがとうございます.
電卓を取り出して確認していたらnckを求める式の途中でintの範囲を超えていることに気づきました.
そうこうしていると皆さんへのお礼が遅くなりました, 申し訳ないです.
今回はakayoroshiさんの回答を見ることで自分の考えが正しいのかどうかが確認できましたのでベストアンサーとさせて頂きました.

回答して頂いた皆さん, あらためてありがとうございました.
これでスッキリして眠れます...

回答No.4

hanabutako

integer overflowです。

正しい結果がほしいなら、gmpなどを使うことを検討すると良いかもしれません。
http://gmplib.org/

参考までに、こんな感じに書き換えられます。 gmpのライブラリーとリンクしてください。
#include <gmp.h>
#include <stdio.h>

void
print_nck(unsigned long k, mpz_t nck) {
char* nck_str;
nck_str = mpz_get_str(NULL, 10, nck);
printf("%12lu\t%s\n", k, nck_str);
free(nck_str);
}

int
main(void)
{
unsigned long n, k;
mpz_t nck;

printf("n = ");
scanf("%lu", &n);

printf(" k nCk\n");

k = 0;
mpz_init_set_ui(nck, 1UL);
print_nck(k, nck);

for (k = 1; k <= n; k++) {
mpz_mul_ui(nck, nck, (n - k + 1));
mpz_fdiv_q_ui(nck, nck, k);
print_nck(k, nck);
}

return 0;
}

お礼

ありがとうございます.
参考にさせて頂きますね.

回答No.2

Tacosan

この場合 #1 の最初の指摘は外れ. それ以外はあってるんだけどね.

お礼

左優先であることをすっかり忘れていました.
計算式の途中でintの範囲を超えていることに気づきました.
ご指摘ありがとうございました.

回答No.1

TooManyBugs

(n-k+1)/kは恒に整数か？

intはどのような変数か？

nckの最大値は？

いずれも基礎中の基礎。

お礼

ご指摘ありがとうございました.