FE SUBJECT B
基本情報技術者 科目Bの問題解説：次のプログラム中の[空欄]に入れる最も適切な式はどれか。 ○…
問題
次のプログラム中の[空欄]に入れる最も適切な式はどれか。
○整数型: toDecimal(文字列型: bits)
整数型: i, result ← 0
for (i を 1 から bitsの文字数 まで 1 ずつ増やす)
result ← [空欄]
endfor
return resultbits は左から右へ読まれる2進数の文字列である。
- ア result ＋ int(bitsのi文字目の文字)
- イ result × 2 ＋ int(bitsのi文字目の文字)（正解）
- ウ result × 2 ＋ int(bitsの(bitsの文字数 - i + 1)文字目の文字)
- エ result ＋ 2 × int(bitsのi文字目の文字)
出典：オリジナル問題｜参考範囲：試験要綱Ver.5.5 / FEシラバスVer.9.2 科目B範囲
正解と解説
正解：result × 2 ＋ int(bitsのi文字目の文字)
2進数を左から読むときは、次の桁を読むたびに、これまでの値を1桁左へずらす必要があります。その操作が result × 2 で、そこへ現在のビットを足します。
例えば bits="1011" なら、result は 1 → 2 → 5 → 11 と変化します。単にビットを足すだけでは 1+0+1+1=3 になり、桁の重みが消えてしまいます。逆順に読む式も、左から読むという処理順とは合いません。
| i | 読む文字 | resultの更新後 |
|---|---|---|
| 1 | 1 | 1 |
| 2 | 0 | 2 |
| 3 | 1 | 5 |
| 4 | 1 | 11 |
このアルゴリズムの正体：これは各桁ごとに 2 のべき乗を計算せず、結果を 2 倍しながら次のビットを足し込むホーナー法による基数変換です。文字数 n に対して乗算と加算を 1 回ずつ繰り返すだけなので計算量は O(n) で、桁の重み 2^k を毎回求める方式より無駄がありません。
この問題について
公開問題・サンプル問題の形式、擬似言語記法、アルゴリズム読解・トレース・空欄補充・セキュリティ事例判断の傾向を参考にした独自問題です。本文・数値・選択肢は新規作成しています。
公式試験問題、公開問題、市販教材、外部問題サイトの問題文を転載・改題したものではありません。