ちくのう症(蓄膿症)は「菌」が原因!?

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

A 回答 (4件)

この方法で、この環境だと、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の最大値を超えることはありません。
    • good
    • 0
この回答へのお礼

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

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

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

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;
}
    • good
    • 0
この回答へのお礼

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

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

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

    • good
    • 0
この回答へのお礼

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

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

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



intはどのような変数か?

nckの最大値は?

いずれも基礎中の基礎。
    • good
    • 0
この回答へのお礼

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

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

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!

このQ&Aを見た人が検索しているワード

このQ&Aと関連する良く見られている質問

Q組み合わせ順列

nCrを求める関数combination(n,r)をC言語で作りたいのですが、どうすればよいか教えてください。また、参考となるようなサイトを教えてください。僕の作った関数だと、すぐに桁あふれになってしまいます。そのことを考慮して、桁あふれにになりにくい関数もつくりました。これは パスカルの三角形の関係を使ったnCr=n-1Cr +n-1Cr-1の関係を使っての再帰関数です。しかし、これだと結果を出すのに時間がかかってしまいます。僕がつくった関数をいくつか出しておきますのでいい考えがあれば教えてください。64C32が高速に正確に出れれば最高です。
long combination(int n,int r)
{
int i, a, b;
long c;
if(r>n/2) r=n-r;
a= n;
b= 1;
c= 1L;
for(i=0 ;i< r ;i++){
c= c* a/ b;
a--;
b++;
}
return c;
}
これはすぐに桁あふれになってしまう。
long combination(int n,int r)
{
int i, a, b;
double c;
if(r>n/2) r=n-r;
a= n;
b= 1;
c= 1.0;
for(i=0 ;i< r ;i++){
c= c/b*a;
a--;
b++;
}
return (long)c;
}
これはcをdoubleにして計算する分、丸めこみが生じ誤差がでる。
long combination(int n,int r)
{
long c;
if(r> n-r) r=n-r;

if(r==0) return 1;
else if(r==1) return n;
else{
c= combination(n-1,r-1)+ combination(n-1,r);
return c;
}
}
これは誤差は出ず正確であるがいかんせん遅い!

nCrを求める関数combination(n,r)をC言語で作りたいのですが、どうすればよいか教えてください。また、参考となるようなサイトを教えてください。僕の作った関数だと、すぐに桁あふれになってしまいます。そのことを考慮して、桁あふれにになりにくい関数もつくりました。これは パスカルの三角形の関係を使ったnCr=n-1Cr +n-1Cr-1の関係を使っての再帰関数です。しかし、これだと結果を出すのに時間がかかってしまいます。僕がつくった関数をいくつか出しておきますのでいい考えがあれば教えてください。64C...続きを読む

Aベストアンサー

お詫びに:

#include <cstdio>

__int64 combination(int n, int r) {
__int64* work = new __int64[n+1]; /* n は 64 まで */
for (int i = 0; i <= n; i++) {
for (int j = i - 1; j > 0; j--) {
work[j] += work[j - 1];
}
work[i] = 1;
}
__int64 result = work[r];
delete[] work;
return result;
}

namespace std {}
using namespace std;

int main() {
for ( int i = 0; i < 33; ++i )
printf("64C%d = %I64d\n", i, combination(64,i));
return 0;
}

----- 結果 -------
.....
64C25 = 401038568751465792
64C26 = 601557853127198688
64C27 = 846636978475316672
64C28 = 1118770292985239888
64C29 = 1388818294740297792
64C30 = 1620288010530347424
64C31 = 1777090076065542336
64C32 = 1832624140942590534

だそうです。# VC6でコンパイル/実行

お詫びに:

#include <cstdio>

__int64 combination(int n, int r) {
__int64* work = new __int64[n+1]; /* n は 64 まで */
for (int i = 0; i <= n; i++) {
for (int j = i - 1; j > 0; j--) {
work[j] += work[j - 1];
}
work[i] = 1;
}
__int64 result = work[r];
delete[] work;
return result;
}

namespace std {}
using namespace std;

int main() {
for ( int i = 0; i < 33; ++i )
printf("64C%d = %I64d\n", i, combination(64,i));
...続きを読む

Qn個の要素で出来る順列組み合わせを全て出力するアルゴリズム

次のようなプログラムをC++で書こうと思っているのですが、
どうも方法が思い浮かびません。
よいやり方、定番のやり方などがありましたら教えてください。

---------------------------------
n個の要素があるとき、
そのn個で出来る順列組み合わせ(計(n!)通り)を全て出力する。


例えばa[4] = {'A', 'B', 'C', 'D'}なら
順列組み合わせは
A B C D
A B D C
A C B D
A C D B
A D B C
A D C B
B A C D
B A D C
B C A D
B C D A
B D A C
B D C A



D C A B
D C B A
の、計24通り

Aベストアンサー

「順列組合せ」ではなく「順列の生成」ですね。

アルゴリズムの原理を知りたければ次のWlframのサイトでわかりやすく説明しています。下のほうのところで、再帰を使ったものが例示されています。
http://mathworld.wolfram.com/Permutation.html

ソースを見たいなら、
http://www.merriampark.com/perm.htm
あたりで。

ただし、C++では、順列生成は標準ライブラリに入っています。
next_permutation,prev_permutation
を使って下さい。
http://www005.upp.so-net.ne.jp/episteme/html/stlprog/_05.html


人気Q&Aランキング