VB.net 2010 视频教程 VB.net 2010 视频教程 python基础视频教程
SQL Server 2008 视频教程 c#入门经典教程 Visual Basic从门到精通视频教程
当前位置:
首页 > 编程开发 > 汇编语言 >
  • P2-汇编语言

通过阅读本文,您的收获可能有:理解递归程序的本质,知道如何用汇编语言去写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++代码,注释部分是对于地址计算和下标的思考。

复制代码
 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[i][j]);
12         }
13     }
14     for(int i=0;i<m2;i++){
15         for(int j=0;j<n2;j++){
16             scanf("%d",&core[i][j]);
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[i][j]+=core[k][l]*matrix[i+k][j+l]
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[i][j]+=core[k][l]*matrix[i+k][j+l];
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[i][j]);
43         }
44         printf("
");
45     }
46 }
复制代码

 

本题我处理不好的地方:虽然一遍就过样例了,但是编写过程中还是出了一些问题:首先是滥用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四个标签(仅供自己留备份+其他同学学习参考!严禁抄袭!提交一定会被查重)

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
C++<br>#include <iostream>
#include <bits/stdc++.h>
int matrix[20][20];
int n,m,sx,sy,ex,ey;
int ans=0;
typedef struct {
    int dx;
    int dy;
}delta;
delta d[4]={{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[i][j]);
        }
    }
    scanf("%d %d",&sx,&sy);
    scanf("%d %d",&ex,&ey);
    matrix[sx][sy]=1;
    dfs(sx,sy);
    printf("%d ",ans);
    return 0;
}
void dfs(int x,int y){
    if(x==ex && y==ey){
        ans++;
        return;
    }//考虑到mips中多开数组或者用结构体在规定时间内编码难以接受,且为了翻译方便,所以没有用循环和方向数组
    //事实上应该声明一个方向结构体数组,存储下来所有方向,然后写一个循环跑所有方向,这样节省在高级语言中的代码量
    if(!overflow(x,y,0,-1) && !matrix[x][y-1]){
        matrix[x][y-1]=1;
        dfs(x,y-1);
        matrix[x][y-1]=0;
    }
    if(!overflow(x,y,0,1) && !matrix[x][y+1]){
        matrix[x][y+1]=1;
        dfs(x,y+1);
        matrix[x][y+1]=0;
    }
    if(!overflow(x,y,-1,0) && !matrix[x-1][y]){
        matrix[x-1][y]=1;
        dfs(x-1,y);
        matrix[x-1][y]=0;
    }
    if(!overflow(x,y,1,0) && !matrix[x+1][y]){
        matrix[x+1][y]=1;
        dfs(x+1,y);
        matrix[x+1][y]=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;
}
复制代码
  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
复制代码

 

 

补充题:

选择排序:

当时没照着视频写,现在拿出来写了一下,发现没必要像教程中一样弄个global main(也不让用),直接写即可。因为怕错+自己太弱,所以先写了C代码,然后翻译的。比视频中写的短,不到70行。当然,有一定的规矩终究是好的,但从助教口中得知,就P2的难度来说,倒没必要这么搞。

矩阵快速幂:

先放出C++代码,注意取模取多了也会变慢而超时。////更新:快速幂的汇编代码考前更新不出来了,只是又写了一遍C的代码,保证如果碰到的话能快速写出正确代码,并做好了测试数据。

复制代码
#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[i][j]);
        }
    }
    power(n,k);
    for(ll i=0;i<n;i++){
        for(ll j=0;j<n;j++){
            printf("%lld ",ans.a[i][j]);
        }
        printf("
");
    }
    return 0;
}
void power(ll n,ll k){
    Matrix base=m;
    for(ll i=0;i<n;i++){
        ans.a[i][i]=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[i][j]=0;
        }
    }
    for(ll i=0;i<n;i++){
        for(ll j=0;j<n;j++){
            for(ll k=0;k<n;k++){
                result.a[i][j]+=(((ans.a[i][k])*(base.a[k][j]))%mod);
//              result.a[i][j]+=((ans.a[i][k]%mod)*(base.a[k][j]%mod)%mod);会慢,超时 
                result.a[i][j]%=mod;
            }
        }
    }
    return result;
}
复制代码

 

汉诺塔:

理解用汇编语言写递归的本质:把所有的参数都存在堆栈里,然后进下一层,最后递归终止时输出一行移动盘子。参考的去年OJ上的输出要求。

复制代码
#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
",from,to);
        return;
    }
    dfs(n-1,from,to,tmp);
    dfs(1,from,tmp,to);
    dfs(n-1,tmp,from,to);
    return;
}
复制代码

下面是递归程序,比较容易写

复制代码
 1 .data
 2 connect:    .asciiz " --> "
 3 enter:    .asciiz "
"
 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     
复制代码

 课上测试部分:

第一题:阶乘求和,给定数n,求1!+2!+…………+n! 这个实现起来还是挺简单的,毕竟二维数组和递归都能熟练操作了,二重循环不算啥了。

第二题:单步汉诺塔,几乎压中。写过普通汉诺塔的那个题的汇编程序的话,这个题也就是十分钟吧。题目做出的改动是:只能相邻柱子之间移动。还好给了C代码,翻译起来和普通汉诺塔如出一辙。追根溯源可知,该题对应这里:https://accoding.cn/problem/1073/index 是17级的一道程设题,上个星期还和室友讨论过……考场遇到研究过的问题是真的爽。

第三题:高精度乘法,碰巧我也准备了C的代码,所以也不会费太多的事。这个题可能卡人的地方可能有同学不会写高精度乘法。不巧我之前的一篇博客介绍过……大家可以移步那里。

出  处:
https://www.cnblogs.com/BUAA-Wander/p/11746238.html


相关教程