茶与健康

这学期有幸选中全校最热门的公选课——茶与健康。之前每学期都是1000+人选28人，在周一晚上上课，从上学期开始每周多开一次下午的课（这个时间选择人数较少），正好我这学期周一下午没课，就来碰碰运气，没想到真的抽中了。这门课之所以这么火，主要是因为上课就是喝喝茶，发表自己的感想，听老师讲述茶文化，期末交一篇论文就可以了，虽然可能被卡优秀率，但只有1学分，花点GPA喝喝茶还是很值得的。

题目

IDE

1. 使用Emu8086仿真(支持DOS16位程序)

   • emu8086不能用：
     1. 32位寄存器
     2. INVOKE
     3. USES
     4. .IF .ENDIF .ELSEIF
     5. .REPEAT .UNTIL

2. 或者MASMPlus+DOSBOX(支持DOS16位或32位程序)

题目

编程计算任一整数加减运算表达式，其中，表达式长度不超过1024个字节，从键盘输入，可带括号，操作数为字数据

题目

最佳调度问题

问题描述

设有n个任务由k个可并行工作的机器来完成，完成任务i需要时间为ti。试设计一个算法找出完成这n个任务的最佳调度，使完成全部任务的时间最早。（要求给出调度方案）

完成全部任务的时间为运行时间最长的机器上运行的总时间，所有机器都是相同的。一个任务只能在一个机器上完成，且在完成之前不会被其他任务抢占。

题目

计算N!（0<N<20）

代码

.MODEL SMALL    

.DATA
    D_N DW 4 DUP(0) ;N   (64bit)
    D_N_FAC DW 4 DUP(0) ;N!    (64bit)
    D_TMP DW 4 DUP(0) 
    D_I DW 4 DUP(0) 
    MAP DB "0123456789ABCDEF" 
    Q_TMP DW 0   
    R_TMP DW 0
.CODE
<!-- more -->


PRINTNEWLINE MACRO _PSTRING ;打印换行符
    PUSH AX
    PUSH DX
    MOV AH,2
    MOV DL,0DH
    INT 21H 
    MOV DL,0AH
    INT 21H
    POP DX
    POP AX
ENDM




PRINTNHEX PROC          ;打印一个64位整数(16进制)
    PUSHA         
    ;---------------- 
    MOV BX,7
    MOV CX,8
PLOOP:
    MOV AL,BYTE PTR D_N_FAC[BX] 
    MOV AH,0
    ;CMP AX,0
    ;JZ PEND:
    MOV DL,10H 
    DIV DL  ;商在AL，余数在AH
    MOV BYTE PTR Q_TMP,AL
    MOV BYTE PTR R_TMP,AH 
    MOV DI,Q_TMP   
    MOV DL,BYTE PTR MAP[DI] 
    MOV AH,2H
    INT 21H  
    MOV DI,R_TMP
    MOV DL,BYTE PTR MAP[DI]
    MOV AH,2H
    INT 21H 
    ;PEND:
    DEC BX             
    LOOP PLOOP       
    ;----------------
    POPA
    RET
ENDP

MOV8 MACRO DATAA,DATAB
    PUSH AX
    MOV AX,DATAB[0]
    MOV DATAA[0],AX
    MOV AX,DATAB[2]
    MOV DATAA[2],AX
    MOV AX,DATAB[4]
    MOV DATAA[4],AX
    MOV AX,DATAB[6]
    MOV DATAA[6],AX 
    POP AX
ENDM

BIGMUL MACRO RES,A,B  
    PUSHA
    ;----------------
    MOV WORD PTR RES[0],0
    MOV WORD PTR RES[2],0
    MOV WORD PTR RES[4],0
    MOV WORD PTR RES[6],0
    MOV CX,4
    MOV BX,0
    LOOP1:
    MOV DI,0
    PUSH CX
    ;------------
        LOOP2:
        MOV AX,B[BX]
        MUL A[DI] ;DX:AX=A[DI]*B[BX]
        MOV SI,BX
        ADD SI,DI ;SI=BX+DI 
        ADD WORD PTR RES[SI],AX
        PUSHF
        CMP SI,6
        JZ AEND
        POPF
        ADC WORD PTR RES[SI+2],DX
        PUSHF  
        CMP SI,4
        JZ AEND
        POPF
        ADC WORD PTR RES[SI+4],0
        PUSHF 
        CMP SI,2
        JZ AEND
        POPF
        ADC WORD PTR RES[SI+6],0  
        JMP AEND2
        AEND:
        POPF
        AEND2:
        ADD DI,2
        LOOP LOOP2  
    ;------------
    POP CX
    ADD BX,2
    LOOP LOOP1
    ;----------------
    POPA 
