次の命令を持ったスタックマシンを想定する。
push x スタックにデータ x をプッシュする。
dup スタックの最上部のデータを複製してスタックにプッシュする。
swap スタックの最上部の2つのデータの位置を交換する。
add スタックから2つのデータをポップし、その和をスタックにプッシュする。
sub スタックから2つのデータをポップし、その差をスタックにプッシュする。
(スタック最上部2番目のデータから最上部のデータを引く。)
mul スタックから2つのデータをポップし、その積をスタックにプッシュする。
div スタックから2つのデータをポップし、その商をスタックにプッシュする。
(スタック最上部2番目のデータを最上部のデータで割る。)
このとき、(a - b)2 / (c + a - b) を計算した結果をスタック最上部に残す最も少ないプログラムの命令数はいくつか。
① 7 ② 8 ③ 9 ④ 10 ⑤ 11
④
「最も少ないプログラム」ということで、a - b が分母にも分子にもあることに着目する。
以下の順に命令すると命令数は10になる。
なお、スタックは後入れ先出し (LIFO = Last In First Out) であることにも留意する。
(1) push a ・・・スタックに a が入る。
(2) push b ・・・スタックの上から順に b, a が入る。
(3) sub ・・・スタックから b, aをポップし、a - b の値 (xとする) がスタックにが入る。
(4) dup ・・・データ x を複製し、スタックの上から順に x, x が入る。
(5) dup ・・・データ x を複製し、スタックの上から順に x, x, x が入る。
(6) mul ・・・スタックから x, xをポップし、x * xの値 (yとする) がスタックに入り、スタックの上から順に y, xが入る。( y = (a - b)2である。)
(7) swap ・・・スタックの位置が変わり、スタックの上から順に x, yが入る。
(8) push c ・・・スタックの上から順に c, x, y が入る。
(9) add ・・・スタックから c, xをポップし、c + x の値 (zとする) がスタックに入り、スタックの上から順に z, y が入る。(z = c + a - bである。)
(10) div ・・・スタックから z, yをポップし、 y / z の値がスタックに入る。
| Ⅲ－７ | 目次 | Ⅲ－９ |