Casl汇编语言辅导

核心提示：6、1996年试题四[程序说明]子程序 OFFSET 用二分法，查找无符号整数 M 在一个长度为 N 的有序（升序）无符号整数列表NTABLE 中的位置，Casl汇编语言辅导(11)，程序中标号为 LOW 和 UP 的两个存储字分别用作存放查找空间的上下限，进入子程序时，若表中找不到 M，GR0 中要放 0，在 GR1

6、1996年试题四

[程序说明]

子程序 OFFSET 用二分法，查找无符号整数 M 在一个长度为 N 的有序（升序）无符号整数列表NTABLE 中的位置。程序中标号为 LOW 和 UP 的两个存储字分别用作存放查找空间的上下限。

进入子程序时，在 GR1 中中给出存放子程序所需参数的起始地址。参数的存放次序如下图：

(GR1)+0	M
1	N
2	NTABLE的首址

START	1
OFFSET	PUSH	0，GR2	2
PUSH	0，GR3	3
LD	GR0，0，GR1	4
LEA	GR2，0	5
ST	GR2，LOW	6
___(1)___	7
___(2)___	8
ST	GR2，UP	9
LOOP	ADD	GR2，LOW	10
SRL	GR2，1	11
LEA	GR3，0，GR2	12
___(3)___	13
___(4)___	14
JZE	FOUND	15
JPZ	INCLOW	16
LEA	GR2，-1，GR2	；M<NTABLE（K）	17
ST	GR2，UP	18
JMP	CMPLU	19
INCLOW	LEA	GR2，1，GR2	；M> NTABLE(K)	20
ST	GR2，LOW	；K+1→LOW	21
___(5)___	22
CMPLU	CPL	GR2，LOW	23
___(6)___	24
___(7)___	25
FOUND	LEA	GR0，1，GR2	26
POP	GR3	27
POP	GR2	28
RET	29
LOW	DS	1	30
UP	DS	1	31
END	32

[解] 二分法查找的基本思想是对任意一段查找空间 [LOW，UP]（有序）中的的表元，试探位置 K=(LOW+UP)/2上的成分 NTABLE(K) 与 M 进行比较，其可能结果有三种：

1）NTABLE（K）= M，找到，结束查找。

2）NTABLE（K）< M，下一查找空间为[K+1，UP]。

3）NTABLE（K）> M，下一查找空间为[LOW，K-1]。

初始查找空间为 LOW=0，UP=N-1。

程序中空格___(1)___和___(2)___前面的两条指令是将查找空间的上限 LOW 中 0，二在它之后的指令是将 GR2 中的值存于查找空间的下限 UP 中。因此这两个空格是把下限初值 N-1 送给 GR2。由于进入子程序时，N 存放在（GR1）+1 中，所以这两条指令为：

LD GR2，1，GR1

LEA GR2，-1，GR2

从标号 LOOP 开始的循环是求试探位置 K，根据 NTABLE(K) 和 M 比较结果，分别处理三种不同的情况，直至查到或查找空间为 0 。

考察空格___(3)___和___(4)___前面的指令，可得 K 在 GR2 和 GR3 中，在执行___(3)___和___(4)___两条指令后，有三种转向，因此这两条指令是将 GR0 中的 M 与 NTABLE(K)比较。而从程序说明中以知，NTABLE(0) 地址在 GR1+2。故 NTABLE(K) 的地址应为 GR2 或 GR3 与（GR1+2）相加（绝对地址）。但GR2 在后面要作相对地址　K用，所以只能是 GR3 与（GR1+2）相加。所以空格___(3)___和___(4)___为：

ADD GR3，2，GR1

CPL GR0，0，GR3

执行上述两条指令后，若不相等则要调整查找空间，在继续查找前，先应判断查找空间是否为 0，在程序中是用标号为 CMPLU 的指令实现，显然 GR2 内应是查找空间的下限 UP。故___(5)___的答案为:

LD GR2，UP

当查找空间不为0时（UP>LOW），应继续查找，所以___(6)___的解答为:

JPZ LOOP

子程序返回时,GR0 中存放查找结果，在表中找到M时，GR0 中存放M在表中的位置序数，在程序中用 "FOUND LEA GR0，1，GR2" 实现（这里 GR2 中是试探位置，与位置序数差 1 ）。

若表中找不到 M，GR0 中要放 0，所以___(7)___处应填 "LD GR2，-1"