约瑟夫问题

问题描述

Josephu(约瑟夫、约瑟夫环)  问题 Josephu  问题为:设编号为1,2,… n的n个人围坐一圈,约定编号为k(1

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

举个例子

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 

重点:出圈

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

 

本文由 @常刚亮[Vip] 发布于 职涯宝 ,未经作者许可,禁止转载,欢迎您分享文章

发表评论

登录后才能评论
小程序
小程序
微信客服
微信客服
QQ客服 建站服务
分享本页
返回顶部