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

学 院 班 级 学 号 姓 名 摘要 本作业解决Josephus问题的求解，以及Josephus问题的扩展的求解。 Josephus问题的描述如下：n个小孩围成圈做游戏，游戏将决定出一个胜利者（Josephus问题扩展则可以求出多个获胜者）。假定一个数m，从第s个小孩起，顺时针计数，每次数到第m个小孩，该小孩离开，接着又从下一个小孩开始数，数到第m个小孩，该小孩也离开，如此不断反复进行，最后剩下的一个（多个）小孩为胜利者。对于给定的n、m和s，找出最后的胜利者。Josephus问题的扩展则是在原来Josephus问题基础上增加了“获胜者个数”这一限制。 在本作业中Josephus问题的解决主要是基于对象的解决方案（Object-Based Solution），其中涉及到BoyRing类和Jose类。主要实现方式则是环链表，这使得Josephus问题得到一个比较满意的解决。 本作业的程序设计达到了要求，实现的方式相对较好。最终得到的结果设计者比较满意。 目录 1 摘要 3 1.1 设计题目 3 1.2 设计内容 3 1.3 开发工具 3 1.4 应用平台 3 2 详细设计 4 2.1 程序结构 4 2.2 主要功能 8 2.3 算法实现 10 2.4 开发日志 15 3 程序调试及运行 15 3.1 程序运行结果 15 3.2 程序使用说明 17 3.3 程序开发总结 18 4 附件（源程序） 18 1 摘要 1.1 设计题目 Josephus问题(Josephus Problem)及其扩展 1.2 设计内容 利用循环链表运用面向对象的设计方案实现Josephus问题的求解。Josephus问题如下：n个小孩围成圈做游戏，游戏将决定出一个胜利者。假定一个数m，从第s个小孩起，顺时针计数，每次数到第m个小孩，该小孩离开，接着又从下一个小孩开始数，数到第m个小孩，该小孩也离开，如此不断反复进行，最后剩下的一个小孩为胜利者。对于给定的n、m和s，找出最后的胜利者。其中n、m和s都为正整数，切有n1,1=m=n和1=s=n的关系。 程序扩展是在Josephus问题的基础上，由原来的1个获胜者扩展到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，这也是程序模块间的关系）。 图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(int m); 用循环的方式数m个小孩，参数为int类型的m int getNum() const; 为一个const函数，返回小孩的编号，无参数 void disengage(); 利用指针实现小孩离队，无参数 void printAll()const; 以特定的格式输出小孩的编号，无参数。本函数在在本程序中没有起任何作用可以去除。 ~BoyRing(); 析构函数。释放申请空间，无参数 图J-2.Josephus问题整体程序流程图 Jose类中的数据成员有：int n, m, s三个int类型的数，分别表示小孩的总数、间隔数、开始数的小孩编号。 Jose类中的成员函数分别为： 函数 相关说明 Jose(int boys, int interval, int begin=1); 构造函数，主要功能初始化各个参数，校验输出的m、n、s参数为int boys, int interval, int begin=1 void getWinner()const; 求胜利者函数，实例化BoyRing类，以特定的格式输出离队小孩的编号和获胜小孩的编号，无参数 主要函数： BoyRing::Bo