北航计算机组成P2推荐题目汇总

前言

题目怎么来的就不再赘述，有感兴趣的同学可以走这里北航计算机组成P1推荐题汇总

P2推荐题目汇总

1202-35 calculate

注意题目要求的是按照输入的顺序输出计数的字符，不是按照ascii码表的位置
我开了两个数组一个记录26个字母的数量，一个记录出现的顺序(重复出现的字母不会进行第二遍)，最后遍历记录出现顺序的数组即可
还有一个小小的点：因为样例看起来是一行读入一个字符，实际测评机是一个接一个的字符读入，所以不需要处理\n(我刚开始就处理了，导致报了一个非法读入的错误)
.macro read_chr(%chr)
li $v0, 12
syscall
move %chr, $v0

# 不需要处理字母后面的\n
# li $v0, 12
# syscall
.end_macro

提供一个有处理是否有重复输入的代码块

 .text
	for_z_begin: # 用于判断是否出现过这个字符
		beq $t2, $s1, for_z_end # 对目前出现的所有字符遍历 
		sll $t3, $t2, 2 
		lw $t4, buffer($t3) # 读出第$t2个已有字符
		sub $t4, $t4, $t1 # 判断是否为同一个字符
		if_begin_1:
			bne $t4, $zero, if_end_1 # 如果不是则跳转
			j not_for_z_end # 如果是则直接结束这段内容
		if_end_1:
		addi $t2, $t2, 1
		j for_z_begin
	for_z_end:
		sll $t3, $t2, 2 # 存入新读入的字符
		sw $t1, buffer($t3)
		addi $s1, $s1, 1
	not_for_z_end:
	
	sll $t1, $t1, 2 # 找到指定字母的偏移字节
	
	lw $t2, num($t1)
	addi $t2, $t2, 1 # 找到的字母加1
	sw $t2, num($t1)
	
	addi $t0, $t0, 1 # 循环继续条件
	j for_i_begin
for_i_end:

1202-52 add

看上去有点麻烦而已，其实完全可以使用一个矩阵接收两次数字完成两次加法(因为所有内存起始值赋值为0)
最后的转置也只是需要将原来的嵌套for循环中的先row后col 改为 **先col后row**就可以了

同样提供一个有大致思路的main模块

 .text
read_in($s0) # 读入n
read_in($s1) # 读入m

li $s2, 2 # 直接设置读入两次
li $t0, 0 # 设置循环变量i
# 双重for循环读入

print_str(hint) # 打印题目要求的hint信息
# 双重for循环打印

1202-53 full_reserved

对于全排列问题(顺序)，可以考虑下面的思路(只想看汇编内容可以跳过，这里主要讲的是全排列是如何写的)
- 我们以1234四个数字举例，开头为1和2的情况
- 1:1234 1243 1324 1342 1423 1432
- 2:2134 2143 2314 2341 2413 2431
- 可以发现，以某个数字开头的全排列其实是以这个数字开头加上剩下所有数字按相对大小重新构成的数字队列的全排列
- 例如1与234的全排列构成1234以1开头的全排列;2与134的全排列构成了1234以2开头的全排列，所以就可以写递归程序了(雾)
- 所以所给递归程序的symbol全局数组是用来记录这个开头的数字
题目要求你改写逆序的全排列汇编程序
- 最方便的思路就是打印的时候不打印array[i]而打印n+1-array[i]这样相当于用n....1来全排列
- 当然，如果你理解了这个C语言程序如何运作的，可以将for循环的顺序反过来，从最高位n来开始，思路同上面的讲解思路
仔细考虑入栈出栈情况，如果使用栈传递参数记得开始时就要先出栈，$ra的保留值在任何一个程序的返回点都要弹出，总之入栈则一定要出栈(虽然有点像废话，但某些地方真的必须考虑清楚)，切记

给出一个可以参考的FullArray函数的模板

full_array:
    addi $sp, $sp, -8 # 给出一定的栈空间
    sw $a0, 4($sp) # 压栈
    sw $ra 0($sp) 
    move $t0, $a0 # t0代表index
    if_begin:
        sltu $t2, $t0, $s0 # 判断index与n的大小
        bne $t2, $zero, if_end
        
        li $t1, 0 # 设置循环变量i
        for_i_begin:
            beq $t1, $s0, for_i_end 
            sll $t2, $t1, 2 
            lw $t3, array($t2) # 得到array[i]
            sub $t3, $zero, $t3
            addi $t4, $s0, 1
            add $t3, $t3, $t4 # 得到n+1-array[i]
            print_int($t3) # 打印这个值
            print_str(space) # 打印空格
            addi $t1, $t1, 1 # 循环i继续条件
            j for_i_begin
        for_i_end:
        print_str(enter) # 打印换行
        add $sp, $sp ,8 # 注意出栈，这里可以不用弹出值，但是一定要栈空间减少
        jr $ra # 返回
    if_end:
        
    # else执行的for循环递归
    addi $sp, $sp, 8 # 将刚开始保留的参数弹出
    lw $a0, -4($sp)
    lw $ra -8($sp)	
    
    jr $ra # 返回

1202-329 sum

