计组上机

Pre

第一题（Logisim）

题目大意：输出一个持续填入数组的当前数an。而an根据输入端type做相应的变化：

type == 0 , an = 0

type == 1 , an = an-1 + 1，a0 == 0

type == 2 , an = a1 + …… + an-1

并且要求有一个reset复位输入端实现同步复位的功能，且电路外观一定要如下（一定不同都不能有）：

电路外观

且要求是Moore状态机（输出值只与有限状态机当前状态值有关区别于Mealy状态机(输出值不仅同状态机当前状态值有关还与当前输入值有关）。

第一”坑“：因为如果左侧从上到下依次放输入，右端放一个输出的logisim默认电路外观是如下的图，在这种情况下评测机会以右侧输出端的绿线为支点，去按照上图的位置取输入的值，因此会导致下图中，左边中间的输入会对应到上图的左上输入端，其他以此类推，会得到意想不到的结果（本人是高位呈浮动数）。因此需要手动去调整，上机第一看：规定的电路外观，一定得要一模一样。

电路外观

回到题目本身，首先输出是an，大多数情况下起作用的输入是type，又因为涉及到求和所以应该多一个存储前n-1项的和的状态sum。因此设计的状态转移电路的输入是nowan、nowsum、type，经过寄存器存储后状态转移电路的输出变为nextan和nextsum，将该电路独立出来，再搭配上输出函数以及输入就可实现了。特别注意：同步复位（置reset后时钟触发时复位）与异步复位（一置reset就复位）有本质的区别，因此在实现时会略有不同。

根据题目要求可以得到状态转移电路如下，用一个子电路表示便于理解与修改：

子电路

之后便要考虑状态的存储的问题：即在状态转移后加上一个寄存器（由于sum也需要存储因此，需要两个寄存器），接下来就需要考虑要求的复位方式，若是异步复位则直接将reset输入同寄存器的cl端相连即可：

异步复位

这样就能实现当reset置1时，当前状态直接复位，即寄存器直接被赋0，无需等时钟触发。

由于题目要求的是同步复位即当reset置为1时，需等到时钟触发才复位，如此一来就不能再直接将reset接到寄存器的cl端了，需要在寄存器存入前去想方法，即转化为使0这个值也成为reset置1时寄存器存入的值，这样就可以像正常存入值时一样使之复位，因此联想到了，多路选择器和reset的搭配：

同步复位

且该组合一定要在寄存器之前起到对于reset的一个特判的作用，当reset为0是寄存器存入正常值；为1时存入0即起到同步复位的作用。

再将状态转移电路和状态存储电路相结合，便可以得到最终的答案：

最终答案

一定注意：主电路的外观十分重要。

第二题（Verilog)

本来是一道很简单的循环问题，但是由于忘记了for循环的正确写法，导致硬控半小时，不得不cv32个式子相加。注意着重理解Verilog语法种语句块的含义，与C语言的串行运行不同，是并行运行的。

题面大意：两个32位wire型输入端vector_a、vector_b，6位输出端result,求出vector_a和vector_b每一位相乘再相加的结果result。

要体会到每个Verilog程序中每个大块都是同时进行的，即并行运行，其中initial块是在仿真一开始执行且只执行一次，而always @(*)块是从仿真开始，块中设计的变量一发生变化（注意并不是条件为真)就执行一次。==尤其注意：这两个块中的语句会在波形图一帧内执行完，即若要在always块内进行循环，需要进行单独的初始化，可以将其理解成每一帧都是always块内的小语句块的重新执行一遍，且一定会执行完（前提是其内变量发生改变）==。

以下是for循环版本：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
module dotProduct(
    input [31:0] vector_a,
    input [31:0] vector_b,
    output [5:0] result
    );
    integer i;
	 reg [5:0] ans;
	 always @(*) begin
		 ans = 0; //initial the circle variate
		 for (i = 0;i < 32; i = i + 1) begin
           ans = ans + (vector_a[i] & vector_b[i]);//multipilication can be changed to and operation
       end
    end		 // each always block can be referred to an independent function
    assign result = ans;
endmodule

