P2-汇编语言

豪哇呦 發表於 2019-10-26 23:17:00

通过阅读本文，您的收获可能有：理解递归程序的本质，知道如何用汇编语言去写dfs，知道P2考试重点要考察的内容。更优质的内容可以移步roife.github.io，roife yyds！
省流助手：过P2需要熟练掌握递归程序的汇编实现、数组（含二维数组）的操作、把C程序翻译成汇编，另外要会用断点调试 or 有优秀的静态调试能力，最好事先熟悉一下已经学过的数据结构和算法。
听说我押中了正考两题和后面的补考两题hhh
upd:19级新考了素数判断，约瑟夫环，快排，可见程设课难度的题都有可能放P2考。另外似乎无脑压栈会导致TLE了，所以压栈的时候要思考一下，哪些是必须压栈的，哪些是可以变的，以及是否能提前算好栈大小，而不是用一个格子就减掉一个格子的位置。
upd: 20级同学的话可能会面对一个造数据的神，上面提到的问题可能真的要仔细思考一下。B站搜索咕咕香，可以找到该神的汇编程序设计补充教程，他会在视频中演示如何用汇编打一棵平衡树等操作。
课下测试部分：
今天晚上才刚开始写作业，目前只写了前两个，感觉和P1课上的时候一样，代码写得慢。基本的对二维数组的操作和多重循环中的例行公事部分（修改计数器，条件判断）有时候会忘记。
矩阵乘法：
基本的二维数组操作，在做之前我特意比较了一下P2教程中的二维数组操作和预习教程中的二维数组操作，发现P2写的类似于使用do while型的循环，有一定的优势，比如do while省标签个数，代码量也相对于for循环少。出现的问题有：循环实现慢（老毛病），写错了一个换行向量的判断条件（比较对象写错了），还有多重循环有一处没有刷新计数变量。此处我用的do while型的循环写的，果然节省了标签和码量，以后的题可以再试试。
回文串：
一维数组操作，比较简单，但题目提示中关于syscall中8和12的区别还是需要注意的：12是单字符读入，类似于getchar()(?)，而8是一行读入，有点像fgets()，会把换行读进去，且需要预先设定到底最多读入多少个字符。几个判断函数需要好好熟悉一下，看看啥时候该用什么。一般for循环喜欢用beq，do while喜欢用bne
卷积运算：
弱化版的卷积运算，不需要填充，也不需要翻转，没有花里胡哨的操作，只要老老实实操作二维数组就行了。在下手之前一定要把地址计算和下标范围给解决了，只有数学上写的是对的，程序才有可能对。下面给出C++代码，注释部分是对于地址计算和下标的思考。
<div class="cnblogs_code">
<pre> 1 #include <bits/stdc++.h>
 2 int ans[10][10];
 3 int m1,n1,m2,n2;
 4 int core[10][10],matrix[10][10];
 5 void Convolution();
 6 void print();
 7 int main() {
 8 scanf("%d %d %d %d",&m1,&n1,&m2,&n2);
 9 for(int i=0;i<m1;i++){
10 for(int j=0;j<n1;j++){
11 scanf("%d",&matrix);
12 }
13 }
14 for(int i=0;i<m2;i++){
15 for(int j=0;j<n2;j++){
16 scanf("%d",&core);
17 }
18 }
19 Convolution();
20 print();
21 return 0;
22 }
23 //本题不需要翻转，也不需要填充
24 //下面用变量i,j控制卷积核的移动，k,l作为数据运算时的卷积核中元素行列标号
25 //分析可知:0<=i<=m1-m2 0<=j<=n1-n2
26 //分析可知:0<=k<m2 0<=l<n2
27 //计算规则:ans+=core*matrix
28 void Convolution(){
29 for(int i=0;i<=m1-m2;i++){
30 for(int j=0;j<=n1-n2;j++){
31 for(int k=0;k<m2;k++){
32 for(int l=0;l<n2;l++){
33 ans+=core*matrix;
34 }
35 }
36 }
37 }
38 }
39 void print(){
40 for(int i=0;i<=m1-m2;i++){
41 for(int j=0;j<=n1-n2;j++){
42 printf("%d ",ans);
43 }
44 printf("\n");
45 }
46 }</pre>
</div>
 
