计组P2总结

本文最后更新于 2024年12月13日 晚上

MIPS的考察方式为将C语言代码翻译成MIPS汇编语言,其中对for循环的翻译、递归函数的转换最为重要

往年题

删数问题

键盘输入一个高精度的正整数 n（不超过 250 位），去掉其中任意 k个数字后剩下的数字按原左右次序将组成一个新的非负整数。编程对给定的 n 和 k，寻找一种方案使得剩下的数字组成的新数最小。

题目来源

P1106 删数问题 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

思路

已知我们要删掉m个数,我们要使得新数字最小,一定会选择前m+1位数中最小的那位作为最高位,设该位为k,则k之前的位均可以删去,保留第i位,对于第i+1位到末尾的数据,我们将m修改为m-(i-1)(因为此时数字已经删去i-1位),采取同样的上述操作,直到m=0.

C++代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<iostream>
#include<string>
using namespace std;
int n,k,a[257],rest,t=1,minp,cnt=0;
bool flag=0;
string num;
int main(){
    cin>>num>>k;
    n=num.length();
    for(int i=1;i<=n;++i)a[i]=num[i-1]-'0';
    rest=n-k;
    while(cnt<rest){
        minp=t;
        for(int i=t;i<=k+t;++i)if(a[minp]>a[i])minp=i;
        if(a[minp])flag=1;
        if(flag)cout<<a[minp];
        k-=minp-t;
        t=minp+1;
        cnt++;
    }
    if(!flag)cout<<0;
    return 0;
}

Java代码

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
import java.util.Scanner;

public class Solution1106 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String n = sc.next();
        int k = sc.nextInt();
        int len = n.length();
        int[] a = new int[len];
        for (int i = 0; i < len; i++) {
            a[i] = n.charAt(i) - '0';
        }
        int rest = len - k;
        int cnt = 0;
        int minp;
        int t = 0;
        boolean flag = false;
        while (cnt < rest) {
            minp = t;
            for (int i = t; i <= k + t; i++) {
                minp = a[minp] > a[i] ? i : minp;
            }
            if (a[minp] > 0) flag = true;
            if (flag) {
                System.out.print(a[minp]);
            }
            k -= minp - t;
            t = minp + 1;
            cnt++;
        }
        if (!flag){
            System.out.print(0);
        }
    }
}

MIPS答案

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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
.data
	a: .space 600
	
.macro push(%i)
	subi $sp, $sp, 4
	sw %i, 0($sp)
.end_macro

.macro pop(%i)
	lw %i, 0($sp)
	addi $sp, $sp, 4
.end_macro

.macro inputInt(%i)
	li $v0, 5
	syscall
	move %i, $v0
.end_macro

.macro printInt(%i)
	li $v0, 1
	move $a0, %i
	syscall
.end_macro

.macro printChar(%c)
	li $v0, 11
	move $a0, %c
	syscall
.end_macro

.macro inputStr(%str)
	li $v0, 12
	la $a0, %str
	li $a1, 150
	syscall
.end_macro

# 使用$t7($t7=i) for (int i = t; i <= k + t; i++)
.macro for_begin(%startLabel, %endLabel, %low, %high)
	move $t7, %low
	%startLabel:
	bgt $t7, %high, %endLabel
.end_macro

.macro for_end(%startLabel, %endLabel)
	addi $t7, $t7, 1
	j %startLabel
	%endLabel:
.end_macro

#使用$t7(记录字符串个数),$t6(记录字符当前对应位置)
.macro input_char_begin(%startLabel, %endLabel)
	li $t7, -1
	li $t6, -4
	%startLabel:
	beq $v0, 10, %endLabel
.end_macro

.macro input_char_end(%startLabel, %endLabel, %str, %len)
	addi $t7, $t7, 1
	addi $t6, $t6, 4
	sw $v0, %str($t6)
	j %startLabel
	%endLabel:
	move %len, $t7
.end_macro

.macro while_begin(%startLabel, %endLabel, %cnt, %rest)
	%startLabel:
	bge %cnt, %rest, %endLabel
.end_macro

.macro while_end(%startLabel, %endLabel)
	j %startLabel
	%endLabel:
.end_macro

.macro load_data(%arr, %i, %data)
	push($t4)
	li $t5, 4
	mult $t5, %i
	mflo $t5
	lw %data, %arr($t5)
	pop($t4)
.end_macro

.text
# 读入字符串a
input_char_begin(start1,end1)
	li $v0, 12 # 读入一个字符到$v0
	syscall
input_char_end(start1,end1,a,$s0)
#a记录字符串位置,$s0记录字符串长度(len)

# 读入k
inputInt($t0) #$t0=k,要删去的字符个数
#48-57
#rest = $s1
sub $s1, $s0, $t0 # rest = len - k
#cnt = $t1 = 0
li $t1, 0
# minp = $t2 = 0
li $t2, 0
# t = $t3 = 0
li $t3, 0
#flag = $t4 = 0 (false)
li $t4, 0

while_begin(start2,end2,$t1,$s1)
	move $t2, $t3 # minp = t
	for_begin(start3, end3,$t3,$t0)
		# minp = a[minp] > a[i] ? i : minp;
		push($s4)
		push($s5)
		load_data(a,$t2,$s4) # $s4 = a[minp]
		load_data(a,$t7,$s5) # $s5 = a[i], 
		bgt $s4, $s5, update
		j skip
		update:
			move $t2, $t7 # minp = i
		skip:
			pop($s5)
			pop($s4)
	for_end(start3,end3)
	
	#printInt($t2)
	load_data(a, $t2, $t5) # $t5 = a[minp]
	#printInt($t5)
	bgt $t5, $0, flag_true
	j skip2
	flag_true:
		li $t4, 1 # flag = true;
	skip2:
	
	beq $t4, $0, skip3  # if (flag) print(a[minp])
		load_data(a, $t2, $t5)# $t5 = a[minp]
		printChar($t5)
	skip3:
		
	sub $t0, $t0, $t2 # k = k - minp
	add $t0, $t0, $t3 # k = k + t
	addi $t3, $t2, 1 # t = minp + 1
	addi $t1, $t1, 1 # cnt++
while_end(start2,end2)

beq $t4, 1, skip4
li $s2, 0
printInt($s2)
skip4:


加法拆分

给一个数n,按照字典序输出它可能的加法拆分

思路

采用dfs

C代码

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
#include <stdio.h>
int arr[5000];

void printArr(int *arr, int cnt)
{
    for (int i = 0; i < cnt - 1; i++)
    {
        printf("%d", arr[i]);
        printf("+");
    }
    printf("%d", arr[cnt - 1]);
    printf("\n");
}

void dfs(int *arr, int cnt, int left, int last)
{
    if (left == 0)
    {
        printArr(arr, cnt);
        return;
    }
    for (int k = last; k <= left; k++)
    {
        arr[cnt] = k;
        dfs(arr, cnt + 1, left - k, k);
    }
}
int main()
{
    int n;
    scanf("%d", &n);
    dfs(arr, 0, n, 1);
}

MIPS答案

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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
.data
	arr: .space 200 # 用于存放待打印数字的数组
	enter: .word '\n'
	plus: .word  '+'
	test: .word 't'
	
#放入堆栈
.macro push(%i)
	addi $sp, $sp, -4
	sw %i, 0($sp)
.end_macro

#从堆栈中取出
.macro pop(%i)
	lw %i, 0($sp)
	addi $sp, $sp, 4
.end_macro

#读入整数
.macro inputInt(%int)
	li $v0, 5
	syscall
	move %int, $v0
.end_macro

#打印整数
.macro printInt(%int)
	li $v0, 1
	move $a0, %int
	syscall
.end_macro

# 打印字符
.macro printChar(%c)
	li $v0, 4
	la $a0, %c
	syscall
.end_macro

#结束程序
.macro done
	li $v0, 10
	syscall
.end_macro

#for循环
.macro for_begin(%startLabel, %endLabel, %start, %end)
	move $t7, %start
	%startLabel:
	bgt $t7, %end, %endLabel
.end_macro

.macro for_end(%startLabel, %endLabel)
	addi $t7, $t7, 1
	j %startLabel
	%endLabel:
.end_macro

# 将数据存在arr的指定位置
.macro store_data(%arr, %data, %index)
	push($t5)
	li $t5, 4
	mult $t5, %index
	mflo $t5
	sw %data, %arr($t5)
	pop($t5)
.end_macro

# arr的指定位置读取数据
.macro load_data(%arr, %data, %index)
	push($t5)
	li $t5, 4
	mult $t5, %index
	mflo $t5
	lw %data, %arr($t5)
	pop($t5)
.end_macro

#打印指定长度的数组
.macro printArr(%arr, %cnt)
	li $t4, 0
	print_loop:
		bge $t4, %cnt, print_end
		
		load_data(%arr, $t6, $t4)
		printInt($t6)
		addi $t4, $t4, 1
		bge $t4, %cnt, print_end
		printChar(plus)
		print_skip:
		j print_loop
	print_end:
		printChar(enter)
.end_macro

# 数据指代
.eqv n $s0
.eqv cnt $a1
.eqv left $a2
.eqv last $a3

