约瑟夫问题

问题描述

Josephu(约瑟夫、约瑟夫环)  问题 Josephu  问题为：设编号为1，2，… n的n个人围坐一圈，约定编号为k（1<=k<=n）的人从1开始报数，数到m 的那个人出列，它的下一位又从1开始报数，数到m的那个人又出列，依次类

推，直到所有人出列为止，由此产生一个出队编号的序列。

举个例子

n = 5 , 即有5个人

k = 1, 从第一个人开始报数

m = 2, 数2下

经过一次出圈后

第二次出圈

第三次出圈

第四次出圈

所以最终的出圈顺序 2->4->1->5->3

以上方法是使用单向循环链表来完成的，下面看代码展示

创建一个孩子类，每个孩子对象表示一个节点

class Boy{
    //小孩编号
    private int no;
    //下一个小孩
    private Boy next;

    //构造器
    public Boy(int no){
        this.no = no;
    }

    public int getNo() {
        return no;
    }

    public Boy getNext() {
        return next;
    }

    public void setNo(int no) {
        this.no = no;
    }

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

创建单向循环链表

并且创建添加孩子和显示的方法

class CircleSingleLinkedList{
    private Boy first = null;

    public CircleSingleLinkedList(){}

    /**
     * 添加指定的节点
     * @param nums
     */
    public void add(int nums){
        if(nums < 1){
            System.out.println("输入的数据不合法~~");
            return;
        }
        Boy curBoy = null;
        for (int i = 1; i < nums + 1; i++) {
            Boy boy = new Boy(i);
            if(i == 1){
                first = boy;
                curBoy = first;
                boy.setNext(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.println("小孩的编号是" + curBoy.getNo());
            if (curBoy.getNext() == first)
                break;
            curBoy = curBoy.getNext();
        }
    }
}

重点：出圈

/**
     * 根据用户输入，计算小孩出圈的顺序
     * @param startNo   开始小孩的编号
     * @param countNum  一次数几下
     * @param nums      总共小孩数
     */
    public void countBoy(int startNo,int countNum,int nums){
        if(first == null || startNo < 1 || startNo > nums){
            System.out.println("输入的数据有误~~~");
            return;
        }
        //创建辅助指针，指向first指针的前一位
        Boy helper = first;
        while(helper.getNext() != first ){
            helper = helper.getNext();
        }
        //根据开始小孩的编号，是first指针指向开始小孩
        for (int i = 0; i < startNo - 1; i++) {
            first = first.getNext();
            helper = helper.getNext();
        }
        //开始报数出队
        while(first.getNext() != first){
            //报数
            for (int i = 0; i < countNum - 1; i++) {
                first = first.getNext();
                helper = helper.getNext();
            }
            //出队
            System.out.println("小孩" + first.getNo() + "出圈~~");
            helper.setNext(first.getNext());
            first = first.getNext();
        }
        System.out.println("最后出圈的小孩编号" + first.getNo());
    }

 

本文地址：https://blog.csdn.net/qq_45796208/article/details/109901904