本题我处理不好的地方：虽然一遍就过样例了，但是编写过程中还是出了一些问题：首先是滥用a0寄存器。这不是我的本意，我真的是用完了t和s，然后想暂时借用一下a0，结果写到最后发现需要输出字符的时候要覆盖掉a0的值，这样我就白忙活了。情急之下，我每次打印字符之前都先把a0拷贝一份，打印完字符之后再拷贝回来,做到了代码改动最少，但是看起来却特别的傻。如果没有意识到这一点，不知道会错成什么样子。第二个问题是a与s打混了，就是因为滥用a0，所以敲着敲着发现有个应该是s0的地方被写成了a0，as在键盘相邻，被打错的可能行还是有的。最后一个问题是mflo打错了，打成了mulo，结果还真有一个mulo，功能大概是考虑溢出的乘法，这个错误也是写着写着扫了一眼发现的，太低级的失误了。
全排列：
典型递归程序，也是P2考试的重点。如果不清楚递归程序写法的，请先在OJ上重新完成全排列问题以及汉诺塔问题。如果不太懂得如何用汇编实现递归程序，请仔细研读下面的汉诺塔汇编代码。以及如果做了哈密顿回路那道题，会发现这个题相当于哈密顿的弱化版（此题没有操作二维数组，所以比较好写一点）。在有了哈密顿的经验之后，操作栈变得更加熟练了。这个题我最开始的确是写了标记数组标记，之后在回溯的时候再消去标记，结果写着写着发现居然只写了注释，没写相应的代码。。发现只有一个输出之后竟然用了十几分钟才发现这里错了。测试debug用n=2或者3就够了，数据大了是给自己添麻烦。推荐过了这个题之后再做做哈密顿那道题，会比较顺利。纠正一个自己之前的迷惑点：之前以为31号寄存器每进入一个新的标签，都会自动改变一下，其实这是不对的。只有jal能改动31号寄存器的值（当时就是纠结这个才会哈密顿写了6小时，不过最后弄明白就很好了）
另外感觉全排列比汉诺塔更适合在大一程设中当做例题讲，汉诺塔很容易把不明白函数传参的都搞晕了，而全排列只传递一个参数，不会卡在这里。不妨压一波P2课上测试考汉诺塔？可能不让输出路径只让输出方案数（推规律用通项公式水过去的统统问答时打死）课下有时间还是自己试试吧，竞赛+运动会完事儿了时间多的一匹，是补作业和肝计组的好时候了。去年好像还考了矩阵快速幂，也可以课下准备准备快速幂取模和矩阵快速幂，操作二维数组应该是比较常用且在考察范围内的知识点吧。
P2之前一定要看一遍preview里的教程，不能再在问答环节尴尬了。
01迷宫：
这个题是二维数组+dfs的题目，是我考场上不敢碰的题（一道一个半小时，不加debug）递归终止条件是到终点。递归深入的条件是：某个方向走完之后没越界，且是0。每次深入之前，先把要到的那个位置在原来的矩阵中修改为1（即以后不可以走），然后再dfs，最后再把原来矩阵修改回去。注意起始点先标记上！
可能遇到的困难：在做这道题之前，室友和我讨论了一下关于在递归中写多个if语句如何实现跳回去再调回来的功能，以保证所有的if都可以执行一次，我依托宏封装基本操作以方便编程，把判断条件单独放入一个标签judge，维护栈并用jal跳转至judge进行判断，最后jr跳回来正好是下一个if语句，解决了这个问题。光说可能不太清楚，下面提供一下汇编程序实现01迷宫，关注dfs,dfswork,judge,back四个标签（仅供自己留备份+其他同学学习参考！严禁抄袭！提交一定会被查重）
 
