Josephus环的四种解法(约瑟夫环)基于java详解
约瑟夫环
约瑟夫环(约瑟夫问题)是一个数学的应用问题:已知n个人(以编号1，2，3…n分别表示)围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列;他的下一个人又从1开始报数，数到m的那个人又出列;依此规律重复下去，直到圆桌周围的人全部出列。
通常解决这类问题时我们把编号从0~n-1，最后结果+1即为原问题的解
引用别人的一个图：直观说明问题
分析：
- 第一步：从1开始报数为3的时候就删除3号结点
- 第二步：从4号结点开始报数，当为3的时候删除6号结点；
- 第三步：从7号结点开始报数，当为3的时候删除1号结点；
- 第四步：从2号结点开始报数，当为3的时候删除5号结点；
- 第五步：从7号结点开始报数，当为3的时候删除2号结点；
- 第六步：从4号元素开始报数，当为3的时候删除8号结点；
- 第七步：又从4号开始报数，当为3的时候删除4号结点，此时链表中只有一个7号结点，所以最后的结点就是7号结点；
1.模拟解法
publicclass模拟{
publicstaticvoidmain(String[]args){
Scannerin=newScanner(System.in);
//总人数
intn=in.nextInt();
//数到m的那个人出列
intm=in.nextInt();
//初始化为0都没有出去
int[]arr=newint[n];
//剩下的人数
intpeopleLeft=n;
//初始化下标
intindex=0;
//下标计算器
intcount=0;
//>0出循环为负
while(peopleLeft>1){
if(arr[index]==0){
//count为计步器不是下标指向
count++;
if(count==m){
arr[index]=1;
count=0;
peopleLeft--;
}
}
index++;
if(index==arr.length){
index=0;
}
}
for(inti=0;i
2.递归解法
/**
*递归式:
*f(1)=0;第一个位置永远为0
*f(i)=f(i)+m%n;
*/
publicstaticintyuesefu(intn,intm){
if(n==1){
return0;
}else{
return(yuesefu(n-1,m)+m)%n;
}
}
publicstaticvoidmain(String[]args){
System.out.println(yuesefu(41,3)+1);
vailCode(41,3);
}
//逆推验证代码
publicstaticvoidvailCode(inta,intb){
System.out.print(b);
intreslut;
for(inti=a;i>=2;i--){
reslut=2;
for(intj=i;j<=a;j++){
reslut=(reslut+b)%j;
}
System.out.printf("->%d",reslut+1);
}
}
3.循环链表解法
publicclassCircularLinkedList{
publicstaticvoidmain(String[]args){
/**
*节点类
*/
classNode{
privateintdata=1;
privateNodenext;
Node(){
next=null;
}
}
Nodehead,temp;
head=newNode();
head.data=1;
inta=41;
intb=3;
//临时节点
temp=head;
for(inti=0;i"+(head.data+1));
head.next=head.next.next;
}
System.out.println(head.data);
}
}
4.Collection解法
publicstaticvoidmain(String[]args){
inta=41;
intb=3;
LinkedListlist=newLinkedList<>();
for(inti=0;i1){
for(inti=0;i"+list.getFirst());
list.remove();//remvehead
}
System.out.println(list.getFirst());
}
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持毛票票。