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

解決済

質問者：sakata572
質問日時：2012/08/16 00:11
回答数：4件

(環境は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以降では途中から答えが狂い始めます.
この現象はなぜ起こるのでしょうか?

通報する

この質問への回答は締め切られました。

質問の本文を隠す

回答 (4件)

ベストアンサー優先
最新から表示
回答順に表示

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の最大値を超えることはありません。

- 0
- 件

通報する

この回答へのお礼

ご丁寧にありがとうございます.
電卓を取り出して確認していたら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;
}