Josephus环的解法有哪些

小编给大家分享一下Josephus环的解法有哪些，相信大部分人都还不怎么了解，因此分享这篇文章给大家参考一下，希望大家阅读完这篇文章后大有收获，下面让我们一起去了解一下吧！

创新互联建站始终坚持【策划先行，效果至上】的经营理念，通过多达十多年累计超上千家客户的网站建设总结了一套系统有效的营销解决方案，现已广泛运用于各行各业的客户，其中包括：格栅板等企业，备受客户赞赏。

约瑟夫环

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

以上是“Josephus环的解法有哪些”这篇文章的所有内容，感谢各位的阅读！相信大家都有了一定的了解，希望分享的内容对大家有所帮助，如果还想学习更多知识，欢迎关注创新互联行业资讯频道！

本文标题：Josephus环的解法有哪些
转载来源：http://myzitong.com/article/ijodis.html

Josephus环的解法有哪些

其他资讯