汇编语言递归求解斐波那契数列第N位

老司机。。 · 发表于 2021-3-31 15:39:06

马上注册，结交更多好友，享用更多功能^_^

您需要登录才可以下载或查看，没有账号？立即注册

x

1.题目：求Fibonacci数FIB
2.要求：
a)程序接收由用户键入的范围在0～100（不包括0和100）之间的n值
b)根据给定的n值，计算Fibonacci数，其定义如下
FIB(1) = 1
FIB(2) = 1
FIB(n) = FIB(n-2) +FIB(n-1) (n>2)
c)程序输出FIB(n)的值
3.提示：程序可由三部分组成
a)输入部分：程序接收用户键入的十进制n值，转换为2进制后存入num单元中
b)用递归子程序fibp求出FIB(n)的值，结果存放在result单元中。
c)输出部分：把result的值转换为十进制后打印输出

自己不会写这个代码，在网上看到的一个，分析到一半到add65536就看不懂了，有木有大佬能给看一下这是啥意思不

，或者有哪位哥哥能写出来自己的也可以

datas segment
str1 db 'please input a number(1-100):n=','$'
str2 db 13,10,'fib(n)=','$'
wrongstr db 13,10,13,10,'a number between 1 and 100 please!',13,10,13,10,'$'
inputbuffer db 3,?,3 dup(?)
n dw ?
result1h dw 0
result1l dw 0
result2h dw 0
result2l dw 0
c10 dw 10
outputbuffer db 11 dup('0')
datas ends;--------------------定义好要输出的提示语以及出错提示，开辟好四个result单元

codes segment
assume cs:codes,ds:datas
start:
mov ax,datas
mov ds,ax
call input;------------------------------------------跳转到输入函数
call fib;--------------------------------------------跳转到求值函数
call output;-----------------------------------------跳转到输出函数
jmp quit;--------------------------------------------跳转到结束函数
input proc
      jmp t1;------------------------------------------t1为将数据段预存数据输出
      wrong:
         lea dx,wrongstr
      mov ah,9
      int 21h
      t1:
         lea dx,str1
         mov ah,9
         int 21h
         lea dx,inputbuffer
         mov ah,10
         int 21h
         mov ax,0
         mov cl,inputbuffer+1
         mov ch,0
         lea bx,inputbuffer+2
      t2:
         mul c10;-------------------------------------将第一个读入的数乘以10
         mov dl,[bx]
         cmp dl,'0';----------------------------------将输入的数和0比较，如果小于零，错误
         jb wrong
         cmp dl,'9';----------------------------------将输入的数和9比较，如果目标数字只是一位数，前面的乘以10就会错误
         ja wrong
         and dl,0fh;----------------------------------取dl的后四位
         add al,dl
         adc ah,0
         inc bx
         loop t2
         cmp ax,0032h;--------------------------------这里以50为界限，超过50的数其实已经到了32位数的极限了
         ja wrong
         cmp ax,1
         jb wrong
         mov n,ax;------------------------------------将输入的数存到n中
         ret
input endp
fib proc
      cmp n,1;-----------------------------------------首先检查n是否等于1，等于1直接跳转到l1
      jz l1
      cmp n,2;-----------------------------------------其次检查n是否等于2，等于2直接跳转到l2
      jz l2
      dec n;-------------------------------------------n减一，准备开始启动递归调用
      call fib;----------------------------------------递归调用fib函数
      mov ax,result2l
      mov dx,result2h
      mov cx,result1l
      add result2l,cx
      mov cx,result1h
      adc result2h,cx
      mov result1l,ax
      mov result1h,dx;---------------------------------循环置换加数
      jmp exit
      l1:
         mov result1l,1
         mov result2l,1
         jmp exit
      l2:
         mov result2l,1
         dec n
         call fib;------------------------------------减一再回到该函数
         exit:ret
