课程设计约瑟夫环程序设计.doc

《课程设计约瑟夫环程序设计.doc》由会员分享，可在线阅读，更多相关《课程设计约瑟夫环程序设计.doc（18页珍藏版）》请在三一办公上搜索。

1、学 号： 课 程 设 计题 目约瑟夫环程序设计学 院计算机科学与技术学院专 业计算机科学与技术专业班 级姓 名指导教师2012年月日课程设计任务书学生姓名： 专业班级： 指导教师： 工作单位： 题目: 约瑟夫环程序设计初始条件：理论：完成了汇编语言程序设计课程，对微机系统结构和80系列指令系统有了较深入的理解，已掌握了汇编语言程序设计的基本方法和技巧。实践：完成了汇编语言程序设计的4个实验，熟悉了汇编语言程序的设计环境并掌握了汇编语言程序的调试方法。要求完成的主要任务: （包括课程设计工作量及其技术要求，以及说明书撰写等具体要求）进一步理解和掌握较复杂程序的设计方法，掌握子程序结构的设计和友好

2、用户界面的设计。具体的设计任务及要求：1） 有 n个人围成一圈，他们的编号为1到n。第一个人从1开始顺序报数，凡报到m时，该人退出圈子。其后的人再从1开始顺序报数，直到最后的一个人退出圈子为止。输出依次退出圈子人的序号。n和m的值从键盘输入，且均小于200。2） 程序采用子程序结构，结构清晰；3） 友好清晰的用户界面，能识别输入错误并控制错误的修改。在完成设计任务后，按要求撰写课程设计说明书；对课程设计说明书的具体要求请见课程设计指导书。阅读资料：1）IBMPC汇编语言程序设计实验教程实验2.42）IBMPC汇编语言程序设计（第2版）例6.11时间安排：设计安排一周：周1、周2：完成系统分析及

3、设计。周3、周4：完成程序调试，和验收。周5：撰写课程设计报告。指导教师签名： 年 月 日系主任（或责任教师）签名： 年 月 日目 录1. 问题描述及要求 41.1问题描述 41.2任务要求 42.设计说明 4 2.1 简要分析 4 2.2 概要设计 4 2.2.1 主要模块 4 2.2.2 主函数结构.73.算法描述. 8 3.1 算法描述. 8 3.2 流程框图 94.源程序与执行结果 10 4.1 源程序 10 4.2 执行结果15 4.2.1 测试方法15 4.2.2 测试结果.155.使用说明.166.总结17汇编语言程序设计-约瑟夫环程序设计一、问题描述及要求1.1问题描述有 n个

4、人围成一圈，他们的编号为1到n。第一个人从1开始顺序报数凡报到m时，该人退出圈子。其后的人再从1开始顺序报数，直到最后的一个人退出圈子为止。输出依次退出圈子人的序号。n和m的值从键盘输入，且均小于200。1.2任务要求1） 程序采用子程序结构，结构清晰；2） 友好清晰的用户界面，能识别输入错误并控制错误的修改。二.设计说明2.1 简要分析 要正确、友好地完成用汇编语言设计约瑟夫环，我们应该完成以下几个功能：（1） 相关的交互提示用语（2） 定义的数据段中包含0-200（3） 编号数n的输入（4） 标志数m的输入（5） 输入设置为只允许输入三位数字,其余均不显示（6） 显示的结果是所有的退出序列

5、,并使用箭标连接2.2 概要设计2.2.1 主要模块（1）变量的定义DATA SEGMENT TABLE LABEL WORD COUNT = 1 REPT 200 DW COUNT COUNT = COUNT + 1 ENDM PRINT1 DB Please input the number of the people(less than 200):$PRINT2 DB Please the flag:$ MESS DB -$ DATA ENDS（2）编号数n输入的处理n1:MOV AH,07H INT 21H CMP AL,0 JB n1 CMP AL,9 JA n1 MOV DL,AL

6、 MOV AH,02H INT 21H MOV AH,0 SUB AL,30H MOV CX,AX MOV BX,CX n2:MOV AH,07H INT 21H CMP AL,0 JB n2 CMP AL,9 JA n2 MOV DL,AL MOV AH,02H INT 21H MOV AH,0 SUB AL,30H MOV DX,10 MUL DX MOV CX,AX MOV AX,BX MOV BX,100 MUL BX ADD CX,AX n3:MOV AH,07H INT 21H CMP AL,0 JB n3 CMP AL,9 JA n3 MOV DL,AL MOV AH,02H I

7、NT 21H MOV AH,0 SUB AL,30H MOV DX,AX ADD CX,DX PUSH CX MOV AX,CX MOV CX,2 MUL CX MOV BP,AX MOV AX,SI+BP MOV AX,0FFH MOV SI+BP,AX CALL CTRL LEA DX,PRINT2 MOV AH,09H INT 21H CALL CTRL （3）标志数m的输入处理n4:MOV AH,07H INT 21H CMP AL,0JB n4CMP AL,9JA n4MOV DL,ALMOV AH,02HINT 21HMOV AH,0 SUB AL,30H MOV CX,AX MO

