Josephu (约瑟夫，约瑟夫环) 问题，是一个计算机科学和数学中的问题，在计算机编程的算法中，类似问题又称为约瑟夫环，又称 “丢手绢问题”。

据说著名犹太历史学家Josephus有过以下的故事

在罗马人占领乔塔帕特后，39 个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自杀方式，41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。然而Josephus 和他的朋友并不想遵从。首先从一个人开始，越过k-2个人（因为第一个人已经被越过），并杀掉第k个人。接着，再越过k-1个人，并杀掉第k个人。这个过程沿着圆圈一直进行，直到最终只剩下一个人留下，这个人就可以继续活着。

问题是，给定了和，一开始要站在什么地方才能避免被处决。Josephus要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏。

故事讲完了，在我们现实开发人员中如何使用单向环形链表解决这类问题呢？我们往下看！

约瑟夫问题的示意图

假设编号为1，2，3，…n的n个犹太人围坐一圈，约定编号为k（1<=k<=n）的人从1开始报数，数到m的那个人出列，它的下一位又从1开始报数，数到m的那个人又出列，依此类推。直到所有人出列为止，由此产生出一个出队编号的序列。

n = 5：即5个人
k = 1：从第一个开始报数
m = 2：数两下

出队列的顺序

首先从1开始报数，数两下2号出队列2号出队列后，这个环状节点就没有了。1号就会重新指向3号，由3号重新开始报数，3号数两下后4号出列。3号指向5号重新报数。5号报两下后1号出队列。1号出队列5号指向3号仍然是个环状。3号开始报数，报两下后5号出队列，5号走后场上就剩下3号，它自已指向自已依然是个环状，报数两下后也最终出了队列，最后得到的顺序为 2->4->1->5->3。

1.单向环形链表的构建与遍历思路分析与代码实现

构建一个单向的环形链表思路

先创建一个节点，让first指向该节点，并形成环形。
后面当我们每创建一个新的节点，就把该节点，加入到已有的环形链表中即可。

遍历环形链表

先让一个辅助指针（变量）curBoy，指向first节点。
然后通过一个while循环遍历该环形链表即可 curBoy.next == first结束。

代码实现

创建一个Boy类，表示一个节点

class Boy{
    //编号
    private int no;
    //指向下一个节点，默认null
    private Boy next;
    public Boy(int no){
        this.no = no;
    }
    public int getNo() {
        return no;
    }
    public void setNo(int no) {
        this.no = no;
    }
    public Boy getNext() {
        return next;
    }
    public void setNext(Boy next) {
        this.next = next;
    }
}

创建一个环形的单向链表并编写添加（add），遍历（show）方法

class CircleSingleLinkdList{
    //创建一个first节点，当前没有编号
    private Boy first =null;
    //添加小孩节点，构建成一个环形的链表
    public void addBoy(int nums){
        //nums 做一个数据校验
        if (nums < 1){
            System.out.println("nums的值不正确！");
            return; //直接结束
        }
        Boy curBoy = null; //辅助指针，帮助构建环形链表
        //使用for来创建我们的环形链表
        for (int i=1;i<=nums;i++){
            //根据编号，创建小孩节点
            Boy boy =new Boy(i);
            //如果是第一个小孩
            if (i == 1){
                first = boy;
                first.setNext(first); //构成环
                curBoy = first; //让curBoy指向第一个小孩
            }else {
                curBoy.setNext(boy);
                boy.setNext(first);
                curBoy = boy;
            }
        }
    }
    //遍历当前的环形链表
    public void showBoy(){
        //判断链表是否为空
        if (first == null){
            System.out.println("没有任何小孩~");
            return;
        }
        //因为first不能动，因此我们仍然使用一个辅助指针完成遍历
        Boy curBoy = first;
        while (true){
            System.out.printf("小孩的编号 %d \n",curBoy.getNo());
            if (curBoy.getNext() == first){ //说明已经遍历完毕
                break;
            }
            curBoy = curBoy.getNext(); //curBoy后移
        }
    }
}

测试添加与展示方法

/**
 * @author mengzhichao
 * @create 2022-04-09-16:14
 */
public class Josephu {
    public static void main(String[] args) {
        CircleSingleLinkdList circleSingleLinkdList =new CircleSingleLinkdList();
        circleSingleLinkdList.addBoy(5);//加入5个小孩节点
        circleSingleLinkdList.showBoy();
    }
}

2.单向环形链表的出队的序列顺序问题思路分析与代码实现

出队思路

需要创建一个辅助指针（变量）helper，事先应该指向环形链表的最后这个节点。
小孩报数前，先让first和herlper移动k-1次
当小孩报数时，让first和helper指针同时的移动 m-1次，然后出圈。
这时就可以将first指向的小孩节点出圈（出队）。first =first.next helper.next = first 原来first指向的节点就没有任何引用，就会被回收。

代码实现

在CircleSingleLinkdList类中新增countBoy方法根据用户的输入，计算小孩的出圈顺序。

    /***
     *
     * @param startNo 表示从第几个小孩开始数数
     * @param countNum  表示数几下
     * @param nums  表示最初有多少个小孩在圈中
     */
    public void countBoy(int startNo,int countNum,int nums){
        //参数校验
        if (first == null || startNo < 1 || startNo > nums){
            System.out.println("参数输入有误！");
            return;
        }
        //创建一个辅助指针，帮助完成小孩出圈
        Boy helper = first;
        //需要创建一个辅助指针（变量）helper，事先应该指向环形链表的最后这个节点。
        while (true){
            if (helper.getNext() == first){ //说明helper指向最后小孩节点
                break;
            }
            helper = helper.getNext();
        }
        //小孩报数前，先让first和herlper移动k-1次
        for (int j = 0;j <startNo - 1;j++){
            first = first.getNext();
            helper = helper.getNext();
        }
        //当小孩报数时，让first和helper指针同时的移动 m-1次，然后出圈。
        //这里是一个循环操作，直到圈中只有一个节点。
        while (true){
            if (helper == first){   //说明圈中只有一个节点
                break;
            }
            //让 first和 herlper指针同时的移动countNum-1
            for (int j = 0;j<countNum - 1;j++){
                first = first.getNext();
                helper = helper.getNext();
            }
            //这时first指向的节点，就是要出圈的小孩节点
            System.out.printf("小孩%d出圈\n",first.getNo());
            //这时将first指向的小孩节点出圈
            first = first.getNext();
            helper.setNext(first);
        }
        System.out.printf("最后留在圈中的小孩编号%d \n",first.getNo());
    }

