约瑟夫环问题

编程题

题目

最近看到一道题目，也就是约瑟夫环的变体，题目如下：一只猫抓住了n只老鼠，其将老鼠排成一圈，依次按照1~m报数，报m值的吃掉，直到只剩下一只老鼠时，猫将其放生，求获生的老鼠编号。

解答1

按照题目意思，直接采用列表记录所有老鼠编号，然后依次模拟筛选过程，则可得到逃生的老鼠编号，代码如下：

def GetLastOut(n, m):
    """
    编号n只老鼠从1~m报数，为m的出列，最后留下的编号
    """
    rats = list(range(1,n+1))
    curr_index = 0
    for i in range(n-1):
        curr_index += m - 1
        curr_index = curr_index % len(rats)
        remove_value = rats[curr_index]
        del rats[curr_index]
        #print('remove index:{}, value:{}, left:{}'.format(curr_index, remove_value, rats[curr_index:]+rats[:curr_index]))
    return rats[0]

解答2

在上面解答的基础上再进一步思考一下，对于每个n吃掉一只老鼠后不就是n-1么，因此可得其递归算法：

def RescueGetLastOut(n, m):
    """
    递归方法，考虑去掉第一个编号之后，其排列顺序相当于[m+1 ... n 1 ... m-1]，与[1 ... n-1]相对应，可以直接进行变换
    """
    if n == 2:
        return 2 if m % 2 else 1
    else:
        v = RescueGetLastOut(n-1, m)
        #print('RescueGetLastOut({}, {}): {}'.format( n - 1, m, v))
        #v-1先转变为0~n-1便于%n，后续再+1变回1~n编号
        return (v - 1 + m) % n + 1

根据递归算法的思想，很容易可以写出其对应的迭代版本， 如下：

def GetLastOut(n, m):
    """
    根据递归方法而来的迭代方法，考虑去掉第一个编号之后，其排列顺序相当于[m+1 ... n 1 ... m-1]，与[1 ... n-1]相对应，可以直接进行变换
    """
    if n < 2:
        return 1
    live_rat = 1 if m % 2 else 0
    for i in range(3, n+1):
        live_rat = (live_rat + m) % i
    #前面是按照0~i-1编号，返回时改为1~n
    return live_rat + 1

思考

对于这种问题，往往会思考一下其是否有特定的公式直接进行计算，针对其m值没有特定的公式，但是当m值为2的时候，是有公式可以计算的，如下：

def GetLastOutFor2(n):
    """
    针对2进行的特殊判断
    """
    import math
    log_v = int(math.log(n, 2))
    return 2*(n - 2**log_v) + 1

这是因为针对任何 2**k 的数，其必定会为 1，而其后面每添加一位将导致整体向右移动两位（偶数位第一次被去掉），如下：