【基本情報】午前試験のアルゴリズムの解き方をマスターする

正解は”エ”

解説しやすいようにそれぞれの処理に名前を付けておきます。

【アルゴリズム問題の鉄則①：具体的な数字を使う】
今回のアルゴリズムは10進数を2進数に変換するものです。例えば「5」を2進数に変換する場合を考えてみましょう。

「5」を2進数に変換すると「00000101」になります。「2進数は下位桁から順に，配列の要素NISHIN(1)からNISHIN(8)に格納される。」と書いてあるので、
・NISHIN(1)=1
・NISHIN(2)=0
・NISHIN(3)=1
・NISHIN(4)=0
・NISHIN(5)=0
・NISHIN(6)=0
・NISHIN(7)=0
・NISHIN(8)=0になるはずです。

【アルゴリズム問題の鉄則②：1Stepずつ丁寧に見る】
処理①：jに「5」を入力

反復構造[kを1~8まで、1ずつ増やしながら処理②と処理③を行う]
●k=1のとき
処理②
ア：j ← j div 2なので処理②が終わった後は、j = 2
イ：j ← j mod 2なので処理②が終わった後は、j = 1
ウ：NISHIN(k) ← j div 2なので処理②が終わった後は、NISHIN(1) = 2
エ：NISHIN(k) ← j mod 2なので処理②が終わった後は、NISHIN(1) = 1

処理③
ア：NISHIN(k) ← j mod 2なので処理②が終わった後は、NISHIN(1) = 0
イ：NISHIN(k) ← j div 2なので処理②が終わった後は、NISHIN(1) = 0
ウ：j ← j mod 2なので処理②が終わった後は、j = 1
エ：j ← j div 2なので処理②が終わった後は、j = 2

k=1の処理が終わった段階でNISHIN(1) = 1となっているのはエだけなので、答えは’エ’になります。答えは分かりましたが、折角なのでk=4くらいまで見てみましょう。

◎k=1終了時点（正解のエのパターンだけ記載）
j = 2
NISHIN(1) = 1

●k=2のとき
処理②
エ：NISHIN(k) ← j mod 2なので処理②が終わった後は、NISHIN(2) = 0
処理③
エ：j ← j div 2なので処理②が終わった後は、j = 1

◎k=2終了時点
j = 1
NISHIN(2) = 0

●k=3のとき
処理②
エ：NISHIN(k) ← j mod 2なので処理②が終わった後は、NISHIN(3) = 1
処理③
エ：j ← j div 2なので処理②が終わった後は、j = 0

◎k=3終了時点
j = 0
NISHIN(3) = 1

●k=4のとき
処理②
エ：NISHIN(k) ← j mod 2なので処理②が終わった後は、NISHIN(4) = 0
処理③
エ：j ← j div 2なので処理②が終わった後は、j = 0

◎k=3終了時点
j = 0
NISHIN(4) = 0

この時点でj=0なので、これ以降はずっとNISHIN(k) = 0になります。

正解は”エ”

解説しやすいようにそれぞれの処理に名前を付けておきます。

【アルゴリズム問題の鉄則①：具体的な数字を使う】
今回の問題では具体的な数字を入力する変数が無いので鉄則①は飛ばします

【アルゴリズム問題の鉄則②：1Stepずつ丁寧に見る】
この問題ではiを条件とした反復構造の中にjを条件とした反復構造が入っています。この場合、i=0のときのj=0~7を考え、次にi=1のときのj=0~7を考え、次にi=2のときのj=0~7を考え、、、という風にアルゴリズムを解きます。

●i=0のとき
・j=0のとき
処理①
ア：B (7-i, 7-j) ← A (i, j)なのでA(0,0)がB(7,7)に移動
イ：B (7-j, i) ← A (i, j)なのでA(0,0)がB(7,0)に移動
ウ：B (i, 7-j) ← A (i, j)なのでA(0,0)がB(0,7)に移動
エ：B (j, 7-i) ← A (i, j)なのでA(0,0)がB(7,7)に移動

A(0,0)には「*」が入っていないので移動先のBにも「*」は入りません。
図3を見るとB(0,7)、B(7,0)、B(7,7)に「*」は入っていません。
なので、この時点ではア～エ全てOKです。

