约瑟夫环四种解法（数组，链表，递归，数学归纳）C/C++
一.题目概述
约瑟夫环问题是一个很经典的问题：一个圈共有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;
}同样这个方法无法得到每一次出局人编号，只能得到最后幸存者的编号。