二進数変換で下位桁をどう順に格納するか
基本情報技術者試験 令和元年度秋期 午前 問1 ／ アルゴリズムとプログラミング › アルゴリズム
過去問にチャレンジ
次の流れ図は，10進整数 j(0＜j＜100) を8桁の2進数に変換する処理を表している。2進数は下位桁から順に，配列の要素 NISHIN(1) から NISHIN(8) に格納される。流れ図のa及びbに入る処理はどれか。ここで，j div 2 はjを2で割った商の整数部分を，j mod 2 はjを2で割った余りを表す。
- ア
a：j ← j div 2 b：NISHIN(k) ← j mod 2
- イ
a：j ← j mod 2 b：NISHIN(k) ← j div 2
- ウ
a：NISHIN(k) ← j div 2 b：j ← j mod 2
- エ
a：NISHIN(k) ← j mod 2 b：j ← j div 2
会話形式の解説
講師この流れ図では、配列の最初の要素に何の桁を入れるかが手がかりです。
受験者下位桁から入れるので、まず二進数の一番右の桁を求めるのですね。
講師はい。現在のjを2で割った余りが、その桁です。商と余りのどちらを先に保存しますか。
受験者余りを配列に保存してから、jを商に更新します。更新を先にすると、最初の桁が分からなくなります。
講師そのとおりです。先に商へ更新してから余りを格納する組合せでは、元のjの最下位桁を飛ばしてしまいます。
受験者jを先に余りへ更新する組合せもありますが、それならjには0か1しか残りませんね。
講師はい。その値を2で割った商は0なので、配列に元の数の各桁を記録できません。
受験者では、商をそのまま配列に入れる組合せはどうですか。
講師商は0か1とは限らず、二進数の一桁として格納する値にはなりません。
受験者余りをNISHIN(k)に入れ、その後でjを商に更新する組合せが正解のエですね。
講師はい。kが次へ進むたびに、更新後のjから一つ上の桁を取り出せます。
受験者元の整数を更新する前に余りを保存する、という順序が大切なのですね。
講師その順序です。途中でjが0になっても、残りの余りは0なので、八つの要素を埋められます。
まとめ
正解はエです。現在のjを2で割った余りをNISHIN(k)に保存すると、その時点の下位桁を記録できます。その後でjを商に更新すれば、次の繰返しで一つ上の桁を取り出せます。商への更新を先にすると、元のjの最下位桁を失います。
解答・解説
正解はエです
この問題のテーマ
整数を2進数に変換するとき、各桁を取り出して配列に入れる順序を問う問題です。
解き方の考え方
図ではkを1から8まで増やし、2進数の下位桁から順に格納します。現在のjを2で割った余りが、その時点の最下位桁です。まず余りをNISHIN(k)に保存し、その後でjを商に更新すれば、次の繰返しで一つ上の桁を取り出せます。
選択肢ごとの解説
- ×ア a：j ← j div 2 b：NISHIN(k) ← j mod 2先にjを商に更新すると、元のjの最下位桁を保存する前に失います。その後の余りは一つ上の桁に当たるため、NISHIN(1)から正しい順序で格納できません。
- ×イ a：j ← j mod 2 b：NISHIN(k) ← j div 2jを余りに更新した時点で、jには0か1しか残りません。その値をさらに2で割った商を格納しても0になり、元の数の各桁を記録できません。
- ×ウ a：NISHIN(k) ← j div 2 b：j ← j mod 2jを2で割った商は、2進数の1桁である0か1とは限りません。その商をNISHIN(k)に入れる処理では、求める桁を格納できません。
- ○エ a：NISHIN(k) ← j mod 2 b：j ← j div 2aで現在の最下位桁を余りとしてNISHIN(k)に保存します。続くbでjを商に更新するので、kが次へ進むたびに一つ上の桁を格納でき、図の処理に合います。
POINT
- 2進数の各桁は、現在の整数を2で割った余りから求めます。
- 元の整数を更新する前に、取り出した桁を保存します。
- 商を次の整数として繰り返すと、下位桁から上位桁へ進みます。
- jが0になった後の余りは0なので、残りの配列要素も0で埋まります。