哈密顿回路汇编语言实现（有小bug）

琳妈發表於 2019-10-20 00:28:00

哈密顿回路汇编语言实现（有小bug）

<div class="cnblogs_code">
<pre>忠告：本代码是有bug的，有一些平行边，单点之类的情况好像没有考虑到，C++代码以及汇编代码只是给大家一个对于递归汇编程序直观的印象，并不是std，且本文的汇编实现 十分不好，是笔者年轻时写的一坨东西。关于更成熟的汇编语言实现递归，请参考笔者P2的那篇文章中的全排列以及汉诺塔部分。 C++实现 #include <iostream>
#include <cstdio>
#include <bits/stdc++.h>
/*邻接矩阵存储图，从起点开始，直接深搜，打标记，一直搜到不可以再搜，看看是不是走了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<m;i++){
 scanf("%d %d",&u,&v);
 graph=graph=1;
}
sign[1]=1;
DFS(1,1);
printf("%d\n",ans);
return 0;
}
void DFS(int now,int step){
if(step==n){
 if(graph[1]){
 ans=1;
 }
 return;
}
for(int i=1;i<=n;i++){
 if(!sign && i!=now && graph){
 sign=1;
 DFS (i,step+1);
 sign=0;
 }
}
return;
}</pre>
</div>
<div class="cnblogs_code">
<pre>汇编实现：（有小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=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]
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
getindex($t3,$a0,$t0) #t3 is
lw $t3,0($t3) #t3 is graph
beq $t2,1,else #if sign==1,return
beq $t0,$a0,else #if i==now,return
beq $t3,0,else #if graph==0,return
sw $t7,0($t1) #sign=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=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</pre>
</div>
 
用汇编语言写递归程序的经验教训：
1.值的进栈与出栈：这个一定要注意，每次调用其他过程的时候，都要想想是不是要把退路保存下来，把原来的变量保存下来，有些甚至不止保存一次，有些甚至会因为分支而要在各个分支中进栈出栈。递归的还得多练，这次居然写了六个小时还被卡了一个点，由此可见我P2大概率会被干掉。
2.判断条件的书写：很多时候用相等判断beq并不够（因为自己写的程序太混乱，值会超过预期），我们需要能判断大于等于，小于等于，严格小，严格大的指令，至于到底使用哪种，一定要在写代码的时候想好。循环退出的条件一般写在循环的最前面。最好每个条件判断后面都写上清晰的注释。
3.别怕。汇编程序看着长，实际上重复的部分有很多是进栈出栈，以后写的时候不能再抓狂到砸东西了！ 
来源：https://www.cnblogs.com/BUAA-Wander/p/11706452.html

頁: [1]

琼殿技术论坛's Archiver

哈密顿回路汇编语言实现（有小bug）