用环状单向链表解决约瑟夫问题

素颜马尾好姑娘i 2023-07-07 08:06 20阅读 0赞

问题描述：N个人围成一圈，从第一个人开始报数，报到m的人出圈，剩下的人继续从1开始报数，报到m的人出圈；如此往复，直到所有人出圈。（模拟此过程，输出出圈的人的序号）

在数据结构与算法书上，这个是用链表解决的  
**思路：**  
1.**创建表示单向链表的类boy**

class Boy {
        private int no;
        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;
        }
    }

**2.怎么样才能使单项链表变成环状？**

//构建环形单链表
        //num 为节点个数
        public void setCircleList(int num) {
            if (num < 1) {
                System.out.println("小孩个数不符合要求");
                return;
            }
            Boy curBoy = null;
            for (int i = 1; i <= num; i++) {
                Boy boy = new Boy(i);
                if (i == 1) {
                    first = boy;
                    first.setNext(first);
                    curBoy = boy;
                } else {
                    curBoy.setNext(boy);
                    boy.setNext(first);
                    curBoy = boy;
                }
            }
        }

**用first指针一直指向第一个小孩，标记第一个小孩，创建一个curBoy指针作为工具指针标记当前小孩的上一个小孩，当只有一个小孩时该小孩的next指向自己；  
人数超过1时，没新增加一个小孩，让curBoy的next指向当前小孩，当前小孩的next指向first就构建成了环形链表；**

**3.出队序列怎么确定？**

//startNo:重第几个开始数数
        //countNum：数几下
        //nums:有几个人参与数数
        public void getCountList(int startNo, int countNum, int nums) {
            //数据校验
            if (first == null || startNo < 1 || startNo > nums) {
                System.out.println("参数有误！！");
                return;
            }
    
            for (int i = 0; i <startNo-1 ; i++) {
                first=first.getNext();
            }
            Boy helper=first;
            //让help指向first的后一个节点
            while (helper.getNext()!=first){
                helper=helper.getNext();
            }
            //报数出队
            while (true){
                if(helper==first){
                    break;
                }
                for (int i = 0; i <countNum-1 ; i++) {
                    first=first.getNext();
                    helper=helper.getNext();
                }
                System.out.println("当前出队编号为："+first.getNo());
                first=first.getNext();
                helper.setNext(first);
            }
            System.out.println("最后出队编号为："+first.getNo());
        }
    }

**（1）创建一个工具节点Boy helper，将first指向第一次报数小孩，helper指向first前一个位置  
（2）循环countNum-1次出一个小孩，每循环一次将helper 和first后移一次；  
(3)循环结束后当前first指向的小孩就是要出队的小孩，  
（4）将firs指向后一个小孩，并将helper的next指向first，小孩完成出队；**

**全部代码：**

package com.yg.linkedList;/*
    @author  GeQiLin
    @date    2020/2/21  16:23
    */
    
    import java.util.spi.CurrencyNameProvider;
    
    public class Josephu {
        public static void main(String[] args) {
            CircleSingleLinkedList circleList = new CircleSingleLinkedList();
            circleList.setCircleList(5);
    //        circleList.showCircleList();
    
            //测试约瑟夫问题
            circleList.getCountList(1,2,5);
        }
    }
    
    class CircleSingleLinkedList {
        private Boy first = null;
    
        public Boy getFirst() {
            return first;
        }
    
        public void setFirst(Boy first) {
            this.first = first;
        }
    
        //构建环形单链表
        //num 为节点个数
        public void setCircleList(int num) {
            if (num < 1) {
                System.out.println("小孩个数不符合要求");
                return;
            }
            Boy curBoy = null;
            for (int i = 1; i <= num; i++) {
                Boy boy = new Boy(i);
                if (i == 1) {
                    first = boy;
                    first.setNext(first);
                    curBoy = boy;
                } else {
                    curBoy.setNext(boy);
                    boy.setNext(first);
                    curBoy = boy;
                }
            }
        }
    
        //打印环形链表
        public void showCircleList() {
            if (first == null) {
                System.out.println("链表为空！！");
                return;
            }
            Boy curBoy = first;
            while (true) {
                System.out.println("当前boy的编号为：" + curBoy.getNo());
                if (curBoy.getNext() == first) {
                    System.out.println("打印完毕");
                    break;
                }
                curBoy = curBoy.getNext();
            }
        }
    
        //约瑟夫问题出队列表
        //startNo:重第几个开始数数
        //countNum：数几下
        //nums:有几个人参与数数
        public void getCountList(int startNo, int countNum, int nums) {
            //数据校验
            if (first == null || startNo < 1 || startNo > nums) {
                System.out.println("参数有误！！");
                return;
            }
    
            for (int i = 0; i <startNo-1 ; i++) {
                first=first.getNext();
            }
            Boy helper=first;
            //让help指向first的后一个节点
            while (helper.getNext()!=first){
                helper=helper.getNext();
            }
            //报数出队
            while (true){
                if(helper==first){
                    break;
                }
                for (int i = 0; i <countNum-1 ; i++) {
                    first=first.getNext();
                    helper=helper.getNext();
                }
                System.out.println("当前出队编号为："+first.getNo());
                first=first.getNext();
                helper.setNext(first);
            }
            System.out.println("最后出队编号为："+first.getNo());
        }
    }
    
    class Boy {
        private int no;
        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;
        }
    }