・j=1のとき
処理①
ア：B (7-i, 7-j) ← A (i, j)なのでA(0,1)がB(7,6)に移動
イ：B (7-j, i) ← A (i, j)なのでA(0,1)がB(6,0)に移動
ウ：B (i, 7-j) ← A (i, j)なのでA(0,1)がB(0,6)に移動
エ：B (j, 7-i) ← A (i, j)なのでA(0,1)がB(1,7)に移動

A(0,1)には「*」が入っているので移動先のBにも「*」は入ります。
図3を見るとB(1,7)だけ「*」が入っています。
なので、この時点ではエが正解だと分かります。

正解は”エ”

【アルゴリズム問題の鉄則①：具体的な数字を使う】
今回の問題ではア～エで初期値が異なるのでそれぞれで具体例を設定します。
ア　a=2, b=1
イ　a=1, b=2
ウ　a=3, b=2
エ　a=2, b=3

【アルゴリズム問題の鉄則②：1Stepずつ丁寧に見る】
処理①：mとnにそれぞれaとbを代入する
ア　a=2, b=1としたので、m=2, n=1
イ　a=1, b=2としたので、m=1, n=2
ウ　a=3, b=2としたので、m=3, n=2
エ　a=2, b=3としたので、m=2, n=3

分岐②：mとnが同値かどうか
ア　m=2, n=1なので、≠
イ　m=1, n=2なので、≠
ウ　m=3, n=2なので、≠
エ　m=2, n=3なので、≠

分岐③：mとnの大小比較
ア　m=2, n=1なので、>
イ　m=1, n=2なので、<
ウ　m=3, n=2なので、>
エ　m=2, n=3なので、<

この問題では「①→②→③→⑤→②→③→④→②→⑥」の順に実行する組み合わせを探しています。分岐③の次に処理⑤に行くのは「<」のパターンです。
よって、この時点で答えはイかエに絞れます。ここからはイとエだけを見ていきましょう。

処理⑤：n ← (n-m)
イ　m=1, n=2なので、n=1になる
エ　m=2, n=3なので、n=1になる

分岐②：mとnが同値かどうか
イ　m=1, n=1なので、=
エ　m=2, n=1なので、≠

「①→②→③→⑤→②→③→④→②→⑥」の順に実行するので、2回目の分岐②の次は分岐③です。分岐③に行くのは≠の時なので、この時点で答えはエになります。答えは分かりましたが、最後まで見てみましょう。

分岐③：mとnの大小比較
エ　m=2, n=1なので、>

処理④：m ← (m-n)
エ　m=2, n=1なので、m=1になる

分岐②：mとnが同値かどうか
エ　m=1, n=1なので、=

出力⑥：mの値を印字

正解は”エ”

解説しやすいようにそれぞれの処理に名前を付けておきます。

【アルゴリズム問題の鉄則①：具体的な数字を使う】
今回の問題では具体的な数字が与えられていますね。
A=876
B=204

【アルゴリズム問題の鉄則②：1Stepずつ丁寧に見る】
処理①：L ← A、S ← B
・L=876
・S=204

分岐④：LとSの比較(1回目)
L=876、S=204なので「>」

処理②：L ← (L-S)
L=876、S=204なので、処理②の後、L=672、S=204になります。

ここから先は下の表のようになります。

比較(分岐④)の数は11回なので、答えはエになります。

正解は”ア”

解説しやすいようにそれぞれの処理に名前を付けておきます。

【アルゴリズム問題の鉄則①：具体的な数字を使う】
乗算についての問題なので、具体的な掛け算を使いましょう。3×5=15で考えてみましょうか。
・乗数(掛ける数)=5 [2進数：0000 0000 0000 0101]
・被乗数(掛けられる数)=3 [2進数：0000 0000 0000 0011]
・答え=15 [2進数：0000 0000 0000 1111]
※乗数、被乗数は16ビット、XとYとZは32ビットと長いので0が続く所は0~0と表記します。

