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

老司机。。

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

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

老司机。。

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

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

jackz007

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

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

xieglt

求任意位的 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