MIPS递归斐波那契数列 [英] MIPS Recursive Fibonacci Sequence
本文介绍了MIPS递归斐波那契数列的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!
问题描述
我在MIPS中递归处理堆栈时遇到了麻烦.我明白了,但是我的程序没有按照我的意思反应.
I'm having trouble dealing with stacks recursively in MIPS. I get the concept, but my program isn't reacting as I mean it to.
我的目标是将用户输入作为n并在n处打印斐波那契数.到目前为止,我的情况在下面.
My goal is to take user input as n and print the Fibonacci number at n. What I have so far is below.
(我很确定问题出在fib函数中数字的实际计算中.)感谢您的帮助! :)
(I'm fairly certain the problem is in the actual calculation of the number in the fib function.) Thanks for any help! :)
.text
main:
# Prompt user to input non-negative number
la $a0,prompt
li $v0,4
syscall
li $v0,5
syscall
move $t2,$v0
# Call function to get fibonnacci #n
move $a0,$t2
move $v0,$t2
jal fib
move $t3,$v0
# Output message and n
la $a0,result
li $v0,4
syscall
move $a0,$t2
li $v0,1
syscall
la $a0,result2
li $v0,4
syscall
move $a0,$t3
li $v0,1
syscall
la $a0,endl
li $v0,4
syscall
# End program
li $v0,10
syscall
fib:
# Compute and return fibonacci number
beqz $a0,zero
beq $a0,1,one
sub $sp,$sp,4
sw $ra,0($sp)
sub $a0,$a0,1
jal fib
lw $ra,0($sp)
add $sp,$sp,4
sub $t8,$v0,2 # n - 2
sub $t9,$v0,1 # n - 1
add $v0,$t8,$t9 # add n-2,n-1
jr $ra # decrement/next in stack
zero:
li $v0,0
jr $ra
one:
li $v0,1
jr $ra
.data
prompt: .asciiz "Enter a non-negative number: "
result: .asciiz "F_"
result2: .asciiz " = "
endl: .asciiz "\n"
示例运行:
Enter a non-negative number: 5
F_5 = -29
Enter a non-negative number: 6
F_6 = -61
正确运行:
Enter a non-negative number: 5
F_5 = 5
Enter a non-negative number: 6
F_6 = 8
推荐答案
以下是正确的代码:
.text
main:
# Prompt user to input non-negative number
la $a0,prompt
li $v0,4
syscall
li $v0,5 #Read the number(n)
syscall
move $t2,$v0 # n to $t2
# Call function to get fibonnacci #n
move $a0,$t2
move $v0,$t2
jal fib #call fib (n)
move $t3,$v0 #result is in $t3
# Output message and n
la $a0,result #Print F_
li $v0,4
syscall
move $a0,$t2 #Print n
li $v0,1
syscall
la $a0,result2 #Print =
li $v0,4
syscall
move $a0,$t3 #Print the answer
li $v0,1
syscall
la $a0,endl #Print '\n'
li $v0,4
syscall
# End program
li $v0,10
syscall
fib:
# Compute and return fibonacci number
beqz $a0,zero #if n=0 return 0
beq $a0,1,one #if n=1 return 1
#Calling fib(n-1)
sub $sp,$sp,4 #storing return address on stack
sw $ra,0($sp)
sub $a0,$a0,1 #n-1
jal fib #fib(n-1)
add $a0,$a0,1
lw $ra,0($sp) #restoring return address from stack
add $sp,$sp,4
sub $sp,$sp,4 #Push return value to stack
sw $v0,0($sp)
#Calling fib(n-2)
sub $sp,$sp,4 #storing return address on stack
sw $ra,0($sp)
sub $a0,$a0,2 #n-2
jal fib #fib(n-2)
add $a0,$a0,2
lw $ra,0($sp) #restoring return address from stack
add $sp,$sp,4
#---------------
lw $s7,0($sp) #Pop return value from stack
add $sp,$sp,4
add $v0,$v0,$s7 # f(n - 2)+fib(n-1)
jr $ra # decrement/next in stack
zero:
li $v0,0
jr $ra
one:
li $v0,1
jr $ra
.data
prompt: .asciiz "This program calculates Fibonacci sequence with recursive functions.\nEnter a non-negative number: "
result: .asciiz "F_"
result2: .asciiz " = "
endl: .asciiz "\n"
希望有用
阿德尔·扎瑞(Adel Zare)
Adel Zare
adel.zare.63 [at] gmail [dot] com
adel.zare.63 [at] gmail [dot] com
这篇关于MIPS递归斐波那契数列的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!
查看全文