约瑟夫环问题

发表于 分类于

约瑟夫斯问题

有时也称为约瑟夫斯置换，是一个出现在计算机科学和数学中的问题。在计算机编程的算法中，类似问题又称为约瑟夫环。
人们站在一个等待被处决的圈子里。 计数从圆圈中的指定点开始，并沿指定方向围绕圆圈进行。 在跳过指定数量的人之后，执行下一个人。 对剩下的人重复该过程，从下一个人开始，朝同一方向跳过相同数量的人，直到只剩下一个人，并被释放。
问题即，给定人数、起点、方向和要跳过的数字，选择初始圆圈中的位置以避免被处决。

问题

有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]
----------------------------------