【数据结构与算法】约瑟夫环（C/C++）

实践要求

1. 问题描述

约瑟夫问题的一种描述是：编号为1,2,…,n的n个人按顺时针方向围坐一圈，每人持有一个密码(正整数)。一开始任选一个正整数作为报数上限值m，从第一个人开始。按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。试设计程序求出出列顺序。

2. 基本要求

利用单向循环链表存储结构模拟此过程，按照出列的顺序印出个人的编号。

3. 测试数据

3.1 input

• m = 20
• n=7
• 7个人的密码分别为：3,1,7,2,4,8,4

3.2 output

(正确的结果应为6,1,4,7,2,3,5)

实践报告

1. 题目分析

说明程序设计的任务，强调的是程序要做什么，此外列出各成员分工

程序设计任务：解决约瑟夫问题——编号为1,2,…,n的n个人按顺时针方向围坐一圈，每人持有一个密码(正整数)。一开始任选一个正整数作为报数上限值m，从第一个人开始。按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。最后输出列顺序。

2. 数据结构设计

说明程序用到的数据结构的定义，主程序的流程及各模块之间的层次关系

使用了单向循环链表。定义了一个Person的类（包含了密码（code）、编号（No）、下一个人的指针 Person* next、以及一个构造函数Person(int c, int N) 其中”c”表示当前人的code，”N”表示当前人的编号 ）

主程序流程图

3. 程序设计

实现概要设计中的数据类型，对主程序、模块及主要操作写出伪代码，画出函数的调用关系

数据类型

• vector数组
• 指针
• int

主程序操作伪代码

4. 调试分析

程序复杂度分析

1. 空间复杂度
$$o(n)$$
2. 时间复杂度
$$O(m+n+\sum code)$$

心得体会

使用链表要注意不能使用空指针，不能使用指向未知内存的指针，以及用完指针后要及时释放。否则就会碰到一些莫名其妙的错误。

5. 测试结果

列出测试结果，包括输入和输出

测试结果一

input

上限值为20、人数为7、每人的密码分别为3、1、7、2、4、8、4

output

6,1,4,7,2,3,5

测试结果二

input

上限值为30、人数为7、每人的密码分别为3、1、7、2、4、8、4

output

2,3,5,4,7,6,1

6. 用户使用说明

给出主界面及主要功能界面

主界面

使用说明

输入上限值后回车 -> 输入人数后回车 -> 输入每个人的密码后回车 -> 全部密码输入完毕后自动打印出列人员的编号。

7. 附录

源程序文件清单:
JosephusProblem.cpp //主程序

8. 全部代码

/*问题描述约瑟夫问题的一种描述是：编号为1,2,...,n的n个人按顺时针方向围坐一圈，每人持有一个密码(正整数)。一开始任选一个正整数作为报数上限值m，从第一个人开始。按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。试设计程序求出出列顺序。基本要求利用单向循环链表存储结构模拟此过程，按照出列的顺序印出个人的编号。测试数据m的初值为20;n=7,7个人的密码: 3,1,7,2,4,8,4。(正确的结果应为6,1,4,7,2,3,5) (报告上要求写出多批数据测试结果实现提示程序运行后首先要求用户指定初始报数上限值与人数，然后读取各人的密码*/#include #include using namespace std;//人类class Person {public://密码int code;//编号int No;//下一个人的指针Person *next = nullptr;//构造函数Person(int c, int N):code(c), No(N) {}};int main() {//下一次要走的步数int step;//有多少个人int num;cout << "请输入报数上限值" ;cin >> step;cout << "请输入总共有多少个人";cin >> num;//head存循环单链表的头，即编号为1的人的位置；tmp为临时变量，但最后它将存放最后一个人的位置Person *head, *tmp;//构造循环单链表，这是一个没有头节点的循环单链表for(int i = 0; i < num; ++i) {int code;//读取密码printf("请输入第%d个人的密码",i + 1); cin >> code;if(i == 0) {//head,即第一个人的位置head = new Person(code, i + 1);tmp = head;}else {tmp->next = new Person(code, i + 1);//更新tmp = tmp->next;}}//将尾衔接到头上tmp->next = head;//start每一次报数开始的位置，随着每个人报数一步步移动Person *start = head;//前驱指针Person *pre = tmp;//存放最终结果的序号列表vector<int> NoList;for(int i = 0; i < num; ++i) {//num次循环，即num次报数for(int j = 0; j < step - 1; ++j) {//前驱结点更新pre = start;//随着报数进行，一步步指向下一个人start = start->next;}//循环结束，指到的人便出列//读取密码step = start->code;//存入序号NoList.push_back(start->No);//记录一下下一个结点的位置，方便删除此结点，即指到的人出列Person *newStart = start->next;//删除结点pre->next = start->next;//释放空间delete start;//更新start = newStart;}//输出结果for(auto i : NoList) {cout << i << ' ';}return 0;}

结束语

  因为是算法小菜，所以提供的方法和思路可能不是很好，请多多包涵~如果有疑问欢迎大家留言讨论，你如果觉得这篇文章对你有帮助可以给我一个免费的赞吗？我们之间的交流是我最大的动力！