ENDM 
   

.STARTUP

    MOV WORD PTR D_N[0],19
    MOV CX,WORD PTR D_N[0] ;循环次数
    MOV D_I[0],1 ;当前i
    MOV D_TMP[0],1 ;临时结果
CALC:
    BIGMUL D_N_FAC,D_TMP,D_I
    MOV8 D_TMP,D_N_FAC  
    CALL PRINTNHEX 
    PRINTNEWLINE
    INC D_I[0]  ;I++
    LOOP CALC 

      
.EXIT 

END

题目

最长公共子序列问题和调研报告

算法设计

1. 最长公共子序列问题（Longest common subsequence problem）的定义

​ 子序列：给定序列X=(x1,x2,…,xm)，序列Z=( z1,z2,…,zk)是X的一个子序列，必须满足：若X的索引中存在一个严格增的序列i1,i2,…,ik，使得对所有的j=1~k，均有xij=zj

​ 公共子序列（CS）：Z是X和Y的子序列，则Z是两者的公共子序列CS。

​ 最长公共子序列（LCS）：在X和Y的CS中，长度最大者为一个最长公共子序列

2. 用动态规划求解LCS

（1）刻画LCS最优解的结构特征

题目

编程实现排序算法，对某文件（txt格式）中的无符号整数进行排序，排序结果输出到屏幕（数据的个数不超过1024）

代码

.MODEL SMALL,STDCALL
<!-- more -->


.DATA
    N DW 0
    TMP DW 1 DUP (0)
    NUMS DW 1024 DUP (0)   
    MSG_ERR DB 0dh,0ah,'THERE ARE SOME ERRORS IN OPERATING THE FILE!','$'  
    MSG_SUCCESS db 0dh,0ah,'SORT RESULT:','$'
    FILEHANDLE DW 0
    FILENAME DB "test2.txt"
    TMPC DB 1 DUP (0)
.CODE   

PRINTC MACRO CHAR;打印字符
    PUSH AX
    PUSH DX 
    MOV AH,2
    MOV DL,CHAR
    INT 21H
    POP DX
    POP AX     
ENDM 

PRINTS MACRO PSTRING ;打印字符串
    PUSH AX
    PUSH DX
    MOV AH,9H
    LEA DX,PSTRING
    INT 21H
    POP DX
    POP AX
ENDM

PRINTN PROC    ;打印一个16位整数,AX
    ;PUSH AX
    PUSH BX
    PUSH CX
    PUSH DX
    ;----------------
    MOV BX,10
    MOV CX,0
DPUSH:
    MOV DX,0
    DIV BX   ;DX:AX/10,即AX/10 商在AX，余数在DX
    PUSH DX ;余数即最低位，压栈
    INC CX  ;统计位数  
    CMP AX,0
    JZ DPOP  ;商为0，已经是最高位，开始出栈   
    JMP DPUSH    
DPOP:
    POP DX
    ADD DL,30H
    MOV AH,2H            
    INT 21H  ;打印栈顶的位        
    LOOP DPOP
    ;----------------
    POP DX
    POP CX
    POP BX
    ;POP AX
    RET
PRINTN ENDP

FGETN PROC ;从文件读取一个16位整数,结果在AX  
    PUSH BX
    PUSH CX
    PUSH DX    
  
    MOV CX,5 ;数的文本长度，最长5位
    MOV AX,0 ;乘法用的AX,初始化
