(環境は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ベストアンサー
- 回答日時:
この方法で、この環境だと、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
- 回答日時:
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;
}
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
似たような質問が見つかりました
- C言語・C++・C# 至急教えてください!プログラミングの問題です。 割られる整数と割る整数を受け取って、商と余りを出力す 3 2022/07/05 10:23
- C言語・C++・C# C言語 3 2022/10/04 15:07
- C言語・C++・C# c言語配列の結合についてです。 なぜうまくいかないのでしょうか。 #include <stdio.h 4 2022/05/30 22:42
- C言語・C++・C# C言語のエラーについて 2 2022/07/11 13:56
- C言語・C++・C# 至急教えてください。プログラミングの問題です。 最初に正の整数nの入力を受け付け、次に分数の分子と分 1 2022/07/19 17:03
- C言語・C++・C# C言語プログラム変更 2 2022/12/21 15:03
- C言語・C++・C# c言語でユーザ関数を利用して複素数のべき乗と絶対値の数列を計算するプログラムが作りたいです。 3 2023/01/29 22:13
- C言語・C++・C# プログラミング c言語 4 2023/03/07 01:05
- C言語・C++・C# C言語階乗の総和を求める 2 2023/03/04 23:31
- C言語・C++・C# 至急お願いします。プログラミングの問題です。 最初に正の整数nの入力を受け付け、次に分数の分子と分母 3 2022/07/19 17:09
関連するカテゴリからQ&Aを探す
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
【C言語教えてください】sin波...
-
printf で二進表示を行いたい。
-
円の面積を求めるプログラミン...
-
C言語で四則演算を使って結果が...
-
%P と %X の違い
-
10個出力で改行したいのですが...
-
ビット演算で!?
-
LU分解法のピボット選択機能実...
-
C言語についてです学籍番号、名...
-
文字を動かしたい
-
ヌメロンの対戦相手
-
scanfに文字が入力されたときに...
-
C言語 タイマーのソースについて
-
入力したお金の金額からお札の...
-
4の倍数を論理演算で表す。。
-
C言語 関数
-
C言語のソースをC++言語に変換...
-
boolean型の戻り値は可能か
-
アドレスの比較について
-
C言語です このプログラミング...
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
10個出力で改行したいのですが...
-
【C言語教えてください】sin波...
-
printf で二進表示を行いたい。
-
c言語でAからZまでを表示する...
-
コマンドラインに出力した文字...
-
strcmp
-
4の倍数を論理演算で表す。。
-
C言語での、年複利の計算方法...
-
C言語 プログラミング
-
scanfに文字が入力されたときに...
-
hit&bolwのプログラミングがで...
-
%P と %X の違い
-
unsigned int型について
-
printf( " %2d", p * q );
-
cshの文字列操作(0埋め)
-
改行について 1行に何個かづ...
-
8人分のテストの点数を入力し、...
-
入力したお金の金額からお札の...
-
三角形の判別
-
テキストカーソル位置の取得
おすすめ情報