2013-03-26 09:26:57Morris
[MIPS] 巴斯卡三角形 pascal\'s triangle
題目內容：印出巴斯卡三角形
使用遞迴找出巴斯卡三角形中第(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 " "
使用遞迴找出巴斯卡三角形中第(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 " "
多謝你啊~Mo大~
你又再次拯救了我QAQ
巴斯卡我只會用JAVA寫~"~
C++我就學起來囉^^
順便學.......計組那讓我摸不著頭緒的程式碼~'"~