Josephus环的四种解法(约瑟夫环)基于java详解

时间:2021-05-20

约瑟夫环

约瑟夫环(约瑟夫问题)是一个数学的应用问题:已知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.模拟解法

public class 模拟 { public static void main(String[] args) { Scanner in=new Scanner(System.in); //总人数 int n=in.nextInt(); // 数到m的那个人出列 int m=in.nextInt(); // 初始化为0 都没有出去 int [] arr=new int[n]; //剩下的人数 int peopleLeft=n; //初始化下标 int index=0; // 下标计算器 int count=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 (int i = 0; i < arr.length; i++) { if(arr[i]==0){ System.out.println(i+1); } } }}

2.递归解法

/** * 递归式: * f(1)=0; 第一个位置永远为0 * f(i)=f(i)+m%n; */ public static int yuesefu(int n,int m){ if(n==1){ return 0; }else { return (yuesefu(n-1,m) + m) % n; } } public static void main(String[] args) { System.out.println(yuesefu(41,3)+1); vailCode(41,3); } //逆推验证代码 public static void vailCode(int a,int b){ System.out.print(b); int reslut; for (int i = a; i >=2 ; i--) { reslut=2; for (int j = i; j <=a ; j++) { reslut=(reslut+b)%j; } System.out.printf("->%d",reslut+1); } }

3.循环链表解法

public class CircularLinkedList { public static void main(String[] args) { /** * 节点类 */ class Node{ private int data=1; private Node next; Node(){ next=null; } } Node head,temp; head=new Node(); head.data=1; int a=41; int b=3; // 临时节点 temp=head; for (int i = 0; i < a; i++) { Node new_node=new Node(); new_node.data=i+1; temp.next=new_node; temp=new_node; } temp.next=head.next; while (head.next!=head){ for (int i = 0; i < b-1; i++) { head=head.next; } System.out.print("->"+(head.data+1)); head.next=head.next.next; } System.out.println(head.data); }}

4.Collection解法

public static void main(String[] args) { int a=41; int b=3; LinkedList<Integer> list = new LinkedList<>(); for (int i = 0; i < a; i++) { list.add(i+1); } while (list.size()>1){ for (int i = 0; i < b-1; i++) { list.add(list.remove()); } System.out.print("->"+list.getFirst()); list.remove();//remve head } System.out.println(list.getFirst()); }

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持。

声明:本页内容来源网络,仅供用户参考;我单位不保证亦不表示资料全面及准确无误,也不保证亦不表示这些资料为最新信息,如因任何原因,本网内容或者用户因倚赖本网内容造成任何损失或损害,我单位将不会负任何法律责任。如涉及版权问题,请提交至online#300.cn邮箱联系删除。

相关文章