基本情報 2022 サンプル問題 問2：テクノロジ系に関する問題

答えは d です(NISHIN(k) ← j mod 2、 j ← j div 2 の順)。

10進数を2進数にする方法は 「2で割って、余りを下から並べる」 がお決まり。たとえば 13 を2進にすると:

• 13 ÷ 2 = 6 余り 1 ← 一番下
• 6 ÷ 2 = 3 余り 0
• 3 ÷ 2 = 1 余り 1
• 1 ÷ 2 = 0 余り 1 ← 一番上

下から読んで `1101` が2進数の13。

この問題で大事なのは順番:

1. 先に余りを取って配列に入れる(余りを取らずに割ってしまうと、本来欲しい余りが消える)

2. そのあと j を割って小さくする

👉 覚え方: 「先に余りを取る、後で半分にする」。順番を逆にすると数字が変わって失敗。

なぜこれが正解か

正解は d。10進→2進変換は「2で割った余りを下位桁から並べる」アルゴリズム。各ループで以下の順序が必須:

1. NISHIN(k) ← j mod 2(現在のjの最下位ビット=余りを配列に格納)

2. j ← j div 2(jを右にビットシフト=次のビットを準備)

順序を逆にすると、先に j を割ってしまい、本来取得すべき余りが失われる。

各選択肢の解説

• a: `j ← j div 2; NISHIN(k) ← j mod 2`。先にjを更新するため、配列に入るのは「シフト後の値」の余りで、1ビットずつズレる。
• b: `j ← j mod 2; NISHIN(k) ← j div 2`。jにmodを代入してしまうとjが0か1になり破壊される。配列には常に0が入る。
• c: `NISHIN(k) ← j div 2; j ← j mod 2`。配列に商(整数部分)を入れている時点で誤り。配列には0/1の各ビットが入るべき。

覚え方・ひっかけ注意

「余り → 商」の順を死守。例: 13 で確認すると k=1 で NISHIN(1)=1, j=6 → k=2 で NISHIN(2)=0, j=3 → … と進み、下位桁から `1,0,1,1,0,0,0,0` が格納される。div と mod の意味を取り違えない(div=商の整数部、mod=余り)。

アルゴリズムの本質

基数変換は「位取り記数法における位の重み」を逆算する操作。10進数 j を 2 で繰り返し除算する手法は、j を 2 進展開 j = Σ b_i × 2^i と見たとき、j mod 2 が b_0 を、(j div 2) mod 2 が b_1 を…と最下位ビット(LSB)から順に取り出す原理に基づく。本流れ図はその古典的実装。

計算量と等価実装

時間計算量は O(log₂ j)。各反復は定数時間で、桁数分(8ビット固定なので最大8回)反復する。等価なビット演算実装は:

```

NISHIN(k) ← j & 1

j ← j >> 1

```

C言語等の低水準コードでは右シフトの方が高速だが、流れ図表現では算術演算で記述するのが一般的。

関連する変換アルゴリズム

• 基数変換の一般化: r 進数への変換は除数を r にするだけ。8進・16進への変換でも同じ枠組み。
• Horner法: 2進→10進は逆向きに、最上位ビットから `result = result*2 + b_i` を繰り返す方式が効率的(MSBファースト)。
• double-dabble法: 2進→BCD変換のハードウェア実装で使われる、シフトと条件加算の組み合わせ。

試験での位置づけ

流れ図問題は基本情報技術者試験で頻出。トレース(実際に値を当てはめて追う)技術が必須スキル。div/mod の取り違え、ループ端の初期値・終値・増分の解釈ミス、配列の添字(0始まり vs 1始まり)に注意。本問は1始まり(k:1,1,8)。

選択肢の発展補足

• 負数を扱う場合: 2の補数表現の負数を直接 div/mod すると言語仕様により結果が異なる(切り捨て方向の差異)。実務では符号を別管理する。
• 浮動小数点の2進変換: 小数部は「2を掛けて整数部を取り出す」逆操作。0.1 が無限循環2進小数になるのが浮動小数誤差の原因。
• アセンブラレベルでは `SHR`(論理右シフト)1命令で `j div 2` と `j mod 2`(キャリーフラグに格納)を同時取得可能。これが基数変換ループの定石実装。