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

1、Josephus相关问题程序设计报告书学 院班 级学 号姓 名摘要本作业解决Josephus问题的求解，以及Josephus问题的扩展的求解。Josephus问题的描述如下：n个小孩围成圈做游戏，游戏将决定出一个胜利者（Josephus问题扩展则可以求出多个获胜者）。假定一个数m，从第s个小孩起，顺时针计数，每次数到第m个小孩，该小孩离开，接着又从下一个小孩开始数，数到第m个小孩，该小孩也离开，如此不断反复进行，最后剩下的一个（多个）小孩为胜利者。对于给定的n、m和s，找出最后的胜利者。Josephus问题的扩展则是在原来Josephus问题基础上增加了“获胜者个数”这一限制。在本作业中Jos

2、ephus问题的解决主要是基于对象的解决方案（Object-Based Solution），其中涉及到BoyRing类和Jose类。主要实现方式则是环链表，这使得Josephus问题得到一个比较满意的解决。本作业的程序设计达到了要求，实现的方式相对较好。最终得到的结果设计者比较满意。目录1 摘要31.1 设计题目31.2 设计内容31.3 开发工具31.4 应用平台32 详细设计42.1 程序结构42.2 主要功能82.3 算法实现102.4 开发日志153 程序调试及运行153.1 程序运行结果153.2程序使用说明173.3 程序开发总结184 附件（源程序）181 摘要1.1 设计题目J

3、osephus问题(Josephus Problem)及其扩展1.2 设计内容利用循环链表运用面向对象的设计方案实现Josephus问题的求解。Josephus问题如下：n个小孩围成圈做游戏，游戏将决定出一个胜利者。假定一个数m，从第s个小孩起，顺时针计数，每次数到第m个小孩，该小孩离开，接着又从下一个小孩开始数，数到第m个小孩，该小孩也离开，如此不断反复进行，最后剩下的一个小孩为胜利者。对于给定的n、m和s，找出最后的胜利者。其中n、m和s都为正整数，切有n>1,1<=m<=n和1<=s<=n的关系。程序扩展是在Josephus问题的基础上，由原来的1个获胜者扩

4、展到m个胜利者，其实现的方式和Josephus问题的实现基本相同。其中n、m、s的要求和Josephus问题的完全相同，新增的1<=w<=n。1.3 开发工具主要用到的开发工具为：Dev C+ 5.0和Win32。1.4 应用平台Windows 2000/XP/Vista 32位2 详细设计2.1 程序结构改程序分成三个抽象层次，第一层是应用层，直接指使Jose类对象去完成求解工作；第二层是Jose类层，描述Josephus问题的求解细节；第三层是BoyRing类层，辅助Jose类完成求解过程（上述三层间的关系描述如图J-1，这也是程序模块间的关系）。Jose类界面主函数Jose类

5、界面BoyRing类界面Jose类内部实现BoyRing类内部实现BoyRing类界面图J-1.对象实现中程序模块的相互关系如图J-1所示，main函数用到了Jose类，Jose类又用到了BoyRing类。整个程序的实现流程如图J-2。程序中类：BoyRing类和Jose类BoyRing类中的数据成员有：Boy *pBegin, *pivot, *pCurrent三个指针，分别为起始位置的指针，哨兵指针，被切掉位置指针。BoyRing类中的成员函数分别为：函数相关说明BoyRing(int n);构造函数。参数为int类型的n，主要完成空间申请，构造链表，初始化个参数。Void countBy

6、(int m);用循环的方式数m个小孩，参数为int类型的mint getNum() const;为一个const函数，返回小孩的编号，无参数void disengage();利用指针实现小孩离队，无参数void printAll()const;以特定的格式输出小孩的编号，无参数。本函数在在本程序中没有起任何作用可以去除。BoyRing();析构函数。释放申请空间，无参数图J-2.Josephus问题整体程序流程图Jose类中的数据成员有：int n, m, s三个int类型的数，分别表示小孩的总数、间隔数、开始数的小孩编号。Jose类中的成员函数分别为：函数相关说明Jose(int boys

7、, int interval, int begin=1);构造函数，主要功能初始化各个参数，校验输出的m、n、s参数为int boys, int interval, int begin=1void getWinner()const;求胜利者函数，实例化BoyRing类，以特定的格式输出离队小孩的编号和获胜小孩的编号，无参数主要函数：BoyRing:BoyRing(int n); if(n<2) throw exception(); pBegin = new Boyn; for(int i=1; i<=n; i+) pBegini-1.next = &pBegini%n; p