while版本：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
module dotProduct(
    input [31:0] vector_a,
    input [31:0] vector_b,
    output [5:0] result
    );
    integer i;
	 reg [5:0] ans;
	 always @(*) begin
	    i = 0;
		 ans = 0; //initial the circle variate
		while (i < 32) begin
           ans = ans + (vector_a[i] & vector_b[i]);//multipilication can be changed to and operation
			  i = i + 1;
       end
    end		 // each always block can be referred to an independent function
    assign result = ans;
endmodule

谨记：always块内应该是每一帧都需要执行的一个“小主函数”

第三题（MIPS）

依照C语言翻译成汇编即可，注意：循环或者函数要记得变量的循环变量的改变以及回转回循环开头的跳转指令。

P0

课下

CRC校验码计算电路的设计与测试

CRC校验是数据通信领域中最常用的一种查错校验方式，它对数据进行多项式计算，并将得到的结果附在帧的后面，接收设备也执行类似的算法，以保证数据传输的正确性和完整性。（帧在此处指的是数据的二进制码）

前置知识

”模二除法“：同算术除法类似，但除法过程中做减法时既不向上借位，也不比较除数和被除数相同位数值的大小；它的运算法则为 1-1=0，0-1=1，1-0=1，0-0=0，（即异或运算，因此该运算可以用异或运算来完成，来加快运算速度）例如 1100-1001=0101。

CRC校验码的计算

只需将原帧补上（被除数的位数-1）个0作为被除数，然后进行模二除法即可。例如：要发送的帧A为10011，发送端和接收端共同选定的除数B为1110，B为4位二进制数，因此需要在A后补上3个0，即可得到A‘=10011000。再将A’作被除数，B作除数，进行“模二除法”，得到商11001，余数110，（注意：若最后的余数不是三位，也需要在余数前补零来凑齐三位），而这就是要求的校验码。将校验码拼接在原数据帧后就得到了要发送的A‘’=10011110，如此一来就完成了CRC校验码的生成。

如何利用Logisim实现CRC校验码的计算呢？即依照除数的位数构造对应位数的模二除法器，（例如：除数为4位，就构造4位的模二除法器），输入输出的位数均相同，那么，当被除数的最高位是1时，该模二除法器的商是1，余数便是被除数同除数的异或结果，舍去最高位（保证除数的最高位为1的情况下）；反之被除数最高位为0时，商为0，余数即为被除数舍去最高位0的结果。根据上述规则构造出低层的模二除法器并根据此模二除法器去构造相应的CRC校验码计算电路即可。

有限状态机

一定要深刻理解Moore机和Mealy机之间的差别：

前者的输出仅与状态机的当前状态有关，或者说输入并不直接参与输出的生成，仅根据判断输入的情况来就决定输出的情况，例题:P0.Q3(navagation)：

计小组要去机房上机考试，需要去B机房，但是目前他在A机房。他现在的时间很充裕，就决定生成一串随机序列，告诉他下一步行走的方向，直到走到B机房。他希望用logisim搭建一个可以导航的Moore型有限状态机，来通过序列告诉他是否到达B机房。

例图

题目要求：

计小组只能往东南西北四个方向行走，且若能行走，则每次只能行走一格。若下一步不存在机房让计小组行走，那么计小组会撞到墙壁并且hit置高一周期，此时计小组仍保持原地不会移动，等待下一周期再进行运动。（如果下一步依旧撞墙， 则hit仍然置高；若下一步不会撞墙，则计小组将会继续行进，hit在此周期置0）

计小组走到B机房后，“到达”信号需要置位，并保持一周期。到达B机房后计小组将会在下一周期回到原点，（下一周期的输入将被忽略掉）等待下下周期的输入，继续测试他的序列。

计小组遵循上北下南左西右东的方向完成操作。

计小组在时钟上升沿的时候就已经知道自己下一步的方向并且瞬移过去，并且立即做出判断。

端口定义：

信号名 方向 描述
dir[1:0] I 表示行走的方向：00：向北走 01：向东走 10：向南走 11：向西走
clk I 时钟信号
reset I 异步复位信号
arrive O 是否到达
hit O 是否撞上墙壁

关注到Moore机的要求，说明最后的输出仅与当前的状态值有关，首先根据将每一块作为一个状态（因为当前状态值决定输出，所以最后的状态是需要进行保存的，区别于某些最后一个状态不需要保存的Mealy机），因此共需要5种状态，又因为2^2^=4<5<2^3^=8,所以需要3位来表示所有的5种状态。其中S0表示A块、S1表示A块北面那块、S2表示B西面那块、S3表示B南面那块、S4表示B块。

