平成28年度 III-1

解説

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

スタックマシンの命令を、順にたどって(トレースして)、スタックの内容の変化を追う問題。

解き方

① スタックを左(底)→右(上)で書きながら追う。sub は「下−上」、cmp は2つ取り除いて比べ、等しくなければジャンプ
② L1: 5から1ずつ減らして積み、1になったら抜ける → [5,4,3,2,1]
L2: add → [5,4,3,3] → 3≠5で戻る → add → [5,4,6] → swap → [5,6,4] → 4≠5で戻る → add → [5,10] → swap → [10,5] → 5=5で抜ける
最後の add で 10+5=15
③ ④

正解が正しい理由

スタックの内容を、下から上の順に書く。push 5で[5]。L1のループ(dup、push 1、sub、dup、push 1、cmp L1)は、スタックの最上部の値を1ずつ減らしながら積み、cmpで、最上部と1を比較して、等しくなければL1に戻る。これを繰り返すと、スタックは[5,4,3,2,1]となり、cmpで、最上部が1と等しくなり、L2へ進む。L2のループ(add、swap、dup、push 5、cmp L2)では、まずadd:[5,4,3,3]、swap(同値で変化なし)、dup、push 5、cmpで3と5が異なるためL2へ。add:[5,4,6]、swap:[5,6,4]、dup、push 5、cmpで4と5が異なるためL2へ。add:[5,10]、swap:[10,5]、dup:[10,5,5]、push 5、cmpで5と5が等しく、ループを抜ける。スタックは[10,5]。最後のaddで15。したがって最上部の値は15で、④が正しい。

各選択肢について

• ① 8は、途中の値ではあるが、最終的な最上部の値ではない。
• ② 10は、最後のadd直前のスタックの下側の値で、最上部の値ではない。
• ③ 12は、この命令列のトレースでは、得られない。
• ④ 最後のaddで、10と5の和15が最上部に積まれる。これが正答。
• ⑤ 20は、この命令列のトレースでは、得られない。

覚えるべきポイント

スタックマシンのトレースでは、各命令ごとに、スタックの内容を書き出す。subは、最上部をa、その直下をbとして、b−aを積む(順序に注意)。cmpは、2つの値をpopして比較する。