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

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

ただいまの
回答率

88.32%

int型の限界を階乗で追う

解決済

回答 6

投稿

  • 評価
  • クリップ 1
  • VIEW 4,127

lack_un

score 50

前提・実現したいこと

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/ツール等のバージョンなど)

より詳細な情報

  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

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

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 過去に投稿した質問と同じ内容の質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

回答 6

checkベストアンサー

+4

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が全て同じという実装もあり得ます(実際にあるかどうかはわかりませんが)。ということで、結論としては、事前に検知して、オーバーフローになる前に回避するしかありません。

#include <limits.h>
#include <stdio.h>
int main(void)
{
    int kaijo = 1;
    for (int i = 1;; i++) {
        if (kaijo > INT_MAX / i) {
            // 乗算がINT_MAXを越える
            printf(u8"%d! = %s\n", i, u8"オーバーフロー");
            break;
        } else {
            // 乗算がINT_MAXを越えることは無い
            kaijo *= i;
            printf(u8"%d! = %d\n", i, kaijo);
        }
    }
    return 0;
}


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

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2016/04/29 07:16

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

    キャンセル

+1

こんにちは。

なかなか苦労されてますね。
こんな時は、自分で作ったプログラムを人間コンパイラになって自分で実行してみると良いですよ。

①kaijo=1
②i=1
③j=1
④kaijo=kaijo*j → kaijo=1*1=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回回るころには何が問題か見えてくると思います。

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

0

(n+1)!(n+1)(n!)です。
なにを当然のことを?と思うかもしれませんが、
これはつまり、1!,2!,3!,...を表示するのに、
一々1から掛け直さなくても、前回の結果に数を1つ掛けるだけで結果が得られるということです。

ループを使わず愚直に書くとこうなります。

fact = 1;
printf("%d" , fact); // 1
fact = fact * 2; 
printf("%d" , fact); // 2
fact = fact * 3; 
printf("%d" , fact); // 6


明らかに繰り返し構造が見て取れるので、
これをforで書きなおせばよいです。

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

0

printfをするタイミングはkaijoの計算が終わる2回目のループのあとですね。
あとprintfで引数にiが抜けていました。

#include <stdio.h>

int main(){

    int i,j,kaijo;

    for(i=1; i<=20; i++){
        kaijo=1;
        for(j=1; j<=i; j++){
            kaijo = kaijo * j;
        }
        printf("%d! = %d\n",i,kaijo);
    }

    return 0;
}

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2016/04/28 14:08

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

    すれば目的を達せるとおもいます。

    キャンセル

0

コンパイル時に int に収まる階乗がわかります。

参考:

int main() {
  static const int factorial[] = {
    1,
    1,
    1 * 2,
    1 * 2 * 3,
    1 * 2 * 3 * 4,
    1 * 2 * 3 * 4 * 5,
    1 * 2 * 3 * 4 * 5 * 6,
    1 * 2 * 3 * 4 * 5 * 6 * 7,
    1 * 2 * 3 * 4 * 5 * 6 * 7 * 8,
    1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9,
    1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10,
    1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10 * 11,
    1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10 * 11 * 12,
    1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10 * 11 * 12 * 13,
    1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10 * 11 * 12 * 13 * 14,
  };
  for (int i = 0; i < sizeof(factorial) / sizeof(int); i++) {
    printf("%d\n", factorial[i]);
  }
  return 0;
}


コンパイル結果:

$ 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

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

-1

#include <stdio.h>
#include <limits.h>

int main() {
  unsigned long long k = 1;
  int i = 0;
  do {
        printf("%d!=%d\n", (int)i, (int)k);
        k *= ++i;
  } while (k <= INT_MAX);
  return 0;
}

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2016/04/28 14:36

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

    キャンセル

  • 2016/04/28 15:00

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

    キャンセル

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

  • ただいまの回答率 88.32%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

関連した質問

同じタグがついた質問を見る