東北大学 工学研究科 電気・情報系 2016年8月実施 専門科目 問題4 計算機1

标签：

• Tohoku-University
• Assembly-Language

Author

祭音Myyura (co-authored with GPT 5.6 SOL)

Description

日本語版

各番地に整数が格納されるメモリと，$1$ つの整数レジスタ $A$ を持つ計算機を考える。Fig. 4(a) の命令を用いて，以下の問に答えよ。

(1) Fig. 4(b) のプログラム（命令の列）を実行した後に，レジスタ $A$ に格納されている値は何か。

(2) メモリの $80$ 番地に格納されている整数 $m$ と，メモリの $81$ 番地に格納されている整数 $n$ との差 $m-n$ を計算し，$m-n\ge0$ ならば $m-n$ を，$m-n<0$ ならば $0$ をメモリの $82$ 番地に格納して停止するプログラムを書け。$82$ 番地以外のメモリの値を変更してはならない。

(3) Fig. 4(c) は，メモリの $80$ 番地に格納されている正の整数 $m$ を，メモリの $81$ 番地に格納されている正の整数 $n$ で割ったときの商をメモリの $82$ 番地に，剰余を $83$ 番地にそれぞれ格納して停止するプログラムである。Fig. 4(c) にある $\boxed{\mathrm w},\boxed{\mathrm x}$ に対する適切な整数，および $\boxed{\mathrm y},\boxed{\mathrm z}$ に対する適切な命令をそれぞれ答えよ。

Fig. 4(a)

命令	動作
SET i	$A$ に整数 $i$ を格納する。
LDR i	メモリの $i$ 番地に格納されている値を $A$ に格納する。
STR i	メモリの $i$ 番地に，$A$ の値を格納する。
SUB i	$A$ の値から，メモリの $i$ 番地に格納されている値を減算し，結果を $A$ に格納する。
INCR	$A$ の値に $1$ を足し，結果を $A$ に格納する。
BLTZ	$A$ の値が $0$ 未満ならば，次の命令をスキップする。
BLA i	先頭の命令から数えて $i$ 番目の命令にジャンプする（ただし先頭の命令を $1$ 番目と数える）。
HALT	プログラムの実行を停止する。

Fig. 4(b)

1: SET 10
2: STR 80
3: INCR
4: SUB 80
5: BLTZ
6: BLA 8
7: LDR 80
8: HALT

Fig. 4(c)

 1: SET 0
 2: STR 82
 3: LDR 80
 4: SUB 81
 5: BLTZ
 6: BLA [w]
 7: BLA [x]
 8: STR 80
 9: LDR 82
10: [y]
11: STR 82
12: BLA 3
13: [z]
14: STR 83
15: HALT

题目描述

计算机有一个整数寄存器 $A$ 和按地址存储整数的内存 $M$。指令语义如下：

指令	操作
SET i	$A\gets i$
LDR i	$A\gets M[i]$
STR i	$M[i]\gets A$
SUB i	$A\gets A-M[i]$
INCR	$A\gets A+1$
BLTZ	若 $A<0$，跳过紧接的一条指令
BLA i	跳到第 $i$ 条指令，从 $1$ 开始编号
HALT	停止

1. 下列程序结束时 $A$ 为多少？

1: SET 10
2: STR 80
3: INCR
4: SUB 80
5: BLTZ
6: BLA 8
7: LDR 80
8: HALT

2. 编程计算 $M[82]=\max\{M[80]-M[81],0\}$ 后停止，不能修改其他内存位置。
3. 下列程序把正整数 $M[80]$ 除以正整数 $M[81]$，商存到 $M[82]$、余数存到 $M[83]$。填写整数 $w,x$ 和指令 $y,z$。

 1: SET 0
 2: STR 82
 3: LDR 80
 4: SUB 81
 5: BLTZ
 6: BLA w
 7: BLA x
 8: STR 80
 9: LDR 82
10: y
11: STR 82
12: BLA 3
13: z
14: STR 83
15: HALT

Kai

(1)

前四步使 $A$ 依次为 $10,10,11,1$，且 $M[80]=10$。因 $A=1\ge0$，第 $5$ 条不跳过下一条，随后跳到第 $8$ 条停止，所以

$$\boxed{A=1.}$$

(2)

1: LDR 80
2: SUB 81
3: BLTZ
4: BLA 6
5: SET 0
6: STR 82
7: HALT

非负差值直接存储；负差值跳过第 $4$ 条，并先置零。仅 $M[82]$ 被修改。

(3)

$$\boxed{w=8,\qquad x=13,\qquad y=\mathrm{INCR},\qquad z=\mathrm{LDR\ 80}.}$$

试减结果非负时，跳到第 $8$ 条保存新余量，并把商加一；结果负时，跳到第 $13$ 条取回尚未试减的余量，作为余数。若原被除数为 $m$、除数为 $n$，每次循环保持

$$m=n\,M[82]+M[80],\qquad M[80]\ge0.$$

退出时 $M[80]<n$，因此所存商和余数满足整数除法定义。