<div class="cnblogs_Highlighter">
<pre class="brush:cpp;gutter:true;">C++ #include <iostream>
#include <bits/stdc++.h>
int matrix;
int n,m,sx,sy,ex,ey;
int ans=0;
typedef struct {
int dx;
int dy;
}delta;
delta d={{0,-1},{0,1},{-1,0},{1,0}}; //高级语言中应该采取的走迷宫的写法
//在dfs中for(i=0;i<4;i++){遍历方向}
void dfs(int x,int y);
int overflow(int x,int y,int dx,int dy);
int main() {
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
scanf("%d",&matrix);
}
}
scanf("%d %d",&sx,&sy);
scanf("%d %d",&ex,&ey);
matrix=1;
dfs(sx,sy);
printf("%d\n",ans);
return 0;
}
void dfs(int x,int y){
if(x==ex && y==ey){
ans++;
return;
}//考虑到mips中多开数组或者用结构体在规定时间内编码难以接受，且为了翻译方便，所以没有用循环和方向数组
//事实上应该声明一个方向结构体数组，存储下来所有方向，然后写一个循环跑所有方向，这样节省在高级语言中的代码量
if(!overflow(x,y,0,-1) && !matrix){
matrix=1;
dfs(x,y-1);
matrix=0;
}
if(!overflow(x,y,0,1) && !matrix){
matrix=1;
dfs(x,y+1);
matrix=0;
}
if(!overflow(x,y,-1,0) && !matrix){
matrix=1;
dfs(x-1,y);
matrix=0;
}
if(!overflow(x,y,1,0) && !matrix){
matrix=1;
dfs(x+1,y);
matrix=0;
}
}
int overflow(int x,int y,int dx,int dy){
if(x+dx<=n && x+dx>=1 && y+dy<=m && y+dy>=1)
return 0;
return 1;
}</pre>
</div>
<div class="cnblogs_code">
<pre>1 .data
2 matrix: .space 400
3 .macro readint(%ans) #常用简单操作写成宏比较方便
4 li $v0,5
5 syscall
6 move %ans,$v0
7 .end_macro
8 .macro save(%a) #入栈
9 sw %a,($sp)
 10 addi $sp,$sp,-4
 11 .end_macro
 12 .macro load(%a) #出栈
 13 addi $sp,$sp,4
 14 lw %a,($sp)
 15 .end_macro
 16 .text
 17 readint($s0) #s0是n
 18 readint($s1) #s1是m
 19 li $s7,0 #s7是方案数
 20 li $t0,1 #t0是i
 21 read_matrix:
 22 bgt $t0,$s0,read_matrix_end
 23 li $t1,1
 24 read:
 25 bgt $t1,$s1,read_end
 26 addi $t2,$t0,-1
 27 mult $t2,$s1
 28 mflo $t2 #t2=(i-1)*m
 29 add $t2,$t2,$t1 #t2=(i-1)*m+j
 30 sll $t2,$t2,2
 31 la $s2,matrix
 32 add $t2,$s2,$t2 #t2是在矩阵中的位置
 33 li $v0,5
 34 syscall
 35 sw $v0,($t2) #数据存储进入矩阵
 36 addi $t1,$t1,1
 37 j read
 38 read_end:
 39 addi $t0,$t0,1
 40 j read_matrix
 41 read_matrix_end:
 42 readint($s2) #s2,s3,s4,s5分别是起始行列，终点行列
 43 readint($s3)
 44 readint($s4)
 45 readint($s5)
 46
 47 addi $t0,$s2,-1
 48 mult $t0,$s1
 49 mflo $t0
 50 add $t0,$t0,$s3
 51 sll $t0,$t0,2
 52 la $t1,matrix
 53 add $t0,$t0,$t1
 54 li $t2,1
 55 sw $t2,($t0) #把出发点的位置标记为1，然后再dfs（最开始忘了，所以最终得到的方案数比预计的多）
 56
 57 move $a0,$s2
 58 move $a1,$s3 #dfs参数，即目前的行和列
 59 jal dfs
 60
 61 li $v0,1
 62 move $a0,$s7
 63 syscall
 64 li $v0,10
 65 syscall
 66
 67
 68 dfs: #dfs写的是返回条件，dfswork里面才写了递归调用
 69 beq $a0,$s4,hope
 70 j dfswork
 71 hope:
 72 beq $a1,$s5,ansadd
 73 j dfswork
 74 ansadd:
 75 addi $s7,$s7,1
 76 jr $31
 77
 78 #多个if语句的跳转的一种写法:为了能让多个if语句都能执行，并不能直接使用beq等指令，一种实现方法是用jal连接下一步并跳转到一个专门用于判断的过程judge中去
 79 #由于jal跳转，所以需要维护栈，如果用宏来封装维护栈的过程的话，这里就特别容易写（推荐把读入数据，维护栈这种常用简单操作封装，至于其他用到额外寄存器的操作，请谨慎封装）
 80 dfswork:
 81 save($a0)
 82 save($a1)
 83 save($31) #第一次进时，这里存的是回主函数的地址
 84 addi $a0,$a0,0
 85 addi $a1,$a1,-1
 86 jal judge
 87 load($31)
 88 load($a1)
 89 load($a0) #完成对于一个方向的判断
 90
 91 save($a0)
 92 save($a1)
 93 save($31)
 94 addi $a0,$a0,0
 95 addi $a1,$a1,1
 96 jal judge
 97 load($31)
 98 load($a1)
 99 load($a0)