8、Begini-1.code = i; pivot = pCurrent = &pBeginn-1; /图J-3为流程图图J-3.BoyRing:BoyRing(int n)函数流程图void BoyRing:countBy(int m) for(int i=1; i<=m; +i) pivot = pCurrent; pCurrent = pCurrent->next; /挪到下一个小孩的位置 /图J-4为流程图图J-4.void BoyRing:countBy(int m)函数流程图void Jose:getWinner()const cout<<"

9、There are "<<n<<" boys.nBoys leaved in order:n"/输出小孩总个数 BoyRing x(n);/创建环状链表（Boying类对象实例化x） x.countBy(s-1);/转到开始位置 for(int i=1,numinLine=0; i<n; +i) x.countBy(m); cout<<" "<<x.getNum()<<(+numinLine%10 ? "" : "n"); x.diseng

10、age(); cout<<"nthe winner isn "<<x.getNum()<<"n" 函数之间的参数传递：1. 由主函数依次输入n、m、s三个数的值；2. 主函数调用Jose:getWinner()函数将n、m、s的值传递到Jose类；同时，Jose类的内部函数Jose:Jose(int boys,int interval,int begin=1)得到传入的参数n、m、s，并对三个数的值进行校验；3. 在void Jose: getWinner()const函数将n、m、s三个参数通过将BoyRing类实例

11、化成对象实例x，调用x.countBy()函数出入到类BoyRing中。4. 传入BoyRing类中的各个带参数的函数。2.2 主要功能Josephus问题程序的主要功能是：通过外界输入3个或（4个）相关参数，在Josephus问题程序成后输出Josephus的的相关结果。利用循环链表实现Josephus的求解。Josephus问题如下：n个小孩围成圈做游戏，游戏将决定出一个胜利者。假定一个数m，从第s个小孩起，顺时针计数，每次数到第m个小孩，该小孩离开，接着又从下一个小孩开始数，数到第m个小孩，该小孩也离开，如此不断反复进行，最后剩下的一个小孩为胜利者。对于给定的n、m和s，找出最后的胜利者

12、。其中n、m和s都为正整数，切有n>1,1<=m<=n和1<=s<=n的关系。Josephus问题主要是利用环链表、指针转向。其实现如图J-5：图J-5.Josephus问题中的环链表算法Jose类内部数据成员小孩总数n开始位置s计数间隔m界面构造函数求获胜者者函数其中，Jose类界面具有的具体操作描述为：构造函数小孩总数校验开始位置校验计数间隔数校验求获胜者函数输出求解开始，小孩总数创建环链表（BoyRing类对象）转到链表开始位置while(小孩多于1个（w个）)数m个小孩小孩输出小孩离队endwhile输出获胜者在Jose类用到了BoyRing类，其设计如下

13、：BoyRing类内部数据成员小孩结构指针当前小孩指针小孩哨兵指针界面构造函数析构函数数m个小孩小孩离队返回当前小孩编号输出所有小孩其中，BoyRing类界面的具体操作描述为：构造函数按小孩的个数申请空间初始化环状结构，为小孩编号指针初始化析构函数释放申请空间数m个小孩函数for(m间隔)挪到下一个小孩的位置endfor小孩离队函数哨兵指向的小孩指向当前小孩的的下一个小孩当前小孩指针赋值与哨兵指针返回当前小孩的编号返回当前小孩指针指向的小孩编号输出所以小孩按特定的格式输出环中所有小孩的编号2.3 算法实现/=/ boyring.h/=#ifndef HEADER_BOYRING#define