LOOP1:
    ;-------------------READCHAR
    PUSH AX
    PUSH BX
    PUSH CX
    PUSH DX
    MOV AH,3FH
    MOV BX,FILEHANDLE
    MOV CX,1  ;读取长度
    LEA DX,TMPC;用于暂存读取的串
    INT 21H   ;读取后AX存放实际读取出的字符数
    JC R_ERR ;CF=1 出错
    CMP AX,0
    JZ R_QUIT ;AX=0, EOF
    CMP TMPC[0],20H
    JZ R_QUIT ;空格
    POP DX
    POP CX
    POP BX
    POP AX
    ;-------------------
    MOV DX,10 ;DX=10
    MUL DX    ;DX:AX=AX*10 由于读取的是16位无符号整数，最后只会在AX中,DX一直是10 
    SUB TMPC[0],30H ;
    ADD AX,WORD PTR TMPC[0] 
    LOOP LOOP1 
R_QUIT:
    POP DX
    POP CX
    POP BX
    POP AX    
    ;此时AX为读取的数
    JMP R_END
    
R_ERR:
    POP DX
    POP CX
    POP BX
    POP AX
R_END:
    POP DX
    POP CX
    POP BX
    RET
FGETN ENDP

SORT PROC ;冒泡排序
    PUSH AX
    PUSH BX
    PUSH CX
    PUSH DX    
    
    MOV CX,N 
    DEC CX    ;外循环次数为N-1
    SLOOP1:
    PUSH CX  ;把外循环计数器存下来
    ;-------------------
        MOV BX,0
        SLOOP2: ;外循环计数器也是内循环次数
        MOV AX,NUMS[BX]
        INC BX
        INC BX
        MOV DX,NUMS[BX]
        CMP AX,DX
        JZ NOEXCHANGE  ;AX=DX 
        JC NOEXCHANGE  ;AX<DX
        EXCHANGE:      ;AX>DX
            MOV NUMS[BX],AX
            DEC BX
            DEC BX
            MOV NUMS[BX],DX
            INC BX
            INC BX
        NOEXCHANGE:
        LOOP SLOOP2
    ;-------------------
    POP CX  ;取出外循环计数器
    LOOP SLOOP1
    
    POP DX
    POP CX
    POP BX
    POP AX
    RET
SORT ENDP

.STARTUP
    ;打开文件
    LEA DX,FILENAME ;MOV DX,OFFSET _FILENAME
    MOV AH,3DH 
    MOV AL,2    
    INT 21H
    JC ERROR ;出错
    ;---------
    MOV FILEHANDLE,AX   ;保存句柄
    CALL FGETN ;读取第一个数，表示接下来有几个数据
    MOV N,AX
    CALL PRINTN
    PRINTC 0DH
    PRINTC 0AH
    MOV BX,0
    MOV CX,N
FREAD:
    CALL FGETN
    MOV NUMS[BX],AX
    CALL PRINTN
    PRINTC 20H
    INC BX
    INC BX ;由于是字节，下标每次要加2
     LOOP FREAD
     
     ;---------
    CALL SORT
    ;---------
    
    PRINTS MSG_SUCCESS  
    PRINTC 0DH
    PRINTC 0AH
    
    MOV CX,N
    MOV BX,0
PRINTRESULT:
    MOV AX,NUMS[BX]
    CALL PRINTN
    PRINTC 20H
    INC BX
    INC BX
    
    LOOP PRINTRESULT

    JMP TOEND
    ;---------
ERROR:
    PRINTS MSG_ERR
    CALL PRINTN; 打印AX存储的错误码
TOEND:
    MOV    AH, 4CH ;按任意键结束 
    INT    21H

.EXIT 

END

题目

红黑树维护算法及其区间树应用

算法设计

（一）红黑树

红黑树是一棵二叉搜索树，是众多平衡二叉树中的一种，它可以保证在最坏情况下基本操作的时间复杂度为O(lgn)

红黑树的每个结点包含5个属性：color、key、left、right、parent，分别表示颜色、关键字、左孩子、右孩子、父亲。

红黑树有以下性质：

① 每个节点必须为红色或黑色；

② 根为黑色；

③ 树中的nil叶子为黑；

④ 若节点为红，则其两个孩子必为黑；

⑤ 每节点到其后代叶子的所有路径含有同样多的黑节点；

红黑树的基本操作：

（1）左旋/右旋

题目

把1~36的自然数按行顺序存入一个6*6的二维数组中，然后打印出该数组的左下半三角