出圈方法测试

//测试一把小孩出圈是否正确
circleSingleLinkdList.countBoy(1,2,5); //2>4>1>5>3

到此本文就结束了，如果在写的过程有什么问题导致异常可以参考下方的完整代码！

完整代码

package com.company.linkedlist;
/**
 * @author mengzhichao
 * @create 2022-04-09-16:14
 */
public class Josephu {
    public static void main(String[] args) {
        CircleSingleLinkdList circleSingleLinkdList =new CircleSingleLinkdList();
        circleSingleLinkdList.addBoy(5);//加入5个小孩节点
        circleSingleLinkdList.showBoy();
        //测试一把小孩出圈是否正确
        circleSingleLinkdList.countBoy(1,2,5); //2>4>1>5>3
    }
}
//创建一个环形的单向链表
class CircleSingleLinkdList{
    //创建一个first节点，当前没有编号
    private Boy first =null;
    //添加小孩节点，构建成一个环形的链表
    public void addBoy(int nums){
        //nums 做一个数据校验
        if (nums < 1){
            System.out.println("nums的值不正确！");
            return; //直接结束
        }
        Boy curBoy = null; //辅助指针，帮助构建环形链表
        //使用for来创建我们的环形链表
        for (int i=1;i<=nums;i++){
            //根据编号，创建小孩节点
            Boy boy =new Boy(i);
            //如果是第一个小孩
            if (i == 1){
                first = boy;
                first.setNext(first); //构成环
                curBoy = first; //让curBoy指向第一个小孩
            }else {
                curBoy.setNext(boy);
                boy.setNext(first);
                curBoy = boy;
            }
        }
    }
    //遍历当前的环形链表
    public void showBoy(){
        //判断链表是否为空
        if (first == null){
            System.out.println("没有任何小孩~");
            return;
        }
        //因为first不能动，因此我们仍然使用一个辅助指针完成遍历
        Boy curBoy = first;
        while (true){
            System.out.printf("小孩的编号 %d \n",curBoy.getNo());
            if (curBoy.getNext() == first){ //说明已经遍历完毕
                break;
            }
            curBoy = curBoy.getNext(); //curBoy后移
        }
    }
    //根据用户的输入，计算小孩的出圈顺序
    /***
     *
     * @param startNo 表示从第几个小孩开始数数
     * @param countNum  表示数几下
     * @param nums  表示最初有多少个小孩在圈中
     */
    public void countBoy(int startNo,int countNum,int nums){
        //参数校验
        if (first == null || startNo < 1 || startNo > nums){
            System.out.println("参数输入有误！");
            return;
        }
        //创建一个辅助指针，帮助完成小孩出圈
        Boy helper = first;
        //需要创建一个辅助指针（变量）helper，事先应该指向环形链表的最后这个节点。
        while (true){
            if (helper.getNext() == first){ //说明helper指向最后小孩节点
                break;
            }
            helper = helper.getNext();
        }
        //小孩报数前，先让first和herlper移动k-1次
        for (int j = 0;j <startNo - 1;j++){
            first = first.getNext();
            helper = helper.getNext();
        }
        //当小孩报数时，让first和helper指针同时的移动 m-1次，然后出圈。
        //这里是一个循环操作，直到圈中只有一个节点。
        while (true){
            if (helper == first){   //说明圈中只有一个节点
                break;
            }
            //让 first和 herlper指针同时的移动countNum-1
            for (int j = 0;j<countNum - 1;j++){
                first = first.getNext();
                helper = helper.getNext();
            }
            //这时first指向的节点，就是要出圈的小孩节点
            System.out.printf("小孩%d出圈\n",first.getNo());
            //这时将first指向的小孩节点出圈
            first = first.getNext();
            helper.setNext(first);
        }
        System.out.printf("最后留在圈中的小孩编号%d \n",first.getNo());
    }
}
//创建一个Boy类，表示一个节点
class Boy{
    //编号
    private int no;
    //指向下一个节点，默认null
    private Boy next;
    public Boy(int no){
        this.no = no;
    }
    public int getNo() {
        return no;
    }
    public void setNo(int no) {
        this.no = no;
    }
    public Boy getNext() {
        return next;
    }
    public void setNext(Boy next) {
        this.next = next;
    }
}

单向环形链表解决Josephu(约瑟夫)问题

约瑟夫问题的示意图

1.单向环形链表的构建与遍历思路分析与代码实现

代码实现

测试添加与展示方法

2.单向环形链表的出队的序列顺序问题思路分析与代码实现

代码实现

出圈方法测试

完整代码

热门文章

最新文章

相关电子书

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

单向环形链表解决Josephu(约瑟夫)问题

约瑟夫问题的示意图

1.单向环形链表的构建与遍历思路分析与代码实现

代码实现

测试添加与展示方法

2.单向环形链表的出队的序列顺序问题思路分析与代码实现

代码实现

出圈方法测试

完整代码

热门文章

最新文章

相关电子书