fib endp
output proc
      mov ax,result2l
      lea si,outputbuffer
      mov cx,5
      r1:
         mov dx,0
         div c10
         inc si
         add [si],dl
         loop r1;-------------------------------------循环5次，将输出缓冲区的数存到内存中
      mov ax,result2h
      lea si,outputbuffer
      mov cx,5
      r2:
         mov dx,0
         div c10
         inc si
         push cx
         cmp dx,0
         je noadd;------------------------------------如果余数为0，说明这个数能被10整除，不是个位数
         mov cx,dx;-----------------------------------将分离出来的个位数存入cx，进行call add65536函数的循环
         addn:
            call add65536
            loop addn
         noadd:
            pop cx
         loop r2
         lea dx,str2
         mov ah,9
         int 21h
         lea si,outputbuffer
         mov bx,10
      r3:
         cmp byte ptr [si+bx],'0'
         ja print;------------------------------------如果大于0就将该数输出
         dec bx
         jmp r3
      print:
         mov dl,[si+bx]
         mov ah,2
         int 21h
         dec bx
         cmp bx,1
         jae print;-----------------------------------bx大于等于1就将[si+di]后的位置的数字输出，否则返回
         ret
output endp
add65536 proc
      add byte ptr [si],6
      mov dl,0
      cmp byte ptr [si],3ah
      jb a1
      sub byte ptr [si],10
      mov dl,1
      a1:
         add byte ptr [si+1],3
         add byte ptr [si+1],dl
         mov dl,0
         cmp byte ptr [si+1],3ah
         jb a2
         sub byte ptr [si+1],10
         mov dl,1
      a2:
         add byte ptr [si+2],5
         add byte ptr [si+2],dl
         mov dl,0
         cmp byte ptr [si+2],3ah
         jb a3
         sub byte ptr [si+2],10
         mov dl,1
      a3:
         add byte ptr [si+3],5
         add byte ptr [si+3],dl
         mov dl,0
         cmp byte ptr [si+3],3ah
         jb a4
         sub byte ptr [si+3],10
         mov dl,1
      a4:
         add byte ptr [si+4],6
         add byte ptr [si+4],dl
         mov dl,0
         cmp byte ptr [si+4],3ah
         jb a0
         sub byte ptr [si+4],10
         mov dl,1
      a5:
         add byte ptr [si+5],dl
         mov dl,0
         cmp byte ptr [si+5],3ah
         jb a0
         sub byte ptr [si+5],10
         mov dl,1
      a6:
         add byte ptr [si+6],dl
         mov dl,0
         cmp byte ptr [si+6],3ah
         jb a0
         sub byte ptr [si+6],10
         mov dl,1
      a7:
         add byte ptr [si+7],dl
         mov dl,0
         cmp byte ptr [si+7],3ah
         jb a0
         sub byte ptr [si+7],10
         mov dl,1
      a8:
         add byte ptr [si+8],dl
         mov dl,0
         cmp byte ptr [si+8],3ah
         jb a0
         sub byte ptr [si+8],10
         mov dl,1
      a9:
         add byte ptr [si+9],dl
      a0:
         ret
add65536 endp
quit:
      mov ah,4ch
      int 21h
codes ends
end start

jackz007 · 发表于 2021-3-31 16:54:46

data segment para public 'DATA'
db 400h dup(0)
data ends
stack segment para stack 'STACK'
db 800h dup(0)
stack ends
code segment para public 'CODE'
assume cs:code , ds:data
fib proc near
push bx
cmp ax,2
ja f1
mov ax,1
jmp f2
f1: dec ax
push ax
call fib
push ax
pop bx
pop ax
dec ax
call fib
add ax,bx
f2: pop bx
retn
fib endp
main proc far
mov ax,data
mov ds,ax
mov ax,10 ; 计算第 10 项的数值
call fib ; ax = 第 10 项的数值
xor ax,ax
int 16h
mov ax,4c00h
int 21h
main endp
code ends
end main

复制代码

老司机。。 · 发表于 2021-3-31 19:22:11

jackz007 发表于 2021-3-31 16:54

看着你的代码好短小精悍啊，但是这个好像只能算16位的，再往后变数变大就会溢出了

jackz007 · 发表于 2021-4-2 00:04:06

老司机。。发表于 2021-3-31 19:22
看着你的代码好短小精悍啊，但是这个好像只能算16位的，再往后变数变大就会溢出了

是啊，16 位、32 位、64 位都有溢出的时候，你能从根本上解决问题吗？

xieglt · 发表于 2021-4-22 16:03:25

求任意位的 fibonacii 数，如果位数不够，把 NUM_LEN 改大就可以了。
程序中的用的 40H（64个word)结果可以算到 64*4 = 256 位