14、HEADER_BOYRINGstruct Boy int code; Boy* next;/-class BoyRing Boy *pBegin, *pivot, *pCurrent;public: BoyRing(int n); void countBy(int m); int getNum() const; void disengage(); void printAll()const; BoyRing();/=#endif / HEADER_BOYRING/=/ boyring.cpp/=#include"boyring.h"#include<iostream&g

15、t;using namespace std;/-/构造函数 /- BoyRing:BoyRing(int n) if(n<2) throw exception(); /发生错误时自动跳出 pBegin = new Boyn; /申请一个新的Boy空间，pBegin指向该空间的开始处 for(int i=1; i<=n; i+) pBegini-1.next = &pBegini%n;/形成链表 pBegini-1.code = i;/给孩子孩子编号 pivot = pCurrent = &pBeginn-1;/各指针初始化 /-/数m个小孩 /- void BoyR

16、ing:countBy(int m) for(int i=1; i<=m; +i) pivot = pCurrent; pCurrent = pCurrent->next;/挪到下一个小孩的位置 /-/返回当前小孩编号 /- int BoyRing:getNum() const return pCurrent->code; /-/小孩离队 /-void BoyRing:disengage() pivot->next = pCurrent->next;/哨兵指针指向的小孩指向当前小孩的下一个小孩 pCurrent = pivot; /当前小孩指针等于哨兵指针 /-/

