FUNDAMENTAL INFORMATION TECHNOLOGY ENGINEER
基本情報技術者の問題解説：次の再帰手続 h(347) を実行したときの戻り値はどれか。…
問題
次の再帰手続 h(347) を実行したときの戻り値はどれか。
○整数型: h(整数型: n)
if (n ＜ 10)
return n
else
return (n mod 10) ＋ 2 × h(n ÷ 10 の商)
endif- ア 21
- イ 24
- ウ 27（正解）
- エ 31
出典：オリジナル問題｜参考範囲：試験要綱Ver.5.5 / FEシラバスVer.9.2 科目B範囲
正解と解説
正解：27
h(347)=7+2×h(34)。h(34)=4+2×h(3)=4+6=10。したがって h(347)=7+2×10=27です。各桁を単純に足すのではなく、上位側の戻り値に2倍が掛かります。
14や24に近い計算は、各桁の和や2倍する位置を誤った場合に出やすくなります。31は h(34) の計算後にさらに余分な2倍を入れた誤りです。
整数除算と剰余を使う再帰は、下位桁を取り出してから残りの桁へ進みます。戻ってくるときに係数が掛かるかどうかを確認しましょう。
このアルゴリズムの正体：各桁を下位から取り出し、上位へ進むたびに2倍を掛ける処理は、十進数の各桁を「基数2の重み」で足し直す計算です。347なら 7×2⁰＋4×2¹＋3×2²＝7＋8＋12＝27 となり、ホーナー法で基数を2として桁を評価したものと一致します。再帰の深さは桁数ぶんで、計算量はO(log n)です。
この問題について
公開問題・サンプル問題の形式、擬似言語記法、アルゴリズム読解・トレース・空欄補充・セキュリティ事例判断の傾向を参考にした独自問題です。本文・数値・選択肢は新規作成しています。
公式試験問題、公開問題、市販教材、外部問題サイトの問題文を転載・改題したものではありません。