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

约瑟夫问题(图文)

第十三双眼睛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：

很赞哦！ ()

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

下一篇：栈(图文)