/*
 * 假设队列中共有500人，每次从1开始数，数到3的人出队，
 * 下一个人接着数1，每次从1开始数 依旧数到3的人出队 数到头就从当前队伍第一个接上数 编写程序找到最后剩下未出队的人是哪一个
 */
public class 约瑟夫环问题 {

    public static void main(String[] args) {        
        
        //设置一个布尔类型数组 数组长度表示队伍总人数且值全设为false表示开始全部未出队
        // 布尔类型标识是否出队 出队true 未出队true
        boolean a[] = new boolean[5];
        for (int i = 0; i < a.length; i++) {
            a[i] = false;
        }
        
        //先把lNum设置为数组长度表示未出队的总人数 它用来判断数量是否被减少到1表示剩下最后一位未出队的人从而停止while循环执行赋true操作
        int lNum = a.length;
        //用来数123 当数到3 while循环设置当前数组编号的值为true表示出队了
        int cNum = 0;
        //设置数数人的编号 用来设置当数到头（数组长度）时 就设置成0又从第一个数组编号值开始设置true 
        //判断每一个数组下标表示的值是否出队 如果未出队再进行数123 出队就不数 这样就摘去出队的数组下标 只挑未出队的人数123操作
        int index = 0;
        
        while (lNum > 1) {// 等未出队人数为1时停止为其赋false 就是最后一个未出队的人
            
            //当当前数组编号的值为未出队状态时 cNum加1
            if (a[index] == false) {//用来判断当前数组值是否为false未出队状态 当值是未出队时候再进行cNum数123操作
                //未出队时cNum加1
                cNum++;
                //当加到3时 
                if (cNum == 3) {
                    //cNum设置为0表示要从新数
                    cNum = 0;
                    //当前数组值设为true表示出队了
                    a[index] = true;
                    //当出队时lNum减1 表示这个数到3的人出队了所以未出队总人数减1
                    lNum--;
                }
            }
            
            
            //数数人编号加1
            index++;
            //等到index编号
            if (index == a.length) {
                //要求要开头接着结尾数123的操作
                index = 0;
            }
        }
        
        // while循环这几遍操作下来全部设置为ture了
        // 开始遍历
        // 当遍历到false时就输出 表示是最后一个未出队的人 操
        for (int i = 0; i < a.length; i++) {
            //如果遍历到数组值为false 
            if (a[i] == false)
                //就输出了 
                System.out.println("最后剩下的人是第" + (i + 1) + "人");
        }
    }
}