大概就是一个变量保留 $n!$ 的值，一个变量保留 $\sum\limits_{i=1}^n i!$，然后进行递推就可以了，千万不要递归啊(雾，大概率会爆吧

提供一个可参考的main模板

main:
    read($s0)
    li $s1, 0
    li $s2, 1
    li $t0, 1
    li $s3, 1
    for_start:
        sltu $s3, $s0, $t0
        bne $s3, $zero, for_end
        multu $t0, $s2
        mflo $s2
        addu $s1, $s1, $s2
        addi $t0, $t0, 1
        j for_start
    for_end:
        printU($s1)
        done

1202-330 hanoi

诶呀，~~是大一写的递归程序呢~~
不论是C语言代码的理解和整体程序都没有难点，所以注意的只有压栈弹栈时候小心即可！
因为函数参数过多，所以我采用了用栈传输参数的思路，所以要更加小心，哪些部分是保存参数、弹出参数，哪些部分是传递参数、接收参数

本题给出了关于模板字符串的提示，虽然没法用占位符

format_str: .asciiz "move disk D from C to C\n"
.macro print(%disk, %from, %to)
    li $t7, 10
    addi $t6, %disk, 48
    sb $t6, format_str($t7)
    
    li $t7, 17
    sb %from, format_str($t7)
    
    li $t7, 22
    sb %to, format_str($t7)
    
    la $a0, format_str
    li $v0, 4
    syscall
.end_macro

同样，给出参考的模板

main:
    read_in($t0) # 读入n
    li $t1, 65
    li $t2, 66
    li $t3, 67
    la $sp, stack
    addi $sp, $sp, 800 # 初始化参数与stack
    
    push($t0) # 传参数
    ...
    jal hanoi
    
    end

hanoi:
    pop($t3) # 接收参数
    ...
    push($ra) # 保存返回值
    if_begin:
        bne $t0, $zero, if_end
        print($t0, $t1, $t2)
        print($t0, $t2, $t3)
        pop($ra) # 弹返回地址
        jr $ra
    if_end:
    
    push($t0) # 保存参数
    ...

    addi $t0, $t0, -1
    push($t0) # 传递参数
    ...
    jal hanoi
    
    pop($t3) # 取出保留的参数
    ...
    print($t0, $t1, $t2)
    
    ...若干递归

1202-415 bsearch

二分查找！！！
因为已经给出了C语言参考模板了，没有的话或许有同学会因为不清楚[low,high]还是[low,high)两种查找方式的区别，而写出一些小bug
注意slt与sltu因为如果查找的key比数组中最小的值还要小的话，那么最后得到的值是-1，但是-1在无符号数中是最大的，会出现死循环哦

直接给出可参考的模板了

binary_search:
    push($s1)
    move $s1, $a0 # key
    li $t0, 0 # low
    addi $t1, $s0, -1 # high
    li $t2, 0 # mid
    
    while_begin:
        slt $t5, $t1, $t0
        bne $t5, $zero, while_end
        
        add $t2, $t0, $t1
        srl $t2, $t2, 1
        
        //判断arr[mid]与key的大小
        j while_begin
    while_end:

    li $t5, 0
    print($t5)
    pop($s1)
    jr $ra

1202-416 flower

简单汇编，直接给出可参考的模板

main:
    read_in($t0) # 读入m
    read_in($s0) # 读入n
    
    for_i_begin:
        beq $t0, $s0, for_i_end
        divu $t1, $t0, 100
        
        mul $t2, $t1, 100
        sub $t4, $t0, $t2
        divu $t2, $t4, 10
        
        mul $t3, $t2, 10
        sub $t3, $t4, $t3
        
        mul $t4, $t1, $t1
        mul $t4, $t4, $t1
        
        mul $t5, $t2, $t2
        mul $t5, $t5, $t2
        add $t4, $t4, $t5
        
        mul $t5, $t3, $t3
        mul $t5, $t5, $t3
        add $t4, $t4, $t5
        
        if_begin:
            bne $t4, $t0, if_end
            print($t0)
        if_end:
        add $t0, $t0, 1
        j for_i_begin
    for_i_end:
    end

1202-419 josef

也是一道大一写的题目呢，~~小海豚~~
其实刚开始我想如果暴力数组没过的话就用循环链表了(没想都暴力可以直接过)
这里主要通过一个数组记录某个编号是否已经被删除了
计数就是数组下标加一，遇到等于数组长度时自动返回0

给出一个可以参考的模板

read($s0) # 读入人数n
read($s1) # 读入报数m

li $t0, 0 # 报数的人的编号
li $t1, 0 # 外层循环变量i,将所有人都出局为止
li $t2, 1 # 设置第一次数数
for_start_i:
    beq $t1, $s0, for_end_i # 达到最大人数结束循环
    for_start_j:
        beq $t2, $s1, for_end_j # 达到报数最大值
        
        //使用while循环处理报数，去除已经out的人
    for_end_j:
        sll $t4, $t0, 2
        li $t5, 1
        sw $t5, people($t4) # 记录出局的人，置1
        addi $t5, $t0, 1 # 打印出局的人的编号
        print($t5)
        li $t2, 0 # 设置每次j的
        addi $t1, $t1, 1 # 循环继续条件
        j for_start_i
for_end_i:
    done