Java单向环形链表解决约瑟夫问题（约瑟夫环）-创新互联

约瑟夫环（约瑟夫问题）是一个数学的应用问题：类似小孩玩丢手绢。已知 n 个人（以编号1，2，3...n分别表示）围坐在一张圆桌周围。从编号为 k 的人开始报数，数到 m 的那个人出圈；他的下一个人又从 1 开始报数，数到 m 的那个人又出圈；依此规律重复下去，直到剩余最后一个胜利者。例如：有5个人围成一圈进行此游戏，每个人编号为 1-5。若规定数到 2 的人出圈。则游戏过程如下：

公司主营业务：成都网站制作、网站建设、外贸网站建设、移动网站开发等业务。帮助企业客户真正实现互联网宣传，提高企业的竞争能力。创新互联是一支青春激扬、勤奋敬业、活力青春激扬、勤奋敬业、活力澎湃、和谐高效的团队。公司秉承以“开放、自由、严谨、自律”为核心的企业文化，感谢他们对我们的高要求，感谢他们从不同领域给我们带来的挑战，让我们激情的团队有机会用头脑与智慧不断的给客户带来惊喜。创新互联推出全椒免费做网站回馈大家。

（1）开始报数，从第一个数到2 的人为 2 号，2号出圈。1，[ 2 ]，3 ， 4， 5。

（2）从3号重新从1开始计数，则接下来数到2的人为4号，4号出圈。

（3）继续循环直到留下最后一人游戏胜利。

图解：

创建节点和链表：

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;
    }
}
//创建一个环形链表
class CircleSingleLinkedList{
    // 创建一个first节点，当前没有编号
    private Boy first = null;
    //添加Boy方法
    public void addBoy(int nums){
        //对nums数据进行校验
        if (nums<1){
            System.out.println("nums值不正确");
            return;
        }
        Boy curBoy = null;//创建辅助节点
        //用for循环创建链表
        for (int i = 1; i<= nums; i++) {
            Boy boy = new Boy(i);
            if (i==1){
                first = boy;
                first.setNext(first);
                curBoy = first;//让curBoy指向第一个小孩
            }else {
                curBoy.setNext(boy);
                boy.setNext(first);
                curBoy = boy;
            }
        }
    }
     //遍历当前环形链表
    public void showBoy() {
        if (first == null) {
            System.out.println("没有小孩");
            return;
        }
        Boy curBoy = first;//辅助
        while (true) {
            System.out.printf("小孩的编号是%d\n", curBoy.getNo());
            if (curBoy.getNext() == first) break;
            curBoy = curBoy.getNext();//后移
        }
    }
    public void outBoy(int starNo,int countNum,int nums) {
        // starNo 从第几个小孩开始数,int countNum 每次数几下,int nums 最初有几个小孩
        //先对数据进行校验
        if (first == null || starNo >nums || starNo< 0) {
            System.out.println("参数输入有误，请重新输入");
            return;
        }
        //创建辅助指针，帮助小孩出圈
        Boy helper = first;
        //先让helper指向最后一个小孩
        while (true) {
            if (helper.getNext() == first) break;//遍历结束，helper指向了最后的小孩
            helper = helper.getNext();
        }
        //让first指向从starNo数开始的小孩，helper紧跟first后面
        for (int i = 0; i< starNo - 1; i++) {
            first = first.getNext();
            helper = helper.getNext();
        }

        while (true) {
            if (helper == first) break;//圈中只有一个节点
            //否则继续循环，每次让first和helper移动countNum-1次
            for (int i = 0; i< countNum - 1; i++) {
                first = first.getNext();
                helper = helper.getNext();
            }
            //此时first就是出圈的小孩
            System.out.printf("小孩%d出圈\n", first.getNo());
            first = first.getNext();
            helper.setNext(first);//重新构成环形
        }
        System.out.printf("最后出圈的小孩编号为%d\n",first.getNo());//也可以是helper.getNo()

    }


}

测试：

public static void main(String[] args) {
        CircleSingleLinkedList c= new CircleSingleLinkedList();
        c.addBoy(5);
        c.showBoy();
        //测试出圈
        System.out.println("从第一个小孩开始，每次数两下，一共5个小孩，则出圈顺序为：");
        c.outBoy(1,2,5);
    }

输出结果：

小孩的编号是1
小孩的编号是2
小孩的编号是3
小孩的编号是4
小孩的编号是5
从第一个小孩开始，每次数两下，一共5个小孩，则出圈顺序为：
小孩2出圈
小孩4出圈
小孩1出圈
小孩5出圈
最后出圈的小孩编号为3

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧

文章名称：Java单向环形链表解决约瑟夫问题（约瑟夫环）-创新互联
本文网址：http://cqcxhl.cn/article/digogg.html