约瑟夫问题

问题描述

传说有这样一个故事，在罗马人占领乔塔帕特后，39 个犹太人与约瑟夫及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自杀方式，41个人排成一个圆圈，第一个人从1开始报数，依次往后，如果有人报数到3，那么这个人就必须自杀，然后再由他的下一个人重新从1开始报数，直到所有人都自杀身亡为止。然而约瑟夫和他的朋友并不想遵从。于是，约瑟夫要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，从而逃过了这场死亡游戏 。

问题转换

41个人坐一圈，第一个人编号为1，第二个人编号为2，第n个人编号为n。

1. 编号为1的人开始从1报数，依次向后，报数为3的那个人退出圈；
2. 自退出那个人开始的下一个人再次从1开始报数，以此类推；
3. 求出最后退出的那个人的编号。

问题解决思路

1. 构建含有41个结点的单向循环链表，分别存储1~41的值，分别代表这41个人；
2. 使用计数器count，记录当前报数的值；
3. 遍历链表，每循环一次，count++；
4. 判断count的值，如果是3，则从链表中删除这个结点并打印结点的值，把count重置为0；

实现方法

public class Josephus {
    public static class Node<T> {
        //存储元素
        public T item;
        //指向下一个结点
        public Node next;

        public Node(T item, Node next) {
            this.item = item;
            this.next = next;
        }
    }

    public static void main(String[] args) {
        //新建结点
        Node<Integer> head = null;
        Node<Integer> pre = null;
        
        //创建41的结点的循环链表
        for (int i = 1; i <= 41; i++) {
            if (i == 1) {
                head = new Node<>(i, null);
                pre = head;
                continue;
            }

            Node<Integer> node = new Node<>(i, null);
            pre.next = node;
            pre = node;
            if (i == 41) {
                //构建循环链表，让最后一个结点指向第一个结点
                pre.next = head;
            }
        }
        
        //创建count计数器
        int count = 0;
        Node<Integer> n = head;
        Node<Integer> before = null;
        System.out.print("依次删除号码为：");
        //判断是否只剩一个结点
        while (n != n.next) {
            //每次count+1
            count++;
            if (count==3){
                //before即n的前一个结点指向n的下一个结点，去除了n结点
                before.next=n.next;
                //重置count
                count=0;
                System.out.print(n.item+" ");
            }else {
                //before指向n，经过下一步操作，before可以处于n的前一个结点
                before=n;
            }
            //n进入下一个结点
            n=n.next;
        }
        System.out.println();
        System.out.println("最后剩余的号码为："+n.item);
    }
}

代码测试