约瑟夫环

问题描述

$NN$ 个人围成一圈报数，报到 $MM$ 的人被淘汰，接着他的下一个人又开始重新报数。如此反复，直至只剩下一个人，求最后的胜利者。

问题分析

记胜利者编号为 $f(N,M)f(N,M)$ ,则：

1.当 $N=1N\; =\; 1$ 时，圈子中只有一名小伙伴，该小伙伴即为获胜者，即： $f(1,M)=1f(1,\; M)\; =1$。

2.当 $N>1N\; >\; 1$ 时，我们可以通过观察 $f(N,M)f(N,M)$ 淘汰一人之后变化，从而寻找与 $f(N-1,M)f(N-1,M)$ 的联系。

如下图所示，淘汰掉 $MM$ 号之后，$M+1M+1$ 号小伙伴重新开始报数。

观察右图：

求得： $x=N-1-Mx=N-1-M$，由此我们不难发现 $f(N,M)f(N,M)$ 淘汰一人之后，与

相对应。

代码如下

int findTheWinner(int n, int m) {
    if(n == 1) return 1;
    return (findTheWinner(n - 1, m) + m - 1) % n + 1;
}