Casl汇编语言辅导
2008-04-28 09:33:27 来源:WEB开发网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"
更多精彩
赞助商链接