n人围成一圈报数

crazyjums

算法题

发布于：Nov 13, 2020

次浏览

有n个人围成一圈，顺序排号。从第一个人开始报数（从1到3报数），凡报到3的人退出圈子，问最后留下的是原来的第几号的那位？

1 解题思路

可以用一个数组，数组大小为$n$，需要执行$n-1$次遍历，每次遍历踢掉一个人，使用一个变量$p$来记录当前报的数，一个变量来保存当前还剩多少人，如果最后只剩下一个人，那么退出循环，否则继续。

public static int nPeople(int n) {
    int count =  n;
    int p = 0;
    boolean[] a = new boolean[n];
    while (count > 1) {
        for (int i = 0; i < n; i++) {
            if (!a[i]) p++;
            if (p == 3) {
                a[i] = true;
                count --;
                p = 0;
            }
        }
    }
    int res = 0;
    for (int i = 0; i < n; i++) {
        if (!a[i])
            res = i +  1;
    }
    return res;
}

2 题目进阶

假如题目没有说从$1$报到$3$，而是从$1$报到$m$，则最后留下的那个人的编号是多少？

在之前的基础上，进行改进即可，即对第$8$行代码进行，判断每次报数的最大值即可。

public static int nPeople(int n, int m) {
    int count =  n;
    int p = 0;
    boolean[] a = new boolean[n];
    while (count > 1) {
        for (int i = 0; i < n; i++) {
            if (!a[i]) p++;
            if (p == m) {
                a[i] = true;
                count --;
                p = 0;
            }
        }
    }
    int res = 0;
    for (int i = 0; i < n; i++) {
        if (!a[i])
            res = i +  1;
    }
    return res;
}