约瑟夫问题面向对象(C++版)程序设计报告

学院班级学姓名摘要本作业解决Josephus问题的求解，以及Josephus问题的扩展的求解。Josephus问题的描述如下：n个小孩闱成圈做游戏，游戏将决定出一个胜利者（Josephus问题扩展则可以求出多个获胜者）。假定一个数m,从第s个小孩起，顺时针计数，每次数到第m个小孩，该小孩离开，接着又从下一个小孩开始数，数到第m个小孩，该小孩也离开，如此不断反复进行，最后剩下的一个（多个）小孩为胜利者。对于给定的n、m和s,找出最后的胜利者。Josephus问题的扩展则是在原来Josephus问题基础上增加了“获胜者个数”这一限制。在本作业中Josephus问题的解决主要是基于对彖的解决方去討咯込^寮（Object-BasedSolution）,其中涉及到BoyRing类和Jose軽適|类逹要实现方式则是坏链表,这使得Josephus问题得到一个解决。林迹作业的程序设计达到了要求,实现的方式相对较女最终绪讐灣缠銚影g柬设计者比较满意。目录TOC\o"1-5"\h\z\o"CurrentDocument"1摘要 3I十3I十1*^'O* 3\o"CurrentDocument"1.3开发工具 3\o"CurrentDocument"1.4应用平台 3\o"CurrentDocument"2详细设计 4丿i；纟石4,4匚X/j冃匕8\o"CurrentDocument"2.3算法实现 10\o"CurrentDocument"2.4开发口志 15\o"CurrentDocument"3程序调试及运行 15\o"CurrentDocument"3.1程序运行结果 153.2程序使用说明 183.3程序开发总结 18\o"CurrentDocument"4附件（源程序） 191摘要1.1设计题目Josephus问题(JosephusProblem)及其扩展1.2设计内容利用循环链表运用面向对象的设计方案实现Josephus问题的求解。Josephus问题如下：n个小孩围成圈做游戏，游戏将决定出一个胜利者。假定一个数m,从第s个小孩起，顺时针计数，每次数到第m个小孩，该小孩离开，接着又从下一个小孩开始数，数到第m个小孩，该小孩也离开，如此不断反复进行，最后剩下的一个小孩为胜利者。对于给定的n、m和s,找出最后的胜利者。其中n、m和s都为正整数，切有n>l,l<=m<=n和l<=s<=n的关系。程序扩展是在Josephus问题的基础上，由原来的1个获胜者扩展到m个胜利者，其实现的方式和Josephus问题的实现基本相同。其中11、m、s的要求和Josephus问题的完全相同，新增的l<=w<=iio1.3开发工具主要用到的开发工具为：DevC卄5.0和Win32o1.4应用平台Wmdows2000/XP/Vista32位2详细设计2.1程序结构改程序分成三个抽象层次，第一层是应用层，直接指使Jose类对象去完成求解工作；第二层是Jose类层，描述Josephus问题的求解细节；第三层是BoyRing类层，辅助Jose类完成求解过程（上述三层间的关系描述如图J-1,这也是程序模块间的关系）。如图J-1所示，main函数用到了Jose类，Jose类乂用到了BoyRmg类。整个程序的实现流程如图J-2o程序中类：BoyRing类和Jose类BovRing类中的数据成员有：Boy*pBegm,*pivot,*pCunent三个指针，分别为起始位置的指针，哨兵指针，被切掉位置指针。BoyRing类中的成员函数分别为：

图J-2.Josephus问题整体程序流程图图J-2.Josephus问题整体程序流程图函数相关说明BoyRing(mt11);构造函数。参数为类型的n,主要完成空间申请，构造链表，初始化个参数。VoidcountBy(intm);用循环的方式数m个小孩，参数为mt类型的mmtgetNuni()const;为一个const函数，返回小孩的编号，无参数voiddisengage();利用指针实现小孩离队，无参数voidpimtAll()const;以特定的格式输出小孩的编号，无参数。本函数在在本程序中没有起任何作用可以去除。〜BoyRmg();析构函数。释放申请空间，无参数

