约瑟夫环

约瑟夫环(约瑟夫问题)是一个数学的应用问题:已知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);  }}