8、V BX,CX n5:MOV AH,07H INT 21HCMP AL,0JB n5CMP AL,9JA n5MOV DL,ALMOV AH,02HINT 21H MOV AH,0 SUB AL,30H MOV DX,10MUL DXMOV CX,AXMOV AX,BX MOV BX,100 MUL BX ADD CX,AX n6:MOV AH,07HINT 21HCMP AL,0JB n6CMP AL,9JA n6MOV DL,ALMOV AH,02HINT 21HMOV AH,0SUB AL,30HMOV DX,AXADD CX,DX MOV DI,CX 2.2.2 主函数结构START:

9、 MOV AX,DATA MOV DS,AX LEA SI,TABLE MOV BX,0 MOV DX,0; CALL PRINT 三.算法描述【求解思路】我们知道第一个人(编号一定是m%n-1) 出列之后，剩下的n-1个人组成了一个新的约瑟夫环（以编号为k=m%n的人开始）:k k+1 k+2 . n-2, n-1, 0, 1, 2, . k-2并且从k开始报0。现在我们把他们的编号做一下转换：k - 0k+1 - 1k+2 - 2.k-2 - n-2k-1 - n-1变换后就完完全全成为了(n-1)个人报数的子问题.假如我们知道这个子问题的解：例如x是最终的胜利者，那么根据上面这个表把这个

10、x变回去不刚好就是n个人情况的解吗？！变回去的公式很简单，可以推出来为：x =(x+k)%n如何知道(n-1)个人报数的问题的解？对，只要知道(n-2)个人的解就行了。(n-2)个人的解呢？当然是先求(n-3)的情况 - 这显然就是一个倒推问题！下面写递推公式：令fi表示i个人玩游戏报m退出最后胜利者的编号，最后的结果自然是fnf1=0;fi=(fi-1+m)%i; (i1)有了这个公式，我们要做的就是从1-n顺序算出fi的数值，最后结果是fn。因为实际生活中编号总是从1开始，我们输出fn+1由于是逐级递推，不需要保存每个fi，程序也是异常简单：翻译成C语言如下代码所示int main() i

