1//假设500个小孩手拉着手围着一圈，数三就退出圈子，最后留在圈内的小孩是第几号？
 2
 3public class Count3Quit {
 4      public static void main(String[] args) {
 5              KidCircle kc = new KidCircle(500);
 6              
 7              Kid k = kc.first;
 8              int countNum = 0;
 9              while(kc.count > 1) {
10                   countNum ++;
11                   if(countNum == 3){
12                         countNum = 0;
13                           kc.del(k);  
14                    }
15                    k = k.right;
16               }
17               System.out.println("剩下的小孩编号是："+(kc.first.id+1));
18       } 
19}
20
21class Kid {
22      int id;
23      Kid left;
24      Kid right;
25}
26
27class KidCircle{
28       int count = 0;
29       Kid first,last;
30 
31
32       KidCircle (int n){
33        for (int i = 0;i<n;i++){add();}
34    }
35
36        void add(){
37            Kid k =new Kid();
38            k.id=count;
39            if (count<=0){
40                first=k;
41                last=k;
42                k.left=k.right=k;
43            } else {
44                k.left =last;
45                k.right =first;
46                last.right=first.left=last=k;
47            }
48            count++;
49        }
50
51        void del(Kid k){
52            if (count<=0){return;}
53            else if (count==1){first=last=null;}
54            else {
55                k.left.right=k.right;
56                k.right.left=k.left;
57                if (k==first){ first=k.right;}
58                else if (k==last){last=k.left;}
59            }
60            count--;
61        }
62}