質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.50%
C

C言語は、1972年にAT&Tベル研究所の、デニス・リッチーが主体となって作成したプログラミング言語です。 B言語の後継言語として開発されたことからC言語と命名。そのため、表記法などはB言語やALGOLに近いとされています。 Cの拡張版であるC++言語とともに、現在世界中でもっとも普及されているプログラミング言語です。

Q&A

解決済

6回答

6747閲覧

int型の限界を階乗で追う

lack_un

総合スコア58

C

C言語は、1972年にAT&Tベル研究所の、デニス・リッチーが主体となって作成したプログラミング言語です。 B言語の後継言語として開発されたことからC言語と命名。そのため、表記法などはB言語やALGOLに近いとされています。 Cの拡張版であるC++言語とともに、現在世界中でもっとも普及されているプログラミング言語です。

0グッド

1クリップ

投稿2016/04/28 04:45

###前提・実現したいこと
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ページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

guest

回答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オプション付きでコンパイルすると確認できます。今回は、kaijoiも0より大きい正の数であることがコードから保証されていますので、正の数同士のパターンだけチェックすれば十分です。オーバーフローを起こしてしまうような組み合わせの場合は、計算はせずに、オーバーフローするというメッセージだけ残して、終了します。

投稿2016/04/28 10:47

raccy

総合スコア21733

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

lack_un

2016/04/28 22:16

理解できました!!ありがとうございます。
guest

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

Chironian

総合スコア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

katoy

総合スコア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
HiroshiWatanabe

総合スコア2160

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

ozwk

2016/04/28 05:36

Cのint型のオーバーフローは未定義動作では?
HiroshiWatanabe

2016/04/28 06:00

ご指摘ありがとうございます。 オーバーフローさせない方法に変えてみました。
guest

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

ttyp03

総合スコア16996

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

CodeLab

2016/04/28 05:08

あとは オーバーフローすると計算不能なので変数はdoubleなど大きい型にする。 limits.hに最大値定義(INT_MAX)があるのでそれで閾値を超えたかどうか判定 すれば目的を達せるとおもいます。
guest

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
ozwk

総合スコア13512

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.50%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問