.text
inputInt(n)
li cnt, 0
move left, n
li last, 1
jal dfs
done

dfs:
	push($ra)
	beq left, $0, dfs_return
	for_begin(dfs_start,dfs_end,last,left)
		# $t7 = k
		store_data(arr, $t7, cnt)
		push(cnt)
		push(left)
		push(last)
		push($t7)
		addi cnt, cnt, 1
		sub left, left, $t7
		move last, $t7
		jal dfs
		pop($t7)
		pop(last)
		pop(left)
		pop(cnt)
	for_end(dfs_start, dfs_end)
	j dfs_done
	
	dfs_return:
		printArr(arr, cnt)
	
	dfs_done:
		pop($ra)
		jr $ra


易错点

  • $a0作为Syscall打印时需要的参数,要避免用户自定义函数中的参数含有$a0,产生不必要的冲突.或者修改print函数,采用入栈+退栈的方式(该方法更安全):
1
2
3
4
5
6
7
.macro printInt(%int)
	push($a0)
	li $v0, 1
	move $a0, %int
	syscall
	pop($a0)
.end_macro
  • 字符应当被指定为word在MIP32中占4字节,即32位,打印字符方式为:
1
2
3
4
5
6
.data 
	plus: .word '+'
.text
	li $v0, 4
	la $a0, plus
	syscall

双关键词排序

冒泡排序基础

为了降低翻译难度,我在这里删去了用来决定提前推出排序的标记flag,同时一定程度上增加了算法的时间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void BubbleSort(int A[], int n)
{
    int i, k, temp;
    for (i = n - 1; i > 0; i--)
    {
        for (k = 0; k < i; k++)
        {
            if (A[k] > A[k + 1])
            {
                temp = A[k];
                A[k] = A[k + 1];
                A[k + 1] = temp;
            }
        }
    }
}

翻译成MIPS:

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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
.data 
	arr: .space 400
	space: .word ' '
	
.macro push(%x)
	subi $sp, $sp, 4
	sw %x, 0($sp)
.end_macro

.macro pop(%x)
	lw %x, 0($sp)
	addi $sp, $sp, 4
.end_macro

.macro inputInt(%int)
	li $v0, 5
	syscall
	move %int, $v0
.end_macro

.macro for_begin_decrease(%startLabel, %endLabel, %i, %start, %end)
	subi %start, %start, 1
	move %i, %start
	addi %start, %start, 1
	%startLabel:
	beq %i, %end, %endLabel
.end_macro

.macro for_end_decrease(%startLabel, %endLabel, %i)
	subi %i, %i, 1
	j %startLabel
	%endLabel:
.end_macro

.macro for_begin(%startLabel, %endLabel, %i, %start, %end)
	move %i, %start
	%startLabel:
	beq %i, %end, %endLabel
.end_macro

.macro for_end(%startLabel, %endLabel, %i)
	addi %i, %i, 1
	j %startLabel
	%endLabel:
.end_macro

#获得数组指定位置的值
.macro load_data(%arr, %index, %value)
	push($t9)
	li $t9, 4
	mult $t9, %index
	mflo $t9
	lw %value, %arr($t9)
	pop($t9)
.end_macro

#将数据存储到数组中的指定位置
.macro store_data(%arr, %index, %value)
	push($t9)
	li $t9, 4
	mult $t9, %index
	mflo $t9
	sw %value, %arr($t9)
	pop($t9)
.end_macro

#交换数组中第i位和第k位,使用$t8,$t9作为temp
.macro swap(%arr, %i, %k)
	push($t7)
	push($t8)
	load_data(%arr, %i, $t7)
	load_data(%arr, %k, $t8)
	store_data(%arr, %k, $t7)
	store_data(%arr, %i, $t8)
	pop($t8)
	pop($t7)
.end_macro

#输入数组元素
.macro input_arr_element(%arr, %index)
	li $v0, 5
	syscall
	store_data(%arr, %index, $v0)
.end_macro

#输出数组元素
.macro print_arr_element(%arr, %index)
	li $v0, 1
	load_data(%arr, %index, $a0)
	syscall
.end_macro

.macro printChar(%c)
	li $v0, 4
	la $a0, %c
	syscall
.end_macro

.eqv n, $s0
.eqv i, $t0
.eqv k, $t1
.eqv k_1 $t2#k+1
.eqv A_k $t3 #arr[k]
.eqv A_k_1 $t4 #arr[k+1]
.text
	#输入数组
	inputInt(n)
	for_begin(start0, end0, i, $0,n)
		input_arr_element(arr, i)
	for_end(start0, end0, i)
	
	#bubble sort
	for_begin_decrease(start1,end1,i,n,$0)
		for_begin(start2,end2,k,$0,i)
			load_data(arr, k, A_k)
			addi k_1, k, 1
			load_data(arr, k_1, A_k_1)
			bgt A_k, A_k_1, swp
			j skip
			swp:
			swap(arr,k,k_1)
			skip:
		for_end(start2,end2,k)
	for_end_decrease(start1,end1,i)
	
	#打印数组
	for_begin(start3, end3, i, $0, n)
		print_arr_element(arr, i)
		printChar(space)
	for_end(start3, end3, i)

稍作修改的答案

本题使用具有稳定性的冒泡排序,先对B数组从小到大进行排序,再对A数组进行相同操作,但在交换数组元素时对另一个数组也要进行相同位置的交换操作.

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
#include <stdio.h>
int a[100];
int b[100];

void swap(int *p, int *q)
{
    int temp = *p;
    *p = *q;
    *q = temp;
}

int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
    {
        scanf("%d%d", &a[i], &b[i]);
    }

    int i, k;
    for (i = n - 1; i > 0; i--)
    {
        for (k = 0; k < i; k++)
        {
            if (b[k] > b[k + 1])
            {
                swap(&a[k], &a[k + 1]);
                swap(&b[k], &b[k + 1]);
            }
        }
    }
    for (i = n - 1; i > 0; i--)
    {
        for (k = 0; k < i; k++)
        {
            if (a[k] > a[k + 1])
            {
                swap(&a[k], &a[k + 1]);
                swap(&b[k], &b[k + 1]);
            }
        }
    }

    for (int i = 0; i < n; i++)
    {
        printf("%d %d\n", a[i], b[i]);
    }
}

翻译成MIPS汇编语言,关键在swap和双层for循环上

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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
.data 
	A: .space 400
	B: .space 400
	space: .word ' '
	enter: .word '\n'
.macro push(%x)
	subi $sp, $sp, 4
	sw %x, 0($sp)
.end_macro

.macro pop(%x)
	lw %x, 0($sp)
	addi $sp, $sp, 4
.end_macro

.macro inputInt(%int)
	li $v0, 5
	syscall
	move %int, $v0
.end_macro

.macro for_begin_decrease(%startLabel, %endLabel, %i, %start, %end)
	subi %start, %start, 1
	move %i, %start
	addi %start, %start, 1
	%startLabel:
	beq %i, %end, %endLabel
.end_macro

.macro for_end_decrease(%startLabel, %endLabel, %i)
	subi %i, %i, 1
	j %startLabel
	%endLabel:
.end_macro

.macro for_begin(%startLabel, %endLabel, %i, %start, %end)
	move %i, %start
	%startLabel:
	beq %i, %end, %endLabel
.end_macro

.macro for_end(%startLabel, %endLabel, %i)
	addi %i, %i, 1
	j %startLabel
	%endLabel:
.end_macro

#获得数组指定位置的值
.macro load_data(%arr, %index, %value)
	push($t9)
	li $t9, 4
	mult $t9, %index
	mflo $t9
	lw %value, %arr($t9)
	pop($t9)
.end_macro

#将数据存储到数组中的指定位置
.macro store_data(%arr, %index, %value)
	push($t9)
	li $t9, 4
	mult $t9, %index
	mflo $t9
	sw %value, %arr($t9)
	pop($t9)
.end_macro

#交换数组中第i位和第k位,使用$t8,$t9作为temp
.macro swap(%arr, %i, %k)
	push($t7)
	push($t8)
	load_data(%arr, %i, $t7)
	load_data(%arr, %k, $t8)
	store_data(%arr, %k, $t7)
	store_data(%arr, %i, $t8)
	pop($t8)
	pop($t7)
.end_macro

#输入数组元素
.macro input_arr_element(%arr, %index)
	li $v0, 5
	syscall
	store_data(%arr, %index, $v0)
.end_macro

#输出数组元素
.macro print_arr_element(%arr, %index)
	li $v0, 1
	load_data(%arr, %index, $a0)
	syscall
.end_macro

.macro printChar(%c)
	li $v0, 4
	la $a0, %c
	syscall
.end_macro

