数据结构与算法——约瑟夫环问题（JosephuRing）

Josephu 问题

• 设编号为1，2，…，n的n个人围坐一圈，约定编号为k(1<=k<=n)的人从1开始报数，数到m的那个人出列，他的下一位又从1开始数，数到m的那个人又出列，依次类推，直到所有人出列为止，由此产生一个出队编号的序列

提示

• 用一个不带头节点的循环链表来处理Josephu 问题：先构成一个又n个节点的单循环链表，然后由k节点起从1开始计数，计到m时，对应节点从链表中删除，然后再从被删除的节点的下一个节点又开始从1开始计数，直到最后一个节点从链表中删除，算法结束

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

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

遍历环形链表

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

两种方式实现出圈功能

• 方法1：创建一个辅助节点temp，初始化在first 指针后面，每次让first 指在需要出圈的节点，然后进行操作
• 方法2：只用一个first 指针，使其每次指在需要出圈节点的前一个节点，然后进行操作

5.3.2 Josephu问题实现代码

核心代码：

下面代码主要利用方法2

/**
     * 约瑟夫问题
     * @param sum 游戏总人数
     * @param k 由第k个人开始
     * @param m 每次数m个数
     */
    public static void JosephuRing(int sum,int k,int m){
        //k,sum和m取值校验
        //即k的值小于等于sum且大于0
        //m的值大于1，虽然理论上可以取1，但我们认为这是毫无意义的，就相当于将first放在k上依次遍历
        if(k > sum || k <= 0 || m <= 1){
            System.out.println("~~~数据输入有误，请输入正确的数据!!!~~~");
            return;
        }
        CircleSingleLinkedList josephu = new CircleSingleLinkedList();
        josephu.addBoy(sum);

        //将孩子出圈的顺序存入数组中
        int[] arr = new int[sum];

        //根据需求，环形链表中的first节点对于本问题无影响
        //首先将first指针指向第k个人
        josephu.setFirst(josephu.find(k));
        System.out.printf("移动到第 %d 个人的位置：",k);
        josephu.showCircle();
        Boy temp = josephu.getFirst();

        //从第k个人开始数（m-1）个数
        //由于sum个人，所以一共只需要循环sum次
        for(int i = 0; i < sum; i++){
            for(int j = 2; j < m; j++){
                //将first节点向后移动一位，直到移动在数(m - 1)个数的时候
                josephu.setFirst(josephu.getFirst().getNext());
            }
            if(josephu.getFirst().getNext() == josephu.getFirst()){
                arr[i] = josephu.getFirst().getNo();
                josephu.setFirst(null);
                System.out.printf("~第 %d 次后，所有人都已经出圈~\n",i + 1);
                //输出孩子出约瑟夫环顺序
                System.out.println("孩子们的出圈顺序为：");
                for(int count = 0; count < arr.length; count ++){
                    System.out.printf(" => %d",arr[count]);
                }
                return;
            }
            arr[i] = josephu.getFirst().getNext().getNo();
            //要出圈的人就是first节点的下一个节点
            josephu.getFirst().setNext(josephu.getFirst().getNext().getNext());
            josephu.setFirst(josephu.getFirst().getNext());
            //输出每次出圈后的情况
            System.out.printf("第 %d 次出圈后顺序：",i+1);
            josephu.showCircle();
        }
    }

完整代码（附环形链表创建及增删改查）

package com.crisp.LinkedList;

public class Josephu {
    public static void main(String[] args) {
        /*//测试环形链表
        CircleSingleLinkedList josephu = new CircleSingleLinkedList();
        //测试环形链表增加功能
        josephu.addBoy(5);
        josephu.showCircle();
        //测试环形链表删除功能
        josephu.delete(5);
        josephu.showCircle();
        //测试环形链表查找功能
        Boy res = josephu.find(5);
        System.out.println(res);*/
        //测试约瑟夫环
        JosephuRing(10,5,2);
    }

