快捷導(dǎo)航

Josephus環(huán)的四種解法(約瑟夫環(huán))基于java詳解

更新時間：2019年09月12日 10:10:12 作者：---dgw博客

這篇文章主要介紹了Josephus環(huán)的四種解法(約瑟夫環(huán))基于java詳解,文中通過示例代碼介紹的非常詳細，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友可以參考下

約瑟夫環(huán)

約瑟夫環(huán)(約瑟夫問題)是一個數(shù)學(xué)的應(yīng)用問題:已知n個人(以編號1，2，3…n分別表示)圍坐在一張圓桌周圍。從編號為k的人開始報數(shù)，數(shù)到m的那個人出列;他的下一個人又從1開始報數(shù)，數(shù)到m的那個人又出列;依此規(guī)律重復(fù)下去，直到圓桌周圍的人全部出列。

通常解決這類問題時我們把編號從0~n-1，最后結(jié)果+1即為原問題的解

引用別人的一個圖：直觀說明問題

分析：

第一步：從1開始報數(shù)為3的時候就刪除3號結(jié)點
第二步：從4號結(jié)點開始報數(shù)，當為3的時候刪除6號結(jié)點；
第三步：從7號結(jié)點開始報數(shù)，當為3的時候刪除1號結(jié)點；
第四步：從2號結(jié)點開始報數(shù)，當為3的時候刪除5號結(jié)點；
第五步：從7號結(jié)點開始報數(shù)，當為3的時候刪除2號結(jié)點；
第六步：從4號元素開始報數(shù)，當為3的時候刪除8號結(jié)點；
第七步：又從4號開始報數(shù)，當為3的時候刪除4號結(jié)點，此時鏈表中只有一個7號結(jié)點，所以最后的結(jié)點就是7號結(jié)點；

1.模擬解法

public class 模擬 {
  public static void main(String[] args) {
    Scanner in=new Scanner(System.in);

    //總?cè)藬?shù)
    int n=in.nextInt();
    // 數(shù)到m的那個人出列
    int m=in.nextInt();
    // 初始化為0 都沒有出去
    int [] arr=new int[n];

    //剩下的人數(shù)
    int peopleLeft=n;
    //初始化下標
    int index=0;
    // 下標計算器
    int count=0;
    // >0 出循環(huán)為負
    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.循環(huán)鏈表解法

public class CircularLinkedList {
  public static void main(String[] args) {
    /**
     * 節(jié)點類
     */
    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;
    // 臨時節(jié)點
    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());
  }

以上就是本文的全部內(nèi)容，希望對大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。

您可能感興趣的文章: