汇编课程设计约瑟夫环程序设计

1、武汉理工大学汇编语言程序设计课程设计报告学 号： 0120910340228汇编课程设计题 目约瑟夫环程序设计学 院计算机科学与技术学院专 业计算机科学与技术专业班 级计算机科学与技术0902班姓 名 xx指导教师 xx2011年12月30日课程设计任务书学生姓名： xx 专业班级 xx 指导教师： xx 工作单位：计算机科学与技术学院 _题目: 约瑟夫环程序设计初始条件：理论：完成了汇编语言程序设计课程，对微机系统结构和80系列指令系统有了较深入的理解，已掌握了汇编语言程序设计的基本方法和技巧。实践：完成了汇编语言程序设计的4个实验，熟悉了汇编语言程序的设计环境并掌握了汇编语言程序的调试方法

2、。要求完成的主要任务: （包括课程设计工作量及其技术要求，以及说明书撰写等具体要求）进一步理解和掌握较复杂程序的设计方法，掌握子程序结构的设计和友好用户界面的设计。具体的设计任务及要求：1） 有 n个人围成一圈，他们的编号为1到n。第一个人从1开始顺序报数，凡报到m时，该人退出圈子。其后的人再从1开始顺序报数，直到最后的一个人退出圈子为止。输出依次退出圈子人的序号。n和m的值从键盘输入，且均小于200。2） 程序采用子程序结构，结构清晰；3） 友好清晰的用户界面，能识别输入错误并控制错误的修改。在完成设计任务后，按要求撰写课程设计说明书；对课程设计说明书的具体要求请见课程设计指导书。阅读资料：

3、1）ibmpc汇编语言程序设计实验教程实验2.42）ibmpc汇编语言程序设计（第2版）例6.11时间安排：设计安排一周：周1、周2：完成系统分析及设计。周3、周4：完成程序调试，和验收。周5：撰写课程设计报告。指导教师签名： 年 月 日系主任（或责任教师）签名： 年 月 日目 录1.需求说明 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 测试结果.15

4、 4.3 调试结果 185.使用说明.196.总结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、（5） 输入设置为只允许输入三位数字,其余均不显示（6） 显示的结果是所有的退出序列,并使用箭标连接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 2

6、1h cmp al,0 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 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 j

7、b n3 cmp al,9 ja n3 mov dl,al mov ah,02h int 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,

8、02hint 21hmov ah,0 sub al,30h mov cx,ax mov 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

9、dx,axadd cx,dx mov di,cx 2.2.2 主函数结构start: mov ax,data mov ds,ax lea si,table mov bx,0 mov dx,0; call print 3.算法描述【求解思路】我们知道第一个人(编号一定是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)个人报数

10、的子问题.假如我们知道这个子问题的解：例如x是最终的胜利者，那么根据上面这个表把这个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由于是逐级递推，不

11、需要保存每个fi，程序也是异常简单：翻译成c语言如下代码所示int main() int 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 ;依次取出

12、table中的数据 cmp ax,0 jz l2 ;ax等于0的时候跳转 cmp ax,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,4ch int 21h outdec proc push ax push dx push cx pus

13、h bx mov cl,100 div cl ;ax=ax/100,al保存商,ah保存余数 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

14、lea dx,mess ;显示箭标 mov ah,09h int 21h l5:pop 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 ;转换成实际数值 mo

15、v cx,ax mov bx,cx ;将最高位数值存入bx 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 ;将最高位数值存入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

16、dl,al mov ah,02h int 21h mov ah,0 sub al,30h 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 cm

17、p al,0 jb n4 cmp al,9 ja n4 mov dl,al mov ah,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 ;将最高位

18、数乘以100,作为百位 add cx,ax ;把百位数存入cx n6:mov ah,07h 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 d

19、l,0dh ;打印回车符 int 21h pop dx pop ax ret ctrl endp code ends end start 4.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测试3 测试4错

20、误结果分析：数据段之定义到200,事实上可以扩展定义到200-999如下图所示:4.3调试结果 使用debug命令检查程序的数据段是否出错5.使用说明 本次课程设计使用第三方的汇编ide-winmasm配合masm 5.0进行实验,ide截图如下:操作过程为:先编写源代码保存为joseph.asm,然后在ide中新建工程,经过编译后在x86系统环境下运行编译的程序即可得出结果.6.总结 本次汇编语言课程设计是约瑟夫环的程序设计,之前在c+语言以及数据结构的课程中均有过了解,所以这次上手还算比较容易,但是中途也遇到了汇编程序特有的难题,那就是输入的问题。课程设计的要求是输入两个小于200的整数,然而汇编语言中规定的中断功能一次只能输入一个字符,这与题目要求相悖甚远,一时竟陷入了编程困惑中,最后经过简单的思考发现只需要多次使用07h或01h中断就可以完成