猴子选大王课程设计报告

-.z.课程设计报告课程设计题目：猴子选大王学生:吴兆专业:软件工程班级:1321813学号:6指导教师:吴建东2015年1月9日东华理工大学目录一：需求分析问题描述根本要求需求分析二：概念设计三：详细设计四：调试分析和测试结果五：总结六：源代码一：需求分析问题描述一堆猴子都有编号，编号是1，2，3...m,这群猴子〔m个〕按照1-m的顺序围坐一圈，从第1开场数，每数到第N个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。根本要求输入数据：输入m,nm,n为整数，n<m。输出形式：中文提示按照m个猴子，数n个数的方法，输出为大王的猴子是几号，建立一个函数来实现此功能。3.需求分析1.输入数据m,n。2.计算出最终猴子大王的序号。3.模拟出整个过程4.找到适宜的数据构造处理这个问题。5.找到正确的方法解决这个问题。二：概念设计这个问题属于约瑟夫环问题，根据问题描述得知，该问题中m个猴子围坐在一群形成首尾相接的环，因此可用循环链表解决。从第n个猴子开场出列相当于从链表中删除一个节点。该程序主要有三个模块组成，建立循环链表，报数利用循环链表实现猴子的出列，最终剩下的猴子即猴王。具体步骤如下：第一步首先创立循环链表。第二步向链表中填入猴子的编号。第三步找第一个开场报数的猴子。第四步数到n让这个猴子出列。第五步接着开场报数，重复第四步，直到剩下最后一个猴子，就是大王。程序流程图如下：开场开场进展1-m的报数进展1-m的报数删除第n只猴子删除第n只猴子否剩下的猴子数是否为1剩下的猴子数是否为1是输出猴子大王的序号输出猴子大王的序号完毕完毕三：详细设计程序中使用的存储构造structL{ intnum; structL*ne*t;};intn;inti=0;程序中使用的循环构造structL*LisDelete(structL*head,intm)//报数为m的退出.{ structL*p,*q; intj=0; p=head; i=i+1; if(p->ne*t==head)return(p); while(j<m-2) { p=p->ne*t; j=j+1; } q=p->ne*t;p->ne*t=q->ne*t; head=p->ne*t; printf("%d第%d个猴子离开.\n",i,q->num); free(q); LisDelete(head,m);}主函数voidmain(){ structL*head; structL*p; intm,N; printf("*********************************************************\n"); printf("猴子选大王:\n"); printf("一堆猴子都有编号，编号1,2,3...m，这群猴子(m个)按照1-m\n"); printf("的顺序围坐一圈，从第1开场数，每数到第n(n<m)个，该猴子就要\n"); printf("离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该\n"); printf("猴子为大王\n"); printf("*********************************************************\n"); printf("输入n(所有猴子的总数):"); scanf("%d",&N); printf("输入m(离开的猴子所报的数):"); scanf("%d",&m); printf("***********************************\n"); if(m>N||m<=0||N<=0) { ERROR(); } else { if(m==1) { printf("结果:第%d个猴子为大王.\n",N); } else {head=creat(N); printf("过程:\n"); p=LisDelete(head,m);printf("***********************************\n"); printf("结果:第%d个猴子为大王.\n",p->num); printf("***********************************\n"); } }}四：调试分析和测试结果得到了预期的结果五：总结本次课程设计，参考了相关教科书和参考书对二分法查找与各种排序方法的描述，对相关功能所需构造体和函数有了初步构思之后，经过代码的输入、语法改错，调试执行等过程，完成了一个简单的功能系统。通过一周时间，从初步思路形成到根本功能完成，对数据构造设计实践与应用局部根本了解了。从本次课程设计我觉得我应该把所学根底知识与具体问题实践结合，根本知识要扎实，对待问题要各方面分析。数据构造与算法设计是一种锻炼人清晰思路的科目，我们应该通过屡次实践让自己的知识得到稳固。六：源代码*include<stdio.h>*include<malloc.h>*defineNULL0*defineLENsizeof(structL)structL{ intnum; structL*ne*t;};intn;inti=0;structL*creat(intN)//建立动态循环链表.{ printf("将猴子顺序编号为：\n"); structL*head; structL*p1,*p2; n=0; p1=p2=(structL*)malloc(LEN); p1->num=1; printf("%d",p1->num); head=NULL; while(p1->num<=N) { n=n+1; if(n==1)head=p1; elsep2->ne*t=p1; p2=p1; p1=(structL*)malloc(LEN); p1->num=n+1; if(p1->num<=N) printf("%d",p1->num); } p2->ne*t=head;//尾指针指向头指针. printf("\n"); printf("***********************************\n"); printf("\n"); return(head);}structL*LisDelete(structL*head,intm)//报数为m的退出.{ structL*p,*q; intj=0; p=head; i=i+1; if(p->ne*t==head)return(p); while(j<m-2) { p=p->ne*t; j=j+1; } q=p->ne*t;p->ne*t=q->ne*t; head=p->ne*t; printf("%d第%d个猴子离开.\n",i,q->num); free(q); LisDelete(head,m);}ERROR(){ printf("m>N或者m<=0或者N<=0!!!ERROR!\n");}voidmain(){ structL*head; structL*p; intm,N; printf("*********************************************************\n"); printf("猴子选大王:\n"); printf("一堆猴子都有编号，编号1,2,3...m，这群猴子(m个)按照1-m\n"); printf("的顺序围坐一圈，从第1开场数，每数到第n(n<m)个，该猴子就要\n"); printf("离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该\n"); printf("猴子为大王\n"); printf("*********************************************************\n"); printf("输入n(所有猴子的总数):"); scanf("%d",&N); printf("输入m(离开的猴子所报的数):"); scanf("%d",&m); printf("***********************************\n"); if(m>N||m<=0||N<=0) { ERROR(); } else { if(m==1) { printf("结果:第%d个猴子为大王.\n",N); } else { h