ハミルトニアンループアセンブリ言語実装(小さなバグあり)
13763 ワード
C++
#include
#include
#include
/* ， ， ， ， ， n ， */
int graph[30][30];
int sign[30];
int n,m,ans=0;
void DFS(int now,int step);
int main() {
int u,v;
scanf("%d %d",&n,&m); // 1
for(int i=0;i){
scanf("%d %d",&u,&v);
graph[u][v]=graph[v][u]=1;
}
sign[1]=1;
DFS(1,1);
printf("%d
",ans);
return 0;
}
void DFS(int now,int step){
if(step==n){
if(graph[1][now]){
ans=1;
}
return;
}
for(int i=1;i<=n;i++){
if(!sign[i] && i!=now && graph[now][i]){
sign[i]=1;
DFS (i,step+1);
sign[i]=0;
}
}
return;
} ：（ bug， ， ）
.macro done
li $v0,10
syscall
.end_macro
#############################################################
.macro initial
li $t0,0
for_1:
beq $t0,$s0,for_1_end
sll $t1,$t0,2 #t1=t0*4(int is 4 byte)
add $t1,$t1,$s3
sw $0,0($t1) #sign[t1]=0
addi $t0,$t0,1 #t0=t0+1
j for_1
for_1_end:
.end_macro
#############################################################
.macro getindex(%ans,%i,%j)
mult %i,$t6 #i*10
mflo $t4 #t4=i*10
add %ans,$t4,%j #t4=i*10+j
sll %ans,%ans,2 #ans=ans*4
.end_macro
#############################################################
.data
matrix: .space 400
sign: .space 40
#########################################################
.text
main:
la $s2,matrix
la $s3,sign
li $t6,10 #tmp
li $t7,1 #tmp
li $s7,0 #s7 is answer
li $v0,5
syscall
move $s0,$v0 #s0 is n
li $v0,5
syscall
move $s1,$v0 #s1 is m
initial
li $t0,0 #t0 is i
for_create:
beq $t0,$s1,for_create_end #if i==m,stop add edge
li $v0,5
syscall
move $t1,$v0 #t1 is u
li $v0,5
syscall
move $t2,$v0 #t2 is v
getindex($t3,$t1,$t2) #get the address in matrix
add $t3,$t3,$s2 #get address in matrix,t3 is address
sw $t7,0($t3) #add edge (u,v)
getindex($t3,$t2,$t1)
add $t3,$t3,$s2
sw $t7,0($t3) #add edge (v,u)
addi $t0,$t0,1 #i++
j for_create
for_create_end:
sw $t7,4($s3) #sign[1]=1
li $a0,1 #a0 is now position
li $a1,1 #a1 is step
jal dfs #the return address is in $31
li $v0,1
li $a0,0
syscall
done
dfs:
sw $31,0($sp)
addi $sp,$sp,-4
blt $a1,$s0,dfs_else
getindex($t3,$t7,$a0)
add $t3,$t3,$s2 #t3 is address in matrix
lw $t4,0($t3) #t4=graph[1][now]
beq $t4,1,arrive_ans
addi $sp,$sp,4
lw $31,0($sp)
jr $31 #if we don't find the ans,return
#omit something…………
dfs_else:
jal dfs_work
addi $sp,$sp,4
lw $31,0($sp)
jr $31
then:
jr $31 #you have jumped to main succesfully
arrive_ans:
li $s7,1
li $a0,1
li $v0,1 #print answer
syscall
done
j then
dfs_work:
#then ,we should do something
li $t0,1 #t0 is i
sw $31,0($sp) #save return address
addi $sp,$sp,-4
for_dfs1:
bgt $t0,$s0,for_dfs1_end
bge $a1,$s0,for_dfs1_end
sw $a0,0($sp) #save now
addi $sp,$sp,-4
sw $a1,0($sp) #save step
addi $sp,$sp,-4 #all the info was saved sucessfully
sll $t1,$t0,2 #t1=t0*4
add $t1,$t1,$s3 #t1 is the address in array_sign
lw $t2,0($t1) #t2 is sign[i]
getindex($t3,$a0,$t0) #t3 is [now][i]
lw $t3,0($t3) #t3 is graph[now][i]
beq $t2,1,else #if sign[i]==1,return
beq $t0,$a0,else #if i==now,return
beq $t3,0,else #if graph[now][i]==0,return
sw $t7,0($t1) #sign[i]=1;
sw $t0,0($sp) #save tmpi in stack
addi $sp,$sp,-4
sw $t1,0($sp) #save the address in array_sign
addi $sp,$sp,-4
move $a0,$t0 #now=i
addi $a1,$a1,1 #step++
jal dfs #next recursion
addi $sp,$sp,4
lw $t1,0($sp) #fetch the address in array_sign
addi $sp,$sp,4
lw $t0,0($sp) #fetch i
sw $t7,0($t1) #sign[i]=0
addi $sp,$sp,4
lw $a1,0($sp)
addi $sp,$sp,4
lw $a0,0($sp) #fetch all the things
addi $t0,$t0,1 #i++
j for_dfs1
for_dfs1_end:
addi $sp,$sp,4
lw $31,0($sp) #fetch the leeway
jr $31
else:
addi $t0,$t0,1
addi $sp,$sp,4
lw $a1,0($sp)
addi $sp,$sp,4
lw $a0,0($sp) #fetch all the things
j for_dfs1アセンブリ言語で再帰プログラムを書く経験と教訓:
1.値のインスタックとアウトスタック:これは必ず注意して、他のプロセスを呼び出すたびに、退路を保存するかどうかを考えて、元の変数を保存して、一度だけ保存していないものもあれば、分岐のために各分岐の中でスタックをアウトにしなければならないものもあります.再帰的にはもっと練習しなければなりませんが、今回は6時間も書いたのに1ポイントも引っかかってしまったので、私のP 2はたぶんやられることになります.
2.判断条件の書き方:等しい判断でbeqが足りない場合が多い(自分で書いたプログラムがあまりにも混乱しているため、値が予想以上になる)と判断するには、等しい、小さい、厳格で小さい、厳格で大きい命令を判断する必要があります.どちらを使うかは、必ずコードを書くときに考えなければなりません.ループ終了の条件は一般的にループの一番前に書かれています.各条件判断の後にはっきりした注釈を書いたほうがいいです.
[原句]怖がらないで.アセンブリプログラムは長いのを見ていますが、実際に重複している部分はスタックに入ってスタックを出ていることが多いので、後で書くときは気が狂って物を壊すことはできません.