则状态转移的真值表为：

nowstatus2 nowstatus1 nowstatus0 dir1 dir0 nextstatus2 nextstatus1 nextstatus0
0 0 0 0 0 0 0 1
0 0 0 0 1 0 0 0
0 0 0 1 0 0 0 0
0 0 0 1 1 0 0 0
0 0 1 0 0 0 1 0
0 0 1 0 1 0 1 1
0 0 1 1 0 0 0 0
0 0 1 1 1 0 0 1
0 1 0 0 0 0 1 0
0 1 0 0 1 1 0 0
0 1 0 1 0 0 0 1
0 1 0 1 1 0 1 0
0 1 1 0 0 1 0 0
0 1 1 0 1 0 1 1
0 1 1 1 0 0 1 1
0 1 1 1 1 0 0 1
1 0 0 0 0 0 0 0
1 0 0 0 1 0 0 0
1 0 0 1 0 0 0 0
1 0 0 1 1 0 0 0
1 ? ? ? ? x x x

由logisim生成相关状态转移电路后：

状态转移电路

就是将该转移模块放在主电路中，连接输入和初状态以及状态存储电路，之后便是处理输出的问题。

关于输出：hit是在撞墙的那个状态置1一个周期，因此想到将当前状态同下一个状态比较，若相等则下一个状态周期，hit置1；否则置0。由此便产生了一些问题：如何让当前状态判断出来的hit置1情况到下一个状态周期才显现，答案是使用一个寄存器去给hit赋值，这样一来hit的值就是需要等到时钟触发也即就是下一个周期才会显现（如果当前周期判断出hit将置1），也就是说，该寄存器将hit当前判断出来且状态还未转移前的值，在状态转移的瞬间（即判断后的下一个时钟触发时刻）赋给hit并输出，这样一来原本在当前状态内判断出来的情况需要到下一个状态开始时才开始赋值，并持续到下下个状态，如此一来便解决了hit的置1一周期且撞墙周期才置1的效果。

从题目关于arrive的描述可以看出，当状态已到达S4（B块）就置1一周期，因此想到了直接将当前状态同S4作比较的“等于”结果赋给arrive即可，又因为下一个时钟触发到来时当前状态已不是最终态，故arrive刚好可以实现置1一周期的效果。

下图为主电路：

主电路

后者的输出不仅与状态机的当前状态有关还与输入值有关，或者说输入将参与到最终的输出

例题：P0.Q4（FSM）：

使用Logisim搭建一个Mealy型有限状态机 检测串行输入字符串中的能匹配正则表达式b{1,2}[ac]{2}的子串并输出。具体模块端口定义如下：

信号名 方向 描述
In[1:0] I 串行方式输入字符串。 为简化电路，我们规定 00 表示 ‘a’，01 表示 ‘b’，10 表示 ‘c’，11 表示其他字符。
CLR I 清除置位信号
Z O 输出是否检测到了与表达式匹配的子串 1：检测到了 0：未检测到

模块功能定义如下：

模块功能定义

  • 必须严格按照模块的端口定义

  • 文件内模块名: fsm

  • 注意: 每当匹配到一个子串时，需要输出一次1。例如对字符串bacbacac,模块应当在第1个c输入和第2个c输入时输出1,而在其他时刻保持输出为0。

  • 注意：有限状态机的设计是Mealy型有限状态机。

    关注到需求是Mealy机，因此在状态转换的电路图设计中应该考虑到输出的参与，即当前状态置值和输入都将会影响输出，根据题意应该有3种状态：S0(读入非法字符)、S1(读入”b“)、S2(读入”a”、”c”)，因此需要2位二进制码参与状态的表示。因此状态转移的真值表为：

nowstatus1 nowstatus0 In1 In0 nextstatus1 nextstatus0 Z
0 0 0 0 0 0 0
0 0 0 1 0 1 0
0 0 1 0 0 0 0
0 0 1 1 0 0 0
0 1 0 0 1 0 0
0 1 0 1 0 1 0
0 1 1 0 1 0 0
0 1 1 1 0 0 0
1 0 0 0 0 0 1
1 0 0 1 0 1 0
1 0 1 0 0 0 1
1 0 1 1 0 0 0