.eqv n, $s0
.eqv i, $t0
.eqv k, $t1
.eqv k_1 $t2#k+1
.eqv A_k $t3 #arr[k]
.eqv A_k_1 $t4 #arr[k+1]
.text
	#输入A,B数组
	inputInt(n)
	for_begin(start0, end0, i, $0,n)
		input_arr_element(A, i)
		input_arr_element(B, i)
	for_end(start0, end0, i)
	
	#先对B数组进行冒泡排序(从小到大)
	for_begin_decrease(start1,end1,i,n,$0)
		for_begin(start2,end2,k,$0,i)
			load_data(B, k, A_k)
			addi k_1, k, 1
			load_data(B, k_1, A_k_1)
			bgt A_k, A_k_1, swp1
			j skip1
			swp1:
			swap(A,k,k_1)
			swap(B,k,k_1)
			skip1:
		for_end(start2,end2,k)
	for_end_decrease(start1,end1,i)
	
	#再对A数组进行冒泡排序(从小到大)
	for_begin_decrease(start3,end3,i,n,$0)
		for_begin(start4,end4,k,$0,i)
			load_data(A, k, A_k)
			addi k_1, k, 1
			load_data(A, k_1, A_k_1)
			bgt A_k, A_k_1, swp2
			j skip2
			swp2:
			swap(A,k,k_1)
			swap(B,k,k_1)
			skip2:
		for_end(start4,end4,k)
	for_end_decrease(start3,end3,i)
	
	#打印数组
	for_begin(start5, end5, i, $0, n)
		print_arr_element(A, i)
		printChar(space)
		print_arr_element(B,i)
		printChar(enter)
	for_end(start5, end5, i)

可以看到,宏可以大幅降低拓展代码的难度

字符统计

P2_L1_calculate - 系统能力课程实验平台 (buaa.edu.cn)

使用MIPS汇编语言写一个具有字符统计功能的汇编程序(不考虑延迟槽)

分析

本题要实现一个计数器,这在C语言中通常使用字典实现,而要在MIPS汇编语言直接构建这样一个部件难度较大,我们可以开两个数组arr与order,arr记录字符对应的出现次数,order记录各个字符的依次出现顺序

MIPS答案

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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
.data
	arr: .space 200 # 26 * 4
	order: .space 200
	space: .word ' '
	enter: .word '\n'

# 别名
.eqv n, $s0 # 输入字符总数
.eqv ct $s1 # 用于记录输入的字符种类
.eqv i, $t0 # 用于for循环
.eqv k, $t1 # 用于for循环
.eqv t, $t3 # 用于for循环
.eqv flag, $s2 # 标志

.macro for_begin(%startLabel, %endLabel, %i,%start,%end)
	move %i, %start
	%startLabel:
	beq %i, %end, %endLabel
.end_macro

.macro for_end(%startLabel, %endLabel, %i)
	addi %i, %i, 1
	j %startLabel
	%endLabel:
.end_macro

.macro inputChar(%c)
	li $v0, 12
	syscall
	move %c, $v0
.end_macro

.macro inputInt(%int)
	li $v0, 5
	syscall
	move %int, $v0
.end_macro

.macro printInt(%int)
	li $v0, 1
	move $a0, %int
	syscall
.end_macro

.macro printChar(%c)
	li $v0, 4
	la $a0, %c
	syscall
.end_macro

#将数字转化为对应字符(0-'a')
.macro printCharFromInt(%int)
	addi $a0, %int, 97
	li $v0, 11
	syscall
.end_macro

.macro store_data(%arr,%index,%value)
	li $t9, 4
	mult $t9, %index
	mflo $t9
	sw %value, %arr($t9)
.end_macro

.macro load_data(%arr, %index, %value)
	sll $t9, %index, 2
	lw %value, %arr($t9)
.end_macro

.macro put(%arr, %order, %k)
	subi %k, %k, 97 
	put_order(%order, %k)

	load_data(%arr, %k, $t7)
	addi $t7, $t7, 1
	store_data(%arr, %k, $t7)
.end_macro

.macro put_order(%order, %k)
	li flag, 1 # 标记当前字符是否未出现
	for_begin(start10, end10, t, $0, ct)
		load_data(order, t, $t7)
		beq $t7, %k, yes # 找到了
		j put_order_end
		yes:
		li flag, 0 # 将标记置为0
		put_order_end:
	for_end(start10, end10, t)
	beq flag, $0, skip
	store_data(order, ct, %k) # 将新的字符种类添加到order中
	addi ct, ct, 1
	skip:
.end_macro

.macro print_arr_element(%arr, %order, %k)
	load_data(%order, %k, $t5) # %k是[0,ct)之间的一个整数, $t5记录第%k个出现的字符种类('a'-97到'b'-97,即[0,26))
	load_data(%arr, $t5, $t4) # $t4寄存对应字符的出现次数
	beq $t4, $0, skip # 该语句无用,但为了代码拓展性和稳定性可以保留
	printCharFromInt($t5) # 0对应'a',25对应'z'
	printChar(space)
	printInt($t4)
	printChar(enter)
	skip:
.end_macro

.macro done
	li $v0, 10
	syscall
.end_macro

.text
	# 初始化
	li ct, 0
	
	# 输入n
	inputInt(n)
	
	# 输入n个字符
	for_begin(start1,end1,i,$0,n)
		inputChar(k)
		put(arr, order, k)
	for_end(start1,end1,i)
	
	# 打印
	for_begin(start2,end2,k,$0,ct)
		print_arr_element(arr, order, k)
	for_end(start2,end2,k)
	
	# 终止程序
	done

易错点

  • MIPS评测机似乎不会有换行符的输入,虽然无法在本地实现对换行符的处理,却可以通过评测机.但倘若增加了一个用于除去换行符影响的ignoreInt()方法,反而会出现RE错误.
  • 在这里要实现读入单个字符,根据手册可以搓出这个宏:
1
2
3
4
5
.macro inputChar(%c)
	li $v0, 12
	syscall
	move %c, $v0
.end_macro
  • 但如何避免换行符的影响?我们可以用读入字符串的方法(此时程序会读入一行字符,包括换行符),在将字符串的第0位字符提取出来.
1
2
3
4
5
6
.macro inputChar(%c)
	li $v0, 8
	li $a1, 10
	syscall
	lw %c, 0($a0)
.end_macro

矩阵转置相加

使用MIPS汇编语言编写一个具有矩阵转置相加功能的汇编程序(不考虑延迟槽).

C语言代码

开两个二维数组a,b,各元素依次相加,通过调换for循环顺序实现对转置矩阵的打印.

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
#include <stdio.h>
int a[8][8];
int b[8][8];
int main()
{
    int n;
    int m;
    scanf("%d", &n);
    scanf("%d", &m);
    for (int i = 0; i < n; i++)
    {
        for (int k = 0; k < m; k++)
        {
            scanf("%d", &a[i][k]);
        }
    }
    for (int i = 0; i < n; i++)
    {
        for (int k = 0; k < m; k++)
        {
            scanf("%d", &b[i][k]);
        }
    }
    for (int i = 0; i < n; i++)
    {
        for (int k = 0; k < m; k++)
        {
            a[i][k] = a[i][k] + b[i][k];
        }
    }
    printf("The result is:\n");
    for (int k = 0; k < m; k++)
    {
        for (int i = 0; i < n; i++)
        {
            printf("%d", a[i][k]);
            if (i != n - 1)
            {
                printf(" ");
            }
        }
        if (k != m - 1)
        {
            printf("\n");
        }
    }
}

MIPS答案

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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
.data
	enter: .word '\n'
	space: .word ' '
	sentence: .asciiz "The result is:\n"
	A: .space 256 # 8 * 8 * 4
	B: .space 256 # 8 * 8 * 4
	
.eqv n, $s0
.eqv m, $s1
.eqv i, $t0
.eqv k, $t1
.eqv temp, $t2
.eqv temp1, $t3

.macro done
	li $v0, 10
	syscall
.end_macro

.macro inputInt(%int)
	li $v0, 5
	syscall
	move %int, $v0
.end_macro

.macro printInt(%int)
	li $v0, 1
	move $a0, %int
	syscall
.end_macro

.macro printStr(%str)
	li $v0, 4
	la $a0, %str
	syscall
.end_macro

.macro for_begin(%startLabel, %endLabel, %i, %start, %end)
	move %i, %start
	%startLabel:
	beq %i, %end, %endLabel
.end_macro

.macro for_end(%startLabel, %endLabel, %i)
	addi %i, %i, 1
	j %startLabel
	%endLabel:
.end_macro

# value = arr[i][k]
.macro load_arr(%arr, %i, %k, %value)
	sll $t9, %i, 3 # $t9 = i * 8
	add $t9, $t9, %k
	sll $t9, $t9, 2 
	lw %value, %arr($t9)
.end_macro

# arr[i][k] = value
.macro store_arr(%arr, %i, %k, %value)
	sll $t9, %i, 3 # $t9 = i * 8
	add $t9, $t9, %k
	sll $t9, $t9, 2 
	sw %value, %arr($t9)
.end_macro

