约瑟夫环问题

约瑟夫斯问题

有时也称为约瑟夫斯置换,是一个出现在计算机科学和数学中的问题。在计算机编程的算法中,类似问题又称为约瑟夫环。

人们站在一个等待被处决的圈子里。 计数从圆圈中的指定点开始,并沿指定方向围绕圆圈进行。 在跳过指定数量的人之后,执行下一个人。 对剩下的人重复该过程,从下一个人开始,朝同一方向跳过相同数量的人,直到只剩下一个人,并被释放。

问题即,给定人数、起点、方向和要跳过的数字,选择初始圆圈中的位置以避免被处决。

问题

有n个人编号,站成一圈:
1 2 3 4 … … n-1 n

现在从1开始进行报数,报到k的出列自杀,然后剩下的人继续从1报数(当到达编号为n的人时,下一个报数的从编号为1的人开始进行):

1 2 3 4… k(出列自杀) 1 2 …

直到圈内只剩余m人,求胜利者的编号。

例如:当n=6, k=5, m=1时,5,4,6,2,3将会被依次处决,而1将会幸免。

示例代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
import java.util.ArrayList;
import java.util.List;

public class JosephProblem {

/**
* 返回活着的人的位置
*
* @param total 总人数
* @param magicNum 报数到该数字的人自杀
* @param remain 笑着活下去的人
* @return
*/
private List getJosephNumbers(int total, int magicNum, int remain) {

List<Integer> peopleList = new ArrayList<>();
for (int i = 1; i <= total; i++) {
peopleList.add(i);
}
List<Integer> diedList = new ArrayList<>();


int index = -1; //当前应该删除的位置
while (true) {
index = (index + magicNum) % peopleList.size();

diedList.add(peopleList.get(index));
peopleList.remove(index);

//从上一个位置开始计数
index--;

//判断是否剩余m个,如果是的话结束
if (peopleList.size() == remain) {
System.out.println("共" + total + "人,依次报数,当报到" + magicNum + "的人自杀," + remain + "个人笑着活下去.");
System.out.println("死掉的序号顺序为:" + diedList);
System.out.println("笑着活下去序号为:" + peopleList);
System.out.println("----------------------------------");
return peopleList;
}
}
}

public static void main(String[] args) {
JosephProblem test = new JosephProblem();

test.getJosephNumbers(10, 4, 1);
test.getJosephNumbers(10, 2, 1);
test.getJosephNumbers(10, 3, 1);
test.getJosephNumbers(20, 10, 3);
test.getJosephNumbers(20, 4, 6);
}
}

输出结果:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
10人,依次报数,当报到4的人自杀,1个人笑着活下去.
死掉的序号顺序为:[4, 8, 2, 7, 3, 10, 9, 1, 6]
笑着活下去序号为:[5]
----------------------------------
10人,依次报数,当报到2的人自杀,1个人笑着活下去.
死掉的序号顺序为:[2, 4, 6, 8, 10, 3, 7, 1, 9]
笑着活下去序号为:[5]
----------------------------------
10人,依次报数,当报到3的人自杀,1个人笑着活下去.
死掉的序号顺序为:[3, 6, 9, 2, 7, 1, 8, 5, 10]
笑着活下去序号为:[4]
----------------------------------
20人,依次报数,当报到10的人自杀,3个人笑着活下去.
死掉的序号顺序为:[10, 20, 11, 2, 14, 6, 19, 15, 9, 7, 5, 8, 13, 18, 12, 4, 17]
笑着活下去序号为:[1, 3, 16]
----------------------------------
20人,依次报数,当报到4的人自杀,6个人笑着活下去.
死掉的序号顺序为:[4, 8, 12, 16, 20, 5, 10, 15, 1, 7, 14, 2, 11, 19]
笑着活下去序号为:[3, 6, 9, 13, 17, 18]
----------------------------------