100
101 save($a0)
102 save($a1)
103 save($31)
104 addi $a0,$a0,-1
105 addi $a1,$a1,0
106 jal judge
107 load($31)
108 load($a1)
109 load($a0)
110
111 save($a0)
112 save($a1)
113 save($31)
114 addi $a0,$a0,1
115 addi $a1,$a1,0
116 jal judge
117 load($31)
118 load($a1)
119 load($a0)
120
121 jr $31 #返回上一个dfs
122
123 judge:
124 bgt $a0,$s0,back #如果行严格大于行数，返回
125 ble $a0,$0,back #如果行号小于等于0，返回
126 bgt $a1,$s1,back #同理
127 ble $a1,$0,back
128 addi $t0,$a0,-1 #由于存的时候就是这样的，所以此处也先减一
129 mult $t0,$s1
130 mflo $t1
131 add $t1,$t1,$a1
132 sll $t1,$t1,2
133 la $t2,matrix
134 add $t1,$t1,$t2
135 lw $t3,($t1) #t3是矩阵中该位置的值，表示是否能走
136 bne $t3,$0,back #如果t3不能走，回退一次
137 li $t4,1
138 sw $t4,($t1) #标记为不能走了
139 save($31) #第一次进时，这里存的是judge下一条的地址
140 save($t1)
141 save($t2)
142 save($t3)
143 save($t4) #不管哪些需要存哪些不需要存了，xjb存就完事了（其实这里只需要$t1存起来），最开始我$t1忘了存了
144 jal dfs
145 load($t4)
146 load($t3)
147 load($t2)
148 load($t1)
149 load($31)
150 sw $0,($t1) #把值修改回去，以后又可以走了
151 jr $31 #回judge的下一条指令，即判断另一个方向
152
153
154 back:
155 jr $31</pre>
</div>
 
 
补充题：
选择排序：
当时没照着视频写，现在拿出来写了一下，发现没必要像教程中一样弄个global main（也不让用），直接写即可。因为怕错+自己太弱，所以先写了C代码，然后翻译的。比视频中写的短，不到70行。当然，有一定的规矩终究是好的，但从助教口中得知，就P2的难度来说，倒没必要这么搞。
矩阵快速幂：
先放出C++代码，注意取模取多了也会变慢而超时。////更新：快速幂的汇编代码考前更新不出来了，只是又写了一遍C的代码，保证如果碰到的话能快速写出正确代码，并做好了测试数据。
<div class="cnblogs_code">
<pre>#include <bits/stdc++.h>
#define ll long long
//矩阵快速幂的快速之处不在于加速两个矩阵相乘时内部的计算速度
//而是减少矩阵之间做乘法的次数 
ll mod=1000000007;
typedef struct{
ll a[200][200];
}Matrix;
Matrix m,ans;
void power(ll n,ll k);
Matrix mult(Matrix ans,Matrix base,ll n);
int main() {
ll n,k;
scanf("%lld %lld",&n,&k);
for(ll i=0;i<n;i++){
 for(ll j=0;j<n;j++){
 scanf("%lld",&m.a);
 }
}
power(n,k);
for(ll i=0;i<n;i++){
 for(ll j=0;j<n;j++){
 printf("%lld ",ans.a);
 }
 printf("\n");
}
return 0;
}
void power(ll n,ll k){
Matrix base=m;
for(ll i=0;i<n;i++){
 ans.a=1; //构造单位矩阵 
 }
while(k>0){
 if(k&1){
 ans=mult(ans,base,n);
 }
 base=mult(base,base,n);
 k>>=1;
}
}
Matrix mult(Matrix ans,Matrix base,ll n){
Matrix result;
for(ll i=0;i<n;i++){
 for(ll j=0;j<n;j++){
 result.a=0;
 }
}
for(ll i=0;i<n;i++){
 for(ll j=0;j<n;j++){
 for(ll k=0;k<n;k++){
 result.a+=(((ans.a)*(base.a))%mod);
// result.a+=((ans.a%mod)*(base.a%mod)%mod);会慢，超时 
 result.a%=mod;
 }
 }
}
return result;
}</pre>
</div>
 
