约瑟夫问题

问题

Josephus 问题（Josephus problem）是下面的游戏：N个人编号从1到N，围坐成一个圆圈。从1号开始传递一个热土豆。经过M次传递后拿着热土豆的人被清除离座，围坐的圆圈缩紧，由坐在被清除的人后面的人拿起热土豆继续进行游戏。最后剩下的人取胜。因此，如果M=0和N=5，则游戏人依序被清除，5号游戏人获胜。如果M=1和N=5，那么被清除的人的顺序是2，4，1，5。
a.编写一个程序解决M和N在一般值下的Josephus问题，应使程序尽可能地高效率，要确保能够清除各个单元。

思路

1. 放到队列
2. 设置一个计数器记录传了几次了
3. 循环判断
   1. 出队一个
   2. 判断
      • 如果次数等于M，输出，重置计数器
      • 否则入队，计数器+1

代码

/**
     * 约瑟夫
     *
     * @param N 总共人数
     * @param M 传递多少次出局
     */
    public static void Josephus(int N, int M) {
        //1.放到队
        Queue<Integer> persons = new LinkedList<>();
        for (int i = 1; i < N + 1; i++) {
            persons.add(i);
        }

        //2. 设置计数器
        int counts = 0;
        //3.循环
        while (!persons.isEmpty()) {
            //1.出队第一个
            Integer person = persons.poll();
            //2.判断
            if (counts == M) {
                System.out.println(person);
                //计数器重置
                counts = 0;
            } else {
                //入队最后一个
                persons.add(person);
                //计数器++
                counts++;
            }

        }
    }