文章目录
一、什么是约瑟夫问题
约瑟夫问题又被叫做幸存者游戏：n个人围成一个圈，从1开始数到m，数到m的人离开其他人重新围成圈，以此循环到只剩下最后一个人，约瑟夫问题解决方法：数组、链表以及递归方法，本文我用数组的方式来进行实现
二、题目分析
ｎ只猴子，按顺时针方向围成一圈选大王（编号从１到ｎ），从第１号开始报数，一直数到ｍ，数到ｍ的猴子退出圈外，剩下的猴子再接着从1开始报数。就这样，直到圈内只剩下一只猴子时，这个猴子就是猴王，编程求输入ｎ，ｍ后，输出最后猴王的编号。
/**
*
* @param n 总猴子树
* @param m 数到m被淘汰
* @param s 从第几个开始
* @return
*/
public int Josephus(int n, int m, int s){
// 辅助变量
int[] monkey = new int[n];
int i, j = 0;
for(i = 0; i < n; i++){
monkey[i] = i+1;
}
// 因为数组的节点是从零开始 所以需要-1 这里写s = s - 1也是可以的
i = s - 1;
while(n > 1){
// 每次淘汰出去的人，取模是放置下标越界
i = (i + m - 1) % n;
// 这里的目的是把淘汰这个位置给拿走
// 就是令后面的前移
for(j = i + 1; j < n; j++){
monkey[j-1] = monkey[j]
}
n--;
// 放置下标越界
if(i == n){
i = 0;
}
}
// 最后剩下的就是最后一个人
System.out.println(a[i]);
}