【アルゴリズム問題の鉄則②：1Stepずつ丁寧に見る】
処理①：各変数に数字を代入する
X=0000 0000 0000 0011, Y=0000 0000 0000 0101, Z=0, i=1

●i=1
分岐②：Yの〇ビットと1を比較する
アとイ：Yの0ビットは1なので「=」（処理③へ）
ウとエ：Yの15ビットは0なので「≠」（処理④へ）

処理③：Z ← (Z+X)
アとイ：Z=0000 0000 0000 0011

処理④：XとYのシフト移動
ア：X=0000 0000 0000 0110, Y=0000 0000 0000 0010
イ：X=0000 0000 0000 0001, Y=0000 0000 0000 1010
ウ：X=0000 0000 0000 0110, Y=0000 0000 0000 0010
エ：X=0000 0000 0000 0001, Y=0000 0000 0000 1010

処理⑤：i ← (i+1)なので、i=2になる
分岐⑥：i≠16なので、処理②へ

●i=2
分岐②：Yの〇ビットと1を比較する
アとイ：Yの0ビットは0なので「≠」（処理④へ）
ウとエ：Yの15ビットは0なので「≠」（処理④へ）
この時点でイのYは、Y=0000 0000 0000 1010であり、
ここからいくら左に0ビットシフトしてもYの第0ビット=1になることはありません。つまり、イはこの先、処理③にいくことは無いので、最終的に出力されるZはこの時点でのZになります。

この時点での、イのZ=0000 0000 0000 0011

処理④：XとYのシフト移動
ア：X=0000 0000 0000 1100, Y=0000 0000 0000 0001
イ：X=0000 0000 0000 0000, Y=0000 0000 0001 0100
ウ：X=0000 0000 0000 1100, Y=0000 0000 0000 0001
エ：X=0000 0000 0000 0000, Y=0000 0000 0001 0100

この時点でエのXは、X=0000 0000 0000 0000であり、
ここからいくら右に0ビットシフトしてもX=0000 0000 0000 0000から
変わりません。つまり、エがこの先、処理③：Z ← (Z+X)に進んだとしても
X=0なので、Zの値は変わりません。なので、最終的に出力されるZはこの時点でのZになります。

この時点での、エのZ=0000 0000 0000 0000

処理⑤：i ← (i+1)なので、i=3になる
分岐⑥：i≠16なので、処理②へ

●i=3
分岐②：Yの〇ビットと1を比較する
ア：Yの0ビットは1なので「=」（処理③へ）
イ：Yの0ビットは0なので「≠」（処理④へ）
ウとエ：Yの15ビットは0なので「≠」（処理④へ）

処理③：Z ← (Z+X)
ア：Z=0000 0000 0000 1111（i=1の時のZとXの足し算結果）

処理④：XとYのシフト移動
ア：X=0000 0000 0001 1000, Y=0000 0000 0000 0000
イ：X=0000 0000 0000 0000, Y=0000 0000 0010 1000
ウ：X=0000 0000 0001 1000, Y=0000 0000 0000 0000
エ：X=0000 0000 0000 0000, Y=0000 0000 0010 1000

処理⑤：i ← (i+1)なので、i=4になる
分岐⑥：i≠16なので、処理②へ

●i=4
分岐②：Yの〇ビットと1を比較する
アとイ：Yの0ビットは0なので「≠」（処理④へ）
ウとエ：Yの15ビットは0なので「≠」（処理④へ）
※この時点でアとウのYは、Y=0000 0000 0000 0000であり、
ここからいくら右に0ビットシフトしてもY=0000 0000 0000 0000から
変わりません。つまり、アとウがこの先、処理③に行くことは無いので、
最終的に出力されるZはこの時点でのZになります。

この時点での、アのZ=0000 0000 0000 1111
この時点での、ウのZ=0000 0000 0000 0000

ここでア～エで出力されるZの値が全て判明しました。
ア：Z=0000 0000 0000 1111
イ：Z=0000 0000 0000 0011
ウ：Z=0000 0000 0000 0000
エ：Z=0000 0000 0000 0000

3×5=15になるはずで、15は2進数で0000 0000 0000 1111です。
これと一致するのはアなのでアが正解です。