【基本情報】午前試験のアルゴリズムの苦手意識を克服する！

【アルゴリズム問題の鉄則①：具体的な数字を使う】
今回は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のとき、処理①
・j=1のとき、処理①
・j=2のとき、処理①
：
：
・j=7のとき、処理①

●i=1のとき
・j=0のとき、処理①
・j=1のとき、処理①
・j=2のとき、処理①
：
：
・j=7のとき、処理①

●i=2のとき
・j=0のとき、処理①
・j=1のとき、処理①
・j=2のとき、処理①
：
：
・j=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です。
これと一致するのはアなのでアが正解です。