算法-约瑟夫环

找出游戏的获胜者

原理

倒推法

1. 还剩1个人，此人获胜，下标为

$$f(1,k)=0$$

2. 还剩2个人，淘汰第k个人，即淘汰下标(k-1)%2，下次从k%2开始，则获胜者下标为

$$f(2,k)=(f(1,k)+k)\mod 2=(0+k)\mod 2$$

3. 还剩3个人，淘汰第k个人，即淘汰下标(k-1)%3，下次从k%3开始，则获胜者下标为

$$f(3,k)=(f(2,k)+k)\mod 3=((0+k)\mod 2+k)\mod 3$$

4. …

5. n个人，淘汰第k个人，即淘汰下标(k-1)%n，下次从k%n开始，则获胜者下标为

$$f(n,k)=(f(n-1,k)+k)\bmod{n}=(\cdots((0+k)\bmod{2}+k)\bmod{3}\cdots)\bmod{n}$$

1
2
3
4
5
6
7

int findTheWinner(int n, int k) {
    int ans = 0;
    for (int i = 2; i <= n; i++) {
        ans = (ans + k) % i;
    }
    return ans + 1;
}