平成24年度 秋期 午前 問7
アルゴリズム
乗算の回数を表す式
n! の値を，次の関数 F(n) によって計算する。乗算の回数を表す式はどれか。
┌ 1 (n＝0)
F(n)＝ ┤
└ n×F(n−1) (n＞0)- アn−1
- イn
- ウn²
- エn!
答えと解説を見る
✓ これが正解イn
解説
1段につき乗算は1回で、n段続くので合計n回です。
この関数は、引数が0のときは1を返し、0より大きいときは自分自身を1つ小さい引数で呼び出して、返ってきた値に自分の引数を掛けます。軸は二つです。一つ目は1段あたりの乗算の数で、掛け算は各段にちょうど1回ずつしか現れません。二つ目は段数で、引数が1ずつ減りながら0に達するまで呼び出しが重なります。引数がnのときは呼び出しがn段重なり、そのそれぞれで1回ずつ掛けるので、乗算の総数はnになります。返る値と手数は別のものだという点が勘所です。値のほうは引数が少し増えただけで急に大きくなりますが、掛ける回数は引数と同じ歩調でしか増えません。
ほかの選択肢はなぜ違うのか
- アn−1：引数が1のときに行う掛け算を数え落とすとこの形になります。その段でも、0の場合に返される値と引数とを実際に掛け合わせているので、1回として数えます。
- ウn²：段ごとに引数の数だけ掛け算が起きると考えるとこの形になりますが、各段で行う掛け算は1回だけです。段数と1段あたりの回数を掛け合わせても二乗にはなりません。
- エn!：これは関数が返す値そのものを表す形です。問われているのは掛け算を行った回数なので、計算の結果として得られる値を答えにはできません。
出典：平成24年度 秋期 基本情報技術者試験 午前 問7（改変：原典の図表をテキストに書き起こした）
この解説に誤りを見つけたら教えてください。直して、直した記録を残します。誤りを報告する（メールが開きます）