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

怎么样用程序来模拟这样的一个过程呢？ 可以使用循环链表的方法，来模拟他们的死亡顺序。

首先建立一个循环链表

public class Josephus {
    private class Data{
        int num;
        Data next = null;
        public Data(int num){
            this.num = num;
        }
    }

    Data head = new Data(0);
    Data tail = new Data(0);
    public Josephus(){
        head.next = tail;
        tail.next = head;
    }

    public void insert(int num){
        Data data = new Data(num);
        tail.next.next = data;
        tail.next = data;
        data.next = head.next;
    }
}

链表显示函数

public void display(){
    Data cur = head.next;
    while(true){
        System.out.print(cur.num+"");
        cur = cur.next;
        if(cur == head.next || cur==cur.next) break;
        else System.out.print("->");
    }
    System.out.println("\n");
}

预览一下

static int sum = 41;
static int t = 3;
public static void main(String[] args){
    Josephus jp = new Josephus();
    System.out.println("\n\n依次填入序号 1-41并显示");
    for(int i = 1; i <= sum; i++){
        jp.insert(i);
    }
    jp.display();
}

输出结果

依次填入序号 1-41并显示
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

可以看到插入链表是没有问题了，接下来就是模拟Josephus问题的过程。

public void core(int live){
    Data cur = head.next;
    // 当指针的下一个指向自己，说明循环链表中只有一个元素了
    while(cur != cur.next){
        // 跳过(暂时)幸存的人，t - 1， 数到3自杀就是1和2还活着
        for(int i = 1; i < t-1; i++){
            cur = cur.next;
        }

        // 删除元素(自杀)
        System.out.print(cur.next.num + "->");
        cur.next = cur.next.next;

        // 指针后移
        cur = cur.next;
    }

    // 把最后一个元素输出
    System.out.println(cur.num);
}

最后在main函数里调用这个方法看看结果

System.out.println("\n模拟");
jp.core();


模拟
3->6->9->12->15->18->21->24->27->30->33->36->39->1->5->10->14->19->23->28->32->37->41->7->13->20->26->34->40->8->17->29->38->11->25->2->22->4->35->16->31

最后面两位，恰好是16和31，与故事中的位置是一致的！

代码，还能更完善吗？ 能否把幸存者的序号输出来呢？

public void core(int live){
    // 将密谋好决定活下来的人数传进来
    // 活下来人数其实不一定是t-1
    // 有可能四个人一起密谋好呢？
    // 有可能两个人中有一个人就是想不开呢？

    Data cur = head.next;
    System.out.println("死亡顺序：");
    while(true){
        for(int i = 1; i < t-1; i++){
            cur = cur.next;
        }
        if(sum > live){
            System.out.print(cur.next.num+"->");
            cur.next = cur.next.next;
            sum--;// 总人数-1
            cur = cur.next;
        } else {
            head.next = cur;
            break;
        }
    }
    System.out.println("\n\n幸存者序号：");
    while(true){
        System.out.print(cur.num+"");
        cur = cur.next;
        if(cur == head.next) break;
        else System.out.print(" , ");
    }
}

稍微做了一点改动。

如果约瑟夫和三位朋友一起密谋了呢？ 就会是这样的结果：

依次填入序号 1-41并显示
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


模拟
死亡顺序：
3->6->9->12->15->18->21->24->27->30->33->36->39->1->5->10->14->19->23->28->32->37->41->7->13->20->26->34->40->8->17->29->38->11->25->2->22->

幸存者序号：
35 , 4 , 16 , 31

附上完整代码

public class Josephus {
    private class Data{
        int num;
        Data next = null;
        public Data(int num){
            this.num = num;
        }
    }

    Data head = new Data(0);
    Data tail = new Data(0);
    public Josephus(){
        head.next = tail;
        tail.next = head;
    }

    public void insert(int num){
        Data data = new Data(num);
        tail.next.next = data;
        tail.next = data;
        data.next = head.next;
    }

    public void core(int live){
        // 将密谋好决定活下来的人数传进来
        // 活下来人数其实不一定是t-1
        // 有可能四个人一起密谋好呢？
        // 有可能两个人中有一个人就是想不开呢？

        Data cur = head.next;
        System.out.println("死亡顺序：");
        while(true){
            for(int i = 1; i < t-1; i++){
                cur = cur.next;
            }
            if(sum > live){
                System.out.print(cur.next.num+"->");
                cur.next = cur.next.next;
                sum--;// 总人数-1
                cur = cur.next;
            } else {
                head.next = cur;
                break;
            }
        }
        System.out.println("\n\n幸存者序号：");
        while(true){
            System.out.print(cur.num+"");
            cur = cur.next;
            if(cur == head.next) break;
            else System.out.print(" , ");
        }
    }

    public void display(){
        Data cur = head.next;
        while(true){
            System.out.print(cur.num+"");
            cur = cur.next;
            if(cur == head.next || cur==cur.next) break;
            else System.out.print("->");
        }
        System.out.println("\n");
    }

    static int sum = 41;
    static int t = 3;
    public static void main(String[] args){
        Josephus jp = new Josephus();
        System.out.println("\n\n依次填入序号 1-41并显示");
        for(int i = 1; i <= sum; i++){
            jp.insert(i);
        }
        jp.display();

        System.out.println("\n模拟");
        jp.core(4);
    }
}