图解约瑟夫环递推公式

约瑟夫问题是个著名的问题，有很多种表述，这里选取一种简单的表述：n个人围成一圈做游戏，每个人都有一个标号从0～n-1，第1个人从0开始报数，报m-1的人（即第m个人）将离开圈子，下一个人接着从0开始报数。如此反复，直到剩下一个人，问最后剩下的那个人标号是几？

例如三个人a, b, c,m=2,则：
第一轮：a、b、c，移除b
第二轮：c、a，移除a
第三轮：c，剩下c

队列的结构

本文主要讲的是递推公式的推导过程，其他解法就不再涉及。

根据游戏规则，每一轮会删除一个元素，经过多轮迭代之后才能知道最终元素是谁，所以对于第1轮，我们不能直接知道最终元素的标号，即图中红色问号位置的index值。

约瑟夫环的递推公式

轮间关系

由于相邻两轮之间存在一定的关系，我们假设：

1. 有一个函数f(n, m)，可以给出游戏开始后的每一轮中最终元素在本轮数列中的位置，不同轮只要传入不同的数列长度即可，目前我们暂时还不知道它的内部实现。

   注意，这里f(n, m)返回的是最终元素在当前轮数列中的位置，这个位置和我们开头所讲的给每个人的标号没有关系。每一轮的起始元素是不一样的，第1轮是从0号元素开始，第2轮则是从M号元素开始，每一轮都是不同的数列。

2. 假设我们还知道下一轮中最终元素在本轮数列中的位置为x，即f(n - 1, m) = x

3. 对于最后一轮，很容易得到f(1, m) = 0，因为最后只有一个元素了，这个元素就是最终元素，且index = 0

约瑟夫环的递推公式2.jpg

对于f(n, m)，就是我们图上要求的在第1轮中最终元素所处的index，根据第2轮的假设，最终元素在第2轮数列中的index是x，即从M元素开始，向后数x次，即可到达最终元素。由于第2轮只是比第1轮少了元素M-1，所以我们在第1轮的数列中的M元素向后数x次就能找到最终元素。假设x比较小，那么在第1轮中最终元素的index = m + x，如果 m + x > n，则index = L1 - 1，L1 - 1 = (m - 1 + L2 + L1) - n = (m - 1 + L2 + L1)%n = (m - 1 + x + 1)%n = (m + x)%n，其实就是将前面的m + x对n取余，于是有f(n, m) = (m + x)%n = (m + f(n - 1, m))%n

递推公式

根据以上分析，可以得到递推关系：

f(n, m) = (m + f(n - 1, m))%n

f(n - 1, m) = (m + f(n - 2, m))%(n - 1)

......

f(2, m) = (m + f(1, m))%2

f(1, m) = 0

根据f(1, m)一步一步就能算出f(n, m)

def LastRemaining_Solution(n, m):
        if n == 0 or m == 0:
            return -1
        
        # 递推公式f(n, m) = (m + f(n - 1, m))%n
        x = 0
        for nn in range(2, n + 1):
            x = (m + x)%nn
        return x

最终我们求出了第1轮的数列中，最终元素所在的index，此时恰好index与元素的标号是相等的，于是我们可以得出标号为index的元素为最终元素