得到如下：

输入与输出关系

最终的主电路如下：

主电路

注意采用MUX+寄存器的方法解决同步复位的问题。

课上

第一题（组合逻辑）

求逆序数：给定输入：a0a1a2a3，ai为左数第（i+1）个数，求给输入的逆序数（∑((ai>aj)?1:0)(0<=i<j<=3))

最简单的办法就是一个一个比较最后将比较得到的结果（1或0）相加即为逆序数。（注意要求是无符号数，所以比较时应是无符号比较）

第二题（Moore机）

与pre的第一题有异曲同工之妙。

题目大意：统计两个教室101、102的总人数，输出至32位的out。每个时钟触发时根据输入room、[1:0] op决定相应的操作：

room == 0：对101教室进行操作；room == 1：对102教室进行操作。

op == 00：教室人数保持不变；op == 01：教室人数加1；op == 10：教室人数减1；op == 11：教室人数清零。

对其中一个教室进行操作时，另一个教室人数不变。

大体流程设计同pre的第一题，其中多出来的设计时对于room输入的处理，如何在room指示一个教室时，对另一个教室不进行处理，答案是：在状态转移电路的最后多一个是否对教室进行操作的选择（由多路选择器MUX+room选择是保持不变还是进行op处理）。

第三题（稍难一点的Moore机）

题目大意是输出串行输入的数串的最大严格递增长度，并且要求同步复位和初始化时输出至0。

数串中任意输入后缀am-1am-2…a0,在这m个数中若am-1<am-2<…<a1<a0，且am>=am-1则a0的最大严格递增长度为m，以此类推。

根据题意很快便可判断出需要两个寄存器，一个用来存储当前最大严格递增长度，另一个用来存储当前输入的前一个输入，通过比较实现状态的相应转移。

在初始化处理方面，由于每次假若比较失败（即前一个输入大于等于当前输入），则此时由于严格递增序列的”重建“，最大长度应该为1，而不是初始化时的0，所以需要将0和1的赋值通过初始化计数器得到结果进行选择一下。

初始化计数器

主要逻辑图

其中indication是an是否大于an-1的结果。

这样一来输出nowlength即可相应的结果。

P1课下

代码规范

用localparam命名状态机的各个状态

编写状态机的时候，用localparam命名各个状态：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
localparam sInit = 2'd0;
localparam sIdle = 2'd1;
localparam sWork = 2'd2;
localparam sDone = 2'd3;

reg [1:0] state;

//若仿真工具不支持在波形中显示为对应的状态名称，可采用以下方法：
`ifndef SYNTHESIS
 reg [39:0] state_string; // 40 bits = 5 bytes,a word needs 1 byte / 8 bits
  
 always @ (*) begin
    case(state)
        sInit: state_string = "sInit";
        sIdle: state_string = "sIdle";
        sWork: state_string = "sWork";
        sDone: state_string = "sDone";
        default: state_string = "?????";
    endcase
 end
`endif

小型通用模板

MUX

