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

 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 }