.text
	# 读入n, m
	inputInt(n)
	inputInt(m)
	
	# 读入矩阵A
	for_begin(start1, end1, i, $0, n)
		for_begin(start2, end2, k, $0, m)
			inputInt(temp)
			store_arr(A, i, k, temp)
		for_end(start2, end2, k)
	for_end(start1,end1, i)
	
	# 读入矩阵B
	for_begin(start3, end3, i, $0, n)
		for_begin(start4, end4, k, $0, m)
			inputInt(temp)
			store_arr(B, i, k, temp)
		for_end(start4, end4, k)
	for_end(start3, end3, i)
	
	# 矩阵A,B相加,结果存储到A中
	for_begin(start5, end5, i, $0, n)
		for_begin(start6, end6, k, $0, m)
			load_arr(A, i, k, temp)
			load_arr(B, i, k, temp1)
			add temp, temp, temp1
			store_arr(A, i, k, temp)
		for_end(start6, end6, k)
	for_end(start5, end5, i)
	
	printStr(sentence)
	
	# 打印A的转置数组
	for_begin(start7, end7, k, $0, m)
		for_begin(start8, end8, i, $0, n)
			load_arr(A, i, k, temp)
			printInt(temp)
			addi i, i, 1
			beq i, n, skip
			printStr(space)
			skip:
			subi i, i, 1
		for_end(start8, end8, i)
		addi k, k, 1
		beq k, m, skip2
		printStr(enter)
		skip2:
		subi k, k, 1
	for_end(start7, end7, k)
	
	# 终止程序
	done

易错点

  • 要注意到矩阵每一行的最后不能出现空格,最后一行的末尾不能有换行符.我们可以先对for循环中的参数(i或k)进行加一操作,判断其是否与n或m相等.

  • 多层循环使用宏会更加方便.对于不同的for循环,一定要将开始和结束的标志符设置为不同的(不要复制粘贴后忘了修改就行)

倒序全排列

使用MIPS实现全排列生成算法

输入一个小于等于7的正整数,求出n的全排列,并按照字典序倒序输出

思路

正序全排列C语言代码

这里题目给出了正序全排列的C语言代码,不难发现:只要将FullArray(int index)中出现的第二个正序for循环改为倒序即可.即:

1
2
3
4
5
for (int i = n - 1; i >= 0; i--) {
    if (symbol[i] == 0) {
        // body
    }
}

MIPS答案

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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
.data
	symbol: .space 28
	array: .space 28
	enter: .word '\n'
	space: .word ' '
	
.eqv n, $s0
.eqv index, $a1
.eqv i, $t0
.eqv k, $t1
.eqv flag, $t2
.eqv one, $t3 # 用于存储立即数1

.macro done
	li $v0, 10
	syscall
.end_macro

.macro push(%x)
	subi $sp, $sp, 4
	sw %x, 0($sp)
.end_macro

.macro pop(%x)
	lw %x, 0($sp)
	addi $sp, $sp, 4
.end_macro

.macro inputInt(%int)
	li $v0, 5
	syscall
	move %int, $v0
.end_macro

.macro printInt(%int)
	li $v0, 1
	move $a0, %int
	syscall
.end_macro

.macro printStr(%str)
	li $v0, 4
	la $a0, %str
	syscall
.end_macro

.macro print_arr_element(%arr, %i)
	sll $t9, %i, 2
	lw $a0, %arr($t9)
	li $v0, 1
	syscall
.end_macro

.macro for_begin(%startLabel, %endLabel, %i, %start, %end)
	move %i, %start
	%startLabel:
	beq %i, %end, %endLabel
.end_macro

.macro for_end(%startLabel, %endLabel, %i)
	addi %i, %i, 1
	j %startLabel
	%endLabel:
.end_macro

# 递减for循环
.macro for_begin_decrease(%startLabel, %endLabel, %i, %start, %end)
	move %i, %start
	subi %i, %i, 1
	%startLabel:
	blt %i, %end, %endLabel
.end_macro

.macro for_end_decrease(%startLabel, %endLabel, %i)
	subi %i, %i, 1
	j %startLabel
	%endLabel:
.end_macro

.macro store_data(%arr, %index, %value)
	sll $t9, %index, 2
	sw %value, %arr($t9)
.end_macro

.macro load_data(%arr, %index, %value)
	sll $t9, %index, 2
	lw %value, %arr($t9)
.end_macro

.text
	inputInt(n)
	li one, 1
	li index, 0
	jal FullArray
	done
	
	FullArray:
		push($ra)
		bge index, n, return
		for_begin_decrease(start2, end2, i, n, $0)
			load_data(symbol, i, flag)
			beq flag, $0, yes
			j no
			yes:
				addi i, i, 1
				store_data(array, index, i)
				subi i, i, 1
				store_data(symbol, i, one)
				addi index, index, 1
				push(i)
				jal FullArray
				pop(i)
				subi index, index, 1
				store_data(symbol, i, $0)
			no:
				
		for_end_decrease(start2, end2, i)
		
		j full_array_end
		
		return:
			for_begin(start1, end1, k, $0, n)
				print_arr_element(array, k)
				printStr(space)
			for_end(start1, end1, k)
			printStr(enter)
		full_array_end:
		pop($ra)
		jr $ra

阶乘连加

1202-329

MIPS答案

实现思路很简单,不需要写一个C语言程序了,但要注意细节问题

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
.eqv n, $s0
.eqv index, $a1
.eqv ans, $s1
.eqv new, $s2
.eqv i, $t0
.eqv k, $t1

.macro inputInt(%int)
	li $v0, 5
	syscall
	move %int, $v0
.end_macro

.macro inputUnsignedInt(%u)
	li $v0, 36
	move $a0, %u
	syscall
.end_macro

.macro done
	li $v0, 10
	syscall
.end_macro

.macro for_begin_decrease(%startLabel, %endLabel, %i, %start, %end)
	move %i, %start
	%startLabel:
	ble %i, %end, %endLabel
.end_macro

.macro for_end_decrease(%startLabel, %endLabel, %i)
	subi %i, %i, 1
	j %startLabel
	%endLabel:
.end_macro

.text
	inputInt(n)
	
	for_begin_decrease(start, end, i, n, $0)
		li new, 1
		for_begin_decrease(start2, end2, k, i, $0)
			mult new, k
			mflo new
		for_end_decrease(start2, end2, k)
		addu ans, ans, new
	for_end_decrease(start, end, i)
	
	inputUnsignedInt(ans)
	
	done

易错点

  • 该程序设计无符号数,add要替换为addu

单步汉诺塔

  • 输入格式：
  • 输入包含1行，只包含1个1位整数，即0-9中的某一个整数，记其为n
  • 汉诺塔三根柱子的编号从左到右依次为'A','B','C',初始的时候所有盘子都在‘A'上，编号从上（小）到下（大）分别为0~n
  • 移动这些盘子到’C‘，要求移动时只能将某个柱子上最上面的盘子移动到相邻的柱子，并且任何情况下大盘子不能在小盘子上面，即A上的盘子不能直接移动到C上
  • 输出格式：请参照下文的C语言样例，要求实现同粒度的输出（即能通过逐行strcmp的检测）
  • 数据范围：
  • 0<n<10

C语言样例已给出:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <stdio.h>
void move(int id, char from, char to) {
  printf("move disk %d from %c to %c\n", id, from, to);
}
void hanoi(int base, char from, char via, char to) {
  if (base == 0) {
      move(base, from, via);
      move(base, via, to);
      return;
  }
  hanoi(base - 1, from, via, to);
  move(base, from, via);
  hanoi(base - 1, to, via, from);
  move(base, via, to);
  hanoi(base - 1, from, via, to);
}
int main() {
  int n;
  scanf("%d", &n);
  hanoi(n, 'A', 'B', 'C');
  return 0;
}

MIPS答案

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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
.data
	sentence: .asciiz "move disk A from A to A\n"
	
.eqv shift, $t3
.eqv shift1, 10
.eqv shift2, 7
.eqv shift3, 5
.eqv n, $s0
.eqv base, $a1
.eqv from, $a2
.eqv via, $a3
.eqv to, $t4
.eqv A, 65
#.eqv B, 66
.eqv C, 67
.eqv zero, 48

# move()函数,使用$t7
.macro move_(%id, %from, %to)
	la $t7, sentence
	addi $t7, $t7, shift1
	sb %id, 0($t7)
	addi $t7, $t7, shift2
	sb %from, 0($t7)
	addi $t7, $t7, shift3
	sb %to, 0($t7)
	printStr(sentence)
.end_macro

.macro printStr(%str)
	li $v0, 4
	la $a0, %str
	syscall
.end_macro

.macro inputInt(%int)
	li $v0, 5
	syscall
	move %int, $v0
.end_macro

.macro push(%x)
	subi $sp, $sp, 4
	sw %x, 0($sp)
.end_macro

.macro pop(%x)
	lw %x, 0($sp)
	addi $sp, $sp, 4
.end_macro

.macro swap(%x, %y)
	push(%x)
	push(%y)
	pop(%x)
	pop(%y)
.end_macro

.macro done
	li $v0, 10
	syscall
.end_macro

.text
	inputInt(n)
	move base, n
	addi base, base, zero
	li from, 65
	li via, 66
	li to, 67
	jal hanoi
	
	done