1
2
3
4
5
6
7
assign result = (Aluop == 4'd0) ? (srca + srcb) :
                   (Aluop == 4'd1) ? (srca - srcb) :
                   (Aluop == 4'd2) ? (srca & srcb) :
                   (Aluop == 4'd3) ? (srca | srcb) :
                   (Aluop == 4'd4) ? (srca ^ srcb) :
                   (Aluop == 4'd5) ? (srca > srcb) :
                   32'd0;

若涉及有符号数的运算，不推荐使用三目运算符，因为需要考虑符号的确定，推荐使用always@()的方式，一般来说 always@() 配合 case 写出的类似 MUX 语句在仿真中的行为类似纯组合逻辑，但是 result 在写代码时应写为 reg 型（即新开一个reg变量）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
always @(*) begin
      case(Aluop)
        4'd0:begin
            result = srca + srcb;
        end
        4'd1:begin
            result = srca - srcb;
        end
        4'd2:begin
            result = srca & srcb;
        end
        4'd3:begin
            result = srca | srcb;
        end
        4'd4:begin
            result = srca ^ srcb;
        end
        4'd5:begin
            result = srca > srcb;
        end
    endcase
  end

流水线寄存器（P5）

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
module pipeline_sample(
   input clk,
   input reset,
   input stall,
   input flush,
   input [31:0] aluResultAtExe,
   // 可能还有其他来自前一级的输入
   output [31:0] aluResultAtMemory
   // 可能还有要输出到后一级的
   // 输入输出应配对
   );
   // 根据端口定义，可能还要开其他的临时寄存器
   reg [31:0] aluResult;
   // 根据临时寄存器的值，可能还要连其他的线
   assign aluResultAtMemory = aluResult;

   always @(posedge clk)
   // 可能还要处理其他的临时寄存器
   begin
       // 复位 或者 清除流水线寄存器（阻塞，异常中断处理会用到）
       if(reset | flush)
       begin
           aluResult <= 32'd0;
       end
       else begin
           // 判定是否应阻塞该级，不阻塞时才更新为前一级的值
           if(!stall)
           begin
               aluResult <= aluResultAtExe;
           end
       end
   end

endmodule

P1课上

第一题（组合逻辑）

题目大意:求两个32位数反序相比位数不同的个数。

采用循环比较判断并用一个变量存储不同位数的个数即可。

注意:循环的写法，参照pre上机的第二题。

第二题（Moore状态机）

题目大意：判断串行输入的01序列是否满足奇偶序列（出现的个数为奇数或偶数）间隔排列，并且需要提供低电平边沿触发的异步复位。

显然，只出现0和1的序列是不满足要求的。

示例：0001111011001，一开始出现的3个0都是不符合要求的，因为此0序列的个数是奇数，所以此后的1序列个数为偶数时将输出check置1。此后的0序列个数为奇数，满足奇偶奇排列，此时也置1。但是需要注意假若出现偶偶排列（第二个偶已经确定）或奇奇排列需要将输出锁住，即不论此后输入是什么，输出都是0.

方法一（状态少，逻辑复杂）：设计5种状态，空状态用于复位时返回的状态（000）、当前序列1个数为奇数（001）、当前序列1个数为偶数（010）、当前序列0个数为奇数（011）、当前序列0个数为偶数（100），还需要两个变量一个用来存储上一个相邻序列的情况用于判断此时是否满足条件，另一个用来判断此前所以序列是否满足要求（即判断输出是否需要锁住）。

由于讨论区已给出相应方法的实现，这里就不赘述了，详见P1上机思路分享与反思

方法二（状态多、逻辑简单）：设计13种变量和一个判断是否锁住输出的变量flag，如下图：

暴力状态图

虽然状态很多，但是很好想，不过一定要注意状态转移要对应清楚（不然大有被硬控半小时的情况）。

第三题

  • 题面：输入序列满足格式 xxxx{key1 : value1, key2 : value2, ……} xxxx……
  1. 其中xxxx是长度大于等于0的序列，不含，：{ }
  2. key是大小写字母和数字组成的连续字符串，其中首字符必须是字母，长度大于等于1
  3. value是数字组成的连续字符串，长度大于等于1
  4. key、value的必须是连续的，内部不允许有空格
  5. key、value、{、：、}、，之间可以有空格
  6. key、value有可能不出现，此时匹配不成功
  7. 若至少有一对key-value，则最后一对后会有逗号，
  8. reset为高电平同步复位信号

统计每一个键值集合中匹配成功的键值对个数each，以及在复位后所有集合中键值对匹配数目的最大值total

简单的思路同样是列出所有可能的状态如下图：

暴力状态图

教训：对于每个状态，都要充分考虑所有的字符输入可能，这样才能实现所有可能序列的覆盖。例如在本题中，对于key：value，间的字符要充分考虑:、,的复用问题，（d : 121,,，这种其实也是正确的，但是若没有特判初始读入状态的下一个输入可能,就会出错)，由于题目对于空格的相关规定，还需要在特判空格，只有能够保证状态转移没问题的字符输入可以一同归入其他中。

当然还有状态数少的方法，感觉不如状态多的直观方便，再次不表，详见zjy大佬的P1上机思路分享与反思.

P2课下

高精度阶乘

题面：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
第一行读取n

计算并输出n的阶乘，输出字符串长度小于等于1000

步数限制为200,000

请使用syscall结束程序：

li $v0, 10
syscall
样例1
给出以下输入：

24
期望的输出为：

620448401733239439360000

由于int型整型数溢出问题，本题不可采用一位一位相乘的方法，因此用C写出如下朴素的利用int型数组将两个数的相乘转化为大数的每一位同小数相乘再进行进位处理：

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
   int i = 2, j;//i=2，从n=2开始计算，n=0和n=1的答案都是1
int length = 0;
array[0] = 1;
for (i; i <= n; i++) {
	for (j = 0; j <= length; j++) {
		array[j] *= i;
	} //大数的每一位都以小数
	for (j = 0; j < length; j++) {
		if (array[j] >= 10) {
			int hold = array[j];
			array[j] %= 10;
			array[j+1] += hold / 10;
		}
	}
	while (array[length] >= 10) {
		int temp = array[length];
		array[length] %= 10;
		array[++length] += temp / 10;
	}//进位处理，
}
if (n == 1) {
	printf("1");
}
else{
	for (i = length; i>=0; i--) {
		printf("%d", array[i]);
	}
}

得到以上代码的汇编版本后却没有通过，个人认为是在进位处理时，后面的进位加到前面导致前面的溢出：

因此考虑令数组的每一位储存大数的更多位数，即：提高进制到1000

得到如下汇编代码：

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
# adjust carry-out
.macro adjust(%now)
   getArrayi($t2, %now) #array[%now]
   move $t3, $t2 #hold = array[%now]
   
   li $v0, 1000
   div $t2, $v0
   mfhi $t2 #$t2 %= 1000
   sll $v0, %now, 2
   sw $t2, array($v0) #array[%now] %= 1000
   
   li $v0, 1000
   div $t3, $v0 #hold / 1000
   mflo $t4
   
   addi $t5, %now, 1 #$t5 = i + 1
   getArrayi($t6, $t5) #$t5 = array[i + 1]
   add $t6, $t6, $t4 
   sll $v0, $t5, 2
   sw $t6, array($v0) #array += hold/1000 
.end_macro

#because the higher binary, the leading zero needs to be adjusted when you print,because it wil print 0 while it actually is 000
           bne n, 1, if_else
           if:
             li $v0, 1
             printInt($v0)
           j for_4_end
           if_else:
           move i, length #i = length
           for_4_begin:
             blt i, 0, for_4_end #i<0
             getArrayi($t2, i)
             beq i, length, three_print
             bge $t2, 100, three_print 
             bge $t2, 10, two_print
             bge $t2, 1, one_print
             printInt($t2)
             printInt($t2)
             printInt($t2) #printf("000"); avoid printing the single zero while there actually three zero
             j if_2_end
             
             two_print:
               printInt($0)
               printInt($t2)
               j if_2_end #print one leading zero
               
             one_print:
               printInt($0)
               printInt($0)
               printInt($t2) #print two leading zero
               j if_2_end
               
             three_print:
               printInt($t2) #printf
          
             if_2_end:
             addi i, i, -1 #i--
             j for_4_begin  #
            
           for_4_end:

注意前导零的处理，循环的书写一定要规范。

MARS小工具

MARS的Tool菜单里有个叫做Instruction Counter的工具，点击Connect to MIPS后运行程序可以看见程序跑了多少条实际的指令，可以作为相应题目指令限制的参考。

P2课上反思与总结

虽然侥幸过了P2课上，但是自我感觉还是有很多错误与不好的习惯暴露出来了，特写此文与君共勉（顺便提高一下讨论区参与度）。

P2_Q1(具体题名忘了QAQ)

题目大意：

一个有n个人的小班的小班长去取糖果来给所有n个人发糖，且取的K满足在最小值L和最大值R之间，即：$L <= K <= R$ ，并将剩余的糖果还回去。

发糖规则：每个人发一个直到剩余的糖果不够n个人再发一次。小班长为了发给同学最多的糖果，同时剩最少的糖果还回去（真是无私的小班长）。（大致版本，记性不好，有误请不吝斧正）

输出剩余糖的最小值，不是K。

刚开始看到这道题的时候其实是挺懵。

最初的想法是写一个循环来判断，然后用一个min变量来存取输出的值，虽然笨人不是用这个方法，但是听室友说有的点会超时，这里就不赘述此种方法了。

虽然好像循环会更好想，但是我一开始却感觉判断会更麻烦，于是思考输出需求同输入的关系（面向输出编程），注意到输出只要剩余的糖果数，因此取$K = mn$（其中m是满足$mn<=R$的最大正整数），易得：

当$mn <= L$时，即L= mn + l,R = mn + r,r>l,(且r、l均为正整数)时，所有同学能拿到的最大糖果数就是m，而此时还回去的糖果数就是l，因此此时输出L%n，K = L ；

当$mn >= L$时，那么此时由于K = mn在[L,R]之间，且m是满足$mn<=R$的最大正整数，因此此时所有同学能拿到的最大糖果数仍是m，而在K = mn与R之间的数都会增加还回去的糖果数，因此此时还回去的糖果数即输出就是0，K = mn。

因此，本题只要判断R/n和L/n的大小关系即可，若相等输出L%n;不等则输出0。

感觉像是一道数学题。

P2_Q2(具体题名忘了QAQ)

题目大意：

利用欧拉筛判断一个输入n是否为质数，虽然题目说是用欧拉筛，但代码给的好像是埃式筛（如果没记错的话）：

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> 
#define Max 2000 //代表判断质数的最大范围
int is_not_prime[Max]; //用来判断2到Max间的某数是否为质数
void Euler sieve() {
    int i,j;
    for (i = 2; i <= Max; i++) {
        if (is_not_prime[i] == 0) {
            //如果i是质数
            for (j = i*2; j <= Max; j += i) {
               //i的倍数都不是质数，因为i的倍数都有i这个因子
                is_not_prime[j] = 1;
            }
        }
    }
}
int main()
{
    int n;
    scanf("%d",&n);
    Euler sieve();
    printf("%d",is_not_prime[n]);
}

既然有了C代码，那就只要快乐肉编就行了。

需要注意的是：

1.for循环的转换一定要将跳转条件放在for循环内的第一条，初始赋值在for循环上一条：

1
2
3
4
5
6
7
8
9
10
11
.eqv Max 2000
.eqv i $t0
……
  li i, 2
  for_begin:
    bgt i, Max, for_end
    ……
    addi i, i, 1
    j for_begin
  for_end:
  ……

2.然后就是善用一些常用的宏，如getInt等（相信大家都已经熟练掌握了吧，这里就不赘述了）。

P2_Q3(具体题名忘了QAQ)

题目大意：

省流：给出在一个有向图中从给定出发点出发可到达的出度为0的点的个数（忘了具体情景了）

输入是先输入三个整型数n、m、k（n为点个数、m为有向边的个数、k为出发点）、接下来的2*m行两行为一组第一行为有向边的起点，第二行为有向边的终点。(其中n<=105,m<=605)

由于已给出了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 N 105
#define M 605
int matrix[N+1][N+1];
int book[N+1];
int out_degree[N+1];

int ans;
int n, m, k;
void dfs(int u);
int main()
{
	scanf("%d%d%d",&n,&m,&k);
	int x,y;
	int i = 0;
	for (i; i < m; i++) {
		scanf("%d%d",&x,&y);
		matrix[x][y] = 1;
		out_degree[x]++;
	}// read the matrix
	
	if (out_degree[k] == 0) {
		printf("0\n");
	}
	else {
		dfs(k);
		printf("%d\n",ans);
	}
	return 0;
}

void dfs(int u) {
	if(u != k && out_degree[u] == 0 && book[u] == 0){
		book[u] = 1;
		ans++;
		return;
	}
	int i = 1;
	for ( i; i<= n; i++) {
		if (matrix[u][i]){
			dfs(i);
		}
	}
}

一些做题中遇到的问题：

1.字符串定义的前移导致后续定义的数组首地址出现字不对齐问题:

1
2
3
4
.data
enter: .asciiz "\n"
head: .space 420 #head数组首地址会出现字未对齐的问题，在对其进行写入和取数操作时会报错QAQ！
……

解决方案：将字符串放到数组定义的后段：

1
2
3
4
5
.data
head: .space 420
……
enter: .asciiz "\n"
.text

2.宏定义的错乱问题：

1
2
3
4
5
6
7
8
9
.eqv n $s0
.eqv m $s1
.eqv k $s2
.eqv Max $s3
……
.eqv ans $s3 
#隔了好几行就会不知道用到哪个寄存器了
#（结果就是被硬控半小时）
#建议是把用了什么寄存器、对应用的别名一起写在草稿纸上，方便用取，不然真的会在不经意间碎掉