约瑟夫环汇编课程设计.docx
《约瑟夫环汇编课程设计.docx》由会员分享，可在线阅读，更多相关《约瑟夫环汇编课程设计.docx（27页珍藏版）》请在冰点文库上搜索。
约瑟夫环汇编课程设计
学号：
0120910340228
汇编课程设计
题目
约瑟夫环程序设计
学院
计算机科学与技术学院
专业
计算机科学与技术专业
班级
计算机科学与技术0902班
姓名
XX
指导教师
XX
2011
年
12
月
30
日
课程设计任务书
学生姓名：
XX专业班级XX
指导教师：
XX工作单位：
计算机科学与技术学院__
题目:
约瑟夫环程序设计
初始条件：
理论：
完成了《汇编语言程序设计》课程，对微机系统结构和80系列指令系统有了较深入的理解，已掌握了汇编语言程序设计的基本方法和技巧。
实践：
完成了《汇编语言程序设计》的4个实验，熟悉了汇编语言程序的设计环境并掌握了汇编语言程序的调试方法。
要求完成的主要任务:
（包括课程设计工作量及其技术要求，以及说明书撰写等具体要求）
进一步理解和掌握较复杂程序的设计方法，掌握子程序结构的设计和友好用户界面的设计。
具体的设计任务及要求：
1）有n个人围成一圈，他们的编号为1到n。
第一个人从1开始顺序报数，凡报到m时，该人退出圈子。
其后的人再从1开始顺序报数，直到最后的一个人退出圈子为止。
输出依次退出圈子人的序号。
n和m的值从键盘输入，且均小于200。
2）程序采用子程序结构，结构清晰；
3）友好清晰的用户界面，能识别输入错误并控制错误的修改。
在完成设计任务后，按要求撰写课程设计说明书；对课程设计说明书的具体要求请见课程设计指导书。
阅读资料：
1）《IBM—PC汇编语言程序设计实验教程》实验2.4
2）《IBM—PC汇编语言程序设计（第2版）》例6.11
时间安排：
设计安排一周：
周1、周2：
完成系统分析及设计。
周3、周4：
完成程序调试，和验收。
周5：
撰写课程设计报告。
指导教师签名：
年月日
系主任（或责任教师）签名：
年月日
目录
1.需求说明…………………………………………………………………………………………………4
2.设计说明…………………………………………………………………………………………………4
2.1简要分析………………………………………………………………………………………4
2.2概要设计………………………………………………………………………………………4
2.2.1主要模块………………………………………………………………………4
2.2.2主函数结构………………………………………………………………….7
3.算法描述……………………………………………………………………………………………….8
3.1算法描述…………………………………………………………………………………….8
3.2流程框图………………………………………………………………………………………9
4.源程序与执行结果………………………………………………………………………………10
4.1源程序……………………………………………………………………………………………10
4.2执行结果…………………………………………………………………………………………15
4.2.1测试方法……………………………………………………………………………15
4.2.2测试结果………………………………………………………………………….15
4.3调试结果………………………………………………………………………………………18
5.使用说明………………………………………………………………………………………………….19
6.总结……………………………………………………………………………………………………………20
约瑟夫环程序设计
1.需求说明
4）有n个人围成一圈，他们的编号为1到n。
第一个人从1开始顺序报数，凡报到m时，该人退出圈子。
其后的人再从1开始顺序报数，直到最后的一个人退出圈子为止。
输出依次退出圈子人的序号。
n和m的值从键盘输入，且均小于200。
5）程序采用子程序结构，结构清晰；
6）友好清晰的用户界面，能识别输入错误并控制错误的修改。
2.设计说明
2.1简要分析
要正确、友好地完成用汇编语言设计约瑟夫环，我们应该完成以下几个功能：
（1）相关的交互提示用语
（2）定义的数据段中包含0-200
（3）编号数n的输入
（4）标志数m的输入
（5）输入设置为只允许输入三位数字,其余均不显示
（6）显示的结果是所有的退出序列,并使用箭标连接
2.2概要设计
2.2.1主要模块
（1）变量的定义
DATASEGMENT
TABLELABELWORD
COUNT=1
REPT200
DWCOUNT
COUNT=COUNT+1
ENDM
PRINT1DB'Pleaseinputthenumberofthepeople（lessthan200）:
$'
PRINT2DB'Pleasetheflag:
$'
MESSDB'->$'
DATAENDS
（2）编号数n输入的处理
n1:
MOVAH,07H
INT21H
CMPAL,'0'
JBn1
CMPAL,'9'
JAn1
MOVDL,AL
MOVAH,02H
INT21H
MOVAH,0
SUBAL,30H
MOVCX,AX
MOVBX,CX
n2:
MOVAH,07H
INT21H
CMPAL,'0'
JBn2
CMPAL,'9'
JAn2
MOVDL,AL
MOVAH,02H
INT21H
MOVAH,0
SUBAL,30H
MOVDX,10
MULDX
MOVCX,AX
MOVAX,BX
MOVBX,100
MULBX
ADDCX,AX
n3:
MOVAH,07H
INT21H
CMPAL,'0'
JBn3
CMPAL,'9'
JAn3
MOVDL,AL
MOVAH,02H
INT21H
MOVAH,0
SUBAL,30H
MOVDX,AX
ADDCX,DX
PUSHCX
MOVAX,CX
MOVCX,2
MULCX
MOVBP,AX
MOVAX,[SI+BP]
MOVAX,0FFH
MOV[SI+BP],AX
CALLCTRL
LEADX,PRINT2
MOVAH,09H
INT21H
CALLCTRL
（3）标志数m的输入处理
n4:
MOVAH,07H
INT21H
CMPAL,'0'
JBn4
CMPAL,'9'
JAn4
MOVDL,AL
MOVAH,02H
INT21H
MOVAH,0
SUBAL,30H
MOVCX,AX
MOVBX,CX
n5:
MOVAH,07H
INT21H
CMPAL,'0'
JBn5
CMPAL,'9'
JAn5
MOVDL,AL
MOVAH,02H
INT21H
MOVAH,0
SUBAL,30H
MOVDX,10
MULDX
MOVCX,AX
MOVAX,BX
MOVBX,100
MULBX
ADDCX,AX
n6:
MOVAH,07H
INT21H
CMPAL,'0'
JBn6
CMPAL,'9'
JAn6
MOVDL,AL
MOVAH,02H
INT21H
MOVAH,0
SUBAL,30H
MOVDX,AX
ADDCX,DX
MOVDI,CX
2.2.2主函数结构
START:
MOVAX,DATA
MOVDS,AX
LEASI,TABLE
MOVBX,0
MOVDX,0;
CALLPRINT
3.算法描述
【求解思路】
我们知道第一个人（编号一定是m%n-1）出列之后，剩下的n-1个人组成了一个新的约瑟夫环
（以编号为k=m%n的人开始）:
kk+1k+2...n-2,n-1,0,1,2,...k-2
并且从k开始报0。
现在我们把他们的编号做一下转换：
k-->0
k+1-->1
k+2-->2
...
...
k-2-->n-2
k-1-->n-1
变换后就完完全全成为了（n-1）个人报数的子问题.
假如我们知道这个子问题的解：
例如x是最终的胜利者，那么根据上面这个表把这个x变回去不刚好就是n个人情况的解吗？
！
！
变回去的公式很简单，可以推出来为：
x'=（x+k）%n
如何知道（n-1）个人报数的问题的解？
对，只要知道（n-2）个人的解就行了。
（n-2）个人的解呢？
当然是先求（n-3）的情况----这显然就是一个倒推问题！
下面写递推公式：
令f[i]表示i个人玩游戏报m退出最后胜利者的编号，最后的结果自然是f[n]
f[1]=0;
f[i]=（f[i-1]+m）%i;（i>1）
有了这个公式，我们要做的就是从1-n顺序算出f[i]的数值，最后结果是f[n]。
因为实际生活中编号总是从1开始，我们输出f[n]+1
由于是逐级递推，不需要保存每个f[i]，程序也是异常简单：
翻译成C语言如下代码所示
intmain（）
{
intn,m,i,s=0;
scanf（"%d%d",&n,&m）;
for（i=2;i<=n;i++）
s=（s+m）%i;
printf（"Thewinneris%d\n",s+1）;
}
类似的汇编代码亦可推之.
【流程框图】
省略部分细节,详见算法描述
4.源程序与执行结果（含测试方法和测试结果）
4.1源程序
DATASEGMENT
TABLELABELWORD
COUNT=1
REPT200
DWCOUNT
COUNT=COUNT+1
ENDM;可以选择编号数的上限
PRINT1DB'Pleaseinputthenumberofthepeople（lessthan200）:
$'
;用CX寄存器保存编号数
PRINT2DB'Pleasetheflag:
$';用DI寄存器保存标志值
MESSDB'->$'
DATAENDS
CODESEGMENT
ASSUMECS:
CODE,DS:
DATA
START:
MOVAX,DATA
MOVDS,AX
LEASI,TABLE;SI指向首地址，BX作为移动指针
MOVBX,0
MOVDX,0;DX作为计数器
CALLPRINT;执行该子程序后返回输入的编号数和标志值,分别为CX和DI
L0:
MOVAX,0
L1:
MOVAX,[SI+BX];依次取出TABLE中的数据
CMPAX,0
JZL2;AX等于0的时候跳转
CMPAX,0FFH
JZL3;AX等于201的时候跳转
ADDDX,1;计数器加1
CMPDX,DI;比较与标志值是否一致
JZL4;一致则跳转
L2:
ADDBX,2;取下一个数据
JMPL1
L3:
MOVBX,0;重置
JMPL1
L4:
MOVAX,[SI+BX];取出数值
CALLOUTDEC
MOVAX,0
MOV[SI+BX],AX
MOVDX,0
LOOPL0
MOVAH,4CH
INT21H
OUTDECPROC
PUSHAX
PUSHDX
PUSHCX
PUSHBX
MOVCL,100
DIVCL;AX=AX/100,AL保存商,AH保存余数
MOVBL,AH
MOVDL,AL
ORDL,30H;转换成字符输出
MOVAH,02H;显示输出DL=输出字符
INT21H
MOVCL,10
MOVBH,0
MOVAX,BX
DIVCL
MOVDL,AL
MOVBL,AH
ORDL,30H
MOVAH,02H;显示输出DL=输出字符
INT21H
MOVDL,BL
ORDL,30H
MOVAH,02H;显示输出DL=输出字符
INT21H
POPBX
POPCX
CMPCX,1
JZL5
LEADX,MESS;显示箭标
MOVAH,09H
INT21H
L5:
POPDX
POPAX
RET
OUTDECENDP
PRINTPROC
PUSHAX
PUSHDX
PUSHBX
LEADX,PRINT1
MOVAH,09H;显示字符串
INT21H
CALLCTRL
n1:
MOVAH,07H;输入编号数n不回显
INT21H
CMPAL,'0';每次输入均验证是否为0-9,否则输入无效
JBn1
CMPAL,'9'
JAn1
MOVDL,AL
MOVAH,02H
INT21H
MOVAH,0
SUBAL,30H;转换成实际数值
MOVCX,AX
MOVBX,CX;将最高位数值存入BX
n2:
MOVAH,07H
INT21H
CMPAL,'0'
JBn2
CMPAL,'9'
JAn2
MOVDL,AL
MOVAH,02H
INT21H
MOVAH,0
SUBAL,30H;转换成实际数值
MOVDX,10
MULDX
MOVCX,AX
MOVAX,BX;将最高位数值存入AX
MOVBX,100
MULBX;将最高位数乘以100,作为百位
ADDCX,AX;把百位数存入CX
n3:
MOVAH,07H
INT21H
CMPAL,'0'
JBn3
CMPAL,'9'
JAn3
MOVDL,AL
MOVAH,02H
INT21H
MOVAH,0
SUBAL,30H
MOVDX,AX
ADDCX,DX;把个位数存入CX,并入栈保存
PUSHCX
MOVAX,CX
MOVCX,2
MULCX;计算在TABLE中所对应的偏移字节
MOVBP,AX
MOVAX,[SI+BP];取出TABLE中对应的数值
MOVAX,0FFH
MOV[SI+BP],AX
CALLCTRL;换行
LEADX,PRINT2
MOVAH,09H;显示字符串
INT21H
CALLCTRL;换行
n4:
MOVAH,07H;输入标志数m不回显
INT21H
CMPAL,'0'
JBn4
CMPAL,'9'
JAn4
MOVDL,AL
MOVAH,02H
INT21H
MOVAH,0
SUBAL,30H;转换成实际数值
MOVCX,AX
MOVBX,CX;将最高位数值存入BX
n5:
MOVAH,07H
INT21H
CMPAL,'0'
JBn5
CMPAL,'9'
JAn5
MOVDL,AL
MOVAH,02H
INT21H
MOVAH,0
SUBAL,30H;转换成实际数值
MOVDX,10
MULDX
MOVCX,AX
MOVAX,BX;将最高位数值存入AX
MOVBX,100
MULBX;将最高位数乘以100,作为百位
ADDCX,AX;把百位数存入CX
n6:
MOVAH,07H
INT21H
CMPAL,'0'
JBn6
CMPAL,'9'
JAn6
MOVDL,AL
MOVAH,02H
INT21H
MOVAH,0
SUBAL,30H
MOVDX,AX
ADDCX,DX;把个位数存入CX
MOVDI,CX;存入DI
CALLCTRL
POPCX
POPBX
POPDX
POPAX
RET
PRINTENDP
CTRLPROC
PUSHAX
PUSHDX
MOVAH,02H
MOVDL,0AH;打印换行符
INT21H
MOVDL,0DH;打印回车符
INT21H
POPDX
POPAX
RET
CTRLENDP
CODEENDS
ENDSTART
4.2执行结果
4.2.1测试方法
本次测试我们采用的是通过提示用语，依次输入编号数和标志数,都为三位数,未满
100的数高位为0.
输入的测试数据n与m均小于200,测试类型3种
（1）n>m测试例子:
n=100m=10
（2）nn=50m=100
（3）n=m测试例子:
n=100m=100（4）大于200的错误测试
另外测试过程中尝试输入除数字以外的字符是无法显示的,这点无法截图显示
4.2.2测试结果
测试1
测试2
测试3
测试4
错误结果分析：
数据段之定义到200,事实上可以扩展定义到200-999
如下图所示:
4.3调试结果
使用debug命令检查程序的数据段是否出错
5.使用说明
本次课程设计使用第三方的汇编IDE----WinMasm配合MASM5.0进行实验,IDE截图
如下:
操作过程为:
先编写源代码保存为Joseph.asm,然后在IDE中新建工程,经过编译后在
x86系统环境下运行编译的程序即可得出结果.
6.总结
本次汇编语言课程设计是约瑟夫环的程序设计,之前在C++语言以及数据结构的课
程中均有过了解,所以这次上手还算比较容易,但是中途也遇到了汇编程序特有的难题,那就是输入的问题。
课程设计的要求是输入两个小于200的整数,然而汇编语言中规定的中断功能一次只能输入一个字符,这与题目要求相悖甚远,一时竟陷入了编程困惑中,最后经过简单的思考发现只需要多次使用07H或01H中断就可以完成这个功能;但是在进一步的研究后发现,程序应该对数字以外的输入进行有效屏蔽,而不是接受所有的字符输入,于是我使用了CMP指令结合跳转指令解决了这个问题,程序要求输入后除了数字字符以外的所有输入将不再显示且也没有任何副作用,达到了一个比较完美的效果.另外程序引入了多个子程序进行构架,力求将程序的可读性和效率发挥到极致,当然程序还有很多需要改进的地方:
输入严重不符合规律时可以尝试给出更友好的交互提示.
本次课程设计让我对汇编语言的几个重要知识点：
寄存器问题、基本命令（mov,
加减乘除操作，跳转、循环操作）、汇编中断程序的功能、汇编程序的基本格式以及函数的定义和调用有了一个比较清楚的了解。
通过本次实验，我也学会了一种调试程序的方法，那就是“一个函数一个函数单独测试”的方法。
另外一般在编写程序时，首先应该写出程序的主体框架，然后再进行修饰、完善。
在查错时，我们一定要一条语句一条语句的推敲，绝不能疏忽大意，因为错误的程序往往都是形似而神非，往往错误就在那一两条语句，所以必须仔细。
总之，这次汇编语言课程设计让我受益菲浅。
是一次重要的，有意思的实践。
本科生课程设计成绩评定表
班级：
XX班 姓名：
XX学号：
XX
序号
评分项目
满分
实得分
1
学习态度认真、遵守纪律
10
2
设计分析合理性
10
3
设计方案正确性、可行性、创造性
20
4
设计结果正确性
40
5
设计报告的规范性
10
6
设计验收
10
总得分/等级
评语：
注：
最终成绩以五级分制记。
优（90-100分）、良（80-89分）、中（70-79分）、
及格（60-69分）、60分以下为不及格
指导教师签名：
201年 月 日
升级会员 