平成22年度春期 プロジェクトマネージャ 午前Ⅰ 問2

流れ図を小さな例で追跡して確かめる

空欄に入る処理を考えるときは、頭の中の理屈だけで決めず、小さな値を自分で用意して流れ図を一歩ずつたどり、各変数の値の変化を記録してみましょう。最終結果が期待どおりになるかで、候補の妥当性を確かめられます。

この問題で問われていること

この種の問題で問われやすいのは、繰返しの各回で変数がどう更新されるかという『状態の移り変わり』です。ループ開始前・各回の処理後・終了時点で、どの変数がどんな値を持つべきかを意識して整理しましょう。

視点

トレース表とは、流れ図の各処理を通過するたびに変数の値を一行ずつ書き留める表です。2進数の値は桁ごとに書くと変化が見やすくなります。判定の分岐をどちらに進んだかも併記すると、繰返し回数や終了条件の確認にも役立ちます。

確認ポイント

• 自分で選んだ小さな値で、最終的に得られるべき結果を先に手計算しておいたか
• 流れ図の各処理を通るたびに、すべての変数の値を表に書き留めたか
• 繰返しの終了時に、記録した値が先に求めた結果と一致するか確かめたか

正解

ア

解説

正解はアです。aでYの第0ビットを調べ、bでXを1ビット左シフト、Yを1ビット右シフトします。すると、i回目には乗数の第(i−1)ビットと被乗数×2^(i−1)が対応し、Zに正しい積が求まります。

理由

ループは i=1〜16 の16回まわります。アの組合せでは、i回目の判定時点でYは(i−1)ビット右シフト済みなので、第0ビットには乗数の元の第(i−1)ビットがあります。Xは(i−1)ビット左シフト済みで、被乗数×2^(i−1)です。よって、Z = Σ(k=0〜15) 乗数の第kビット × 被乗数 × 2^k = 被乗数 × 乗数 となります。bは16回すべてで実行されるため、Xは最終的に16ビット左シフトされます。ただし、Zに加算されるときのXのシフト量は最大15ビットです。16ビットの被乗数を16ビット左シフトしても最上位は第31ビットなので、32ビットに収まります。積も最大 (2^16−1)^2 < 2^32 なので、Zからはみ出しません。

検算例

被乗数3（11）、乗数5（101）で確かめます。i=1：Yの第0ビットは1なので Z=0+3=3。その後 X=6、Y=2（10）になります。i=2：第0ビットは0なので加算しません。その後 X=12、Y=1 になります。i=3：第0ビットは1なので Z=3+12=15。それ以降、Yの第0ビットは0のままです。結果は 3×5=15 と一致します。

比較

イとエはXを右シフトします。そのため、繰り返すたびに加える値が小さくなり、下位ビットも失われます。ウは乗数の最上位ビット（重み2^15）を被乗数×2^0に対応させてしまいます。さらに、Yを右シフトするので2回目以降の第15ビットは0になり、乗数の他のビットが判定されません。重みが一致するのはアだけです。

選択肢ア（正解）

これは正解だよ。aでYの第0ビットが1ならZにXを加え、bでXを1ビット左シフト、Yを1ビット右シフトする。i回目の判定では乗数の第(i−1)ビットが第0ビットにあり、Xは被乗数×2^(i−1)なので、Zは積になる。bは16回実行されるので、Xは最終的に16ビット左シフトされる。加算に使われるXのシフト量は最大15ビットで、16ビットの値を16ビットずらしても32ビットに収まる。

選択肢イ

これは不正解だよ。aでYの第0ビットを調べる点はアと同じだけど、bでYを左シフトすると第0ビットには0が入る。そのため2回目以降の判定は常に0になり、乗数の第1ビット以降が積に反映されない。さらにXを右シフトすると、加える値が1/2ずつ小さくなって下位ビットも失われる。乗数の第kビットに被乗数×2^kを対応させられない。

選択肢ウ

これは不正解だよ。bはアと同じだけど、aでYの第15ビットを調べると、1回目は乗数の最上位ビット（重み2^15）が1のときに被乗数×2^0を加えてしまい、重みが合わない。また、Yを右シフトすると第15ビットには上位の0が入るので、2回目以降は常に0と判定され、乗数の残りのビットが積に反映されない。

選択肢エ

これは不正解だよ。Yの第15ビットを調べてYを左シフトすれば、乗数を最上位ビットから第15、第14…の順に調べられる。しかしXを右シフトするので、重み2^15のビットに被乗数×2^0が、次のビットにはさらに1/2にした値が対応し、重みの大小が逆になる。右シフトで下位ビットも失われるので、正しい積は得られない。

学習のポイント

乗数の判定ビットの重みと、加算する被乗数の重みを毎回そろえるシフト方向を理解する。