assume cs:code,ds:data
data segment
NUM_LEN = 40H
_BASE = 10000
_Number1 DW NUM_LEN DUP(0)
_Number2 DW NUM_LEN DUP(0)
data ends
code segment
_start:
MOV AX,data
PUSH AX
POP DS
PUSH AX
POP ES
MOV AX,1000
PUSH AX
CALL _Fibonacii
PUSH AX
CALL _OutputNumber
MOV AX,4C00H
INT 21H
;[BP+4]----第几个 fibonacii 数
;[BP+2]----return address
;[BP+0]----old bp
_Fibonacii PROC
PUSH BP
MOV BP,SP
PUSH CX
PUSH SI
PUSH DI
PUSHF
PUSH WORD PTR [BP+4]
POP CX
LEA SI,_Number1
LEA DI,_Number2
XOR AX,AX
;第一个 Fibonacii 数置0
MOV WORD PTR DS:[SI],AX
INC AX
;第二个 Fibonacii 数置1
MOV WORD PTR ES:[DI],AX
DEC CX
MOV AX,SI
TEST CX,CX
JE @FB_1
DEC CX
MOV AX,DI
TEST CX,CX
JE @FB_1
@FB_2:
;前数 + 后数 =>前数
PUSH DI
PUSH SI
CALL _AddNumber
;交换前数后数的地址
XCHG DI,SI
LOOP @FB_2
MOV AX,DI
@FB_1:
POPF
POP DI
POP SI
POP CX
MOV SP,BP
POP BP
RET 2
_Fibonacii ENDP
;[BP+6]----dst number
;[BP+4]----src number
;[BP+2]----return address
;[BP+0]----old bp
_AddNumber PROC
PUSH BP
MOV BP,SP
PUSH BX
PUSH CX
PUSH DX
PUSH SI
PUSH DI
PUSHF
;取得加数地址 => DI
PUSH WORD PTR [BP+4]
POP DI
;取得被加数地址 => SI
PUSH WORD PTR [BP+6]
POP SI
MOV CX,NUM_LEN
MOV BX,_BASE
XOR DX,DX
@AN_1:
;取加数
LODSW
;加数 + 被加数
ADD AX,WORD PTR ES:[DI]
;加进位
ADD AX,DX
;计算是否进位
XOR DX,DX
DIV BX
XCHG AX,DX
;保存和
STOSW
;和为0了则结束循环
ADD AX,DX
TEST AX,AX
JZ @AN_3
LOOP @AN_1
;循环结束后加进位
ADD WORD PTR [DI],DX
@AN_3:
POPF
POP DI
POP SI
POP DX
POP CX
POP BX
MOV SP,BP
POP BP
RET 4
_AddNumber ENDP
_OutputNumber PROC
PUSH BP
MOV BP,SP
PUSH BX
PUSH CX
PUSH DX
PUSH SI
PUSH DI
PUSHF
PUSH WORD PTR [BP+4]
POP DI
MOV CX,NUM_LEN
SHL CX,1
ADD DI,CX
SHR CX,1
SUB DI,2
STD
XOR AX,AX
REPZ SCASW
MOV SI,DI
INC CX
ADD SI,2
@ON_1:
LODSW
PUSH AX
CALL _OutputWord
LOOP @ON_1
CLD
POPF
POP DI
POP SI
POP DX
POP CX
POP BX
MOV SP,BP
POP BP
RET 2
_OutputNumber ENDP
_OutputWord PROC
PUSH BP
MOV BP,SP
SUB SP,8
PUSH BX
PUSH CX
PUSH DX
PUSH SI
PUSH DS
PUSHF
PUSH SS
POP DS
MOV SI,BP
SUB SI,8
MOV CX,4
PUSH WORD PTR [BP+4]
POP AX
MOV BX,10
@OW_1:
XOR DX,DX
DIV BX
ADD DL,030H
MOV DS:[SI],DL
INC SI
LOOP @OW_1
MOV CX,4
@OW_2:
DEC SI
MOV AH,02H
MOV DL,DS:[SI]
INT 21H
LOOP @OW_2
POPF
POP DS
POP SI
POP DX
POP CX
POP BX
ADD SP,8
MOV SP,BP
POP BP
RET 2
_OutputWord ENDP
code ends
end _start

复制代码

账号		自动登录	找回密码
密码			立即注册