2進数を整数に変換する擬似言語、桁の重みと合計の更新式を確かめる

ITパスポート試験令和6年度問85 ／アルゴリズムとプログラミング › アルゴリズムとプログラミング

過去問にチャレンジ

令和6年度問85

関数binaryToIntegerは、1桁以上の符号なし2進数を文字列で表した値を引数binaryStrで受け取り、その値を整数に変換した結果を戻り値とする。例えば、引数として“100”を受け取ると、4を返す。プログラム中のa、bに入れる字句の適切な組合せはどれか。〔プログラム〕

○整数型: binaryToInteger(文字列型: binaryStr)
  整数型: integerNum, digitNum, exponent, i
  integerNum ← 0
  for (iを1からbinaryStrの文字数まで1ずつ増やす)
    digitNum ← binaryStrの末尾からi番目の文字を整数型に変換した値
    // 例: 文字“1”であれば整数値1に変換
    exponent ← a
    integerNum ← b
  endfor
  return integerNum

ア
a：(2のi乗)−1、b：integerNum × digitNum × exponent
イ
a：(2のi乗)−1、b：integerNum + digitNum × exponent
ウ
a：2の(i−1)乗、b：integerNum × digitNum × exponent
エ
a：2の（i−1乗） b：integerNum ＋ digitNum ✕ exponent

解答・解説を見る

講師

今回は、2進数の文字列を整数に直すプログラムの穴埋めです。見るところは二つで、空欄aは「その桁の重み」、空欄bは「合計値をどう更新するか」です。

受験者

重みというのは、2進数の各桁が表している大きさのことですか。10進数でいう一の位、十の位のようなものだと考えています。

講師

その理解で合っています。2進数では右端、つまり最下位の桁から1、2、4、8…と2倍ずつ増えます。そして2進数の値は「各桁の値×その桁の重み」をすべて足したものです。

受験者

プログラムは末尾からi番目の文字を取り出していて、iは1から始まります。i=1で重み1、i=2で重み2、i=3で重み4なので、2の(i−1)乗だと思います。

講師

そのとおりです。iが1から始まるので、i=1のときに2の0乗の1になるよう、指数はi−1になります。では(2のi乗)−1のほうはどうでしょう。

受験者

iが1、2、3のとき、1、3、7になります。重みの1、2、4と合わないので、aが(2のi乗)−1の組合せは外れますね。

講師

はい。ちなみに(2のi乗)−1は「i桁の2進数で表せる最大値」を表す式なので、重みと取り違えないようにしましょう。次は空欄bです。掛け算で更新する式と、足し算で更新する式がありますね。

受験者

掛け算のほうが、重みを掛けていく感じがして一瞬それらしく見えました。でも、integerNumは最初に0が入っています。

講師

そこが大事な点です。初期値が0なので、integerNum×digitNum×exponentで更新すると、0に何を掛けても0のままです。どんな入力でも0を返してしまいます。

受験者

では、重みは正しくてもbが掛け算の組合せは誤りで、aが(2のi乗)−1でbが掛け算の組合せは、aもbも誤りということですね。

講師

そうです。残りの、bは足し算でもaが(2のi乗)−1の組合せは、問題文の例“100”で試すとはっきりします。1が立っているのはi=3の桁ですが、重みが7になるので結果は7になり、4と一致しません。

受験者

正解の組合せでもたどってみます。i=1で0＋0×1＝0、i=2で0＋0×2＝0、i=3で0＋1×4＝4です。例のとおり4になりました。

講師

確認できましたね。aが2の(i−1)乗、bがintegerNum＋digitNum×exponentの組合せが正解です。合計を求める変数は0で初期化して加算で積み上げる、という形はよく出てきます。穴埋めで迷ったら、問題文にある具体例を各選択肢でたどってみると確実に絞り込めます。

まとめ

2進数の値は、各桁の値にその桁の重みを掛け、すべて足し合わせて求めます。このプログラムは末尾（最下位）の桁から順に処理し、iが1から始まるため、i番目の桁の重みは2の(i−1)乗で、1、2、4…となります。合計値integerNumは0で初期化されているため、掛け算で更新すると常に0のままです。したがって、更新式は「integerNum＋digitNum×exponent」の加算が正しくなります。例の“100”をたどると4になり、問題文の例とも一致します。

解答・解説

正解はエです

この問題のテーマ

擬似言語で書かれた、2進数の文字列を整数に変換するプログラムの穴埋め問題です。桁の重みの求め方と、合計値を積み上げていく更新式を理解しているかが問われます。

解き方の考え方

2進数の値は「各桁の値×その桁の重み」をすべて足し合わせたものです。プログラムは文字列の末尾、つまり最下位の桁から順に処理しているので、i番目の桁の重みは1、2、4、8…となり、2の(i−1)乗で表せます。これが空欄aに入ります。合計値integerNumは0から始まるので、各桁の積を「加算」していく式が空欄bに入ります。最後に例の“100”をたどって、4になるか確かめます。

選択肢ごとの解説

×ア a：(2のi乗)−1、b：integerNum × digitNum × exponent
重みを(2のi乗)−1とすると、iが1、2、3のときに1、3、7となり、2進数の重み1、2、4と合いません。さらに、integerNumを掛け算で更新する式では、初期値が0なので何を掛けても結果は0のままです。aもbも誤りです。
×イ a：(2のi乗)−1、b：integerNum + digitNum × exponent
integerNumに積を足していく更新式は正しいものの、重みの(2のi乗)−1が誤りです。“100”で試すと、1が立っているi=3の桁の重みが7になるので、結果は4ではなく7になってしまいます。
×ウ a：2の(i−1)乗、b：integerNum × digitNum × exponent
重みの2の(i−1)乗は正しいですが、bが掛け算による更新になっています。integerNumの初期値は0なので、どの繰返しでも0×（何か）＝0となり、常に0を返してしまいます。
○エ a：2の（i−1乗） b：integerNum ＋ digitNum ✕ exponent
aの2の(i−1)乗で末尾から1、2、4…の重みを作り、bの「integerNum＋digitNum×exponent」で各桁の値を合計に足していきます。“100”をたどると、i=1では0＋0×1＝0、i=2では0＋0×2＝0、i=3では0＋1×4＝4となります。最終値は4で、問題文の例と一致します。

補足

穴埋めの擬似言語問題では、問題文にある具体例（ここでは“100”→4）を各選択肢でたどってみると、確実に絞り込めます。(2のi乗)−1は「i桁の2進数で表せる最大値」（1、3、7…）を表す式なので、重みと取り違えないように注意してください。また、iを1から始めるか0から始めるかで、指数が「i」と「i−1」のどちらになるかが変わる点もよく狙われます。

POINT

2進数の各桁の重みは、右端（最下位）から1、2、4、8…と2倍ずつ増えます。
末尾からi番目の桁の重みは2の(i−1)乗で、i=1のときは2の0乗の1になります。
2進数を10進数にするには、各桁の値と重みを掛けたものをすべて足し合わせます。
合計を求める変数は0で初期化して加算で更新し、掛け算で更新すると0のままになります。

過去問にチャレンジ

会話形式の解説

まとめ

解答・解説

この問題のテーマ

解き方の考え方

選択肢ごとの解説

補足