约瑟夫环的数学推导（9步简洁易懂的推导）

证明过程尽量写的简洁、易懂，参考自文章：这或许是你能找到的最详细约瑟夫环数学推导！

约瑟夫环问题是一个数学问题。我们定义一个函数f(n, k)表示：在n个人围成的环中，从1开始数，数到k的人被杀掉，然后接着从1开始数，直到只剩下一个人，幸存者的编号就是f(n, k)。

1、 假设我们把n个人从0开始编号，分别为0, 1, 2, …, n-2, n-1；

2、 那么很明显，我们的函数有一个最基本的值，就是f(1, k) = 0；

3、 第一个被淘汰的数字肯定是编号为(k-1)%n的数，那么剩余的序列为0, 1, 2, 3, …, k-3, k-2, k, k+1

4、 换句话说，要从编号为k的人重新开始数，即转化为n-1个人的约瑟夫环问题（过程是递归的，所以肯定有递归式），只不过序列从0, 1, 2, …, n-1变成了新序列k, k+1, k+2, …, n-1, 0, 1, 2, …, k-2。

5、 因为这个序列不同于从0开始编号，所以f(n, k)已经不适用于新序列，故建立新函数L(n – 1, k)表示从k开始编号的n-1个人的约瑟夫环的解。由于新序列其实是原先序列的子问题，所以L(n – 1, k)的解与f(n, k)的解是同一个序号，即L(n – 1, k) = f(n, k)。

6、 可是两个函数不同，无法建立递归式，所以我们需要建立一个在两个序列之间转化的映射，以求把L(n – 1, k)转化f(n – 1, k)的类型：

k -> 0 k + 1 -> 1 … n - 1 -> n – k - 1 0 -> n - k 1 -> n – k + 1 … k - 2 -> n - 2

7、 观察上面的映射可以发现，我们可以用一个函数g(x) = ( x + n – k ) % n来表示从左到右的映射。反过来，如果需要从右边到左边的映射，那么可以用h(x) = ( x + k) % n。

8、 那么在映射之后进行操作的约瑟夫环就有：

f(n – 1, k) = g( L(n – 1, k) ) 所以： L(n – 1, k) = g-1( f(n - 1, k) ) = h( f(n - 1, k) ) = [ f(n – 1, k) + k ] % n

9、 很好，又因为5中我们已经解释过L(n – 1, k) = f(n, k)，那么递归公式就已经得到了：

f(n, k) = [ f(n – 1, k) + k ] % n f(1, k) = 0

可以，递归式有了，那么这道题就已经解决了，代码用循环就可以简单的写出来了：