约瑟夫环问题

奇安信2020秋招笔试题

/**
 * 约瑟夫环问题：
 * N个人排成一队，从1到5轮流报数，报5的是幸运者，出列
 * 报到队尾后，从队尾接着报，依此循环
 * 问：排在队尾的人是第几名幸运者？
 * N为小于100000的正整数
 * 例如：1人排成一队，他就是第一名幸运者
 * 3人排成一队，队尾是第二名幸运者
 * 5人排成一队，队尾是第一名幸运者
 * 8人排成一队，队尾是第三名幸运者
 *
 * 输入：队伍的总人数————20
 * 输出：队尾者的幸运编号——————4
 *
 */

package package3;

import java.util.Scanner;

/**
 * Created by fan on 2019/9/9.
 */
public class JosephRing {
        public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            System.out.println("请输入人的个数n:");
            int n = sc.nextInt();
            fun(n);
            sc.close();
        }

        private static void fun(int n) {
            boolean[] ps = new boolean[n];
            int num = 0;
            //开始都有人，初始化为true
            for (int i = 0; i < ps.length; i++) {
                ps[i] = true;
            }
            //数到5剔除
            for(int i = 0,j = 0;;i++){
                if(ps[i]){
                    j++;
                    if(j == 5){
                        if(i == (ps.length-1)){
                            num++;
                            break;
                        }
                        ps[i] = false;
                        j=0;
                        num++;
                    }
                }
                //从开始继续循环
                if(i == ps.length -1){
                    i = -1;
                }
            }
            System.out.println("排在队尾的是第" + num +"名幸运者");
        }
}