MIPS Assembly - Попытка написать рекурсивную программу для вычисления nCr (Combination)

Question

Я пытаюсь создать программу сборки mips, чтобы вычислить nCr рекурсивно.

Я написал всю программу, включая драйвер, но не работает правильно. Все мои входы и выходы работают, но мой рекурсивный алгоритм возвращает сумасшедшие цифры. Например, Ncr == 268501120 вместо 10.

Обновленный код: http://pastebin.com/52ueQu99

Вот только отрывок из моего алгоритма:

nCk: 
sub $sp, $sp, 16 #allocate the needed space in stack. 
sw $ra, 0($sp) #save return address in first position 
sw $t3, 4($sp) #save n in the stack 
sw $t4, 8($sp) #save k in the stack 

sub $t3, $t3, 1 #Subtract one from n 
sub $t4, $t4, 1 #Subtract one from k 

jal checkBounds #Check for end of recursion. 
sw $v0, 12($sp) #copy returned 1 or 0 into stack. 

lw $t3, 4($sp) #Load original n back into t3. 
lw $t4, 8($sp) #Load original k back into t4. 

sub $t3, $t3, 1 #Subtract one from n again. (n-1 step of recursive algorithm) 
jal checkBounds #Check for end of recursion with n 1 number lower. 

lw $t2, 12($sp) #Load the value held in the previously returned v0. 
add $v0, $v0, $t2 #Add old returned value to new returned value. 

lw $ra, 0($sp) #Load the original return address. 
addi $sp, $sp, 16 #Add 16 more bytes to the stack. 
jr $ra 


checkBounds: #Check if program should still recurse 
beq $t3, $t4, return1 #If n==k 
beq $t4, $0, return1 #if k==0 
li $v0, 0 #If (j!=k || k!=0){ return 0}; 
jal nCk 
jr $ra 


return1: #Returns 1 
li $v0, 1 
jr $ra 

Answer 1

Я позаботился о том, чтобы немного переработать ваш код и пропустить часть проверки ошибок, чтобы показать вам наиболее важные части. По сути, я выполнил итеративную процедуру factorial, которая не выполняет проверку ошибок на входном значении. Затем в основной программе я получаю входные данные от пользователя, вычисляю факториалы и применяю формулу. Надеюсь, это поможет.

.data 
    enterN: .asciiz "Please enter the n value: \n" 
    enterK: .asciiz "Please enter the k value: \n" 
    output: .asciiz "Result is: " 
.text 

j main 

factorial: 
    # iterative factorial procedure 
    # $a0 - number, no error checking is performed on input 
    # $v0 - factorial of the number 
    addi $sp, $sp, -4 
    sw $ra, 0($sp) 

    li $v0, 1 
    li $s0, 1 
factorial_begin: 
    beq $s0, $a0, factorial_end # n == 1? 
    mul $v0, $v0, $a0 # $v0 = $v0 * n 
    subi $a0, $a0, 1 # n = n - 1 
    j factorial_begin 
factorial_end: 
    lw $ra, 0($sp) 
    addi $sp, $sp, 4 
    jr $ra 


main: 
    # compute cobination (n choose k) = n!/k!(n-k)! 
    # ---------------------------------------------- 
    la $a0, enterN #Ask for the first param, n. 
    li $v0, 4 #String syscall 
    syscall #Prints out string. 
    li $v0, 5 
    syscall #Places inputted value in v0. 
    la $t0, ($v0) # $t0 = n 

    # computer factorial of n 
    move $a0, $t0 
    jal factorial 
    move $t1, $v0 # $t1 = n! 

    la $a0, enterK #Asks for the second param, k. 
    li $v0, 4 #String syscall 
    syscall #Prints out string 
    li $v0, 5 
    syscall #Places inputted value in v0. 
    la $t2, ($v0) # $t2 = k 

    # computer factorial of k 
    move $a0, $t2 
    jal factorial 
    move $t3, $v0 # $t3 = k! 

    sub $a0, $t0, $t2 # $a0 = n - k 
    jal factorial 
    move $t4, $v0 # $t4 = (n-k)! 

    mul $t3, $t3, $t4 # $t3 = k! * (n-k)! 
    div $t1, $t1, $t3 # $t1 = n!/(k! * (n-k)!) 

    # print out the result 
    la $a0, output 
    li $v0, 4 
    syscall 

    move $a0, $t1 
    li $v0, 1 
    syscall 

Answer 2

Этот код имеет так много ошибок, что трудно перечислить. Для начала у него есть синтаксические ошибки и отсутствующие метки, поэтому он даже не собирается. Затем входные значения никогда не записываются в $t3 и $t4, потому что вы получили ордер операнда в обратном порядке. Кроме того, ваш CheckBounds использует JAL без сохранения $ra. То же самое касается main. Что касается печати, результат находится в $v0, поэтому вам нужно сохранить это до того, как вы clobber $v0, распечатав предыдущий материал.

Фиксация всех, кажется, заставляет работать.

Вы должны научиться использовать отладчик/симулятор, чтобы исправить ошибки. Например, определить, что регистры не имеют ожидаемых значений, легко.