汇编语言辗转相除法求最大公约数

里克贝斯

发布于 2021-05-21 15:31:09

1.7K1

发布于 2021-05-21 15:31:09

辗转相除法，又名欧几里德算法（Euclidean algorithm），是求最大公约数的一种方法。它的具体做法是：用较小数除较大数，再用出现的余数（第一余数）去除除数，再用出现的余数（第二余数）去除第一余数，如此反复，直到最后余数是0为止。如果是求两个数的最大公约数，那么最后的除数就是这两个数的最大公约数。

汇编中的主要子程序

①主程序模块
②显示模块，调用DOS命令显示字符串，注意显示字符时要先将数值类型的数转化为字符类型
③辗转相除模块

代码（包括详细注释）

实验环境为MASM集成开发环境，win10DOSBOX

Assembly (x86)

DATA SEGMENT
X DW ?
Y DW ?
Z DW ?
DATA ENDS
CODE SEGMENT
ASSUME CS:CODE, DS:DATA
START:

CALL SHURU
MOV X, BX
CALL SHURU
MOV Y, BX
CALL GONGYUESHU
MOV BX, Z
CALL XIANSHI
CALL GONGBEISHU
JMP  OUT1

SHURU:     ; 输入数字到BX
MOV BX, 0
S1: 
MOV AH, 1   
INT 21H 
CMP AL, 0DH ; 输入是回车是结束
JZ  EXIT
AND AX, 000FH   
XCHG AX, BX   
MOV CX, 10   
MUL CX       ;之前输入的数乘以10 加上新输得数..比如123先是 0*10+1 ->1*10+2 ->12*10+3
ADD BX, AX  
JMP S1
EXIT:         ;输入了回车 退出
MOV DL, 0AH  ;换行
MOV AH, 2
INT 21H
RET


XIANSHI:        ; 显示BX当中的数
MOV DL, 0AH  ;换行
MOV AH, 2
INT 21H
MOV AX, BX        
MOV BX, 10
MOV CX, 0
LET1:        ;将要显示的数处以10 把余数入栈
MOV DX, 0     
INC CX   
IDIV BX
PUSH DX
CMP AX, 0    ;余数为0时结束
JNZ LET1
LET2:        
POP AX       ;将余数弹入 AX
ADD AX, 3030H ;余数调整为ASC码
MOV DL, AL     ;显示
MOV AH, 2
INT 21H
LOOP LET2
RET



GONGYUESHU: ;求 X 和 Y 的最大公约数..BX是除数
MOV BX, 1
SS1:
MOV DX, 0
MOV AX, X
DIV BX
CMP DX, 0
JNZ SS2    ; 如果BX不能被X整除 BX不是公约数 跳到SS2
MOV DX, 0
MOV AX, Y
DIV BX
CMP DX, 0
JNZ SS2    ; 如果BX不能被Y整除 BX不是公约数 跳到SS2
MOV Z, BX   ;如果既能被X整除又能被Y整除的值放到Z里面 
SS2:      ; BX加到等于被除数的时候跳出 ..否则除数加1..判断BX+1是不用公约数..
CMP BX, X  
INC BX    
JNZ SS1  
RET

GONGBEISHU: ;公倍数就是X乘Y在除以最大公约数...
MOV AX, X
MUL Y
DIV Z
MOV BX, AX
CALL XIANSHI

RET


OUT1:  
MOV AH, 4CH 
INT 21H
CODE ENDS
END START

效果：