11、nt n, m, i, s=0; scanf(%d%d, &n, &m); for (i=2; i $ DATA ENDS CODE SEGMENT ASSUME CS:CODE,DS:DATA START: MOV AX,DATA MOV DS,AX LEA SI,TABLE ;SI指向首地址，BX作为移动指针 MOV BX,0 MOV DX,0 ;DX作为计数器 CALL PRINT ;执行该子程序后返回输入的编号数和标志值,分别为CX和DIL0:MOV AX,0 L1:MOV AX,SI+BX ;依次取出TABLE中的数据 CMP AX,0 JZ L2 ;AX等于0的时候跳转 CMP A

12、X,0FFH JZ L3 ;AX等于201的时候跳转 ADD DX,1 ;计数器加1 CMP DX,DI ;比较与标志值是否一致 JZ L4 ;一致则跳转L2:ADD BX,2 ;取下一个数据 JMP L1 L3:MOV BX,0 ;重置 JMP L1 L4:MOV AX,SI+BX ;取出数值 CALL OUTDEC MOV AX,0 MOV SI+BX,AX MOV DX,0 LOOP L0 MOV AH,2H INT 21HOUTDEC PROC PUSH AX PUSH DX PUSH CX PUSH BX MOV CL,100 DIV CL ;AX=AX/100,AL保存商,AH保存

13、余数 MOV BL,AH MOV DL,AL OR DL,30H ;转换成字符输出 MOV AH,02H ;显示输出 DL=输出字符 INT 21H MOV CL,10 MOV BH,0 MOV AX,BX DIV CL MOV DL,AL MOV BL,AH OR DL,30H MOV AH,02H ;显示输出 DL=输出字符 INT 21H MOV DL,BL OR DL,30H MOV AH,02H ;显示输出 DL=输出字符 INT 21H POP BX POP CX CMP CX,1 JZ L5 LEA DX,MESS ;显示箭标 MOV AH,09H INT 21H L5:POP

14、DX POP AX RET OUTDEC ENDP PRINT PROC PUSH AX PUSH DX PUSH BX LEA DX,PRINT1 MOV AH,09H ;显示字符串 INT 21H CALL CTRL n1:MOV AH,07H ;输入编号数n不回显 INT 21H CMP AL,0 ;每次输入均验证是否为0-9,否则输入无效 JB n1 CMP AL,9 JA n1 MOV DL,AL MOV AH,02H INT 21H MOV AH,0 SUB AL,30H ;转换成实际数值 MOV CX,AX MOV BX,CX ;将最高位数值存入BX n2:MOV AH,07H

15、INT 21H CMP AL,0 JB n2 CMP AL,9 JA n2 MOV DL,AL MOV AH,02H INT 21H MOV AH,0 SUB AL,30H ;转换成实际数值 MOV DX,10 MUL DX MOV CX,AX MOV AX,BX ;将最高位数值存入AX MOV BX,100 MUL BX ;将最高位数乘以100,作为百位 ADD CX,AX ;把百位数存入CX n3:MOV AH,07H INT 21H CMP AL,0 JB n3 CMP AL,9 JA n3 MOV DL,AL MOV AH,02H INT 21H MOV AH,0 SUB AL,30H

16、 MOV DX,AX ADD CX,DX ;把个位数存入CX,并入栈保存 PUSH CX MOV AX,CX MOV CX,2 MUL CX ;计算在TABLE中所对应的偏移字节 MOV BP,AX MOV AX,SI+BP ;取出TABLE中对应的数值 MOV AX,0FFH MOV SI+BP,AX CALL CTRL ;换行 LEA DX,PRINT2 MOV AH,09H ;显示字符串 INT 21H CALL CTRL ;换行 n4:MOV AH,07H ;输入标志数m不回显 INT 21H CMP AL,0 JB n4 CMP AL,9 JA n4 MOV DL,AL MOV AH

17、,02H INT 21H MOV AH,0 SUB AL,30H ;转换成实际数值 MOV CX,AX MOV BX,CX ;将最高位数值存入BX n5:MOV AH,07H INT 21H CMP AL,0 JB n5 CMP AL,9 JA n5 MOV DL,AL MOV AH,02H INT 21H MOV AH,0 SUB AL,30H ;转换成实际数值 MOV DX,10 MUL DX MOV CX,AX MOV AX,BX ;将最高位数值存入AX MOV BX,100 MUL BX ;将最高位数乘以100,作为百位 ADD CX,AX ;把百位数存入CX n6:MOV AH,07

18、H INT 21H CMP AL,0 JB n6 CMP AL,9 JA n6 MOV DL,AL MOV AH,02H INT 21H MOV AH,0 SUB AL,30H MOV DX,AX ADD CX,DX ;把个位数存入CX MOV DI,CX ;存入DI CALL CTRL POP CX POP BX POP DX POP AX RET PRINT ENDP CTRL PROC PUSH AX PUSH DX MOV AH,02H MOV DL,0AH ;打印换行符 INT 21H MOV DL,0DH ;打印回车符 INT 21H POP DX POP AX RET CTRL

19、ENDP CODE ENDS END START4.2 执行结果4.2.1 测试方法 本次测试我们采用的是通过提示用语，依次输入编号数和标志数,都为三位数,未满100的数高位为0. 输入的测试数据n与m均小于200,测试类型3种 (1)nm 测试例子:n=100 m=10 (2) nm 测试例子:n=50 m=100(3)n=m 测试例子:n=100 m=100 (4) 大于200的错误测试另外测试过程中尝试输入除数字以外的字符是无法显示的,这点无法截图显示。4.2.2 测试结果测试1测试2五、使用说明本次课程设计使用MASMPlus进行实验，截图如下：六、总结本次汇编语言课程设计是约瑟夫环的

20、程序设计,之前在C+语言以及数据结构的课程中均有过了解,所以这次上手还算比较容易,但是中途也遇到了汇编程序特有的难题,那就是输入的问题。课程设计的要求是输入两个小于200的整数,然而汇编语言中规定的中断功能一次只能输入一个字符,这与题目要求相悖甚远,一时竟陷入了编程困惑中,最后经过简单的思考发现只需要多次使用07H或01H中断就可以完成这个功能;但是在进一步的研究后发现,程序应该对数字以外的输入进行有效屏蔽,而不是接受所有的字符输入,于是我使用了CMP指令结合跳转指令解决了这个问题,程序要求输入后除了数字字符以外的所有输入将不再显示且也没有任何副作用,达到了一个比较完美的效果.另外程序引入了多

21、个子程序进行构架,力求将程序的可读性和效率发挥到极致,当然程序还有很多需要改进的地方:输入严重不符合规律时可以尝试给出更友好的交互提示.本次课程设计让我对汇编语言的几个重要知识点：寄存器问题、基本命令（mov,加减乘除操作，跳转、循环操作）、汇编中断程序的功能、汇编程序的基本格式以及函数的定义和调用有了一个比较清楚的了解。通过本次实验，我也学会了一种调试程序的方法，那就是“一个函数一个函数单独测试”的方法。另外一般在编写程序时，首先应该写出程序的主体框架，然后再进行修饰、完善。在查错时，我们一定要一条语句一条语句的推敲，绝不能疏忽大意，因为错误的程序往往都是形似而神非，往往错误就在那一两条语句，所以必须仔细。总之，这次汇编语言课程设计让我受益菲浅。是一次重要的，有意思的实践。本科生课程设计成绩评定表班级： 姓名： 学号：序号评分项目满分实得分1学习态度认真、遵守纪律102设计分析合理性103设计方案正确性、可行性、创造性204设计结果正确性405设计报告的规范性106设计验收10总得分/等级评语：注：最终成绩以五级分制记。优（90-100分）、良（80-89分）、中（70-79分）、及格（60-69分）、60分以下为不及格指导教师签名：20 年月日