约瑟夫环问题

有n个人围成一圈,从第一个开始报数,每次数到m的人出圈,直到剩下最后一个人。

这个问题,可以借助队列。

import java.util.LinkedList;
import java.util.Queue;

// 有n个人围成一圈,从第一个开始报数,每次数到m的人出圈,直到剩下最后一个人
// 通过队列(Queue)来实现这个循环链表,每次将队首元素移动到队尾,以此模拟环状结构。报数为m的人将被移出队列,直到队列中只剩下一个元素,即最后留下的人。最后,返回这个人的编号

public class 约瑟夫环问题 {

    public static void main(String[] args) {
        int n = 18; // 总人数
        int m = 5; // 报数的数字
        initQueue(n, m);
    }
    static void initQueue(int num, int m) {
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 1; i<=num;i++) {
            queue.offer(i);
        }
        // 模拟报数过程
        int count = 0; // 计数器
        while (queue.size() > 1) { // 留下唯一一个人
            count++;
            if (count == m) {
                queue.poll(); // 报数为m的人
                count = 0; // 重置计数器
            } else {
                // 取得当前非特殊的数字
                int front = queue.peek();
                // 将数字从队列头移除
                queue.poll();
                // 加入到队列尾
                queue.offer(front);
            }
        }

        // 最后剩余的队列中的数字
        System.out.println(queue.poll());
    }
}
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容