hanoi:
	push($ra)
	beq base, zero, return
		push(base)
		push(from)
		push(to)
		subi base, base, 1
		jal hanoi
		pop(to)
		pop(from)
		pop(base)
		move_(base, from, via)
		
		push(base)
		push(from)
		push(to)
		subi base, base, 1
		swap(from, to)
		jal hanoi
		pop(to)
		pop(from)
		pop(base)
		move_(base, via, to)
	
		subi base, base, 1
		jal hanoi
	
	j hanoi_end
	return:
		move_(base, from, via)
		move_(base, via, to)
	hanoi_end:
		pop($ra)
		jr $ra

难点(修改字符串)

  • 对于字符串的修改,可以采用以下模板:
1
2
3
4
5
6
7
# 将字符串第i位修改为指定字符c
.macro modify_str(%str, %i, %c)
	la $t9, modify_str
	add $t9, $t9, %i
	sb %c, 0($t9) # sb存入一个byte(比特),这是因为asciiz字符串中一个字符占8位(即1byte)
.end_macro

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
.data
	sentence: .asciiz "hello, world!\n"

.eqv c, $t0 # 待加入的字符
.eqv shift, $t1 # 偏移量

# 将字符串第i位修改为指定字符c
.macro modify_str(%str, %i, %c)
	la $t9, %str
	add $t9, $t9, %i
	sb %c, 0($t9) # sb存入一个byte(比特),这是因为asciiz字符串中一个字符占8位(即1byte)
.end_macro

.macro printStr(%str)
	li $v0, 4
	la $a0, %str
	syscall
.end_macro

.text
li shift, 3
li c, 70 # 'F'对应ASCII码为70
modify_str(sentence, shift, c)
printStr(sentence)

# output:
# helFo, world!

二分查找的实现与应用

P2_L1_bsearch - 系统能力课程实验平台 (buaa.edu.cn)

C语言代码

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
#include <stdio.h>
int arr[1000];
int binary_search(int key,int a[],int n) //自定义函数binary_search()
{
    int low,high,mid,count=0,count1=0;
    low=0;
    high=n-1;
    while(low<=high)    //査找范围不为0时执行循环体语句
    {
        count++;    //count记录査找次数
        mid=(low+high)/2;    //求中间位置
        if(key<a[mid])    //key小于中间值时
            high=mid-1;    //确定左子表范围
        else if(key>a[mid])    //key 大于中间值时
            low=mid+1;    //确定右子表范围
        else if(key==a[mid])    //当key等于中间值时，证明查找成功
        {
            printf("1");
            count1++;    //count1记录查找成功次数
            break;
        }
    }
    if(count1==0)    //判断是否查找失敗
        printf("0");
    return 0;
}

int main(){
    int m;
    scanf("%d", &m);
    for (int i = 0; i < m; i++) {
        scanf("%d", &arr[i]);
    }
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &key);
        binary_search(key, arr, m);
    }
}

MIPS答案

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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
.data
	arr: .space 4000
	enter: .word '\n'
	
.eqv n, $s0
.eqv m, $s1
.eqv low, $t0
.eqv high, $t1
.eqv mid, $t2
.eqv count, $t3
.eqv count1, $t4
.eqv temp, $t5
.eqv i, $t6
.eqv k, $t7
.eqv key, $t8

.macro for_begin(%startLabel, %endLabel, %i, %start,%end)
	move %i, %start
	%startLabel:
	beq %i, %end, %endLabel
.end_macro

.macro for_end(%startLabel, %endLabel, %i)
	addi %i, %i, 1
	j %startLabel
	%endLabel:
.end_macro

.macro while_begin(%startLabel, %endLabel, %low, %high)
	%startLabel:
	bgt %low, %high, %endLabel
.end_macro

.macro while_end(%startLabel, %endLabel)
	j %startLabel
	%endLabel:
.end_macro

.macro inputInt(%int)
	li $v0, 5
	syscall
	move %int, $v0
.end_macro

.macro printImmediate(%imm)
	li $v0, 1
	li $a0, %imm
	syscall
.end_macro

.macro printChar(%c)
	li $v0,  4
	la $a0, %c
	syscall
.end_macro

.macro load_data(%arr, %index, %value)
	sll $t9, %index, 2
	lw %value, %arr($t9)
.end_macro

.macro store_data(%arr, %index, %value)
	sll $t9, %index, 2
	sw %value, %arr($t9)
.end_macro

.macro binary_search(%key, %a, %n)
	li count, 0
	li count1, 0
	li low, 0
	subi high, %n, 1
	while_begin(start1, end1, low, high)
		addi count, count, 1
		add mid, low, high
		srl mid, mid, 1 # mid = (low + high) / 2;
		load_data(%a, mid, temp)
		blt key, temp, less
		beq key, temp, same
		bgt key, temp, greater
		
		less:
		subi high, mid, 1
		j judge_end
		same:
		printImmediate(1)
		printChar(enter)
		addi count1, count, 1
		j break_mark
		greater:
		addi low, mid, 1
		judge_end:
	while_end(start1,end1)
	break_mark:
	beq count1, 0, fail
	j skip0
	fail:
	printImmediate(0)
	printChar(enter)
	skip0:
.end_macro

.macro done
	li $v0, 10
	syscall
.end_macro

.text
	inputInt(m)
	for_begin(start2, end2, i, $0, m)
		inputInt(temp)
		store_data(arr,i,temp)
	for_end(start2, end2, i)
	
	inputInt(n)
	for_begin(start3,end3,k,$0,n)
		inputInt(key)
		binary_search(key, arr, m)
	for_end(start3,end3,k)
	
	done

水仙花数的判断

C语言代码

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
#include <stdio.h>
int square(int x) {
    return x * x * x;
}
int narcissus(int x) {
    int a0;
    int a1;
    int a2;
    a0 = x % 10;
    a1 = (x % 100) / 10;
    a2 = x / 100;
    if (square(a0) + square(a1) + square(a2) == x) {
        return 1;
    }
    return 0;
}
int main() {
    int m;
    int n;
    scanf("%d", &m);
    scanf("%d", &n);
    for (int i = m; i < n; i++) {
        if (narcissus(i)) {
            printf("%d", i);
            printf("\n");
        }
    }
}

MIPS答案

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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
.data
	enter: .word '\n'
	
.eqv n, $s0
.eqv m, $s1
.eqv ten, $s2
.eqv hundred, $s3

.eqv a0, $t0
.eqv a1, $t1
.eqv a2, $t2
.eqv i, $t3
.eqv sum, $t4
.eqv temp, $t5

.macro done
	li $v0, 10
	syscall
.end_macro

.macro for_begin(%startLabel, %endLabel, %i, %start,%end)
	move %i, %start
	%startLabel:
	beq %i, %end, %endLabel
.end_macro

.macro for_end(%startLabel, %endLabel, %i)
	addi %i, %i, 1
	j %startLabel
	%endLabel:
.end_macro

.macro inputInt(%int)
	li $v0, 5
	syscall
	move %int, $v0
.end_macro

.macro printInt(%int)
	li $v0, 1
	move $a0, %int
	syscall
.end_macro

.macro printChar(%c)
	li $v0,  4
	la $a0, %c
	syscall
.end_macro

.macro square_add_to(%x, %sum)
	mult %x, %x
	mflo temp
	mult %x, temp
	mflo temp
	add sum, sum, temp
.end_macro

.macro narcissus(%x)
	li sum, 0
	div %x, ten
	mfhi a0
	square_add_to(a0, sum)
	div %x, hundred
	mfhi a1
	div a1, a1, 10
	square_add_to(a1, sum)
	div a2, %x, 100
	square_add_to(a2, sum)
	
	beq sum, %x, yes
	j no
	yes:
		printInt(%x)
		printChar(enter)
	no:
.end_macro

.text
	li ten, 10
	li hundred, 100
	
	inputInt(m)
	inputInt(n)
	for_begin(start0,end0,i,m,n)
		narcissus(i)
	for_end(start0,end0,i)

除法操作

实现除法有以下操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# 1
div $t0, $t1
mflo $t2 # $t0 % $t1 的结果存储在低位中
mfhi $t3 # $t0 // $t1的结果存储在高位中

# 2
div $t2, $t0, $t1 # $t2 = $t0 // $t1 (整数除法)

# 3
div $t0, $t1, 100 # $t0 = $t1 // 100 (除以16-bit立即数)

# 4
div $t0, $t1, 100000 # $t0 = $t1 // 100000(除以32-bit立即数)

# 5
srl $t0, 2 # $t0值向右移两位,即除以4

约瑟夫环问题

C语言代码

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
#include <stdio.h>
int a[100];

int main() {
    int n;
    int m;
    scanf("%d", &n);
    scanf("%d", &m);
    int i = 0;
    int count = 1;
    int flag = 1;

    while (1) {
        if (flag == n) {
            break;
        }
        if (a[i] == 1) {
            i = i + 1;
        }
        else {
            if (count == m) {
                a[i] = 1;
                flag++;
                i++;
                printf("%d", i);
                printf("\n");
                count = 1;
            } else {
                count++;
                i++;
            }
        }

        if (i == n) {
            i = 0;
        }
    }
    for (int i = 0; i < n; i++) {
        if (a[i] != 1) {
            printf("%d", i+1);
            break;
        }
    }
}

MIPS答案

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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
.data
	a: .space 400
	space: .word ' '
	enter: .word '\n'
