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 回答日時： 2012/08/16 02:02

この方法で、この環境だと、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さんの回答を見ることで自分の考えが正しいのかどうかが確認できましたのでベストアンサーとさせて頂きました.

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

お礼日時：2012/08/16 02:33

No.4 回答者： hanabutako 回答日時： 2012/08/16 02:17

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;
}

この回答へのお礼

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

お礼日時：2012/08/16 02:25

No.2 回答者： Tacosan 回答日時： 2012/08/16 01:01

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

この回答へのお礼

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

お礼日時：2012/08/16 02:24

No.1 回答者： TooManyBugs 回答日時： 2012/08/16 00:47

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

intはどのような変数か？

nckの最大値は？

いずれも基礎中の基礎。

この回答へのお礼

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

お礼日時：2012/08/16 02:21