约瑟夫环问题Java实现

java利用循环链表实现约瑟夫环问题

约瑟夫环问题的起源来自犹太历史学家约瑟夫和他的朋友以及39其余的犹太人，总共41人为了躲避敌人，藏在一个山洞中，39个犹太人决定宁愿死也不被敌人抓到，于是决定自杀，所有人排成一个圈，由第一个人开始报数，每当数到3，就自杀。这个游戏接着从自杀的位置开始，还是从1数到3。依次类推，约瑟夫将朋友和自己安排在了16和31的位置，最后顺利逃过了，自杀这一劫，因为最后就剩他一个人了。

环形链表遍历的时候会是一个无限循环，如果链表中的数据逐渐减少，不控制终究会一个不剩，这又不满足我们问题的求解。因此我们需要定义出循环结束的条件，按照约瑟夫环的规则，只剩下一个的时候就结束，在环形链表结构中，那就是环形链表中只剩一个结点的时候。这样就可以结束遍历了。最后打印出剩下的结点，问题解决。

代码实现：

public class Josepfu {

    public static void main(String[] args) {
        CricleSingleLinkedList cricleSingleLinkedList = new CricleSingleLinkedList();
        cricleSingleLinkedList.addBoy(41);
        cricleSingleLinkedList.showBoy();
        cricleSingleLinkedList.countBoy(1, 3, 41);
    }
}

//创建一个环形单向链表
class CricleSingleLinkedList {
    Boy first = null;

    void addBoy(int nums) {
        //nums做一个数据的校监
        if (nums < 1) {
            System.out.println("输入的数目不正确");
            return;
        } else {
            //辅助指针  用来构成环形链表
            Boy curBoy = null;
            first = new Boy(1);
            //使用for来创建环形链表
            for (int i = 1; i <= nums; ++i) {
                //如果只有一个节点的话，也需要形成环
                if (i == 1) {
                    curBoy = first;
                } else {
                    Boy boy = new Boy(i);
                    curBoy.setNext(boy);
                    boy.setNext(first);
                    curBoy = boy;
                }
            }
        }
    }

    void showBoy() {
        if (first == null) {
            System.out.println("没有要遍历的数据");
            return;
        }
        Boy curBoy = first;
        while (true) {
            System.out.println("编号为: " + curBoy.getId() + "");
            curBoy = curBoy.getNext();

            if (curBoy == first) {
                break;
            }
        }

    }
    //根据用户输入，输出小孩的出圈顺序

    /**
     * @param start    从第几个小孩开始报数
     * @param countNum 数多少下
     * @param nums     一共有多少小孩
     */
    public void countBoy(int start, int countNum, int nums) {
        //辅助指针
        Boy helper;
        if (first == null) {
            System.out.println("没有数据");
            return;
        }
        if (start < 1 || countNum < 1 || nums < start) {
            System.out.println("输入的数据有误！");
            return;
        }
        helper = first;
        //定位到起始位置
        if (start == 1) {
            for (int j = 1; j < nums; j++) {
                helper = helper.getNext();
            }
        } else {
            for (int i = 1; i < start; i++) {
                first = first.getNext();
                if (i >= 2) {
                    helper = helper.getNext();
                }
            }
        }
        while (true) {
            if (first == helper) {
                System.out.println("最后一个编号为：" + first.getId());
                break;
            }
            for (int i = 1; i < countNum; ++i) {
                first = first.getNext();
                helper = helper.getNext();
            }
            System.out.println(first.getId() + "号出圈");
            first = first.getNext();
            helper.setNext(first);
        }
    }
}


class Boy {
    private int id;
    Boy next;

    Boy(int id) {
        this.id = id;
    }

    public int getId() {
        return id;
    }

    public void setId(int id) {
        this.id = id;
    }

    public Boy getNext() {
        return next;
    }

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