队列实现约瑟夫环（数据结构实验报告1）

约瑟夫环问题

问题分析

完整代码

运行结果

约瑟夫环问题

实验题目：约瑟夫环问题：设编号为1，2，3，……，n的n(n>0)个人按顺时针方向围坐一圈，m为任意一个正整数。从第一个人开始顺时针方向自1起顺序报数，报到m时停止并且报m的人出列，再从他的下一个人开始重新从1报数，报到m时停止并且报m的人出列。如此下去，直到所有人全部出列为止。要求设计一个程序模拟此过程，对任意给定的m和n，求出出列编号序列。

实验说明：用顺序表实现，并分析算法的时间和空间复杂性。

队列也是一种线性表，这里使用队列实现约瑟夫环问题

问题分析

有n个人，围绕一圈循环报数，报到m的人出列，剩余人继续循环报数，直到所有人都出列。

使用c++里stl里的队列实现这道题目。

从队头开始报数，报数到m的人就出队，报数不是m的人就移动到队尾。

输入n和m，输出报到m的人的编号。

输入8个人，报到4的人出列。

时间复杂度为O（n）空间复杂度为O（n）。

完整代码

#include<bits/stdc++.h>
using namespace std;queue<int> que;void solve(int m) {while(!que.empty()) {for(int i = 1; i <= m; i++) {//从1开始报号,报到m就出队if(i == m) {//如果是要出列的的人则让他出列并且输出int j = que.front();que.pop();cout << "出列的人的编号为：" << j << '\n';}else {//如果不是要出列的就放在队尾int x = que.front();que.pop();que.push(x);}}}
}int main() {int n,m;//n为小朋友的个数，m为报到要出列的小朋友的编号cin >> n >> m;for(int i = 1; i <= n; i++) {que.push(i);//将小朋友都放入队列}solve(m);return 0;
}