实践要求
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
)
o(n)
o(n)
2. 时间复杂度
O
(
m
+
n
+
∑
c
o
d
e
)
O(m+n+\sum code)
O(m+n+∑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 //主程序文章来源：https://www.toymoban.com/news/detail-523271.html
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 <iostream>
#include <vector>
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;
}
结束语
因为是算法小菜，所以提供的方法和思路可能不是很好，请多多包涵~如果有疑问欢迎大家留言讨论，你如果觉得这篇文章对你有帮助可以给我一个免费的赞吗？我们之间的交流是我最大的动力！文章来源地址https://www.toymoban.com/news/detail-523271.html
到了这里，关于【数据结构与算法】约瑟夫环（C/C++）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
