您现在的位置是:首页 > 后台技术 > 数据结构与算法数据结构与算法

约瑟夫问题(图文)

第十三双眼睛2022-06-06【数据结构与算法】人已围观

简介约瑟夫问题

编号为1.2....n,一共n个人围成一圈,约定从编号为k的人开始报数,数到m的那个人出列,他的下一位再从1开始报数,数到m的人再出列。以此类推,知道所有的人出列完成。
创建一个小孩节点
package day001;
public class Boy {
    private int no;
    public Boy next;
    public Boy(int no){
        this.no = no;
    }
    public int getNo() {
        return no;
    }
    public void setNo(int no) {
        this.no = no;
    }
}
创建一个环形链表
package day001;
public class CircleLinkedList {
    private Boy first = new Boy(-1);
    public void addBoy(int nums){
        if(nums < 1){
            System.out.println("nums不正确");
            return;
        }
        Boy curBoy = null;
        for(int i=1;i<=nums;i++){
            Boy boy = new Boy(i);
            if(i==1){
                first = boy;
                first.next=first;
                curBoy=first;
            }else{
                curBoy.next=boy;
                boy.next=first;
                curBoy=boy;
            }
        }
    }
    public void showBoy(){
        if(first==null){
            System.out.println("链表为空");
            return;
        }
        Boy curBoy=first;
        while(true){
            System.out.println("小孩的编号"+curBoy.getNo());
            if(curBoy.next==first){
                System.out.println("已经遍历完毕");
                break;
            }
            curBoy=curBoy.next;
        }
    }
    public void countBoy(int startNo,int count,int nums){
        if(first==null||startNo<1||startNo>nums){
            System.out.println("参数输入有误");
            return;
        }
        Boy helper=first;
        while(true){
            if(helper.next==first){
                break;
            }
            helper=helper.next;
        }
        for(int j=0;j<startNo-1;j++){
            first=first.next;
            helper=helper.next;
        }
        while (true){
            if(helper==first){
                break;
            }
            for(int j=0;j<count-1;j++){
                first=first.next;
                helper=helper.next;
            }
            System.out.println("小孩"+first.getNo());
            first=first.next;
            helper.next=first;
        }
        System.out.println("最后出圈的是小孩"+first.getNo());
    }
}
测试一下
package day001;
public class CircleLinkedListDemo {
    public static void main(String[] args) {
        CircleLinkedList circleLinkedList = new CircleLinkedList();
        circleLinkedList.addBoy(5);
        circleLinkedList.countBoy(5,2,5);
    }
}
测试结果
小孩1
小孩3
小孩5
小孩4
最后出圈的是小孩2

 

Tags:

很赞哦! ()

上一篇:双向链表(图文)

下一篇:栈(图文)

文章评论

    共有条评论来说两句吧...

    用户名:

    验证码:

本站推荐

站点信息

  • 网站名称:JavaStudy
  • 建站时间:2019-1-14
  • 网站程序:帝国CMS7.5
  • 文章统计153篇文章
  • 标签管理标签云
  • 统计数据百度统计
  • 微信公众号:扫描二维码,关注我们