###前提・実現したいこと
int型が入るオーバーフローしない最大の階乗数は何になるのか、を調べたい。
###発生している問題・エラーメッセージ
1!=1 2!=1 3!=2 3!=2 3!=4 4!=12 4!=12 4!=24 4!=72 ...
###該当のソースコード
#include <stdio.h> int main(){ int i,j,kaijo; kaijo=1; for(i=1; i<=20; i++){ for(j=1; j<=i; j++){ kaijo=kaijo*j; printf("%d! = %d\n",kaijo); } } return 0;
###試したこと
二段ループを使って、階乗を一行ずつ作りだそうとしたがうまくいかなかった。
理想としているのは
1!=1
2!=2
3!=6
4!=24
..
###補足情報(言語/FW/ツール等のバージョンなど)
より詳細な情報
気になる質問をクリップする
クリップした質問は、後からいつでもMYページで確認できます。
またクリップした質問に回答があった際、通知やメールを受け取ることができます。
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
回答6件
0
ベストアンサー
int型が入るオーバーフローしない最大の階乗数は何になるのか、を調べたい。
難しい部類に入る課題だと思います。C言語についてそれなりに知っておかないと厳しいです。まず、C言語ではintについて次のような仕様になっています。
- int同士の乗算が
INT_MAX
(intの最大値)を越える場合の動作は未定義。(オーバーフローと呼ばれるものです) - int__より大きい__整数型が存在するとは限らない。(longとlong longはint__以上__であることは保証されますが、__より大きい__とは限りません。)
上記を踏まえて、JPCERT/CCの下記ページをお読みください。
INT32-C. 符号付き整数演算がオーバーフローを引き起こさないことを保証する
C言語における未定義というのは、何が起きるかわからないことを意味し、0や負の値が返る場合もあれば、返る値がランダムだったり、エラーとなってプログラムが落ちる場合もあります。つまり、何が起きるかわからないオーバーフローを引き起こしてはいけません。では、intをそれより大きい整数にあらかじめ入れておけばと考えるかも知れませんが、C言語では、long long ≧ long ≧ intと言う関係しか決められておらず、long longとlongとintが全て同じという実装もあり得ます(実際にあるかどうかはわかりませんが)。ということで、結論としては、事前に検知して、オーバーフローになる前に回避するしかありません。
C
1#include <limits.h> 2#include <stdio.h> 3int main(void) 4{ 5 int kaijo = 1; 6 for (int i = 1;; i++) { 7 if (kaijo > INT_MAX / i) { 8 // 乗算がINT_MAXを越える 9 printf(u8"%d! = %s\n", i, u8"オーバーフロー"); 10 break; 11 } else { 12 // 乗算がINT_MAXを越えることは無い 13 kaijo *= i; 14 printf(u8"%d! = %d\n", i, kaijo); 15 } 16 } 17 return 0; 18}
オーバーフローが起きているかどうかは、gccなら-ftrapvオプション付きでコンパイルすると確認できます。今回は、kaijo
もi
も0より大きい正の数であることがコードから保証されていますので、正の数同士のパターンだけチェックすれば十分です。オーバーフローを起こしてしまうような組み合わせの場合は、計算はせずに、オーバーフローするというメッセージだけ残して、終了します。
投稿2016/04/28 10:47
総合スコア21733
0
こんにちは。
なかなか苦労されてますね。
こんな時は、自分で作ったプログラムを人間コンパイラになって自分で実行してみると良いですよ。
①kaijo=1
②i=1
③j=1
④kaijo=kaijoj → kaijo=11=1ですね。
⑤printf("d! = %d\n", kaijo)
→ %dが2つあるけど表示する変数が1つしかないので、最初の%dのみ適切に表示されます。
ループ
⑥j++ → j=2
2つめのforループの条件(j<=i)を満たさなくなった(2<=1)ので、さらに戻る
⑦i++ → i=2
⑧j=1
:
というような具合です。iのforループを2~3回回るころには何が問題か見えてくると思います。
投稿2016/04/28 05:20
総合スコア23272
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
0
コンパイル時に int に収まる階乗がわかります。
参考:
f.c
c
1int main() { 2 static const int factorial[] = { 3 1, 4 1, 5 1 * 2, 6 1 * 2 * 3, 7 1 * 2 * 3 * 4, 8 1 * 2 * 3 * 4 * 5, 9 1 * 2 * 3 * 4 * 5 * 6, 10 1 * 2 * 3 * 4 * 5 * 6 * 7, 11 1 * 2 * 3 * 4 * 5 * 6 * 7 * 8, 12 1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9, 13 1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10, 14 1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10 * 11, 15 1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10 * 11 * 12, 16 1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10 * 11 * 12 * 13, 17 1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10 * 11 * 12 * 13 * 14, 18 }; 19 for (int i = 0; i < sizeof(factorial) / sizeof(int); i++) { 20 printf("%d\n", factorial[i]); 21 } 22 return 0; 23}
コンパイル結果:
$ gcc f.c f.c:18:54: warning: overflow in expression; result is 1932053504 with type 'int' [-Winteger-overflow] 1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10 * 11 * 12 * 13, ^ f.c:19:54: warning: overflow in expression; result is 1932053504 with type 'int' [-Winteger-overflow] 1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10 * 11 * 12 * 13 * 14, ^ f.c:19:59: warning: overflow in expression; result is 1278945280 with type 'int' [-Winteger-overflow] 1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10 * 11 * 12 * 13 * 14, ^ 3 warnings generated $ gcc --version Configured with: --prefix=/Applications/Xcode.app/Contents/Developer/usr --with-gxx-include-dir=/usr/include/c++/4.2.1 Apple LLVM version 7.3.0 (clang-703.0.29) Target: x86_64-apple-darwin15.4.0 Thread model: posix InstalledDir: /Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin
投稿2016/04/28 22:01
総合スコア22324
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
0
c
1#include <stdio.h> 2#include <limits.h> 3 4int main() { 5 unsigned long long k = 1; 6 int i = 0; 7 do { 8 printf("%d!=%d\n", (int)i, (int)k); 9 k *= ++i; 10 } while (k <= INT_MAX); 11 return 0; 12} 13
投稿2016/04/28 05:29
編集2016/04/28 05:58総合スコア2160
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
0
printfをするタイミングはkaijoの計算が終わる2回目のループのあとですね。
あとprintfで引数にiが抜けていました。
C
1#include <stdio.h> 2 3int main(){ 4 5 int i,j,kaijo; 6 7 for(i=1; i<=20; i++){ 8 kaijo=1; 9 for(j=1; j<=i; j++){ 10 kaijo = kaijo * j; 11 } 12 printf("%d! = %d\n",i,kaijo); 13 } 14 15 return 0; 16} 17
投稿2016/04/28 05:05
総合スコア16996
0
(n+1)!
は(n+1)(n!)
です。
なにを当然のことを?と思うかもしれませんが、
これはつまり、1!,2!,3!,...
を表示するのに、
一々1から掛け直さなくても、前回の結果に数を1つ掛けるだけで結果が得られるということです。
ループを使わず愚直に書くとこうなります。
C
1fact = 1; 2printf("%d" , fact); // 1 3fact = fact * 2; 4printf("%d" , fact); // 2 5fact = fact * 3; 6printf("%d" , fact); // 6
明らかに繰り返し構造が見て取れるので、
これをforで書きなおせばよいです。
投稿2016/04/28 04:58
編集2016/04/28 05:01総合スコア13512
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
あなたの回答
tips
太字
斜体
打ち消し線
見出し
引用テキストの挿入
コードの挿入
リンクの挿入
リストの挿入
番号リストの挿入
表の挿入
水平線の挿入
プレビュー
質問の解決につながる回答をしましょう。 サンプルコードなど、より具体的な説明があると質問者の理解の助けになります。 また、読む側のことを考えた、分かりやすい文章を心がけましょう。
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
2016/04/28 22:16