约瑟夫问题Josephu算法求解

????????约瑟夫问题是一个著名的数学问题，起源于一个关于犹太人的历史故事。据说在罗马人占领乔塔帕特后，39个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自杀方式：41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。然而，Josephus和他的朋友并不想遵从这个规则，Josephus要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏。

????????在算法领域，约瑟夫问题通常指的是n个人围坐一圈，约定编号为k的人从1开始报数，数到m的那个人出列，它的下一位又从1开始报数，数到m的那个人又出列，依此类推，直到所有人出列为止。这个问题可以用多种方法解决，例如使用递归或循环链表等数据结构。????????

构建环形链表算法思想：

1.先创建第一个节点，让first指向该节点，并形成环状；

2.当我们每创建一个新的节点，就把该节点，加入到已有的环形链表中

遍历环形链表：

1.先让一个辅助指针(变量)curBoy,指向first节点

2.然后通过一个while循环遍历 该环形链表即可 curBoy.next == first 结束

约瑟夫问题求解算法思想：

1.需求创建一个辅助指针(变量)helper,事先应该指向环形链表的最后一个节点

tips:小孩报数前，先让first 和 helper 移动? k -?1

2.当小孩报数时，让first 和 helper指针同时移动 m - 1

3.这时就可以将 first 指向的小孩节点出圈

?first = first.next

helper.next = first
?

创建孩子对象：?

class Boy {
    private int no; //编号
    private Boy next; //指向下一个节点，默认null

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

    public Boy(int no) {
        this.no = no;
    }

    @Override
    public String toString() {
        return "Boy{" +
                "no=" + no +
                ", next=" + next +
                '}';
    }
}

环形链表：

//创建一个环形的单向链表
class CircleSingleLinkedList {
    //创建一个first节点。没有编号
    private Boy first = new Boy(-1);

    //添加小孩节点，构建成一个环形的链表
    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;  //将辅助指针，指向第一个节点
            }
            //boy为最新节点，curBoy为当前节点
            curBoy.setNext(boy); //将上一次的节点连接最新节点
            boy.setNext(first); //最新节点指向第一个节点
            curBoy = boy; //移动指针
        }
    }

    //遍历环形链表
    public void showList() {
        Boy temp = first;
        if (first == null) {
            System.out.println("链表为空~");
            return;
        }
        while (true) {
            System.out.printf("小孩的编号%d\n", temp.getNo());
            if (temp.getNext() == first) {
                break;
            }
            temp = temp.getNext(); //相当于将指针后移
        }
    }

    /**
     * 根据用户输入，让对应的小孩出圈
     *
     * @param starNo   表示从第几个小孩开始数数
     * @param countNum 表示数几下
     * @param nums     表示最初有多少小孩再圈中
     */
    public void countBoy(int starNo, int countNum, int nums) {
        //先对数据进行校验
        if (first == null || starNo < 1 || starNo > nums) {
            System.out.println("参数输入有误，请重新输入");
            return;
        }
        //创建要给的辅助指针，帮助完成小孩出圈
        Boy helper = first;
        //需求创建一个辅助指针(变量) helper
        while (true) {
            if (helper.getNext() == first) { //说明helper指向最后的小孩节点
                break;
            }
            helper = helper.getNext();
        }
        //小孩报数前，先让 first 和 helper 移动 k-1 次
        for (int i = 0; i < starNo - 1 ; i++) {
            first = first.getNext();
            helper = helper.getNext();
        }
        /* 从第m个位置开始
        当小孩报数时，让 first 和 helper 指针同时移动 m - 1 次 ，然后出圈
        这里是一个循环操作，知道圈中有只有一个节点
         */
        while (true){
            if(helper == first){
                break;
            }
            /* 每次数数 countNum 下
             * 让 first 和 helper 指针同时移动 countNum -1
             */
            for (int j = 0; j < countNum -1 ; j++) {
                first = first.getNext();
                System.out.printf("出圈的孩子为%d号\n",first.getNo());
                helper = helper.getNext();
            }
            first = first.getNext();
            helper.setNext(first);
        }
        System.out.printf("最后留在圈中的小孩编号为%d\n",helper.getNo());
    }

测试类：
?

public class Josepfu {
    public static void main(String[] args) {
        //测试相关数据
        CircleSingleLinkedList circleSingleLinkedList = new CircleSingleLinkedList();

        //添加节点
        circleSingleLinkedList.addBoy(5);

        //遍历数组
        System.out.println("======原始节点数据=====");
        circleSingleLinkedList.showList();

        //出圈操作
        System.out.println("======出圈后=====");
        circleSingleLinkedList.countBoy(1, 2, 5);
    }
}

输出结果：