数据结构与算法（五）单向环形链表---约瑟夫问题

一、Josephu 问题

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

二、代码实现

1、创建孩子对象

class Body{
    private int no;
    private Body next;

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

    public Body getNext() {
        return next;
    }

    public void setNext(Body next) {
        this.next = next;
    }

    public int getNo() {
        return no;
    }
}

2、实现孩子出圈

/**
 * 单向环形链表---约瑟夫问题
 */
public class CircleSingleLinkedList {



    private Body first=null;

    /**
     * 约瑟夫问题 构建环形
     * @param nums
     */

    public void addBodys(int nums){
        if(nums<1){
            throw new RuntimeException("输入的参数不正确");
        }
        Body curBody=null;
        for (int i=1;i<=nums;i++){
                Body body=new Body(i);
                if (i == 1){
                    first=body;
                    first.setNext(first);
                    curBody=first;
                }else {
                    curBody.setNext(body);
                    body.setNext(first);
                    curBody=body;
                }
        }
    }

    /**
     * 显示链表节点
     */
    public void show(){
        if (first == null){
            throw new RuntimeException("没有数据");
        }
        Body body=first;
        while (true){
            System.out.printf("小孩编号为：%d \n",body.getNo());
            if (body.getNext().getNo() == first.getNo()){
                break;
            }
            body=body.getNext();
        }
    }

    /**
     * 小孩出圈
     * @param startNo
     * @param countNum
     * @param nums
     */
    public void countBody(int startNo,int countNum,int nums){
        if ( first == null || startNo <1 || startNo>nums){
            throw new RuntimeException("游戏参数不对");
        }
        Body helper=first;
        while (true) {
            if (helper.getNext() == first) {
                break;
            }
            helper = helper.getNext();
        }
        for(int j=0;j<startNo-1;j++){
            first=first.getNext();
            helper=helper.getNext();
        }
        while (true){
            if (helper==first){
                break;
            }
            for(int j=0;j<countNum-1;j++){
                first=first.getNext();
                helper=helper.getNext();
            }
            System.out.printf("小孩编号为：%d 出圈\n",first.getNo());
            first=first.getNext();
            helper.setNext(first);
        }
        System.out.printf("最后留在圈里的小孩编号：%d 出圈 \n",first.getNo());
    }


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

        circleSingleLinkedList.addBodys(5);
        circleSingleLinkedList.show();

        circleSingleLinkedList.countBody(1,2,5);

    }

}