java算法实现之约瑟夫问题(Josephu)

约瑟夫问题 image.png

首先这个问题我们可以很清楚的看出来，可以使用单向环形队列的数据结构来代入这个问题。
我先来分析一下这道题的思路:
第一步，确定是单向环形链表后，我们需要先构建这样一个数据结构，
由于每个人的最后都出列后，这个队伍中的人数为0，因此我们不需要设置头节点，比较简便。所以我们先构建一个，包含编号、指向下一个节点的类。

class Baby{

    //编号
    private int no;
    //指向下一个节点
    private Baby next;
//get\set....
}

2.队列有了，那么我们第二部，就需要普通的数据结构都需要有的基本方法，遍历，新增，修改，删除。。。根据题意，只需要遍历(用于测试)还有新增，就足够了。所以我们在新建一个内部类，把该单向环形链表作为私有类，写一些常用方法来操作它。

class CircleSingleLinkedList{

    //创建一个fist节点
    private Baby first=new Baby(-1);
    //添加一个小孩，构建一个环形链表
    public void addBaby(int nums){
        //nums 代表要添加几个小孩
        if(nums<1){
            System.out.println("nums值，不正确");
            return ;
        }

        //辅助指针帮助构建环形链表
        Baby curBaby=null;
        //使用一个for循环，来创建我们的环形链表
        for (int i=1;i<=nums;i++){
            //根据编号，创建小孩节点
            Baby baby = new Baby(i);
            if(i==1){
                first=baby;
                first.setNext(first);
                curBaby=first;
            }else{
                curBaby.setNext(baby);
                baby.setNext(first);
                curBaby=baby;
            }
        }
    }

    /**
     * 遍历当前环形链表
     */
    public void list(){
        if(first.getNext()==null){
            System.out.println("该链表为null");
            return ;
        }
        Baby curBaby=first;
        while (true){
            System.out.println("小孩的编号为:"+curBaby.getNo());
            if(curBaby.getNext()==first) {
                break;
            }
            curBaby = curBaby.getNext();
        }
    }

第三步，我们再来考虑，如何出队列的问题。通常遇到这种数据结构的问题，一定要思路清晰。越是复杂的数据处理，最最基本的数据结构越需要先理清楚出来，再来去思考，最复杂的需要怎么实现。下图是实现的思路 image.png

为什么需要一个辅助指针，这个指针，是作为每次报数后，出链表的前一个元素，用来指向后一个元素(也就是删除那个元素的，这个时候，被删除的元素由于没有被引用了，就会被垃圾回收了)

还有一点，两个节点同时移动的次数，其实就是出列后，从下一个节点作为1开始计算的次数。
代码如下:

  /**
     *  根据用户输入，计算小孩出圈的顺序
     * @param startNo  表示从第几个小孩开始数数
     * @param countNum  表示数几下
     * @param nums       表示最初多少个小孩在圈中
     */
    public void countBaby(int startNo,int countNum,int nums){
        if(first == null || startNo<1 || startNo>nums){
            System.out.println("输入参数有误，请重新输入");
            return ;
        }
        //创建要给辅助指针，帮助小孩出圈
        Baby helper=first;
        //需求创建一个辅助指针，helper，事先应该指向环形链表的最后一个节点
        while(true){
            //说明helper指向最后一个小孩节点
            if(helper.getNext()== first){
                break;
            }
            helper=helper.getNext();
        }
        //报数之前，我们还有一个参数是从第几个人之中开始出队列的，于是我们需要把辅助节点还有first节点一起移动到startNo-1的位置
        for (int i=0;i<startNo-1;i++){
                first=first.getNext();
                helper=helper.getNext();
            }

        //小孩报数时，让两个指针同时移动countNum-1次
        while (true){

            if(helper==first){
                break;
            }
            for(int i=0;i<countNum-1;i++){
                first=first.getNext();
                helper=helper.getNext();
            }
            System.out.println("出列的人编号为:"+first.getNo());
            first=first.getNext();
            helper.setNext(first);
        }
        System.out.println("出列的人编号为"+first.getNo());
    }

好了，以上就是约瑟夫问题的java解法实现。

感谢您阅读我的文章，如果满意可以帮我点歌赞，谢谢哈。
如果对文章部分还有什么见解或者疑惑，可以私信评论我，欢迎技术讨论。如果需要获取完整的文件资源，可以加我微信z985085305，获取我整理的全套笔记。
思想的碰撞最能促进技术的进步哦。