Jose类中的数据成员有：lilt11,m,s三个11H类型的数，分别表示小孩的总数、间隔数、开始数的小孩编号。Jose类中的成员函数分别为：函数相关说明Jose(intboys,mtinterval、mtbegin=l);构造函数，主要功能初始化各个参数，校验输出的m、s参数为mtboys,intinterval,mtbegm=lvoidgetWumei()const;求胜利者函数，实例化BoyRing类，以特定的格式输出离队小孩的编号和获胜小孩的编号，无参数主要函数：BoyRing：:BovRHig(mtn);{if(n<2)tliiowexceptionQ;pBegin=newBoy[n];fbr(inti=l;i<=n;i++){pBegin[i-l].next=&pBegin[i%n];pBegiii[i-l].code=i;}pivot=pCurrent=&pBegiii[n-l];图J-3.BoyRnig::BoyRing(mtn)函数流程图〃图图J-3.BoyRnig::BoyRing(mtn)函数流程图voidBoyRing::countBy(mtm){fbr(inti=l;i<=m;++i){pivot=pCunent;pCurrent=pCunent->next;〃挪到下一个小孩的位置}}〃图J-4为流程图图J-4.voidBoyRnig::countBy(iiitm)函数流程图voidJose::getWumer()const{cout«MThereaie,«n«Mboys.nBoysleavedino】deE\n”;//输出小孩总个数BoyRingx(n);〃创建环状链表(Boymg类对彖实例化x)x.countBy(s-l);//转到开始位置foi(inti=ljnuninLme=O;i<n;++i){x.countBy(m);cout«H,,«x.getNuniQ«(++nunuiiLme%10? V);x.disengageQ;i}丿cout«H\nthewinneris\n',«x.getNumQ«H\nH;函数之间的参数传递:

由主函数依次输入n、m、s三个数的值；主函数调用Jose::getWumer()函数将n、m、s的值传递到Jose类；同时，Jose类的内部函数Jose::Jose(intbovsjntmten^aLiiitbegin=l)得到传入的参数n、m、s,并对三个数的值进行校验；在voidJose::getWnuier()const函数将n、m>s三个参数通过将BoyRing类实例化成对象实例x,调用x.countByO函数出入到类BovRing中。传入BoyRmg类中的各个带参数的函数。2.2主要功能Josephus问题程序的主要功能是：通过外界输入3个或(4个)相关参数，在Josephus问题程序成后输出Josephus的的相关结果。利用循环链表实现Josephus的求解。Josephus问题如下：n个小孩围成圈做游戏，游戏将决定出一个胜利者。假定一个数m,从第s个小孩起，顺时针计数，每次数到第m个小孩，该小孩离开，接着乂从下一个小孩开始数，数到第m个小孩，该小孩也离开，如此不断反复进行，最后剩下的一个小孩为胜利者。对于给定的n、m和s,找出最后的胜利者。其中n、m和s都为正整数，切有n>l,l<=m<=n和1.〈二s〈二n的关系。Josephus问题主要是利用环链表、指针转向。其实现如图J-5：算法Jose类｛算法Jose类｛内部数据成员小孩总数n开始位置s计数间隔m界面构造函数求获胜者者函数其中，Jose类界面具有的具体操作描述为：构造函数小孩总数校验开始位置校验计数河隔数校验求获胜者函数输出求解开始，小孩总数创建坏链表（BoyRuig类对彖）转到链表开始位置while（小孩多于1个（w个））数m个小孩小孩输出小孩离队endwhile输出获胜者在Jose类用到了BoyRing类,其设计如下:BovRuig类｛内部数据成员小孩结构指针当前小孩指针小孩哨兵指针界面构造函数析构函数数m个小孩小孩离队返回当前小孩编号输出所有小孩其中，BoyRing类界面的具体操作描述为:构造函数按小孩的个数申请空间初始化坏状结构，为小孩编号指针初始化析构函数释放申请空间数m个小孩函数for（m间隔）挪到下一个小孩的位置endfbr小孩离队函数哨兵指向的小孩指向当前小孩的的卜•一个小孩当前小孩指针赋值与哨兵指针返回当前小孩的编号返回当前小孩指针指向的小孩编号输出所以小孩按特定的格式输出坏中所有小孩的编号2.3算法实现//boyiiiig.h#ifiidefHEADER_BOYRING#defiiieHEADER_BOYRINGstiuctBoy{intcode;Bov*next;J z};// classBoyRuig{Boy*pBegiii,*pivot,*pCunent;public:BovRHig(intn);voidcountBy(intm);intgetNum()const;voiddisengageQ;voidprmtAll()const;-BoyRingO；}；//=———==———==—#endif//HEADER.BOYRING//boyriiig.cpp11=================#mcludenboyring.hH#iiiclude<iostreain>usingnamespacestd;// 〃构造函数// BovRiiig::BoyRmg(intn){if(n<2)throwexception。;//发生错误时自动跳出pBegin=newBoy[n]; 〃申请一个新的Boy空间，pBegin指向该空间的开始处fbr(iiiti=l;i<=n;i++){pBegin[i-l].next=&pBegin[i%n]^/形成链表pBegin[i-l].code= 给孩子孩子编号}pivot=pCurrent=&pBegm[n-l];//各指针初始化}// //数m个小孩voidBoyRuig::countBv(iiitm){for(mti=l;i<=m;++i){pivot=pCuirent;pCunent=pCuiTent->next;//挪到下一个小孩的位置}}// 〃返回当前小孩编号intBovRuig::getNum()const{retuinpCunent->code;}// 〃小孩离队// voidBoyRiiig::disengageQ{pivot->next=pCunent->next;//哨兵指针指向的小孩指向当前小孩的下一个小孩pCunent=pivot;//当前小孩指针等于哨兵指针}// 〃输出所有小孩编号// voidBoyRiiig::piiiitAll()const{intnununLme=0;Boy*p=pCunent;do{cout«H"«p->code;if(!(++numinLme%10))cout«H\nV/每一行输出10个p=p->next;}wlule(p!=pCunent);cout«H\nn;}// 〃析构函数BovRuig:>BoyRmg(){delete[]pBegm^/释放申请空间}// //jose.hIi==—=======#ifiidefHEADER_JOSE#defiiieHEADER_JOSEclassJose{protected:liltn,m.s;public:Jose(intboys,mtinterval,mtbegin=l);voidgetWiimer()const;#endif//HEADER.JOSE//jose.cpp//=———==———===——#mcludenboyring.hH#iiicludenjose.hH#mclude<iostreain>usingnamespacestd;// 〃构造函数// Jose::Jose(mtboys,iiitinterval,intbegin):n(boys)jn(inteival),s(begin){if(n<2||m<l||m>=n||s<l||s>=n)//校验n、m.s{cerr«Hdataenor.\nH;thiowexception。;//出现错误跳出}}// 〃求获胜者voidJose::getWimier()constcout«nThereareH«n«Hboys.\nBoysleavedmoider:\nM;//输出小孩总个数BovRuigx(n);//仓ij建坏状链表(Boyiiig类对象实例化x)x.countBv(s-l);//转到开始位置fdr(iiiti=LnuniuiLiiie=O;i<n;++i)x.countBv(m);cout«HM«x.getNum()«(++numinLme%10?,n,:n\ir);x.disengage();丿cout«n\iithewnineris\nn«x.getNum()«n\nH;// //maiii.cpp//JosephusProblemObject-basedSolvingmclude<iostream>mcludeHjose.hHusingnamespacestd;intmam(){cout«*'请依次输入孩子的个数/间隔人数/开始编号:\n”;intn,m,s;cm»n»m»s;Jose(njii).getWuuier();Jose(njiKS).getWiiuief();//=

2.4开发日志推进时间主要事务2011年01月01日问题分析，流程设计，确定项目中各个类，找出各类的之间的联系以及类内部的各个成员。2011年01月02日根据分析所得设计实现算法，编写代码，编译、调试程序。2011年01月03日项目完成，进行总结。3程序调试及运行3.1程序运行结果沁\TedDocumwntsandSettings\Administrator面\作业\C++\^j^^\I>ebug\Main^exew1033Thereare10hoys・Boysleavedinorder:36927185 10thewinnepisI4Thereare10boys・Boysleavedinorder：581493 10 72t?)ewinnerisI6PvessanykeytocontinueJosephus的执行结果Josephus问题程序执行•后输出的结果。由键盘依次输入小孩总数10、间隔人数3、开始编号3；程序执行后输出两个结果，第一个结果是Jose(n,m).getWnmei-()的执行结果，由于在只有n、m两个参数是，其第三个参数默认值设定为1,所以，其结果执行为：Thereare10boys。Boyleavedinoider：36927185 10thewiimeris4第二个结果是Jose(n,ni,s).getWiiniei()的执行结果，由于这一3个参数完全，所以，其执行结果为：Thereare10boys。Boyleavedinoider：58 1493 1072thewiimeris6pleaseinputboyNum/interNum/staptPos/winNum:10333Thereare16boys.Boysleavedinorder：36927185 10winners:4ThereareIBboys.Boysleavedinorder：581493 10 72v/inners=6ThereareIBboys.Boysleavedinorder：8 1 4 9 3 10v/inners=7 2 6PressanykeytocontinueJosephus的扩展程序执行结果Josephus问题扩展程序执行后输出的结果。由键盘依次输入小孩总数10、间隔人数3、开始编号3；程序执行后输出三个结果，第一个结果是Jose(n,m).getWnmei()的执行结果，由于在只有n、m两个参数是，其第三个参数默认值设定为1,所以，其结果执行为：Thereare10boysoBoyleavedinorder：36927185 10thewnmei'is4第二个结果是Jose(n,ni,s).getWiiniei()的执行结果，由于这一3个参数完全，所以，其执行结果为：Thereare10boysoBoyleavedinorder：58 1493 1072thewnmeris6第三个结果是Jose(n,ni,s,w).getWiimeiQ的执行结果，由于这次多了一个获胜者人数的参数3,所以，其执行结果为：Thereare10boysoBoyleavedinorder：57 1 4 9 3 10wnuiers 7 2 63.2程序使用说明本程序在使用要注意：输入参数时要注意数据的格式为正整数；输入参数的个数Josephus为3(Josephus问题的扩展为4个)；输入个参数之间的关系，小孩总数大于等1个；开始位置要大于等于1且小于等小孩总数；计数间隔要大于1且小于小孩总数。3.3程序开发总结通过这个学期对面向对象的程序设计的学习，使我本人理解了面向对象的重要性及实用性，同时也锻炼了我们自主学习、查阅资料等方面的能量。本次程序设计虽然是书上的原程序，整个作业的完成有没有花很多的时间，但我从作业的完成过程中学到了很多东西，它使我明白了独立思考的重要性，动手实践的重要性，看懂了，不代表理解了，会做了。亲自对手才能发现问题，才知道想办法去解决，而不是理所当然的认为是什么样的。同时，它也磨练了我们的意志，开发了我们的大脑。使我们明白什么'‘叫吃得苦中苦，方为人上人”；明白了成功需要怎样做。它也教会了我们怎样学习，怎样生活，怎么面对将來的路。4附件（源程序）//bovrmg.h#ifhdefHEADER_BOYRING#defineHEADER_BOYRING#iiiclude<iostream>usingnamespacestd;// stmctBovintcode;B°V*MXt;classBoyRmgprivate:Boy*pBegin,*pivot,*pCurrent;public:BoyRing(mtn);voidcountBy(mtm);intgetNumQconst;voiddisengageQ;voidprintAll()const;-BovRuigO；#endif//HEADER.BOYRING// 〃构造函数// BovRuig::BoyRmg(intn)if(n<2)tluowexceptioii();〃发生错误时自动跳出pBegin=newBoy[n]; 〃申请一*个新的Eoy空间，pBegin指向该空间的开始处for(mti=l;i<=n;i++){pBegin[i-l].next=&pBegin[i%n];//形成链表pBegin[i-l].code=i;//给孩子孩子编号}pivot=pCurrent=&pBegm[n-l];//各指针初始化}// 〃数m个小孩// voidBovRiiig::countBv(iiitm){for(mti=l;i<=m;++i){pivot=pCurrent;pCurrent=pCuiTent->next;//挪到下一个小孩的位置}}// 〃返回当前小孩编号intBoyRuig::getNumQconst{retuinpCunent->code;}// 〃小孩离队voidBovRiiig::disengageQ{pivot->next=pCunent->next;//哨兵指针指向的小孩指向当前小孩的卞一个小孩pCurrent=pivot;〃当前小孩指针等于哨兵指针}// 〃输岀所有小孩编号// voidBovRiiig::pimtAll()const{intnununLme=0;Boy*p=pCunent;do{cout«H"«p->code;if(?(-H-numinLme%10))cout«H\nny/每一行输出10个p=p->next;}wlule(p!=pCuixent);cout«H\nH;}// 〃析构函数// BovRuig:>BoyRmg(){delete[]pBegiii;//释