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

╰+哭是因爲堅強的太久メ 2023-10-11 17:16 56阅读 0赞

#### 文章目录 ####

*  约瑟夫问题的示意图
 *  1.单向环形链表的构建与遍历思路分析与代码实现
 *   *  代码实现
     *  测试添加与展示方法
 *  2.单向环形链表的出队的序列顺序问题思路分析与代码实现
 *   *  代码实现
     *  出圈方法测试
 *  完整代码

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

![在这里插入图片描述][fcc0e4cb3b2940e5b5f4fa33cb08a084.png]

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

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

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

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

![在这里插入图片描述][2269db9d9b6c42f0853dd9e62a3a8259.png]

## 约瑟夫问题的示意图 ##

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

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

![请添加图片描述][04a3987cb9404d80a6b02fc349d38ee6.png]

**出队列的顺序**

首先从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.单向环形链表的构建与遍历思路分析与代码实现 ##

![在这里插入图片描述][03019ad18c8d482099b37ec317b064bb.png]  
**构建一个单向的环形链表思路**

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

**遍历环形链表**

1.  先让一个辅助指针（变量）curBoy，指向first节点。
2.  然后通过一个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();
        }
    }

![在这里插入图片描述][8268d74d46044fc2b262b13f3c3fb15a.png]

--------------------

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

![在这里插入图片描述][da08963fefe5456881bc160e416a96e4.png]

**出队思路**

1.  需要创建一个辅助指针（变量）helper，事先应该指向环形链表的最后这个节点。
2.  小孩报数前，先让first和herlper移动k-1次
3.  当小孩报数时，让first和helper指针同时的移动 m-1次，然后出圈。
4.  这时就可以将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

![在这里插入图片描述][6fba40ecca2641689403c8d03a0c00ad.png]

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

--------------------

## 完整代码 ##

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;
        }
    }

[fcc0e4cb3b2940e5b5f4fa33cb08a084.png]: https://img-blog.csdnimg.cn/fcc0e4cb3b2940e5b5f4fa33cb08a084.png
[2269db9d9b6c42f0853dd9e62a3a8259.png]: https://img-blog.csdnimg.cn/2269db9d9b6c42f0853dd9e62a3a8259.png
[04a3987cb9404d80a6b02fc349d38ee6.png]: https://img-blog.csdnimg.cn/04a3987cb9404d80a6b02fc349d38ee6.png
[03019ad18c8d482099b37ec317b064bb.png]: https://img-blog.csdnimg.cn/03019ad18c8d482099b37ec317b064bb.png
[8268d74d46044fc2b262b13f3c3fb15a.png]: https://img-blog.csdnimg.cn/8268d74d46044fc2b262b13f3c3fb15a.png
[da08963fefe5456881bc160e416a96e4.png]: https://img-blog.csdnimg.cn/da08963fefe5456881bc160e416a96e4.png
[6fba40ecca2641689403c8d03a0c00ad.png]: https://img-blog.csdnimg.cn/6fba40ecca2641689403c8d03a0c00ad.png