0

我目前正在学习汇编语言（Motorola 68K Assembler）课程。我有一个项目，我的任务是打印最大为 30 的斐波那契数的结果。例如，如果用户输入 4，结果应该是 3（因为它是前两个数字的总和）。但是，我的主程序（prog4.s）连续打印出0。问题与递归方法的逻辑有关吗？问题出在其他地方吗？这是我的递归方法代码（fib.s）

* fib.s
* long fib(int n) {
*     if(n==0) { 
*      return 0;
*     }
*     else if(n==1) {
*      return 1;
*     }
*     return fib(n-1) + fib(n-2);
* }

ORG $7000

fib:
    link      A6,#0
    movem.l   D1-D2,-(SP)
    move.w    8(A6),D1
    TST.w     D1
    BNE       next
    BRA       out

next:
    cmpi.w    #1,D1
    BNE       recurse
    add.w     #1,D0
    BRA       out

recurse:
    move.w    D1,D2
    subq.w    #1,D1
    move.w    D1,-(SP)
    JSR       fib
    move.w    D0,D1      * save copy of fib(n-1)

    adda.l    #2,SP

    subq.w    #2,D2
    move.w    D2,-(SP)
    JSR       fib
    add.w     D2,D1
    add.w     D1,D0        * return fib(n-1) + fib(n-2)

    adda.l    #2,SP

out:
    movem.l   (SP)+,D1-D2
    unlk      A6
    rts

    end

这是我调用 fib.s 的程序的代码

fib:   EQU   $7000
start: initIO
setEVT

lineout     title
lineout     prompt
linein      buffer
cvta2       buffer,D1

* Place parameter on the stack and move the stack pointer
move.w      D1,-(SP)

*Jump to the fib subroutine
JSR         fib

*Pop starting parameter off the stack 
adda.l      #2,SP

cvt2a       buffer,#6
stripp      buffer,#6
lea         buffer,A0
adda.l      D0,A0
clr.b       (A0)
lineout     answer

break

prompt:     dc.b 'Enter a number between 1 and 30: ',0
answer:     dc.b 'The Fibonacci number is: '
buffer:     ds.b  80
       end

需要注意的一点：fib.s 中注释掉的算法是我需要使用的算法。任何帮助/建议将不胜感激。

4

2 回答 2

4

你的程序几乎是正确的。
问题不在于它自身的递归逻辑，而在于您如何返回每次调用计算的值。
使用调试器进行几个跟踪会话将帮助您发现问题。

我先给你个提示。这些行

add.w     D1,D2      *fib(n-1) + fib(n-2)
add.w     D2,D0      *add fib(n-2)

不要做评论所说的。
D2持有n-2，D1持有fib(n-1)，D0所以fib(n-2)最终的结果是fib(n-1) + fib(n-2) + n - 2。只需将它们替换ADD.W D1, D0为 return fib(n-1) + fib(n-2)。

还有另外两个错误，但是在您如何返回其他两种情况（n = 0 和n = 1）的值方面。

我强烈建议您尝试使用 Easy68k 附带的 68k 模拟器来调试自己的fib(0)调用fib(1)。
一个重要的建议：D0在开始模拟之前设置一个随机值（例如：$55555555）并使用F7来跟踪执行。

如果你没能找到其他错误，这里就是

用于在n = 1 情况下返回 1 的指令ADD.W #1, D0取决于 的先前值D0。
应该是MOVE.W #1, D0。
如果n = 0 函数分支到out没有修改D0，它应该设置D0为零。
类似MOVE.W #0, D0或其他归零成语。

于 2016-12-07T21:53:45.357 回答
0

问题在于调用程序 prog4.s。您正确读取了该值，但是您将错误的寄存器传递到堆栈中。宏 linein 将二进制补码整数存储在 D0，而不是 D1。由于 D1 在您传入之前已包含零，因此每次都返回零。这是调用程序的正确代码应该是：

fib:    EQU             $7000
start:  initIO                  * Initialize (required for I/O)
        setEVT                  * Error handling routines
*       initF                   * For floating point macros only


lineout         title
lineout         prompt
linein          buffer
cvta2           buffer,D0


* Place parameters on the stack and move the stack pointer
move.w          D0,-(SP)


* Jump to the fib subroutine
JSR             fib


* Pop starting parameters off of the stack
adda.l          #2,SP


cvt2a           buffer,#6
stripp          buffer,#6
lea             buffer,A0
adda.l          D0,A0           * Sets A0 to the address of D0
clr.b           (A0)
lineout         answer


break                           * Terminate execution
*
*----------------------------------------------------------------------
*       Storage declarations


title:  dc.b    'Program #4, Christopher Moussa, cssc0702',0
prompt: dc.b    'Enter a number between 1 and 30: ',0
answer: dc.b    'The Fibonacci number is: '
buffer: ds.b    80
    end
于 2016-12-09T15:54:06.787 回答