.eqv n, $s0
.eqv m, $s1
.eqv one, $s2

.eqv i, $t0
.eqv count, $t1
.eqv flag, $t2
.eqv temp, $t3

.macro load_data(%arr, %index, %value)
	sll $t9, %index, 2
	lw %value, %arr($t9)
.end_macro

.macro store_data(%arr, %index, %value)
	sll $t9, %index, 2
	sw %value, %arr($t9)
.end_macro

.macro for_begin(%startLabel, %endLabel, %i, %start,%end)
	move %i, %start
	%startLabel:
	beq %i, %end, %endLabel
.end_macro

.macro for_end(%startLabel, %endLabel, %i)
	addi %i, %i, 1
	j %startLabel
	%endLabel:
.end_macro

.macro inputInt(%int)
	li $v0, 5
	syscall
	move %int, $v0
.end_macro

.macro printInt(%int)
	li $v0, 1
	move $a0, %int
	syscall
.end_macro

.macro printChar(%c)
	li $v0,  4
	la $a0, %c
	syscall
.end_macro

.macro done
	li $v0, 10
	syscall
.end_macro

.text
	inputInt(n)
	inputInt(m)
	
	li i, 0
	li count, 1
	li flag, 1
	li one, 1
	while:
		beq flag, n, break_
		load_data(a, i, temp)
		beq temp, $0, else
		add_:
			addi i, i, 1
			j while_end
		else:
			beq count, m, yes
			no:
				addi count, count, 1
				addi i, i, 1	
				j while_end
			yes:
				store_data(a,i,one)
				addi flag, flag, 1
				addi i, i, 1
				printInt(i)
				printChar(enter)
				li count, 1
		while_end:
			beq i, n, mod
			j skip
			mod:
				li i, 0
			skip:
			j while
	
	break_:
	
	for_begin(start0, end0, i, $0, n)
		load_data(a, i, temp)
		beq temp, $0, find
		j skip2
		find:
			addi i, i, 1
			printInt(i)
			j break2
		skip2:
	for_end(start0, end0, i)
	
	break2:
	done

练习题

回文串判断

其实用了足够多的封装之后,对于一些简单的MIPS题目已经不用特意写一遍C语言了

MIPS答案

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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
.data
	arr: .space 80

.eqv n, $s0
.eqv m, $s1
.eqv flag, $s2
.eqv i, $t0
.eqv temp, $t1
.eqv temp1, $t2
.eqv temp2, $t3
.macro load_data(%arr, %index, %value)
	li $t9, 4
	mult $t9, %index
	mflo $t9
	lw %value, arr($t9)
.end_macro

.macro store_data(%arr, %index, %value)
	li $t9, 4
	mult $t9, %index
	mflo $t9
	sw %value, arr($t9)
.end_macro

.macro done
	li $v0, 10
	syscall
.end_macro

.macro inputInt(%int)
	li $v0, 5
	syscall
	move %int, $v0
.end_macro

.macro inputChar(%c)
	li $v0, 12
	syscall
	move %c, $v0
.end_macro

.macro printInt(%int)
	li $v0, 1
	move $a0, %int
	syscall
.end_macro

.macro printImmediate(%imm)
	li $v0, 1
	li $a0, %imm
	syscall
.end_macro

.macro for_begin(%startLabel, %endLabel, %i, %start, %end)
	move %i, %start
	%startLabel:
	beq %i, %end, %endLabel
.end_macro

.macro for_end(%startLabel, %endLabel, %i)
	addi %i, %i, 1
	j %startLabel
	%endLabel:
.end_macro

.text
	inputInt(n)
	for_begin(start1, end1, i, $0, n)
		inputChar(temp)
		store_data(arr, i, temp)
	for_end(start1, end1, i)
	
	srl m, n, 1
	li flag, 1
	for_begin(start2, end2, i, $0, m)
		load_data(arr, i, temp1)
		sub temp, n, i
		subi temp, temp, 1
		load_data(arr, temp, temp2)
		beq temp1, temp2, skip
		li flag, 0
		skip:
	for_end(start2, end2, i)
	
	beq flag, 1, yes
	no:
		printImmediate(0)
		j flag_end
	yes:
		printImmediate(1)
	flag_end:
		done

全排列生成

参考往年题中的倒序全排列

矩阵相乘

MIPS答案

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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
.data
	A:.space 256 # 8 * 8 * 4
	B:.space 256
	C:.space 256
	enter: .word '\n'
	space: .word ' ' 
.macro done
	li $v0, 10
	syscall
.end_macro

.macro inputInt(%int)
	li $v0, 5
	syscall
	move %int, $v0
.end_macro

.macro printInt(%int)
	li $v0, 1
	move $a0, %int
	syscall
.end_macro

.macro printStr(%str)
	li $v0, 4
	la $a0, %str
	syscall
.end_macro

.macro for_begin(%startLabel, %endLabel, %i, %start, %end)
	move %i, %start
	%startLabel:
	beq %i, %end, %endLabel
.end_macro

.macro for_end(%startLabel, %endLabel, %i)
	addi %i, %i, 1
	j %startLabel
	%endLabel:
.end_macro

# value = arr[i][k]
.macro load_arr(%arr, %i, %k, %value)
	sll $t9, %i, 3 # $t9 = i * 8
	add $t9, $t9, %k
	sll $t9, $t9, 2 
	lw %value, %arr($t9)
.end_macro

# arr[i][k] = value
.macro store_arr(%arr, %i, %k, %value)
	sll $t9, %i, 3 # $t9 = i * 8
	add $t9, $t9, %k
	sll $t9, $t9, 2 
	sw %value, %arr($t9)
.end_macro

.eqv n, $s0
.eqv i, $t0
.eqv k, $t1
.eqv f, $t2
.eqv temp, $t3
.eqv temp1, $t4
.eqv temp2, $t5
.eqv temp0, $t6
.text
	inputInt(n)
	for_begin(start1, end1, i, $0, n)
		for_begin(start2, end2, k, $0, n)
			inputInt(temp)
			store_arr(A,i,k,temp)
		for_end(start2, end2, k)
	for_end(start1,end1,i)
	
	for_begin(start3, end3, i, $0, n)
		for_begin(start4, end4, k, $0, n)
			inputInt(temp)
			store_arr(B,i,k,temp)
		for_end(start4, end4, k)
	for_end(start3,end3,i)
	
	for_begin(start5,end5,i,$0,n)
		for_begin(start6, end6, k, $0, n)
			li temp, 0
			for_begin(start7, end7, f, $0, n)
				load_arr(A,i,f,temp1)
				load_arr(B,f,k,temp2)
				mult temp1, temp2
				mflo temp0
				add temp, temp, temp0
			for_end(start7, end7, f)
			store_arr(C,i,k,temp)
		for_end(start6, end6, k)
	for_end(start5,end5,i)
	
	for_begin(start8, end8, i, $0, n)
		for_begin(start9, end9, k, $0, n)
			load_arr(C, i, k, temp)
			printInt(temp)
			printStr(space)
		for_end(start9, end9, k)
		printStr(enter)
	for_end(start8, end8, i)
	
	done

01迷宫(哈密顿回路)

分析

采用DFS(深度优先算法),从起点出发,向四个方向前进,并以没有到达过(vis[i][j]==0)以及不存在障碍(puzzle[i][j]==1)作为可以前进的判断依据,到达终点时将ans加一操作.

C语言代码

C语言中不建议使用goto语句,但这里为了翻译方便采用了该语句

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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
#include <stdio.h>
int n;
int m;
int i;
int k;
int start_x;
int start_y;
int end_x;
int end_y;
int puzzle[8][8];
int vis[8][8];
int ans;

void solve(int curr_x, int curr_y) {
    if (curr_x == end_x && curr_y == end_y){
        ans += 1;
        return ;
    }

    //up 
    if (curr_x == 0) {
        goto brk1;
    }
    if (vis[curr_x-1][curr_y] == 1){
        goto brk1;
    }
    if (puzzle[curr_x-1][curr_y] == 1){
        goto brk1;
    }
    vis[curr_x-1][curr_y] = 1;
    solve(curr_x-1,curr_y);
    vis[curr_x-1][curr_y] = 0;
    brk1:

    //right
    if (curr_y == m-1) {
        goto brk2;
    }
    if (vis[curr_x][curr_y+1] == 1){
        goto brk2;
    }
    if (puzzle[curr_x][curr_y+1] == 1){
        goto brk2;
    }
    vis[curr_x][curr_y+1] = 1;
    solve(curr_x,curr_y+1);
    vis[curr_x][curr_y+1] = 0;
    brk2:

    // down
    if (curr_x == n-1) {
        goto brk3;
    }
    if (vis[curr_x+1][curr_y] == 1){
        goto brk3;
    }
    if (puzzle[curr_x+1][curr_y] == 1){
        goto brk3;
    }
    vis[curr_x+1][curr_y] = 1;
    solve(curr_x+1,curr_y);
    vis[curr_x+1][curr_y] = 0;
    brk3:

    //left
    if (curr_y == 0) {
        goto brk4;
    }
    if (vis[curr_x][curr_y-1] == 1){
        goto brk4;
    }
    if (puzzle[curr_x][curr_y-1] == 1){
        goto brk4;
    }
    vis[curr_x][curr_y-1] = 1;
    solve(curr_x,curr_y-1);
    vis[curr_x][curr_y-1] = 0;

    brk4:

    return ;
}