    /**
     * 约瑟夫问题
     * @param sum 游戏总人数
     * @param k 由第k个人开始
     * @param m 每次数m个数
     */
    public static void JosephuRing(int sum,int k,int m){
        //k,sum和m取值校验
        //即k的值小于等于sum且大于0
        //m的值大于1，虽然理论上可以取1，但我们认为这是毫无意义的，就相当于将first放在k上依次遍历
        if(k > sum || k <= 0 || m <= 1){
            System.out.println("~~~数据输入有误，请输入正确的数据!!!~~~");
            return;
        }
        CircleSingleLinkedList josephu = new CircleSingleLinkedList();
        josephu.addBoy(sum);

        //将孩子出圈的顺序存入数组中
        int[] arr = new int[sum];

        //根据需求，环形链表中的first节点对于本问题无影响
        //首先将first指针指向第k个人
        josephu.setFirst(josephu.find(k));
        System.out.printf("移动到第 %d 个人的位置：",k);
        josephu.showCircle();
        Boy temp = josephu.getFirst();

        //从第k个人开始数（m-1）个数
        //由于sum个人，所以一共只需要循环sum次
        for(int i = 0; i < sum; i++){
            for(int j = 2; j < m; j++){
                //将first节点向后移动一位，直到移动在数(m - 1)个数的时候
                josephu.setFirst(josephu.getFirst().getNext());
            }
            if(josephu.getFirst().getNext() == josephu.getFirst()){
                arr[i] = josephu.getFirst().getNo();
                josephu.setFirst(null);
                System.out.printf("~第 %d 次后，所有人都已经出圈~\n",i + 1);
                //输出孩子出约瑟夫环顺序
                System.out.println("孩子们的出圈顺序为：");
                for(int count = 0; count < arr.length; count ++){
                    System.out.printf(" => %d",arr[count]);
                }
                return;
            }
            arr[i] = josephu.getFirst().getNext().getNo();
            //要出圈的人就是first节点的下一个节点
            josephu.getFirst().setNext(josephu.getFirst().getNext().getNext());
            josephu.setFirst(josephu.getFirst().getNext());
            //输出每次出圈后的情况
            System.out.printf("第 %d 次出圈后顺序：",i+1);
            josephu.showCircle();
        }
    }
}

//创建一个环形的单向链表
class CircleSingleLinkedList{
    //创建一个first节点，当前无编号
    private Boy first = null;

    //获取头节点
    public Boy getFirst() {
        return first;
    }

    //设置头节点位置
    public void setFirst(Boy first) {
        this.first = first;
    }

    //添加节点，构建成一个环形的链表
    //直接输入参与游戏的人数
    public void addBoy(int sum){
        //对sum做一个数据校验
        if(sum < 1){
            System.out.println("游戏人数不正确~");
            return;
        }
        //创建一个辅助指针，帮助创建变量
        Boy cur = null;
        //使用for循环创建环形链表
        for(int i = 1; i <= sum; i++){
            //根据编号创建节点
            Boy boy = new Boy(i);
            //如果是第一个小孩
            if(i == 1){
                first = boy;
                first.setNext(first);//构成环
                cur = first;//让cur指向第一个节点
            }else{
                cur.setNext(boy);
                boy.setNext(first);
                cur = boy;
            }
        }
    }

    //删除节点
    public void delete(int delnum){
        //判断链表是否为空
        if(first == null){
            System.out.println("~~~链表为空！！！~~~");
            return;
        }
        //创建两个辅助节点
        //一个跟在另一个的后面
        //由前一个cur1发现需要删除的节点
        //后面的cur2指向发现节点的下一个节点
        Boy cur1 = first.getNext();
        Boy cur2 = first;
        //遍历链表找到需要删除的节点
        while(true){
            //System.out.println(cur1.getNo());
            //System.out.println(cur2.getNo());
            if(cur1.getNo() == delnum){
                 cur2.setNext(cur1.getNext());
                if(cur1.getNo() == first.getNo()){
                    first = cur2.getNext();
                }
                 return;
            }
            if(cur1.getNo() == first.getNo()){
                System.out.println("~没有发现所要删除的节点~");
                return;
            }
            //两个节点均向后移位
            cur1 = cur1.getNext();
            cur2 = cur2.getNext();
        }
    }

    //查找节点
    //由于是一个环形节点
    //所以输入值应该为从头节点开始的第num个数，而不是编号值
    //注意：first节点应该算作第一个数
    public Boy find(int num){
        //定义辅助指针，用来在链表中移动
        Boy temp = first;
        for(int i = num; i > 1; i--){
            temp = temp.getNext();
        }
        return temp;
    }

    //遍历当前环形链表
    public void showCircle(){
        //判断是否为空
        if(first == null){
            System.out.println("链表为空~");
            return;
        }
        //first不可移动，因此使用辅助指针
        Boy temp = first;
        while(true){
            System.out.printf("=> %d ",temp.getNo());
            if(temp.getNext() == first){
                //最后一个节点
                System.out.println();
                return;
            }
            temp = temp.getNext();
        }
    }
}


//创建一个Boy类，表示一个节点
class Boy{
    private int no;//编号
    private Boy next;//指向下一个节点
    //构造器
    public Boy(int no) {
        this.no = no;
    }
    //set方法
    public void setNo(int no) {
        this.no = no;
    }
    public void setNext(Boy next) {
        this.next = next;
    }
    //get方法
    public int getNo() {
        return no;
    }
    public Boy getNext() {
        return next;
    }

    //重写toString，方便查看
    @Override
    public String toString() {
        return "Boy{" +
                "no=" + no +
                '}';
    }
}

该笔记整理自B站BV1E4411H73v，博主稍加整理改进以及排版