1 package day_2;  2  3 import java.util.Scanner; 4  5 /** 6  * @author Administrator 7  *  约瑟夫环问题：  设编号为 1,2,3，....n的N个人围坐一圈，约定编号为k（1<=k<=n） 8  *  的人从1开始报数，数到m的那个人出列，它的下一位又从1开始报数，数到m的那个人又出列，依次 9  *  类推，直到所有人出列为止，由此产生一个出队编号的序列。10  *  方法一：数组取模法、（模拟）11  */12 13 public class Demo_1 {14     public static void main(String args [])15     {16       int n,m;17       Scanner cin;18       while(true)19       {20           cin = new Scanner(System.in);21           n=cin.nextInt();22           m=cin.nextInt();23           if( 0==n+m ) break;24            fun_2(n,m);25       }26        // cin.close();27        }28     //方法一： 数组模拟29  static void fun_1(int n ,int m){30         boolean [] arr = new boolean [n+1];31         for(int i=0;i<=n;i++)32              arr[i]=true;33         //双亲数组法34          int  pos=1;35          m--;36        while(true){37           int cnt=pos;38           while(!arr[(pos+m)%(n+1)==0?1:(pos+m)%(n+1)]){39                   ++pos;40           if(pos-cnt>=n)    return ;41           }42           pos=(pos+m)%(n+1)==0?1:(pos+m)%(n+1);43            arr[pos]=false;44           System.out.println(pos);45           ++pos;46        }       47     }48  49  /**50  *  方法二： 循环链表模拟 51  */52 static void fun_2(int n , int m){    53     class child{    54         int id ;55         child  next ;56         public child(){};57         int getId() {58             return id;59         }60         child getNext() {61             return next;62         }63     } ;64     65   //模拟c循环链表    66    child head,a;67     a = new child() ;68     a.id = 1 ;69     head = a ;  70     for(int i=2 ; i<=n ; i++ ){71          child b = new child() ;72             b.id = i ;73          head.next = b ;74         head = b ;75     }76       head.next = a;77     while(a!=a.next){78         child b=head.next;79       for(int i=1; i<m ;i++ ){80           b=a; 81           a=a.next; 82       }83      System.out.println(a.id);84           a=a.next;85           b.next=a;86           System.gc();87     }88     if(m>1) System.out.println(a.id);89 }90 }