WEB开发网
开发学院软件开发汇编语言 Casl汇编语言辅导 阅读

Casl汇编语言辅导

 2008-04-28 09:33:27 来源:WEB开发网   
核心提示: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"

上一页  6 7 8 9 10 11 

Tags:Casl 汇编语言 辅导

编辑录入:爽爽 [复制链接] [打 印]
赞助商链接