汉诺塔：
理解用汇编语言写递归的本质：把所有的参数都存在堆栈里，然后进下一层，最后递归终止时输出一行移动盘子。参考的去年OJ上的输出要求。
<div class="cnblogs_code">
<pre>#include <stdio.h>
#include <stdlib.h>
void dfs(int n,char from,char tmp,char to);
int main() {
int n;
char from='A',tmp='B',to='C';
scanf("%d",&n);
dfs(n,from,tmp,to);

return 0;
}
void dfs(int n,char from,char tmp,char to){
if(n==1){
 printf("%c --> %c\n",from,to);
 return;
}
dfs(n-1,from,to,tmp);
dfs(1,from,tmp,to);
dfs(n-1,tmp,from,to);
return;
}</pre>
</div>
下面是递归程序，比较容易写
<div class="cnblogs_code">
<pre> 1 .data
 2 connect: .asciiz " --> "
 3 enter: .asciiz "\n"
 4 _a: .asciiz "A"
 5 _b: .asciiz "B"
 6 _c: .asciiz "C"
 7 .macro save(%a)
 8 sw %a,($sp)
 9 addi $sp,$sp,-4
10 .end_macro
11
12 .macro swap(%a,%b)
13 move $t0,%a
14 move %a,%b
15 move %b,$t0
16 .end_macro
17
18 .macro load(%a)
19 addi $sp,$sp,4
20 lw %a,($sp)
21 .end_macro
22
23 .text
24 li $v0,5
25 syscall
26 move $s0,$v0 #s0是n
27 move $a0,$v0
28 la $a1,_a
29 la $a2,_b
30 la $a3,_c #配置四个参数：盘子数，from,tmp,to
31 jal dfs
32
33 li $v0,10
34 syscall
35
36 dfs:
37 bgt $a0,1,dfs_work
38 move $a0,$a1
39 li $v0,4
40 syscall
41 la $a0,connect
42 li $v0,4
43 syscall
44 move $a0,$a3
45 li $v0,4
46 syscall
47 la $a0,enter
48 li $v0,4
49 syscall
50 jr $31
51
52 dfs_work:
53 save($31)
54 save($a0)
55 save($a1)
56 save($a2)
57 save($a3)
58 addi $a0,$a0,-1
59 swap($a2,$a3)
60 jal dfs
61 load($a3)
62 load($a2)
63 load($a1)
64 load($a0)
65 load($31)
66
67 save($31)
68 save($a0)
69 save($a1)
70 save($a2)
71 save($a3)
72 li $a0,1
73 jal dfs
74 load($a3)
75 load($a2)
76 load($a1)
77 load($a0)
78 load($31)
79
80 save($31)
81 save($a0)
82 save($a1)
83 save($a2)
84 save($a3)
85 addi $a0,$a0,-1
86 swap($a1,$a2)
87 jal dfs
88 load($a3)
89 load($a2)
90 load($a1)
91 load($a0)
92 load($31)
93
94 jr $31
95 </pre>
</div>
 课上测试部分：
第一题：阶乘求和，给定数n，求1！+2！+…………+n! 这个实现起来还是挺简单的，毕竟二维数组和递归都能熟练操作了，二重循环不算啥了。
第二题：单步汉诺塔，几乎压中。写过普通汉诺塔的那个题的汇编程序的话，这个题也就是十分钟吧。题目做出的改动是：只能相邻柱子之间移动。还好给了C代码，翻译起来和普通汉诺塔如出一辙。追根溯源可知，该题对应这里：https://accoding.cn/problem/1073/index 是17级的一道程设题，上个星期还和室友讨论过……考场遇到研究过的问题是真的爽。
第三题：高精度乘法，碰巧我也准备了C的代码，所以也不会费太多的事。这个题可能卡人的地方可能有同学不会写高精度乘法。不巧我之前的一篇博客介绍过……大家可以移步那里。 
来源：https://www.cnblogs.com/BUAA-Wander/p/11746238.html

頁: [1]

琼殿技术论坛's Archiver

P2-汇编语言