约瑟夫环 实验报告

程序设计课程设计报告

项目名称：约瑟夫环学生姓名：学号：班级：计科1111班指导老师：日期：2013年1月3号

1、项目描述约瑟夫问题主要是n个人围坐成一个圈，然后分别给每个参与者编一个号，再定义一个循环数，由玩家自定义起始报数者，当游戏开始时，报数为循环数的人被踢出，其他人继续。此设计就是通过一位数组、一维结构体数组与循环链表来实现这些功能的。2、项目的需求分析在软件工程中，需求分析指的是在建立一个新的或改变一个现存的系统或产品时，确定新系统的目的、范围、定义和功能时所要做的所有工作。需求分析是软件工程中的一个关键过程。在这个过程中，系统分析员和软件工程师确定顾客的需要。只有在确定了这些需要后他们才能够分析和寻求新系统的解决方法。需求按层次分为用户需求和系统需求：用户需求是用自然语言加图的形式给出的、关于系统需要提供哪些服务以及系统操作受到哪些约束的声明；系统需求详细地给出系统将要提供的服务以及系统所受到的约束，系统需求文档有时也称为功能描述，应该是精确的，它可能成为系统买方和软件开发者之间合同的重要内容。软件系统需求常常分为功能需求和非功能需求：功能需求包括对系统应该提供的服务、如何对特殊输入做出反应，以及系统在特定条件下的行为的描述，在某些情况下，功能需求可能还需声明系统不应该做什么；非功能需求是对系统提供的服务或功能的约束，包括时间约束、开发过程的约束和所受到的标准的约束，非功能需求经常适用于整个系统而不是个别的系统功能或服务，例如性能，可靠性，安全性和可用性等。非功能需求通常会比个别的功能需求更加关键，它会影响整个系统的体系结构，而不是个别的组件。例如，为了保证系统的性能需求，就必须合理组织系统使得组件之间的通信量达到最小。图SEQ图\*ARABIC1需求获取和分析的产品2.1、界面需求 MicrosoftVisualC++6.0软件里面实现代码操作,MicrosoftOfficeWord20032.2、输入输出要求 才用C++中的输入输出函数，即cin与cout，而在C中用printf即可。2.3、功能需求 （1）采用一维数组解决约瑟夫问题； （2）采用一维结构体数组解决约瑟夫问题；2.4、程序的结构要求 要包含以下函数： 主函数：main(); 一维数组：a[i] 一维结构体数组：structNode{ boolflag;//1为未出列0为已列出}; 约瑟夫问题的实现：voidJosephus(Node*p,intn,intm)//n为总人数，m为报数上限输出函数： 3、项目设计软件设计在软件工程过程中处于技术核心，并且它的应用与所使用的软件过程模型无关。一旦对软件需求进行分析和建模，软件设计就开始了。软件设计是建模活动的最后一个软件工程活动，接着便要进入构造阶段（代码生成和测试）。在软件系统设计的过程中，开发者定义项目的设计目标，将系统分解为更小的子系统，这些子系统可以由各个团队分别实现，开发者还要选择构建系统的策略，比如硬件/软件策略、持久性数据管理策略、全局控制流、访问控制策略、边界条件处理等。系统设计后得到的是一个包括子系统分解和每个策略都清晰描述的模型。系统设计是与算法无关的，它由一些活动组成，每一个活动都专注于分解系统整个问题中的某一部分：标识设计目标。开发者标识并区分应进行优化的各种系统特征的优先顺序。设计初始子系统分解。根据用例和分析模型将系统分解成一些小部分，在此活动中，开发者将采用标准的体系结构风格（分层体系结构，容器体系结构，客户机-服务器体系结构，管道和过滤器体系结构）作为起始点。求精子系统分解以应对设计目标。初始的分解大都不满足所有的设计目标，必须不断分解和求精，直到所有的设计目标都满足了。主函数main()主函数main()一维数组Yiweishuzu()以为结构体数组Yiweijiegoutishuzu()选择界面一维数组Yiweishuzu()以为结构体数组Yiweijiegoutishuzu()选择界面约瑟夫环问题的实现约瑟夫环问题的实现约瑟夫环问题的实现约瑟夫环问题的实现输出函数输出函数输出函数输出函数3.2、程序结构设计 （1）一位数组：定义两个变量（游戏总人数n，游戏循环数m），利用两个for()循环，第一个控制总次数，第二个控制报数，当报到数值m时，输出对应的游戏者的编号； （2）一维结构体数组：定义一个一维结构体数组，组内为游戏者的编号n，其余与（1）同，在使用num编号时，由结构体名调用。3.3、数据结构及类型设计 一维结构体数组，一位数组3.4、功能模块设计 （1）一位数组函数：输入游戏总人数及游戏循环数，利用for()和while()循环实现游戏者的踢出； （2）一维结构体数组：输入游戏总人数及游戏循环数利用两个for()循环实现游戏者的踢出；4、测试用例设计软件工程中的测试用例是一组条件或\o"变量"变量（输入数据和期望结果的集合），测试者根据它来确定\o"应用软件"应用软件或\o"软件系统"软件系统是否正确工作。测试用例是通过实验达到引起构件失效和发现构件故障的目的。确定软件程序或系统是否通过测试的方法叫做\o"测试准则"测试准则。一个测试用例有5个属性：名称、可执行的路径全称、输入数据、测试预言（期望的测试结果与输出结果的比较）和日志（测试产生的输出）。4.1、输入/输出测试用例4.2、函数功能测试用例 一位数组：项目/软件约瑟夫游戏版本MicrosoftVisualC++6.0作者功能模块名利用一维数组实现游戏要求用例编号Em0001修改历史编制时间2013.01.03功能特性将参与游戏者逐个踢出去测试目的检验代码是否可以实现以上功能预置条件测试数据总人数可自定义（如8），循环数：可自定义（比如5）操作描述建立一个动态数组，将总人数存储进去,然后利用for()循环将每次游戏报数为5输出期望结果输出的顺序为5、2、8、7、1、4、6实际结果测试人员开发人员测试日期2013.01.03一维结构体数组：项目/软件约瑟夫游戏版本MicrosoftVisualC++6.0作者功能模块名用一维结构体数组实现约瑟夫游戏要求用例编号Em0001编制人修改历史编制时间2013.01.03功能特性利用一维结构体数组实现约瑟夫问题的输入输出测试目的查看程序是否正确预置条件建立一个一维结构体测试数据总人数：可以自己输入，游戏循环数：自己输入操作描述期望结果输出顺序为5、2、8、7、1、4、6、3实际结果测试人员开发人员测试日期2013.01.03关键代码设计创建动态数组并计算过程： Node*a=newNode[n]; intk=n,count=0,max=m; for(inti=0;i<n;i++) { a[i].flag=1; //先把没有报数的人标记为1 } for(i=0;;i=(i+1)%n) { if(a[i].flag==1) { count++; //如果这个人是有标记的话，计数++,表示的是被标记的总人数，即所有的玩家人数 } if(count==max) //当报数达到我们所需的最大报数max时，输出 { cout<<i+1<<""; count=0; //同时计数清零 k--; //这时候需要处理的人数就会少一个 a[i].flag=0; //把它标记为已经报数 } if(k==0) //需要处理的人数为1时就跳出循环 { cout<<endl; cout<<"Thewinneris:"<<i+1<<endl; break; } }}以及一维数组中的计算及其动态数组的建立：int*a=newint[n]; for(inti=0;i<n;i++) { a[i]=i+1;//给每个小孩编号 } printf("Thestartnumberis:"); for(i=0;i<n;i++) { printf("%d\n",a[i]); intk=1; //表示处理第K个离开的小孩 inti=-1; //数组下标（因为第一个下标是0） printf("Theleaveorderis:"); while(1) { for(intj=0;j<m;) { i=(i+1)%n;//数组的下标 if(a[i]!=0)//判断人是不是还在圈中 { j++;//因为数到interval的时候，会归为0，如果在是0的地方J也加1的话，，则会导致数数不正确 } } if(k==n)//看是否为最后一个小孩 { break; } printf("%d,",a[i]); a[i]=0; //已经出圈的归为0 k++; //处理第k+1个小孩 } break; } printf("\n"); for(i=0;i<n;i++) { if(a[i]!=0) { printf("Thewinneris:%d\n",a[i]);//输出最终留下的 } } 5.1、总控程序关键代码一维数组：程序的结构：主函数中处理#include<iostream>usingnamespacestd;inti;voidmain(){ intnum=0; intinterval;D: printf("Pleaseinputthetotalnumber:"); scanf("%d",&num); if(num<=0) { printf("Error!pleaseinputagain!"); getchar(); gotoD; } H: printf("Pleseainputthestopnumber:"); scanf("%d",&interval); if(interval<=0) { printf("Error!pleaseinputagain!"); getchar(); gotoH; } int*a=newint[num]; for(i=0;i<num;i++) { a[i]=i+1;//给每个小孩编号 } printf("Thestartnumberis:"); for(i=0;i<num;i++) { printf("%d\n",a[i]); intk=1; //表示处理第K个离开的小孩 inti=-1; //数组下标（因为第一个下标是0） printf("Theleaveorderis:"); while(1) { for(intj=0;j<interval;) { i=(i+1)%num;//数组的下标 if(a[i]!=0)//判断人是不是还在圈中 { j++;//因为数到interval的时候，会归为0，如果在是0的地方J也加1的话，，则会导致数数不正确 } } if(k==num)//看是否为最后一个小孩 { break; } printf("%d,",a[i]); a[i]=0; //已经出圈的归为0 k++; //处理第k+1个小孩 } break; } printf("\n"); for(i=0;i<num;i++) { if(a[i]!=0) { printf("Thewinneris:%d\n",a[i]);//输出最终留下的 } }}}一维结构体：程序的结构：#include<iostream>usingnamespacestd;structNode{ boolflag; //标记每个数数的人，1为未出列0为已出列};voidmain(){ intn;//总人数 intm;//数到就要出列的D: printf("Pleaseinputthetotalnumber:"); scanf("%d",&n); if(n<=0) { printf("Error!pleaseinputagain!"); getchar(); gotoD; } H: printf("Pleseainputthestopnumber:"); scanf("%d",&m); if(m<=0) { printf("Error!pleaseinputagain!"); getchar(); gotoH; } Node*a=newNode[n]; intk=n,count=0,max=m; for(inti=0;i<n;i++) { a[i].flag=1; //先把没有报数的人标记为1 } for(i=0;;i=(i+1)%n) { if(a[i].flag==1) { count++; //如果这个人是有标记的话，计数++,表示的是被标记的总人数，即所有的玩家人数 } if(count==max) //当报数达到我们所需的最大报数max时，输出 { cout<<i+1<<""; count=0; //同时计数清零 k--; //这时候需要处理的人数就会少一个 a[i].flag=0; //把它标记为已经报数 } if(k==0) //需要处理的人数为1时就跳出循环 { cout<<endl; cout<<"Thewinneris:"<<i+1<<endl; break; } }}}6、程序调试与测试测试活动技术主要包括：构件检查、可用性测试、单元测试、集成测试和系统测试。构件检查是通过对源代码的手工检查发现单个构件中的故障。可用性测试用于找出现实系统做了什么和用户所期望系统应该做什么之间的差异。单元测试通过使用测试桩程序和测试驱动程序来隔离单个构件的方法以发现故障，也可以通过对一个构件执行测试用例来完成这个功能。集成测试通过集成多个构件来查找故障。系统测试狐妖关注整个系统、系统的功能和非功能需求以及目标环境等。6.1、用例1测试结果6.2、用例2测试结果7、总结 约瑟夫问题理解起来很容易，但在写代码时，总是会不知道从哪里开始下手，每次开始着手写的时候都只是写个开头，总是在写后来核心的计算部分时候写着写着就会觉得哪里不对劲，然后又重新开始写，浪费了很多时间。后来程序写出来以后调试好久，总是会在输出的部分会出差错，后来用了程序中不常用的goto语句才实现的。而且由于对核心部分的理解不是很透彻，所以在检验结果的时候，一个不小心输出时，被提出者就会要么往前一位，要么退后一位，得不到正确结果。有了写数组时候的经验写以为结构体数组的时候稍微轻松点，但是由于忘记了之前学习过的结构体，所以在写程序的时候结构体中究竟存什么也很让人费解，因为约瑟夫问题所需的变量完全可以不用结构体。所以在这个问题上花费了大量的时间，后来经过和同学的讨论才确定下来的，用一个标记来作为结构体中所存的变量，这样在计算的时候不仅更加方便而且也解决了问题。通过这次的项目，我不仅复习了以前学习的知识，同时也了解到了很多写程序的方法。对于不同变量的处理方法，以及用不同的解题思路去解决同一个问题。自己在以后的学习中也可以运用到这次项目当中所学到的技巧和知识。8、附件：项目程序代码一维数组：程序的结构：主函数中处理#include<iostream>usingnamespacestd;inti;voidmain(){ intnum=0; intinterval;D: printf("Pleaseinputthetotalnumber:"); scanf("%d",&num); if(num<=0) { printf("Error!pleaseinputagain!"); getchar(); gotoD; } H: printf("Pleseainputthestopnumber:"); scanf("%d",&interval); if(interval<=0) { printf("Error!pleaseinputagain!"); getchar(); gotoH; } int*a=newint[num]; for(i=0;i<num;i++) { a[i]=i+1;//给每个小孩编号 } printf("Thestartnumberis:"); for(i=0;i<num;i++) { printf("%d\n",a[i]); intk=1; //表示处理第K个离开的小孩 inti=-1; //数组下标（因为第一个下标是0） printf("Theleaveorderis:"); while(1) { for(intj=0;j<interval;) { i=(i+1)%num;//数组的下标 if(a[i]!=0)//判断人是不是还在圈中 { j++;//因为数到interval的时候，会归为0，如果在是0的地方J也加1的话，，则会导致数数不正确 } } if(k==num)//看是否为最后一个小孩 { break; } printf("%d,",a[i]); a[i]=0; //已经出圈的归为0 k++; //处理第k+1个小孩 } break; } printf("\n"); for(i=0;i<num;i++) { if(a[i]!=0) { printf("Thewinneris:%d\n",a[i]);//输出最终留下的 } }}}一维结构体：程序的结构