问题来历

据说著名犹太历史学家Josephus有过以下的故事：在罗马人占领乔塔帕特后，39 个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自杀方式，41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。然而Josephus 和他的朋友并不想遵从。首先从一个人开始，越过k-2个人（因为第一个人已经被越过），并杀掉第k个人。接着，再越过k-1个人，并杀掉第k个人。这个过程沿着圆圈一直进行，直到最终只剩下一个人留下，这个人就可以继续活着。问题是，给定了和，一开始要站在什么地方才能避免被处决。Josephus要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏。 [1]

17世纪的法国数学家加斯帕在《数目的游戏问题》中讲了这样一个故事：15个教徒和15 个非教徒在深海上遇险，必须将一半的人投入海中，其余的人才能幸免于难，于是想了一个办法：30个人围成一圆圈，从第一个人开始依次报数，每数到第九个人就将他扔入大海，如此循环进行直到仅余15个人为止。问怎样排法，才能使每次投入大海的都是非教徒。

问题分析

约瑟夫问题实际上是一个环形单向链表的问题，每个节点都存在下一个节点的地址，最后一个节点指向第一个节点

环形列表以及自杀顺序

1.我们先找出从哪一个位置开始报数

2.我们要知道一共有多少个人

3.我们要知道要自杀的上一个节点以及下一个节点的人

代码实现

节点实体类：

package com.zyp.joseph;/** * @author zyp * @create 2021/12/21 * 节点 */public class Node {    private int id;    public int getId() {        return id;    }    public void setId(int id) {        this.id = id;    }    public Node getNextNode() {        return nextNode;    }    public void setNextNode(Node nextNode) {        this.nextNode = nextNode;    }    private Node nextNode;    Node(int id){        this.id = id;    }}

环形链表实体类以及测试：

package com.zyp.joseph;/** * @author zyp * @create 2021/12/21 * 单向环形链表 */public class CircularLinked {    Node firstNode = null;    //添加节点    public void addNode(int num){        //当前节点，为了好将节点添加进去        Node curNode = null;        for(int i = 1;i<=num;i++){            if(i == 1){                firstNode = new Node(i);                firstNode.setNextNode(firstNode);                curNode = firstNode;            }else{                Node newNode = new Node(i);                curNode.setNextNode(newNode);                newNode.setNextNode(firstNode);                curNode = newNode;            }        }    }    //遍历所有节点    public void showNodeList(){        if(firstNode == null){            System.out.println("该单向环形链表没有元素");            return;        }        Node curNode = firstNode;        while(true){            System.out.println("节点："+curNode.getId());            curNode = curNode.getNextNode();            if(curNode == firstNode){                break;            }        }    }    //当前节点的总数    public int totalNode(){        int total = 0;        Node curNode = firstNode;        if(firstNode == null){            return total;        }else{            while(true){                total++;                curNode = curNode.getNextNode();                if(curNode == firstNode){                    break;                }            }        }        return total;    }    /**     * @param id 从这个用户开始报数     * @param num 报数为num的用户出列表     */    public void joseph(int id ,int num){        if(firstNode == null){            System.out.println("节点为空");            return;        }        //开始报数的节点        Node startNode = firstNode;        //上一个节点        Node node = null;        while(true){            if(startNode.getId() == id){                break;            }else{                startNode = startNode.getNextNode();            }        }        int delTotal = 0;        int total = totalNode();        while(true){            for(int i = 1;i<num;i++){                if(i == num -1){                    node = startNode;                }                startNode = startNode.getNextNode();            }//            System.out.println("start:"+startNode.getId()+";node:"+node.getId());            System.out.println("删除的节点为:"+startNode.getId());            //将上一个节点指向要删除节点的下一个节点            node.setNextNode(startNode.getNextNode());            delTotal++;            if(total == delTotal){                break;            }            startNode = startNode.getNextNode();        }    }    public static void main(String[] args){        CircularLinked circularLinked = new CircularLinked();        circularLinked.addNode(41);        circularLinked.showNodeList();        int totalNode = circularLinked.totalNode();        System.out.println("总节点数量为："+totalNode);        circularLinked.joseph(1,3);    }}

结果展示：

结果展示