BUAA_CO_P2

`P2`汇编语言

[toc]

宏定义

P2_L0_Matrix和P2_L1_factorial涉及矩阵读入，运算与输出。可以使用一些宏定义可以增加代码可读性：

.data
str_enter : .asciiz "\n"         # .asciiz 伪指令用于定义一个以空字符结尾的字符串常量。
str_space : .asciiz " "          # .ascii 伪指令不包含结尾处的空字符

.macro printSpace                # 输出一个空格
    la $a0, str_space            # 用于将标签或变量的地址加载到指定的寄存器中。
    li $v0, 4
    syscall    
.end_macro    

.macro printEnter                # 输出一个换行符
    la $a0, str_enter
    li $v0, 4
    syscall                 
.end_macro

.macro getInt(%des)              # 读入一个整数到指定的寄存器
    li $v0, 5
    syscall
    move %des, $v0
.end_macro

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

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

由于矩阵是储存在内存堆中的，矩阵运算需要频繁的涉及访存操作，用宏定义简化该过程：

.data
matrix : .space 256             # 申请256字节连续空间用以储存矩阵

#### 使用宏定义简化访存操作
.macro save(%desn, %dest, %desi, %desj)  # 把寄存器%dest的值存入matrix[i][j]
    mult %desn, %desi            # Lo = n * i
    mflo $t3                     # t3 = n * i
    add  $t3, $t3, %desj         # t3 = n * i + j
    sll  $t3, $t3, 2             # offset = t3 = t3 << 2
    sw %dest, matrix($t3)        # matrix[i][j] = t0
.end_macro

.macro get(%desn, %des, %desi, %desj)  # 把matrix[i][j]的值存入寄存器%dest
    mult %desn, %desi            # Lo = n * i
    mflo $t3                     # t3 = n * i
    add  $t3, $t3, %desj         # t3 = n * i + j
    sll  $t3, $t3, 2             # offset = t3 = t3 << 2
    lw %des, matrix($t3)         # matrix[i][j] = t0
.end_macro

P2_L0_full和P2_L1_puzzle涉及到递归操作，这需要频繁的入栈和出栈操作。我们同样通过宏定义的方式来简化该过程：

.macro push(%src)                # 入栈
    addi $sp, $sp, -4
    sw %src, 0($sp)
.end_macro

.macro pop(%des)                 # 出栈
    lw %des, 0(sp)
    addi $sp, $sp, 4
.end_macro

`DFS`（深度优先搜索）

#include<stdio.h>
int n,m,x0,y0,x2,y2,sum,map[7][7];     // 维护一个数组map来表示地图上当前点是否已被访问
void DFS(int x,int y) {
    map[x][y] = 1;
    if (x == x2 && y == y2) {          // DFS的起点恰好是所要搜索的终点 return
        sum++;
        map[x][y] = 0;
        return;
    }
    if (y > 0 && map[x][y-1] == 0) {   // 如果(x,y)旁边的点未被访问，从其旁边的点开始深度优先搜索 
        DFS(x,y-1);
    }
    if (x > 0 && map[x-1][y] == 0) {
        DFS(x-1,y);
    }
    if (y + 1 < m && map[x][y+1] == 0) {
        DFS(x,y+1);
    }
    if (x + 1 < n && map[x+1][y] == 0) {
        DFS(x+1,y);
    }
    map[x][y] = 0;
}

高精度阶乘

这里直接介绍一种时间复杂度较低的算法：

#include <stdio.h>
// 输出结果不超过1000位， 对应n_max = 450
int ans[1000];                          // 输出数组
int lenth;                              // 维护输出数组的长度

void mult (int x) { 
    int j = 0;
    int temp = 0;                       // 高精度数每一位与低精度数的乘积 
    int carry = 0;
    for (j = 0; j < lenth; j++) {
        temp = ans[j] * x;
        temp += carry;
        ans[j] = temp % 10;
        carry = temp / 10;              // carry最多可以是3位 
    }

    if (carry > 99) {                   // 最高位的进位大于等于100
        ans[j] = carry % 10;
        ans[j+2] = carry / 100;
        ans[j+1] = (carry - ans[j+2] * 100) / 10;
        lenth += 3;
    } else if (carry > 9) {             // 最高位的进位大于等于10 
        ans[j] = carry % 10;
        ans[j+1] = carry / 10;
        lenth += 2;
    } else if (carry > 0) {             // 最高位的进位大于等于1
        ans[j] = carry;
        lenth += 1;
    }                                   // 最高位无进位
}

int main() {
    int i,n;
    scanf("%d",&n);
    ans[0] = 1;
    lenth = 1;       // 初始化
    for (i = 1; i < n + 1; i++) {
        mult(i);
    }
    for (i = lenth - 1; i > -1; i--) {
        printf("%d",ans[i]);
    }
    return 0;
}