基本情報技術者 2017年 春期 午後 問09
次のCプログラムの説明及びプログラムを読んで、設問1〜3に答えよ。
マーク式試験の答案を採点するプログラムである。問題と受験者の解答の例を、図1に示す。
ここでは、unsigned int型のデータは、16ビットのビット列で表し、連続する8ビットが全て0のときは0…0、全て1のときは1…1と表記する。
〔プログラムの説明〕
(1) 関数markingは、1回の実行で受験者1人分の答案を採点する。
(2) 関数markingの引数の仕様は、次のとおりである。ここで、引数の値に誤りはないものとする。
① 問の数は、numQである。引数である各配列の要素数も、numQである。
② 1問当たりの選択肢の個数は16個以下である。
③ type[]の各要素には、答えを一つマークする問の場合は1、複数個マークする問の場合はマークする個数n（2 ≦ n ≦ 8）が格納されている。
④ ansC[]の各要素は、16ビットのビット列で、図2の例に示すように、最上位のビットから1ビットずつ順に選択肢ⓐ、ⓑ、…に対応し、正答の選択肢に対応するビット位置に1が格納されている。他の全てのビットは0である。
⑤ ansE[]の各要素は、ansC[]と同様の形式で、受験者の解答が格納されている。
(3) 関数markingは、各問（要素番号i：0, 1, …, numQ − 1）について、表1に示す解答形式に応じた採点方法で採点する。採点結果はmark[i]に格納する。
(4) 関数markingから呼ばれる関数countMarkBitsは、引数の値に含まれる1のビットの個数を返却値として返す。
設問1：
問題文を見る プログラム1中のに入れる正しい答えを、解答群の中から選べ。
a〜cに関する解答群
ア：2
イ：3
ウ：ansC[i]
エ：ansC[i] & ansE[i]
オ：ansC[i] | ansE[i]
カ：ansE[i]
キ：type[i]
ク：type[i] + 1
模範解答
a：カ、b：キ、c：エ
解説
解答の導き方
複数個マークする問では、正答と受験者の解答をそのまま比べるのではなく、まず選んだ個数を確認し、その後に正答と重なった個数を数えます。
-
受験者がマークした個数を確認します。
本文には、複数個マークする問について「受験者の解答中の1のビットの個数が 個以上なら0」とあります。ビットは、ここでは選択肢を選んだかどうかを表す0または1です。したがって、受験者がマークした数を数える対象は、受験者の解答であるansE[i] です。countMarkBitsは、引数に含まれる1の個数を返す関数です。そのため、aにはansE[i] を指定します。受験者がマークした数が、問題で指定された個数を超えていないかを確認する条件は、次の形になります。countMarkBits(ansE[i]) <= type[i] -
マーク数の上限と比べます。
複数個マークする問では、type[i]にマークする個数 が格納されています。よって、bにはtype[i] が入ります。マークした個数がtype[i] 以下なら、採点処理に進みます。type[i]より多くマークしている場合は、この条件が成り立たず、最初に設定されたmark[i] の0がそのまま残ります。 -
正答と受験者の解答の両方で1の位置を数えます。
本文では、上限を超えていない場合、「ansC[i] とansE[i] の対応するビットがともに1である個数」を採点結果にするとあります。つまり、正答であり、かつ受験者もマークした選択肢の数を数えます。ビットごとのAND（同じ位置の両方が1のときだけ1にする演算）を使うと、この条件に合う位置だけを残せます。その結果の1の個数を数えるため、cにはansC[i] & ansE[i] が入ります。図2の例では、正答はⓑとⓔ、受験者の解答はⓑとⓓです。両方でマークされているのはⓑだけなので、ビットごとのANDの結果に含まれる1は1個です。このように、正答と解答が完全に一致しなくても、両方に含まれる選択肢の数を採点結果にできます。
誤りやすいポイント
- aにansC[i] を入れるのは誤りです。条件で調べるのは、正答の数ではなく、受験者がマークした個数です。
- bに定数を入れるのは誤りです。マークすべき個数は問ごとに異なり、type[i]に格納されています。
- cにansC[i]だけ、またはansE[i]だけを指定すると、正答と受験者の解答の重なりを数えられません。
- 複数個マークする問でも、ansC[i]とansE[i]が完全に等しいかどうかだけで採点するわけではありません。両方で1になっているビットの個数が採点結果になります。
- マーク数がtype[i]を超えた場合は、部分点を計算しません。条件に入らないため、最初に設定されたmark[i]の0のままです。
FAQ
Q: 受験者が指定された個数より少なくマークした場合はどうなりますか？
A: 受験者の解答に含まれる1の個数はtype[i]以下なので、採点処理に進みます。そのうえで、正答と受験者の解答の両方に含まれる選択肢の数が採点結果になります。
A: 受験者の解答に含まれる1の個数はtype[i]以下なので、採点処理に進みます。そのうえで、正答と受験者の解答の両方に含まれる選択肢の数が採点結果になります。
Q: ansC[i]とansE[i]が同じでない場合は、必ず0点ですか？
A: いいえ。複数個マークする問では、完全一致ではなく、正答と受験者の解答で重なった選択肢の数を採点します。ただし、受験者が指定個数を超えてマークした場合は0点です。
A: いいえ。複数個マークする問では、完全一致ではなく、正答と受験者の解答で重なった選択肢の数を採点します。ただし、受験者が指定個数を超えてマークした場合は0点です。
Q: なぜビットごとのANDを使うのですか？
A: 正答と受験者の解答の両方で選ばれた位置だけを1として残せるからです。その1の個数を数えると、正答と一致した選択肢の数が分かります。
A: 正答と受験者の解答の両方で選ばれた位置だけを1として残せるからです。その1の個数を数えると、正答と一致した選択肢の数が分かります。
関連キーワード: ビット列、ビット演算、ビットごとのAND、配列、条件分岐
設問2：
問題文を見る 関数countMarkBitsのプログラムを、プログラム2に示す。次の記述中のに入れる正しい答えを、解答群の中から選べ。
コメント /* γ */ を付した行の代入式を実行するとき、実行前のworkの値が0101 0000 0…0であれば、実行後のworkの値はdとなる。
コメント /* γ */ を付した行の代入式を、
work = work && (work - 1);
と変更して、プログラム2の実行を試みた場合、e。
dに関する解答群
ア：0001 0000 0…0
イ：0100 0000 0…0
ウ：0100 1111 1…1
エ：1001 0000 0…0
eに関する解答群
ア：演算子&&と&とは実行する演算の内容が同じなので、正しい結果を返す
イ：演算子&&はビットごとの論理積を求めることはしないので、誤った結果を返す
ウ：変数workには実行前の値が保持されたまま変わらないので、無限ループになる
模範解答
d：イ、e：イ
解説
解答の導き方
まず、コメント「γ」の行で使われている「&」は、ビットごとの論理積です。左右の同じ位置のビットがどちらも1のときだけ、結果も1になります。
実行前の「work」は、16ビットで表すと次のとおりです。
2行目では、末尾側の0から繰り下がりが起きます。実行前の「work」と「work - 1」を同じ位置ごとに「&」で比べると、次の結果になります。
したがって、dに入るのは「0100 0000 0…0」に当たるイです。この演算では、workの中で最も右にある1が0になります。プログラムはこの処理を繰り返し、1のビットを一つずつ減らして個数を数えています。
次に、「&」を「&&」に変えた場合を考えます。「&&」はビットごとの演算ではありません。左右の値がどちらも0以外なら1を返し、そうでなければ0を返す論理演算です。そのため、結果はビット列ではなく0または1になります。
たとえば、workが「0100 0000 0000 0000」の場合、workもwork - 1も0以外なので、「work && (work - 1)」の結果は1です。次の繰返しでは、workが1になり、work - 1は0になります。結果は0となり、ループは終了します。しかし、countは2になってしまいます。もとのworkにある1は1個なので、正しい個数を返せていません。
このように「&&」にすると正しい結果にならない場合があります。したがって、eに入るのは、演算子&&はビットごとの論理積を求めないため誤った結果を返す、というイです。
誤りやすいポイント
- 「&」と「&&」を同じ演算だと考えないようにします。「&」は各ビットを比べますが、「&&」は値が0かどうかを調べ、結果として0または1を返します。
- 「work - 1」を、単に末尾の数字を1減らす処理だと思わないようにします。2進数では、末尾側の0から繰り下がります。
- 「&&」に変えると無限ループになる、と決めつけないようにします。この例ではworkが1や0に変わるためループは終了しますが、数える結果が誤ることがあります。
- 問題に示された「0101 0000 0…0」では、変更後も偶然、1の個数と同じ回数だけループするため、変更の誤りに気づきにくい点に注意します。
FAQ
Q: 「work & (work - 1)」で、なぜ1のビットを一つずつ減らせるのですか？
A: 「work - 1」によって、workの最も右にある1が0になります。その右側にあった0は1になりますが、「&」でworkと比べると、右側のビットはwork側が0なので結果も0です。結果として、最も右にある1だけが消えます。
A: 「work - 1」によって、workの最も右にある1が0になります。その右側にあった0は1になりますが、「&」でworkと比べると、右側のビットはwork側が0なので結果も0です。結果として、最も右にある1だけが消えます。
Q: 「&&」に変えた場合、いつも間違った結果になりますか？
A: いつもとは限りません。問題の「0101 0000 0…0」のように、偶然正しい個数になることもあります。ただし、たとえば1のビットが1個だけの値でも2回数える場合があるため、一般には正しい個数を求められません。
A: いつもとは限りません。問題の「0101 0000 0…0」のように、偶然正しい個数になることもあります。ただし、たとえば1のビットが1個だけの値でも2回数える場合があるため、一般には正しい個数を求められません。
関連キーワード: ビット演算、論理演算、2進数、ビット列、ビットカウント
設問3：
問題文を見る 次の記述中のに入れる正しい答えを、解答群の中から選べ。
解答形式に、順不同形式を追加する。順不同形式とは、答えを一つマークする問が2問以上連続していて、共通の解答群から答えを選んでいくが、その選択の順序は入れ替わってもよい形式である。図3の例では、問21、22、23の順に正答ⓑ、ⓓ、ⓔが設定されているが、これを受験者の解答の例のように異なる順序で解答してもよい。正しい答えが幾つ選択されたかによって、採点結果が決まる。
順不同形式の問題に対する解答を含む答案を採点するために、プログラム1を次のとおり修正した。
(1) プログラム1中のコメント /* α */ の行を、次の1行で置き換える。
unsigned int sumC, sumE;
(2) プログラム1中のコメント /* β */ の行を、次の13行で置き換える。
else if ((11 <= type[i]) && (type[i] <= 13)) {
if (type[i] == 11) {
sumC = 0;
sumE = 0;
}
sumC = sumC | ansC[i];
if (countMarkBits(ansE[i]) == 1) {
sumE = sumE | ansE[i];
}
if (type[i] == 13) {
mark[i] = countMarkBits(sumC & sumE);
}
}
順不同形式の問を表すtype[]の値は、11〜13である。一組の順不同形式の問題において、値11は先頭の問を表し、値13は末尾の問を表す。値12は3問以上から成る順不同形式の問題における中間の問を表す。
図3の順不同形式の問題に対する解答を含む答案を、修正したプログラム1で採点する。ある受験者の解答の採点例として、関数markingに渡された各配列要素の内容、及びこれらの内容に基づく採点結果を、図4に示す。
また、図4に示す解答の採点が完了した時点で、変数sumEには値gが格納されている。
fに関する解答群
gに関する解答群
ア：0…0 0…0
イ：0000 1000 0…0
ウ：0101 0000 0…0
エ：0101 1000 0…0
模範解答
f：ア、g：イ
解説
解答の導き方
この設問では、図4の3問について、採点結果と採点後のsumEを求めます。順不同形式では、各問の正答と受験者の解答をまとめ、正しく選ばれた選択肢の数を採点結果にします。
まず、type[20]が11なので、問20は順不同形式の先頭です。プログラムではこのときsumCとsumEを0に戻します。その後、各問の正答と受験者の解答を、ビットごとの論理和（どちらかのビットが1なら結果を1にする演算）でまとめます。
まずsumCを求めます。図4の正答は、問20が「0100 0000 0・・・0」、問21が「0001 0000 0・・・0」、問22が「0000 1000 0・・・0」です。これらを順に論理和でまとめると、次のようになります。
- 問20の後：0100 0000 0・・・0
- 問21の後：0101 0000 0・・・0
- 問22の後：0101 1000 0・・・0
したがって、最後の問の処理時点でsumCは「0101 1000 0・・・0」です。
次にsumEを求めます。プログラムには「countMarkBits(ansE[i]) == 1」とあり、受験者がその問で1つだけ選んだ場合に限って、解答をsumEに加えます。countMarkBitsは、値に含まれる1のビットの個数を数える関数です。
問20と問21の解答は同じビット位置が1なので、論理和を取ってもそのビットは1のままです。問22は1の個数が2なので、sumEには加えません。よって、採点後のsumEは「0000 1000 0・・・0」です。これがgに入ります。
最後に、type[22]が13なので、問22の処理で採点結果を求めます。プログラムはsumCとsumEのビットごとの論理積（両方のビットが1の場合だけ結果を1にする演算）を取り、その1の個数を数えます。
0101 1000 0・・・0
AND 0000 1000 0・・・0
= 0000 1000 0・・・0
AND 0000 1000 0・・・0
= 0000 1000 0・・・0
1の個数は1個です。そのためmark[22]は1になります。一方、mark[i]は各問の処理の最初に0に設定され、問20と問21では採点結果を書き換えません。したがって、mark[20]、mark[21]、mark[22]は上から0、0、1となり、fはアです。
誤りやすいポイント
- 問22のansEには1が2個あります。「1個以下」ではなく「1個」の場合だけsumEに加えるため、問22の解答は加えません。
- 問20と問21のansEは同じビット位置が1です。論理和では同じ位置の1を重ねても、1が2個にはなりません。
- mark[20]とmark[21]は、順不同形式の途中の問なので0のままです。採点結果が格納されるのは、末尾のtype[22]が13の問です。
- sumCとsumEの論理積は、同じ位置で正答と受験者の解答の両方が1になっているビットだけを残します。
FAQ
Q: 問22の受験者の解答は、なぜ採点に使われないのですか？
A: その解答には1のビットが2個あります。sumEに加える条件は、1のビットがちょうど1個であることです。
A: その解答には1のビットが2個あります。sumEに加える条件は、1のビットがちょうど1個であることです。
Q: 問20と問21の受験者の解答が同じでも、sumEが変わらないのはなぜですか？
A: sumEは、選択されたビットを論理和でまとめています。同じ位置のビットがすでに1なら、もう一度1を加えてもその位置は1のままです。
A: sumEは、選択されたビットを論理和でまとめています。同じ位置のビットがすでに1なら、もう一度1を加えてもその位置は1のままです。
Q: 正答と受験者の解答の論理積を取る理由は何ですか？
A: 両方で選ばれた選択肢だけを取り出すためです。その後、残った1の個数を数えることで、正しく選ばれた数を求められます。
A: 両方で選ばれた選択肢だけを取り出すためです。その後、残った1の個数を数えることで、正しく選ばれた数を求められます。
関連キーワード: ビット列、ビット演算、論理和、論理積、配列
