Keengle's Blog

约瑟夫问题非常古老，最佳的解法早有人提出来了，之前看过还不太理解，最近又细细的想了想，感觉思路又清晰了许多，因此作个笔记。
【约瑟夫问题】N个人(编号为0,1,2,...(N-1))围成一圈，从第一个开始报数，第M个将被杀掉，最后剩下一个，其余人都将被杀掉。例如N=6，M=5，被杀掉的人的序号为5，4，6，2，3。最后剩下1号。

一开始我们可能会去模拟整个过程，我们会用一个列表来保存现有的数，当然我们不会愚蠢到用个记数器从1累加至M再把那个数去掉，我们会直接把每N%M个数直接去掉：(以下代码用python描述)

def force(n,m):
    l = range(1,n+1)
    while len(l)>1:
        ix = (m-1) % len(l)
        p = l[ ix ]
        newl = []
        dif = 1
        while len(newl) != len(l)-1:
            newl.append( l[ (ix + dif)%len(l) ] )
            dif += 1
        l = newl
    return l[0]

学了递归之后，我们隐约的感觉到，剔除了第一个人后的子问题似乎跟原问题极度的相似，刚开始的问题的问题解记为f(n,m)，剔除了第一个人后的子问题的解为f(n-1,m),我们只要把f(n,m)跟f(n-1,m)的递推关系找出来，就能很轻松的写出一个递归程序了。我们不妨假设m<n-1，刚开始的数列表是这样的：
0,1,2,...,(m-1),m,...,(n-1)
每一轮之后，数就变成了:
m,(m+1),(m+2),...(n-1),0,1...
这个子问题的解为f(n-1,m),不愿为原来的编号就是( f(n-1,m)+m )%n了，也就是：
f(n,m) = (f(n-1,m)+m)%n
因此我们得到了一个递归的解法：

def jesf_rec(n,m):
    if (n==1):
        return 0
    else:
        return (jesf_rec(n-1,m)+m)%n

递归的解法很容易看懂，但如果n很大至10^8,那程序很容易会超出最大的递归层数，而程序无法完成，下面就把这种尾递归转为非递归的程序：

def jesf(n,m):
    result = 0
    for i in range(1,n+1):
        result = ( result + m ) % i
    return result

这样一层层的慢慢想下来，就很容易理解了，但如果一开始就给了第3种解法，就没那么容易理解了。需要好好琢磨一下才行的。傻瓜可能会继续想，有没有更快的方法呢?通过f(n,m) = (f(n-1,m)+m)%n有没有办法把f(n,m)解出来呢，但由于递推式里对递推变量n做了求模运算，找不到突破口...