C言語の基礎
int fact(int n) {
if (n <= 1)
return 1;
return n * fact(n - 1);
}int は32ビット(最大値 2147483647)とする。上の関数 fact(n) が、n の階乗をオーバーフローを起こさずに正しく返す最大の n はどれか。
- A12
- B13
- C20
答えと解説を見る
正解：A. 12
fact は、n × fact(n − 1) のように自分自身を呼び出し、n が1以下になったら1を返す再帰関数です。12! = 479001600 は int の最大値 2147483647 より小さいので正しく求まりますが、13! = 6227020800 は最大値を超えます。fact(13) では最後の 13 × 479001600 の掛け算で符号付き整数のオーバーフローが起こり、これは未定義動作です。たとえば最適化をしない x86-64 の gcc では、6227020800 を 2³² で割った余りの1932053504が返りますが、この結果は保証されません。より大きな n には、64ビットの long long(n = 20 まで)などを使います。
- A. 正しい。12! = 479001600 は最大値より小さく、13! は最大値を超えます。
- B. 13! = 6227020800 は int の最大値 2147483647 を超えるので、正しく求まりません。
- C. 20 は、64ビットの符号付き整数(long long など)で正しく求まる最大の n です。