0%

孩子们的游戏（圆圈中最后剩下的数）

发表于 更新于

让小朋友们围成一个大圈。然后,随机指定一个数m,让编号为0的小朋友开始报数。每次喊到m-1的那个小朋友要出列,从他的下一个小朋友开始,继续0…m-1报数…这样下去…直到剩下最后一个小朋友。哪个小朋友会得到这份礼品呢？(注：小朋友的编号是从0到n-1)

如果没有小朋友，请返回-1

记初始编号为n0n_0，共NN个小朋友，第一个出列小朋友的初始编号为n0=(m−1)%Nn_0=(m-1)\%N，从其下一个初始编号为n0=m%Nn_0=m\%N的小朋友开始重新编号为新编号n1=0n_1=0，则再下一个出列小朋友为新编号n1=(m−1)%(N−1)n_1=(m-1)\%(N-1)。

对于任意小朋友，新旧编号的关系为

n1≡f0(n0)≡[n0−(m%N)]%(N−1)n_1 \equiv f_{0}(n_0) \equiv [n_0-(m\%N)]\%(N-1)

推广之

ni≡fi−1(ni−1)≡{ni−1−[m%(N−i+1)]}%(N−i)n_i \equiv f_{i-1}(n_{i-1}) \equiv \{n_{i-1}-[m\%(N-i+1)]\}\%(N-i)

反之

ni−1≡fi−1−1(ni)≡{ni+[m%(N−i+1)]}%(N−i+1)≡(ni+m)%(N−i+1)n_{i-1} \equiv f_{i-1}^{-1}(n_{i}) \equiv \{ n_i + [m\%(N-i+1)] \} \% (N - i + 1) \\ \equiv ( n_i + m ) \% (N - i + 1)

显然，最后一个小朋友即为

nN−1=0n_{N-1} = 0

即对该小朋友

0=nN−1={nN−2−[m%2]}%(N−i)=fN−1(n0)0 = n_{N-1} = \{n_{N-2}-[m\%2]\}\%(N-i)=f_{N-1}(n_0)

而最后一个小朋友初始时的编号

n0=f0−1(n1)=f0−1[f1−1(n2)]=f0−1⋯fN−2−1(nN−1)n_0 = f_0^{-1}(n_1) = f_0^{-1}[f_1^{-1}(n_2)] = f_0^{-1} \cdots f_{N-2}^{-1} (n_{N-1})

代入即

n0=f0−1⋯fN−2−1(0)n_0 = f_0^{-1} \cdots f_{N-2}^{-1}(0) 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int LastRemaining_Solution(int n, int m)
    {
        if (n < 1 || m < 1)
        {
            return -1;
        }
        else
        {
            int r = 0;
            for (int i = 2; i <= n; i++)
            {
                r = (r + m) % i;
            }
            return r;
        }
    }
};