Morris' Blog

2013-03-26 09:26:57Morris

[MIPS] 巴斯卡三角形 pascal\'s triangle

留言 1 收藏 0 推薦 0

題目內容：印出巴斯卡三角形
使用遞迴找出巴斯卡三角形中第(n,k)個值填入特定位置。

改寫的 C/C++ 代碼如下。

#include <stdio.h>
int pascal(int n, int k) {
    if(k == 0 || n == k)
        return 1;
    return pascal(n-1, k-1) + pascal(n-1, k);
}
int main() {
    int i, j, n = 16;
    puts("Row Column");
    for(i = 0; i <= n; i++) {
        printf("%d", i+1);
        if(i+1 >= 10)   goto pspace;
        printf(" ");
        pspace:
            printf("   ");
        for(j = 0; j <= i; j++)
            printf("%d ", pascal(i, j));
        puts("");
    }
    return 0;
}

這次有幾個挑戰的地方。
1. 使用遞迴求解
2. 輸入格式要對齊，先採定不會有三位數的情況，
用遞迴解也不太可能會問 100 階，因為跑的次數等價於其值，用 tab 字符對齊也是可以，
不過相對的間隔可能太大？

#print pascall triangle using recursion
#int pascal(int n, int k)
#   if(k == 0 || n == k)   return 1;
#   return pascal(n-1, k-1) + pascal(n-1, k);
        .text
        .globl main
main:   #start process
       addi    $sp, $sp, -12
       sw      $ra, 0($sp)
       sw      $s0, 4($sp)
       sw      $s1, 8($sp)

       li      $v0, 4         # printString("Number of levels:")
       la      $a0, inmsg
       syscall
       li      $v0, 5         # readInt
       syscall                # return $v0
       move    $t0, $v0       # $t0 = input levels

       li      $v0, 4         # printString("Row Column")
       la      $a0, outmsg
       syscall

       li      $s0, 0         # $s0 = i = 0
for1tst:
       slt     $t1, $s0, $t0 # $t1 = ($s0 < $t0);while(i < n)
       beq     $t1, $zero, exit1
       #process print("%-5d", i+1);
       li      $v0, 1
       addi    $t2, $s0, 1    # $t2 = i+1
       move    $a0, $t2
       syscall
       li      $t3, 10
       slt     $t1, $t2, $t3
       beq     $t1, $zero, pspace# $t2 < 10 print 4 space
       li      $v0, 4         # printString(" ")
       la      $a0, space
       syscall
pspace: #print 3 space
       li      $v0, 4         # printString("   ")
       la      $a0, space3
       syscall
       li      $s1, 0         # $s1 = j = 0
for2tst:
       move    $a0, $s0
       move    $a1, $s1
       jal     pascal         # call pascal($a0, $a1)
       move    $s2, $v0       # move result to $s2

       li      $v0, 1         # printInt(&a0)
       move    $a0, $s2
       syscall
       li      $v0, 4         # printString(" ")
       la      $a0, space
       syscall

       addi    $s1, $s1, 1    # j++

       slt     $t1, $s0, $s1 # $t1 = (i < j)
       beq     $t1, $zero, for2tst # j <= i goto for2tst
       #for2tst end

       li      $v0, 4         # printString("\n")
       la      $a0, nl
       syscall

       addi    $s0, $s0, 1   # i++
       j       for1tst
       #for1tst end
exit1:
       lw      $s1, 8($sp)
       lw      $s0, 4($sp)
       lw      $ra, 0($sp)
       addi    $sp, $sp, 12
       jr      $ra
       #end process
#function pascal(int n, int k)=>($a0, $a1)
pascal: addi    $sp, $sp, -16
       sw      $ra, 0($sp)
       sw      $s0, 4($sp)
       sw      $t0, 8($sp)
       sw      $t1, 12($sp)

       li      $v0, 1           # default result
       beq     $a1, $zero, pexit
       beq     $a0, $a1, pexit # (k == 0 || n == k) return 1

       move    $t0, $a0         # copy argv in function
       move    $t1, $a1         # copy argv in function
       addi    $a0, $t0, -1
       addi    $a1, $t1, -1
       jal     pascal
       move    $s0, $v0         # $s0 = C(n-1, k-1)

       addi    $a0, $t0, -1
       move    $a1, $t1
       jal     pascal
       add     $v0, $s0, $v0    # $v0 = $s0 + C(n-1, k)
pexit:
       lw      $t1, 12($sp)
       lw      $t0, 8($sp)
       lw      $s0, 4($sp)
       lw      $ra, 0($sp)
       addi    $sp, $sp, 16
       jr      $ra
#function pascal end
       .data
inmsg: .asciiz "Number of levels:"
outmsg: .asciiz "Row Column\n"
nl:     .asciiz "\n"
space: .asciiz " "
space3: .asciiz "   "

上一篇：[MIPS] 泡泡排序 Bubble Sort

下一篇：[組合語言] File Ouput 練習