大家好，又见面了，我是你们的朋友全栈君。
什么是约瑟夫问题？
约瑟夫问题：n个人围成一圈，初始编号从1~n排列，从约定编号为x的人开始报数，数到第m个人出圈，接着又从1开始报数，报到第m个数的人又退出圈，以此类推，最后圈内只剩下一个人，这个人就是赢家，求出赢家的编号。
是不是有点点复杂，其实该问题归结为模拟类型的算法题，根据题目要求模拟即可。
我说，一行代码解决约瑟夫问题！
？？？我去
别着急，我们一步一步学习
方法一：数组
在第一次遇到这个题的时候，我是用数组做的，我猜绝大多数人也都知道怎么做。方法是这样的：
用一个数组来存放 1，2，3 … n 这 n 个编号，如图（这里我们假设n = 6, m = 3）
然后不停着遍历数组，对于被选中的编号，我们就做一个标记，例如编号 arr[2] = 3 被选中了，那么我们可以做一个标记，例如让 arr[2] = -1，来表示 arr[2] 存放的编号已经出局的了。
然后就按照这种方法，不停着遍历数组，不停着做标记，直到数组中只有一个元素是非 -1 的，这样，剩下的那个元素就是我们要找的元素了。我演示一下吧：
这种方法简单吗？思路简单，但是编码却没那么简单，临界条件特别多，每次遍历到数组最后一个元素的时候，还得重新设置下标为 0，并且遍历的时候还得判断该元素时候是否是 -1。用这种数组的方式做，千万不要觉得很简单，编码这个过程还是挺考验人的。
这种做法的时间复杂度是 O(n * m), 空间复杂度是 O(n);
下面给出数组方法的参考代码：
#include<algorithm>
#include<iostream>
using namespace std;
int main(){
int a[1001]={0}; //初始化化数组作为环
int n,m;//n代表总的人数，m代表报数到几退出
cin>>n>>m;
int count=0;//记录退出的个数
int k=-1;//这里假定开始为第一个人，下标为0，编号为1，如需从编号x开始，则k=x-2
while(count<n-1){ //总共需要退出n-1个人
int i=0;//记录当前报数编号
while(i<m){
k=(k+1)%n; //循环处理下标
if(a[k]==0){
i++;
if(i==m){
a[k]=-1;
count++;
}
}
}
}
for(int i=0;i<n;i++){
if(a[i]==0){
printf("%d\n",i+1);
break;
}
}
return 0;
}方法二：环形链表
学过链表的人，估计都会用链表来处理约瑟夫环问题，用链表来处理其实和上面处理的思路差不多，只是用链表来处理的时候，对于被选中的编号，不再是做标记，而是直接移除，因为从链表移除一个元素的时间复杂度很低，为 O(1)。当然，上面数组的方法你也可以采用移除的方式，不过数组移除的时间复杂度为 O(n)。所以采用链表的解决方法如下：
1、先创建一个环形链表来存放元素：
2、然后一边遍历链表一遍删除，直到链表只剩下一个节点，我这里就不全部演示了
感兴趣的友友可以自己实现以下代码，这里就不放了
下面我们来看看，是如何一行代码实现约瑟夫问题！
方法三：递归
其实这道题还可以用递归来解决，递归是思路是每次我们删除了某一个人之后，我们就对这些人重新编号，然后我们的难点就是找出删除前和删除后编号的映射关系。
我们定义递归函数 f(n，m) 的返回结果是存活士兵的编号，显然当 n = 1 时，f(n, m) = 1。假如我们能够找出 f(n，m) 和 f(n-1，m) 之间的关系的话，我们就可以用递归的方式来解决了。我们假设人员数为 n, 报数到 m 的人就自杀。则刚开始的编号为
… 1 … m – 2
m – 1
m
m + 1
m + 2 … n …
进行了一次删除之后，删除了编号为 m 的节点。删除之后，就只剩下 n – 1 个节点了，删除前和删除之后的编号转换关系为：
删除前 — 删除后
… — …
m – 2 — n – 2
m – 1 — n – 1
m —- 无(因为编号被删除了)
m + 1 — 1(因为下次就从这里报数了)
m + 2 —- 2
… —- …
新的环中只有 n – 1 个节点。且删除前编号为 m + 1, m + 2, m + 3 的节点成了删除后编号为 1， 2， 3 的节点。
假设 old 为删除之前的节点编号， new 为删除了一个节点之后的编号，则 old 与 new 之间的关系为 old = (new + m – 1) % n + 1。
注：有些人可能会疑惑为什么不是 old = (new + m ) % n 呢？主要是因为编号是从 1 开始的，而不是从 0 开始的。如果 new + m == n的话，会导致最后的计算结果为 old = 0。所以 old = (new + m – 1) % n + 1. 这样，我们就得出 f(n, m) 与 f(n – 1, m)之间的关系了，而 f(1, m) = 1.所以我们可以采用递归的方式来做。
代码如下：
int f(int n, int m){ return n == 1 ? n : (f(n - 1, m) + m - 1) % n + 1; }
卧槽，以后有人让你手写约瑟夫问题，你就扔这一行代码给它。
本文转自帅地大佬的 一气之下，我一行代码搞定了约瑟夫环问题，面试官懵了_帅地的博客-CSDN博客
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/136647.html原文链接：https://javaforall.net
