coPre测试题目与解析

Pre共有三道题，分别考察了MIPS、Verilog和Logisim，考试时间2小时。
以下试题内容均为回忆版，还请见谅。

第一题：supaltitude

题干

阿庄哥（随便起的名字）从某处开始沿着山路骑车。设起点的相对海拔为$0$，从起点到终点一共经过了$n$个记录点，给出该记录点与前一个记录点的相对海拔差，输出整个过程中所处的最高相对海拔值。

输入

• 一个正整数$n$，表示从起点开始总共经过的记录点的个数；
• 一个数组$a[n]$，其中$a[i]$表示第$i$个记录点相对于第$i-1$个检查点的相对海拔差；
• 输入数据保证$0 \le n \le 128$, $-128 \le a[i] \le 128$。

输出

• 一个整数，表示整个过程中所处的最高相对海拔值。

样例1

输入

7
3
-1
-4
1
5
-3
1

输出

4

样例2

输入

6
-4
-3
-2
-1
4
4

输出

0

分析

首先需要考虑的是，需不需要开辟数组空间？

题目的本质是想要我们求连续子数组的最大和，所以其实只需要每次读入一个数，更新当前的前缀和，并与最大前缀和对比即可，并不需要开辟数组空间。

前缀和：从nums数组第0个数开始累加，到第$i$个位置的累加结果。

清楚题意之后，我们可以尝试写出以下c语言代码：

#include<stdio.h>
int main(void)
{
    int max = 0, sum = 0, n, a;
    // max是最大前缀和，sum是当前前缀和
    scanf("%d", &n);
    for(int i = 0; i < n; i++)
    {
        scanf("%d", &a);
        sum += a;
        if(max < sum)
            max = sum;
    }
    printf("%d", max);
}

我们在Pre的MIPS汇编程序设计中已经学习了条件语句和循环语句的写法：

.text
li $t1, 100             #t1 = 100
li $t2, 200             #t2 = 200
slt $t3, $t1, $t2       #if(t1 < t2) t3 = 1 
beq $t3, $0, if_1_else
nop
#do something
j if_1_end              #jump to end
nop
if_1_else:
#do something else

if_1_end:
li $v0, 10
syscall

.text
li $t1, 100             #n = 100
li $t2, 0               #i

for_begin1:             #for (int i = 0; i < n; i++)
slt $t3, $t2, $t1       #{
beq $t3, $0, for_end1  
nop      
#do something
addi $t2, $t2, 1        #i++
j for_begin1
nop                     #}  

for_end1:
li $v0, 10
syscall

基于以上分析与所学知识，我们便可以完成所需的MIPS程序。

提示：

• 对于MIPS程序设计题，先写出可解决该问题的C语言程序代码，再逐句“翻译”成对应的MIPS指令，是一种值得尝试的选择；
• 编写MIPS代码时可以添加一些空格、缩进、标签、注释等，增强代码的可读性。

解答

main:
	li   $v0, 5
	syscall
	move $s0, $v0 #n = $v0 = $s0
	li   $s1, 0   #max = 0
	li   $s2, 0   #sum = 0
	li   $t0, 0   #i = 0
for_loop:
	beq  $t0, $s0, for_loop_end
	li   $v0, 5
	syscall
	move $t1, $v0
	add  $s2, $s2, $t1
	ble  $s2, $s1, else
	if:
		move $s1, $s2
	else:
	addi $t0, $t0, 1
	j    for_loop

for_loop_end:
	move $a0, $s1
	li   $v0, 1
	syscall
	li   $v0, 10
	syscall

第二题：noDescendSequence

题干

“不下降数”表示一个整数的高位数码不会大于低位数码。例如，$1234$、$1223$是“不下降数”，而$1243$不是“不下降数”。

使用Verilog构建一个判断一个4位16进制数输入是否为“不下降数”的电路。

端口定义如下：

信号名	方向	描述
in[15:0]	I	接受带判断的数字
out	O	如果是“不下降数”，返回1； 否则，返回0

分析

这道题很简单，只需要把in的四个数码分别比较即可。

在完成模块的设计后，最好使用testbench进行测试。

解答

module noDescendSequence(
	input [15:0] in,
	output out
	);
	assign out = (in[15:12] <= in[11:8] && in[11:8] <= in[7:4] 
	&& in[7:4] <= in[3:0]) ? 1'b1 : 1'b0;
endmodule

第三题：tetris

忘了题目了，好像是Mealy型自动机，大家全面准备吧:)