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.模拟解法

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());
 }

来源：https://www.cnblogs.com/dgwblog/p/10086189.html