一.题目概述
约瑟夫环问题是一个很经典的问题：一个圈共有N个人（N为不确定的数字），第一个人的编号为1第二个人的编号为2号，第三个人的编号为3号，第N个人的编号为N号，现在提供一个数字M，第一个人开始从1报数，第二个人报的数就是2，依次类推，报到M这个数字的人出局，紧接着从出局的这个人的下一个人重新开始从1报数，和上面过程类似，报到M的人出局，直到N个人全部出局，请问，这个出局的顺序是什么？
二.解题流程
1.问题重述
通过阅读题干，我们可总结出本题的关键信息：
N个人围成一个圈，编号由一到N ，报到M 的人出局直到剩最后一个人，求出局的顺序。
2.分析问题
首先，要求出局的顺序，说明要按出局顺序输出这N个人的编号，所以我们先要存储N个人的编号，存储已知个数的数据，首先想到的是数组，但数组开辟的固定空间无法释放，若N的值非常大，会造成空间占用过大，此时可以想到用链表存储这N个数据，可通过释放节点空间进行空间节约，同时在出局操作中链表也更便捷。
解决了存储问题后，第二步我们要考虑的便是如何淘汰报数到M的人，这里的解决方法根据存储方式的不同而不同，我们下面对数组和链表分别进行分析。
3.解决问题
1.普通数组法
最直接的思路便是把N个人的编号存储到大小为N的数组中。
因为题目要求从1开始报数，所以我们可以从数组的下标1开始存储，不使用下标0。
对于出局的操作，我们将出局的人的编号改为一个标记值，例如本题可以选择将淘汰的人的标号值赋值为零，通过判断0的个数得出淘汰了多少人。
最后解决什么时候数到M的问题，本题必然涉及遍历数组，但遍历过程中的 i 值是固定1-N的，永远都在 M 的倍数处赋0，无法实现目标。这时转换思路，重新定义一个变量例如 j ，j 从 1 开始自增，遇到 M 时把对应的编号置零，这是可能有疑问，报数到M后从新从1开始报数，如果 j 一直自增如何遇到第二个M ， 其实很好解决，只要 j 是 M 的整数倍，便是下一次报到M的时候，即 ( j % M == 0 ) 。至此几个关键问题我们均已解决，接下来便是代码实现了。
#include <iostream>using namespace std;int main(){ int n,m; cin >> n >> m; int cnt = n;//存储人数 int p[n];//编号数组 int j=1; //构建编号数组 for(int i=1;i<=n;i++) { p[i] = i; } //人数大于1时进入循环 while(cnt > 1) { //循环遍历数组 for(int i=1;i<=n;i++) { if(p[i]==0)continue;//标记为0 跳过本次循环 if( j % m == 0 )//报数到M { cnt--;//人数自减 cout << p[i] << " ";//输出出局人编号 p[i]=0;//标记为0 j++;//报数自增 } else { j++;//报数自增 } } } for(int i=0;i<n;i++) { if(p[i]!=0)cout << p[i] << endl;//输出最后的幸存者的编号 } return 0;}2.1.循环链表法
使用循环链表在空间利用上更加灵活，同时思路更加清晰，出局操作只需要将前一节点的指针指向出局结点的后一个结点即可，同时将出局的节点空间释放。
#include <stdio.h>int main(){ int n, m; scanf("%d %d", &n, &m); struct List { int num; struct List *next; }; List *head = new List;//虚拟头结点 List *p = new List;//链表结点 p = head;//初始结点在虚拟头结点位置 // 创建链表 for (int i = 1; i <= n; i++) { List *node = new List;//新建结点 node->num = i;//赋初值 node->next = NULL;//新结点的后结点初始化为空 //p随node移动形成链式结构 p->next = node; p = p->next; } p->next = head->next;//尾结点指向头结点形成循环链表 // 遇到m-1 指针跳两个 指向自己时停 p = head->next;//p从第一个结点开始 int i = 1;//报数的值 while (p->next->num != p->num)//只剩一个结点（指针指向自己）时结束 { if (i == m - 1)//出局结点的前一个结点 { printf("%d ", p->next->num);//输出出局者编号 List *temp = p->next;//临时变量存出局者结点 p->next = p->next->next;//淘汰出局者 i = 0;//报数归零 delete temp;//释放出局者空间 } i++;//从一报数 p = p->next;//移动链表 } printf("%d", p->num);//输出幸存者编号 return 0;}2.2模拟链表法
对于链表运用不熟的伙伴，我们可以用数组模拟链表的效果，用数组下标表示每个人的编号，数组的值为下一个结点的地址（下一个下标）。同时最后一个结点指回头部。
#include <stdio.h>int main(){ int n, m; scanf("%d %d", &n, &m); int peo[n]; for (int i = 1; i <= n; i++)//初始化模拟链表 { peo[i] = i + 1;//数组的值为下一个结点的下标 } peo[n] = 1;//最后一个值指向头结点形成循环 int k = 1; while (peo[k] != k) { for (int i = 1; i < m - 1; i++) { k = peo[k];//移动链表 printf("%d ", peo[k]); } k = peo[k] = peo[peo[k]];//淘汰出局者 } printf("%d", k);//打印幸存者 return 0;}3.递归法
本题的结束条件是人数变为1，我们可将此条件作为递归结束条件，另一个输入变量是M 可作为函数的另一个参数，由此构建一个函数 f (int n , int m)
其中 n 表示当前环内人数，m 表示报数淘汰者报数
最终要求的是淘汰人的编号，所以下一步要找出每一轮报数与最初编号的关系：
第一次报数顺序（即编号）为 1 2 ... M M+1 M+2 ... 一直到 n
淘汰一次后报数顺序变为 1 2 ... 淘汰 1 2 M M+1 M + 2
淘汰两次后报数顺序变为 1 2 ... 1 2 淘汰 1 2
上下对应可发现 每个人的编号等于当前报的数加M取余n，n为当前轮次的人数。 因为从1开始编号，所以需要将（报数+M-1）后再对n取余（从1开始会使加M的结果多1，顾减去一个1），取余后再加1 ，确保从1开始编号的结果。
#include <iostream>using namespace std;int f(int n,int m){ return n == 1 ? n : (f(n - 1 , m) + m - 1) % n + 1;}int main(){ int n,m; cin >> n >> m; int ans = f(n,m); cout << ans << endl; return 0;}需要注意的是递归法只能求得最后幸存者的编号，无法输出前几次淘汰者的编号。
4.数学归纳法
由于递归对空间占用较大，我们可以通过数学归纳法总结刚才的规律，得到公式。
将刚才递归的推到过程逆转，最后幸存者的编号等于他报的数加M取余当前的人数（n==1），倒数第二轮幸存者必然安全，他的编号同样等于他报的数加M取余n（两个人n==2）以此类推，直到n个人时，幸存者的编号为报的数加M取余n（n==n）。取余的数由1到n ,用一个循环即可实现。
#include <iostream>using namespace std;int main(){ int n,m; cin >> n >> m; int ans = 0; for(int i=1;i<=n;i++) { ans = (ans+m)%i; } cout << ans + 1 << endl;//从1开始报数 return 0;}同样这个方法无法得到每一次出局人编号，只能得到最后幸存者的编号。