约瑟夫环数数

题目：

　　有n个孩子站成一圈，从第一个孩子开始顺时针方向报数，报到3的人出列，下一个人继续从1报数，直到最后剩下一个孩子为止。问剩下第几个孩子。

(另一种题型 -> 约瑟夫环 -> 递归算法 http://www.cnblogs.com/yangyh/archive/2011/10/30/2229517.html)

分析：

　　数到3的人退出，可暂将此人的去留状态修改。

正确代码：

写法1：

 1 public static void main(String[] args) {
 2         //    n为在对人数,out为当前出列的人    
 3         int n=0,out=0;
 4         Scanner sc = new Scanner(System.in);
 5         int aa = sc.nextInt();
 6         int[] a = new int[aa];
 7         
 8         while(true){
 9             for (int i = 0; i < a.length; i++) {
10                 if(a[i]==0){
11                     n++;
12                     if(n==3){
13                         a[i]=1;
14                         n=0;
15                         out++;
16                         if(out==aa){
17                         //    直接显示最后一个人
18                             System.out.println(i+1);
19                         }
20                         //    显示过程中每次出列的人
21                         //    System.out.println("出列："+(i+1));
22                     }
23                 }
24             }
25             if(out==aa) break;
26         }    
27     }

写法2(ZB)：

public class Yuesefu {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int [] arr = new int[n];
        int count = 0;
        int sum = 0;
        for (int i = 0; sum < arr.length -1; i++) {
            if (i==arr.length) {
                i = 0;
            }
            if (arr[i] == 0) {
                count ++;                
            }
            if (count == 3) {
                arr[i] = 1;
                count = 0;
                sum++;
            }
        }
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == 0) {
                System.out.println(i+1);                
            }
        }
    }
}

约瑟夫环数数

推荐阅读