Java学习之约瑟夫环的两中处理方法

 package day_2; 

 import java.util.Scanner;

 /**

  * @author Administrator

  *  约瑟夫环问题：  设编号为 1,2,3，....n的N个人围坐一圈，约定编号为k（1<=k<=n）

  *  的人从1开始报数，数到m的那个人出列，它的下一位又从1开始报数，数到m的那个人又出列，依次

  *  类推，直到所有人出列为止，由此产生一个出队编号的序列。

  *  方法一：数组取模法、（模拟）

  */

 public class Demo_1 {

     public static void main(String args [])

     {

       int n,m;

       Scanner cin;

       while(true)

       {

           cin = new Scanner(System.in);

           n=cin.nextInt();

           m=cin.nextInt();

           if( 0==n+m ) break;

            fun_2(n,m);

       }

        // cin.close();

        }

     //方法一： 数组模拟

  static void fun_1(int n ,int m){

         boolean [] arr = new boolean [n+1];

         for(int i=0;i<=n;i++)

              arr[i]=true;

         //双亲数组法

          int  pos=1;

          m--;

        while(true){

           int cnt=pos;

           while(!arr[(pos+m)%(n+1)==0?1:(pos+m)%(n+1)]){

                   ++pos;

           if(pos-cnt>=n)    return ;

           }

           pos=(pos+m)%(n+1)==0?1:(pos+m)%(n+1);

            arr[pos]=false;

           System.out.println(pos);

           ++pos;

        }

     }

  /**

  *  方法二： 循环链表模拟

  */

 static void fun_2(int n , int m){

     class child{

         int id ;

         child  next ;

         public child(){};

         int getId() {

             return id;

         }

         child getNext() {

             return next;

         }

     } ;

   //模拟c循环链表

    child head,a;

     a = new child() ;

     a.id = 1 ;

     head = a ;

     for(int i=2 ; i<=n ; i++ ){

          child b = new child() ;

             b.id = i ;

          head.next = b ;

         head = b ;

     }

       head.next = a;

     while(a!=a.next){

         child b=head.next;

       for(int i=1; i<m ;i++ ){

           b=a;

           a=a.next;

       }

      System.out.println(a.id);

           a=a.next;

           b.next=a;

           System.gc();

     }

     if(m>1) System.out.println(a.id);

 }

 }

Java学习之约瑟夫环的两中处理方法的相关教程结束。