int main() {
    scanf("%d", &n);
    scanf("%d", &m);
    for (i = 0; i < n; i++) {
        for (k = 0; k < m; k++) {
            scanf("%d", &puzzle[i][k]);
        }
    }
    scanf("%d", &start_x);
    scanf("%d", &start_y);
    scanf("%d", &end_x);
    scanf("%d", &end_y);

    start_x -= 1;
    start_y -= 1;
    end_y -= 1;
    end_x -= 1;
    vis[start_x][start_y] = 1;
    solve(start_x,start_y);

    printf("%d\n", ans);
}

MIPS答案

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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
.data
	puzzle:.space 256 # 8 * 8 * 4
	vis:.space 256

.macro done
	li $v0, 10
	syscall
.end_macro

.macro push(%x)
	subi $sp, $sp, 4
	sw %x, 0($sp)
.end_macro

.macro pop(%x)
	lw %x, 0($sp)
	addi $sp, $sp, 4
.end_macro

.macro inputInt(%int)
	li $v0, 5
	syscall
	move %int, $v0
.end_macro

.macro printInt(%int)
	li $v0, 1
	move $a0, %int
	syscall
.end_macro

.macro printStr(%str)
	li $v0, 4
	la $a0, %str
	syscall
.end_macro

.macro for_begin(%startLabel, %endLabel, %i, %start, %end)
	move %i, %start
	%startLabel:
	beq %i, %end, %endLabel
.end_macro

.macro for_end(%startLabel, %endLabel, %i)
	addi %i, %i, 1
	j %startLabel
	%endLabel:
.end_macro

.macro load_arr(%arr, %i, %k, %value)
	sll $t9, %i, 3
	add $t9, $t9, %k
	sll $t9, $t9, 2
	lw %value, %arr($t9)
.end_macro

.macro store_arr(%arr, %i, %k, %value)
	sll $t9, %i, 3
	add $t9, $t9, %k
	sll $t9, $t9, 2
	sw %value, %arr($t9)
.end_macro

.eqv n, $s0
.eqv m, $s1
.eqv start_x, $s2
.eqv start_y, $s3
.eqv end_x, $s4
.eqv end_y, $s5
.eqv ans, $s6
.eqv one, $s7

.eqv i, $t0
.eqv k, $t1
.eqv temp, $t2
.eqv curr_x, $t3
.eqv curr_y, $t4
.eqv temp1, $t5

.text
	li one, 1
	
	inputInt(n)
	inputInt(m)
	for_begin(start1, end1, i, $0, n)
		for_begin(start2, end2, k, $0, m)
			inputInt(temp)
			store_arr(puzzle, i, k, temp)
		for_end(start2, end2, k)
	for_end(start1, end1, i)
	
	inputInt(start_x)
	inputInt(start_y)
	inputInt(end_x)
	inputInt(end_y)
	
	subi start_x, start_x, 1
	subi start_y, start_y, 1
	subi end_x, end_x, 1
	subi end_y, end_y, 1
	move curr_x, start_x
	move curr_y, start_y
	store_arr(vis, curr_x, curr_y, one)
	jal solve
	

	printInt(ans)
	
	done
	
solve:
	push($ra)
	bne curr_x, end_x, skip
	bne curr_y, end_y, skip
		addi ans, ans, 1
		pop($ra)
		jr $ra
	skip:
		beqz curr_x, brk1
		subi temp1, curr_x, 1
		load_arr(vis, temp1, curr_y, temp)
		beq temp, one, brk1
		load_arr(puzzle, temp1, curr_y, temp)
		beq temp, one, brk1
		
		store_arr(vis, temp1, curr_y, one)
		push(curr_x)
		push(curr_y)
		subi curr_x, curr_x, 1
		jal solve
		pop(curr_y)
		pop(curr_x)
		subi temp1, curr_x, 1
		store_arr(vis, temp1, curr_y, $0)
	brk1:
		addi temp1, curr_y, 1
		beq temp1, m, brk2
		load_arr(vis, curr_x, temp1, temp)
		beq temp, one, brk2
		load_arr(puzzle, curr_x, temp1, temp)
		beq temp, one, brk2
		
		store_arr(vis, curr_x, temp1, one)
		push(curr_x)
		push(curr_y)
		addi curr_y, curr_y, 1
		jal solve
		pop(curr_y)
		pop(curr_x)
		addi temp1, curr_y, 1
		store_arr(vis, curr_x, temp1, $0)
	brk2:
		addi temp1, curr_x, 1
		beq temp1, n, brk3
		load_arr(vis, temp1, curr_y, temp)
		beq temp, one, brk3
		load_arr(puzzle, temp1, curr_y, temp)
		beq temp, one, brk3
		
		store_arr(vis, temp1, curr_y, one)
		push(curr_x)
		push(curr_y)
		addi curr_x, curr_x, 1
		jal solve
		pop(curr_y)
		pop(curr_x)
		addi temp1, curr_x, 1
		store_arr(vis, temp1, curr_y, $0)
	brk3:
		beqz curr_y, brk4
		subi temp1, curr_y, 1
		load_arr(vis, curr_x, temp1, temp)
		beq temp, one, brk4
		load_arr(puzzle, curr_x, temp1, temp)
		beq temp, one, brk4
		
		store_arr(vis, curr_x, temp1, one)
		push(curr_x)
		push(curr_y)
		subi curr_y, curr_y, 1
		jal solve
		pop(curr_y)
		pop(curr_x)
		subi temp1, curr_y, 1
		store_arr(vis, curr_x, temp1, $0)
	brk4:
		
	pop($ra)
	jr $ra

易错点

  • 当调用递归函数时,若函数中可能出现多次递归,我们必须将:
    • 作为函数参数的寄存器入栈再调用递归函数,退出递归后再退栈,保持函数参数不变($a1,$a2,...)
    • 用来记录状态的数组在调用递归函数前的修改,应当在退出递归后修改回原值,比如本题中的vis
    • 若递归出现在for循环,while循环中,必须将作为循环参数的i,k等入栈保存,其他递归函数中会修改的寄存器同理($t0,$t1,...)

矩阵卷积

C语言代码

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
#include <stdio.h>
int A[100][100];
int B[100][100];
int C[100][100];
int temp;
int i;
int k;
int ii;
int kk;
void evolv(int A[][100], int B[][100], int C[][100], 
        int m1, int n1, int m2, int n2) {
    for(i = 0; i < m1 - m2 + 1; i++) {
        for (k = 0; k < n1 - n2 + 1; k++) {
            temp = 0;
            for (ii = 0; ii < m2; ii++) {
                for (kk = 0; kk < n2; kk++) {
                    // printf("%d %d \n", ii + i, kk + k);
                    temp = temp + A[ii+i][kk+k] * B[ii][kk];
                }
            }
            C[i][k] = temp;
        }
    }
    return ;
}
int main(){
    int m1, n1, m2, n2;
    scanf("%d", &m1);
    scanf("%d", &n1);
    scanf("%d", &m2);
    scanf("%d", &n2);

    for(i = 0; i < m1; i++) {
        for (k = 0; k < n1; k++) {
            scanf("%d", &A[i][k]);
        }
    }

    for(i = 0; i < m2; i++) {
        for (k = 0; k < n2; k++) {
            scanf("%d", &B[i][k]);
        }
    }

    evolv(A,B,C,m1,n1,m2,n2);

    for(i = 0; i < m1-m2+1; i++){
        for (k = 0; k < n1-n2+1; k++) {
            printf("%d ", C[i][k]);
        }
        printf("\n");
    }
}

MIPS答案

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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
.data
	A:.space 2000 # 10 * 10 * 4 = 400
	B:.space 2000
	C:.space 2000
	enter: .word '\n'
	space: .word ' ' 
	
.macro done
	li $v0, 10
	syscall
.end_macro

.macro inputInt(%int)
	li $v0, 5
	syscall
	move %int, $v0
.end_macro

.macro printInt(%int)
	li $v0, 1
	move $a0, %int
	syscall
.end_macro

.macro printStr(%str)
	li $v0, 4
	la $a0, %str
	syscall
.end_macro

.macro for_begin(%startLabel, %endLabel, %i, %start, %end)
	move %i, %start
	%startLabel:
	beq %i, %end, %endLabel
.end_macro

.macro for_end(%startLabel, %endLabel, %i)
	addi %i, %i, 1
	j %startLabel
	%endLabel:
.end_macro

# value = arr[i][k]
.macro load_arr(%arr, %i, %k, %value)
	sll $t9, %i, 4 # $t9 = i * 16
	add $t9, $t9, %k
	sll $t9, $t9, 2 
	lw %value, %arr($t9)
.end_macro

# arr[i][k] = value
.macro store_arr(%arr, %i, %k, %value)
	sll $t9, %i, 4 # $t9 = i * 16
	add $t9, $t9, %k
	sll $t9, $t9, 2 
	sw %value, %arr($t9)
.end_macro

.eqv n1, $s0
.eqv m1, $s1
.eqv m2, $s2
.eqv n2, $s3

.eqv m1_m2_1, $s4
.eqv n1_n2_1, $s5

.eqv i, $t0
.eqv k, $t1
.eqv temp3, $t2
.eqv temp, $t3
.eqv temp1, $t4
.eqv temp2, $t5
.eqv temp0, $t6
.eqv ii, $t7
.eqv kk, $t8

.text
	inputInt(m1)#行数
	inputInt(n1)#列数
	inputInt(m2)
	inputInt(n2)
	
	# 读取待卷积矩阵
	for_begin(start1, end1, i, $0, m1)
		for_begin(start2, end2, k, $0, n1)
			inputInt(temp)
			store_arr(A, i, k, temp)
		for_end(start2, end2, k)
	for_end(start1, end1, i)
	
	#读取卷积核
	for_begin(start3, end3, i, $0, m2)
		for_begin(start4, end4, k, $0, n2)
			inputInt(temp)
			store_arr(B, i, k, temp)
		for_end(start4, end4, k)
	for_end(start3, end3, i)
	
	#m1-m2+1
	sub m1_m2_1, m1, m2
	addi m1_m2_1, m1_m2_1, 1
	
	sub n1_n2_1, n1, n2
	addi n1_n2_1, n1_n2_1, 1
	
	#卷积
	for_begin(start5, end5, i, $0, m1_m2_1)
		for_begin(start6, end6, k, $0, n1_n2_1)
			 li temp, 0
			 for_begin(start7, end7, ii, $0, m2)
			 	for_begin(start8, end8, kk, $0, n2)
			 		add temp3, ii, i
			 		add temp0, kk, k
			 		load_arr(A, temp3, temp0, temp1)
			 		load_arr(B, ii, kk, temp2)
			 		mult temp1, temp2
			 		mflo temp0
			 		add temp, temp, temp0
			 	for_end(start8, end8, kk)
			 for_end(start7, end7, ii)
			 store_arr(C, i, k, temp)
		for_end(start6,end6,k)
	for_end(start5, end5, i)
	
	#打印卷积结果
	for_begin(start9, end9, i, $0, m1_m2_1)
		for_begin(start10, end10, k, $0, n1_n2_1)
			load_arr(C, i, k, temp)
			printInt(temp)
			printStr(space) 
		for_end(start10, end10, k)
		printStr(enter)
	for_end(start9,end9, i)
	
	done

高精度阶乘的计算

C语言代码

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
#include "stdio.h"
#define MAX 10000
int f[MAX];
void Arr_reset(int a[],int m,int n)
{
    int i;
    for(i=m;i<=n;i++)
    {
        a[i]=0;
    }
}
int main(void)
{
    int i,j,n;
    scanf("%d",&n);
    Arr_reset(f,0,(sizeof(f)/sizeof(int)));//对数组进行初始化
    f[0]=1;
    int jj= 0 ;
    for(i=2;i<=n;i++)
    {
        //乘以 i4
        int c=0;

        for(j=0;j<=jj;j++)//最不易理解的
        {
            int s=f[j]*i+c;
            f[j]=s%10;
            c=s/10;
            if (j == jj && c != 0){
                jj++;
            }
            //算出的 s 是单位数时，会连续覆盖 f[0]
            //否则一个多位数会倒过来存储，如 123，f[0]存 3，f[1]存 2，f[3]存 1
            //因此上式先求余，在求模
        }
    }
    printf("jj=%d\n", jj);
    for(j=MAX-1;j>=0;j--)
        if(f[j])
            break;//忽略前导 0
    for(i=j;i>=0;i--)
        printf("%d",f[i]);
    printf("\n");
    return 0;
}

MIPS答案

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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
.data
	a:.space 4000
	enter:.word '\n'
	
.macro done
	li $v0, 10
	syscall
.end_macro

.macro inputInt(%int)
	li $v0, 5
	syscall
	move %int, $v0
.end_macro

.macro printInt(%int)
	li $v0, 1
	move $a0, %int
	syscall
.end_macro

.macro printStr(%str)
	li $v0, 4
	la $a0, %str
	syscall
.end_macro

.macro for_begin(%startLabel, %endLabel, %i, %start, %end)
	move %i, %start
	%startLabel:
	beq %i, %end, %endLabel
.end_macro

.macro for_c_begin(%startLabel, %endLabel, %i, %start, %end)
	move %i, %start
	%startLabel:
	bgt %i, %end, %endLabel
.end_macro

.macro for_decrease_begin(%startLabel, %endLabel, %i, %start, %end)
	li %i, %start
	subi %i, %i, 1
	%startLabel:
	blt %i, %end, %endLabel
.end_macro

.macro for_decrease_c_begin(%startLabel, %endLabel, %i, %start, %end)
	move %i, %start
	%startLabel:
	blt %i, %end, %endLabel
.end_macro

.macro for_decrease_end(%startLabel, %endLabel, %i)
	subi %i, %i, 1
	j %startLabel
	%endLabel:
.end_macro

.macro for_end(%startLabel, %endLabel, %i)
	addi %i, %i, 1
	j %startLabel
	%endLabel:
.end_macro

.macro load_arr(%arr, %index, %value)
	sll $t9, %index, 2
	lw %value, %arr($t9)
.end_macro

.macro store_arr(%arr, %index, %value)
	sll $t9, %index, 2
	sw %value, %arr($t9)
.end_macro


.eqv i, $t0
.eqv k, $t1
.eqv s, $t2
.eqv temp, $t3
.eqv c, $t4
.eqv jj, $t5
.eqv n, $s0
.eqv two, $s1
.eqv ten, $s2
.eqv max, $s3
.eqv one, $s4
.eqv MAX, 1000

.text
	li one, 1
	li two, 2
	li ten, 10
	li max, MAX
	#for_c_begin(start0, end0, i, $0, MAX)
		#store_arr(a, i, 0)
	#for_end(start0, end0, i)
	
	inputInt(n)
	store_arr(a, $0, one)
	li jj, 0
	for_c_begin(start1, end1, i, two, n) # 2<=i<=n
		li c, 0
		for_c_begin(start2, end2, k, $0, jj)
			load_arr(a, k, temp)
			mult temp, i
			mflo s
			add s, s, c # s = a[k] * i + c
			div s, ten
			mfhi temp
			mflo c # c = s / 10
			store_arr(a, k, temp) # a[k] = s % 10
			beqz c, skip
			bne k, jj, skip
			addi jj, jj, 1
			skip: 
		for_end(start2, end2, k)
	for_end(start1, end1, i)
	
	for_decrease_c_begin(start4, end4, i, jj, $0) #k>=i>=0
		load_arr(a, i, temp)
		printInt(temp)
	for_decrease_end(start4, end4, i)
	
	printStr(enter)
	done

易错点

  • 超时问题,题目所给字符串为1000,为了避免每次循环都要进行1000次,我们设立一个参数jj,用来记录计算答案可能到达的最高位
    • 初始,jj=0
    • 在for循环中,若循环参数j==jj,且此时向高一位传递的数不为0(c!=0),则对jj加一操作
  • load_arr与store_arr中不要用mult,这样涉及的寄存器会增多,且指令数会暴增,必须用sll.

上机

P2_Q1 发糖

取K个糖,分发给n个人,要求每个人得到的糖果数量相同,剩下糖果若不够给每个人发一个,则视为剩余的糖果.现要求\(L\leq K\leq R\),保证n个人能得到的糖果最多,同时剩余的糖果最少.只输出剩余的糖果数量.

思路

若L和R能发给同学的数量相同,即\(\lfloor \frac{L}{n}\rfloor=\lfloor \frac{R}{n}\rfloor\),则K取最小值即可,此时剩余糖果数量为\(L\%n\),若若L和R能发给同学的数量不相同,则K取\(\lfloor \frac{R}{n}\rfloor\times n\)个,剩余糖果数量一定为0

C语言

1
2
3
4
5
6
7
8
9
10
#include <stdio.h>
int main() {
    int n, L, R;
    scanf("%d %d %d", &n, &L, &R);
    if (L / n == R / n) {
        printf("%d", L % n);
    } else {
        printf("0");
    }
}

P2_Q2 欧拉筛

利用欧拉筛判断n是否为素数

P2_Q3 有向图dfs

输入一个有向图,输出从一个规定起点出发能找到的死角(出度为0的点)个数,起点为死角则输出0

易错点

这道题只是一个翻译题,考察对递归函数的使用,但上级时出现了一些细节上的错误:

  • 寄存器重复赋别名,导致了多个变量共用一个寄存器,运行结果中出现了超时的问题,很遗憾没能早点发现for循环的参数和别的变量弄混了.
  • 宏中的变量没有用%作为前缀,导致了本该是%arr的地方出现了arr,调用宏时指向了错误数组地址
#CO #MIPS
计组P2总结
https://meteor041.git.io/2024/10/07/计组P2总结/
作者
meteor041
发布于
2024年10月7日
许可协议