FUNDAMENTAL INFORMATION TECHNOLOGY ENGINEER
基本情報技術者の問題解説：次の再帰関数を実行したとき、戻り値はどれか。ここで÷は整数除算である。 ○整数型: h…
問題
次の再帰関数を実行したとき、戻り値はどれか。ここで÷は整数除算である。
○整数型: h(整数型: n)
if (n ＜ 10)
return n
else
return (n mod 10) ＋ 2 × h(n ÷ 10)
endif
h(472) を呼び出す。- ア 21
- イ 28
- ウ 32（正解）
- エ 36
出典：オリジナル問題｜参考範囲：試験要綱Ver.5.5 / FEシラバスVer.9.2 科目B範囲
正解と解説
正解：32
nが2桁以上なら、最下位桁n mod 10を取り出し、残りの桁n÷10に対するhの結果を2倍して足します。472は472→47→4の順に再帰呼出しされます。
| n | 計算 | 戻り値 |
|---|---|---|
| 4 | 一桁なので4 | 4 |
| 47 | 7+2×4 | 15 |
| 472 | 2+2×15 | 32 |
単なる桁和ではなく、再帰結果を2倍するため32になります。
選択肢の見分け方：21は単純な桁和を加工した値、28や36は2倍する段をずらした値です。最下位桁を足し、残りの桁の結果を2倍するという順番を守りましょう。
このコードの正体：このhは各桁に「下位から1, 2, 4…と2のべき乗の重み」を掛けて合計する関数です。472なら2×1＋7×2＋4×4＝32となり、トレースした値と一致します。再帰の深さは桁数だけなので計算量はO(log n)です。重みが2倍ずつ増える点を押さえると、暗算でも検算できます。
この問題について
公開問題・サンプル問題の形式、擬似言語記法、アルゴリズム読解・トレース・空欄補充・セキュリティ事例判断の傾向を参考にした独自問題です。本文・数値・選択肢は新規作成しています。
公式試験問題、公開問題、市販教材、外部問題サイトの問題文を転載・改題したものではありません。