Josephu问题

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

代码实现

/**
 * @author : e-Tianlun.Zhan
 * @date: 2022/9/8 13:40
 */
public class Josephe {

    public static void main(String[] args) {
        CircleSingleLinkedList circleSingleLinkedList = new CircleSingleLinkedList();
        circleSingleLinkedList.addBoy(5);

        circleSingleLinkedList.showBoy();
        System.out.println("测试小孩出圈是否正确~~");

        circleSingleLinkedList.countBoy(1, 2, 5);
    }
}

class CircleSingleLinkedList {
    //定义first节点
    private Boy first = new Boy(-1);

    //新增boy
    public void addBoy(int nums) {
        if (nums < 1) {
            System.out.println("数量太小无法新增");
            return;
        }
        //定义CurBoy
        Boy curBoy = new Boy(-1);
        for (int i = 0; i <= nums; i++) {
            Boy boy = new Boy(i);
            if (i == 1) {
                //first
                first = boy;
                //构成一个环
                first.setNext(first);
                //让curBoy指向第一个小孩
                curBoy = first;
            } 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 = curboy.getNext();
        }
    }

    /**
     * 一共m个元素，从n开始报数，报k下，求出队顺序
     *
     * @param startNo  开始位置，从n号开始
     * @param countNum 喊的号
     * @param nums     个数
     */
    public void countBoy(int startNo, int countNum, int nums) {
        //定义辅助节点first，指向第一个元素，定义helper元素，指向最后一个元素，
        //首先将first和helper移动n-1下
        //然后first和helper移动k-1下，这个时候first就是要出列的对象，然后first = first.next，helper.next = first
        if (first == null || startNo > countNum || nums < 0) {
            System.out.println("参数输入有误，请重新输入");
            return;
        }
        //创建辅助指针
        Boy helper = first;
        //将辅助指针移动到最后一个元素
        while (true) {
            if (helper.getNext() == first) {
                break;
            }
            helper = helper.getNext();
        }
        //first和help移动startNo - 1 次
        for (int i = 0; i < startNo - 1; i++) {
            helper = helper.getNext();
            first = first.getNext();
        }
        //first和helper移动k-1下，这个时候first就是要出列的对象
        while (true) {
            //如果first 与 helper相等，出圈
            if (first == helper) {
                break;
            }
            //循环k-1下
            for (int i = 0; i < countNum - 1; i++) {
                first = first.getNext();
                helper = helper.getNext();
            }
            //这时first指向的节点就是要出圈的节点
            System.out.printf("要出圈的节点是：%d", first.getNo());
            System.out.println();
            first = first.getNext();
            helper.setNext(first);
        }
        System.out.printf("最后留在圈中的是小孩编号是：%d \n", 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;
    }
}