17、输出所有小孩编号 /-void BoyRing:printAll()const int numinLine = 0; Boy* p = pCurrent; do cout<<" "<<p->code; if(!(+numinLine%10) cout<<"n"/每一行输出10个 p = p->next; while(p!=pCurrent); cout<<"n"/-/析构函数 /-BoyRing:BoyRing() delete pBegin;/释放申请空间 /-/=/ jo

18、se.h/=#ifndef HEADER_JOSE#define HEADER_JOSEclass Joseprotected: int n, m, s;public: Jose(int boys, int interval, int begin=1); void getWinner()const;/=#endif / HEADER_JOSE/=/ jose.cpp/=#include"boyring.h"#include"jose.h"#include<iostream>using namespace std;/-/构造函数 /-Jose:

19、Jose(int boys, int interval, int begin):n(boys),m(interval),s(begin) if(n<2 | m<1 | m>=n | s<1 | s>=n) /校验n、m、s cerr<<"data error.n" throw exception();/出现错误跳出 /-/求获胜者 /-void Jose:getWinner()const cout<<"There are "<<n<<" boys.nBoys leav

20、ed in order:n"/输出小孩总个数 BoyRing x(n);/创建环状链表（Boying类对象实例化x） x.countBy(s-1);/转到开始位置 for(int i=1,numinLine=0; i<n; +i) x.countBy(m); cout<<" "<<x.getNum()<<(+numinLine%10 ? "" : "n"); x.disengage(); cout<<"nthe winner isn "<<

21、x.getNum()<<"n" /-/=/ main.cpp/ Josephus Problem Object-based Solving/=#include<iostream>#include"jose.h"using namespace std;/-int main() cout<<"请依次输入孩子的个数/间隔人数/开始编号:n" int n, m, s; cin>>n>>m>>s; Jose(n,m).getWinner(); Jose(n,m,s).get

22、Winner();/=2.4 开发日志推进时间主要事务2011年01月01日问题分析，流程设计，确定项目中各个类，找出各类的之间的联系以及类内部的各个成员。2011年01月02日根据分析所得设计实现算法，编写代码，编译、调试程序。2011年01月03日项目完成，进行总结。3 程序调试及运行3.1 程序运行结果Josephus的执行结果Josephus问题程序执行后输出的结果。由键盘依次输入小孩总数10、间隔人数3、开始编号3；程序执行后输出两个结果，第一个结果是Jose(n,m).getWinner()的执行结果，由于在只有n、m两个参数是，其第三个参数默认值设定为1，所以，其结果执行为：Th

23、ere are 10 boys。Boy leaved inorder：3692718510the winner is 4第二个结果是Jose(n,m,s).getWinner()的执行结果，由于这一3个参数完全，所以，其执行结果为：There are 10 boys。Boy leaved inorder：5814931072the winner is 6Josephus的扩展程序执行结果Josephus问题扩展程序执行后输出的结果。由键盘依次输入小孩总数10、间隔人数3、开始编号3；程序执行后输出三个结果，第一个结果是Jose(n,m).getWinner()的执行结果，由于在只有n、m两个参

24、数是，其第三个参数默认值设定为1，所以，其结果执行为：There are 10 boys。Boy leaved inorder：3692718510the winner is 4第二个结果是Jose(n,m,s).getWinner()的执行结果，由于这一3个参数完全，所以，其执行结果为：There are 10 boys。Boy leaved inorder：5814931072the winner is 6第三个结果是Jose(n,m,s,w).getWinner()的执行结果，由于这次多了一个获胜者人数的参数3，所以，其执行结果为：There are 10 boys。Boy leaved

25、 in order：57149310winners 726 3.2 程序使用说明本程序在使用要注意：1. 输入参数时要注意数据的格式为正整数；2. 输入参数的个数Josephus为3（Josephus问题的扩展为4个）；3. 输入个参数之间的关系，小孩总数大于等1个；开始位置要大于等于1且小于等小孩总数；计数间隔要大于1且小于小孩总数。3.3 程序开发总结通过这个学期对面向对象的程序设计的学习，使我本人理解了面向对象的重要性及实用性，同时也锻炼了我们自主学习、查阅资料等方面的能量。本次程序设计虽然是书上的原程序，整个作业的完成有没有花很多的时间，但我从作业的完成过程中学到了很多东西，它使我明白

26、了独立思考的重要性，动手实践的重要性，看懂了，不代表理解了，会做了。亲自对手才能发现问题，才知道想办法去解决，而不是理所当然的认为是什么样的。同时，它也磨练了我们的意志，开发了我们的大脑。使我们明白什么“叫吃得苦中苦，方为人上人”；明白了成功需要怎样做。它也教会了我们怎样学习，怎样生活，怎么面对将来的路。4 附件（源程序）/=/ boyring.h/=#ifndef HEADER_BOYRING#define HEADER_BOYRING#include<iostream>using namespace std;/-struct Boy int code; Boy* next;/-

27、class BoyRing private: Boy *pBegin, *pivot, *pCurrent; public: BoyRing(int n); void countBy(int m); int getNum() const; void disengage(); void printAll()const; BoyRing();/=#endif / HEADER_BOYRING/-/构造函数 /- BoyRing:BoyRing(int n) if(n<2) throw exception(); /发生错误时自动跳出 pBegin = new Boyn; /申请一个新的Boy空

28、间，pBegin指向该空间的开始处 for(int i=1; i<=n; i+) pBegini-1.next = &pBegini%n;/形成链表 pBegini-1.code = i;/给孩子孩子编号 pivot = pCurrent = &pBeginn-1;/各指针初始化 /-/数m个小孩 /- void BoyRing:countBy(int m) for(int i=1; i<=m; +i) pivot = pCurrent; pCurrent = pCurrent->next;/挪到下一个小孩的位置 /-/返回当前小孩编号 /- int BoyR

29、ing:getNum() const return pCurrent->code;/-/小孩离队 /-void BoyRing:disengage() pivot->next = pCurrent->next;/哨兵指针指向的小孩指向当前小孩的下一个小孩 pCurrent = pivot; /当前小孩指针等于哨兵指针 /-/输出所有小孩编号 /-void BoyRing:printAll()const int numinLine = 0; Boy* p = pCurrent; do cout<<" "<<p->code; if

30、(!(+numinLine%10) cout<<"n"/每一行输出10个 p = p->next; while(p!=pCurrent); cout<<"n"/-/析构函数 /-BoyRing:BoyRing() delete pBegin;/释放申请空间 /-/=/ jose.h/=#ifndef HEADER_JOSE#define HEADER_JOSE#include"boyring.h"#include<iostream>using namespace std;/-class Jose int n, m, s;public: Jose(int boys, int interval, int be