约瑟夫问题详解

约瑟夫环问题一般形式

约瑟夫问题是个有名的问题：N个人围成一圈，从第一个开始报数，第M个将被杀掉，最后剩下一个，其余人都将被杀掉。例如N=6，M=5，被杀掉的顺序是：5，4，6，2，3，1。

问题分析

首先将人围成一圈，此时小鱼头脑风暴

1、使用数组类型模拟N个人围成一圈,
2、创建N个人的数组
3、将前X(M减去数组长度对M取余数得出)个人连接到最后构成一个长度为M倍数的数组，形成虚拟的收尾相接圆圈结构

4、位置在M或M倍数位置的人会被杀死
5、一轮之后将前X个人移动到数组最后，然后重新构建首位相连的虚拟数组开始下一轮杀人

import time

N,M=100000,3
arry = list(range(1, N+1))  # 构建数组
def ysf(arry,M): #构建递归函数
    # print('剩余%s人' % len(arry))
    if len(arry)<=M:    #数组长度小于M时一轮只能杀一个人
        if len(arry)==1:    #结束条件
            print('最终活下来的为第%s个人'%arry[0])
            return arry[0]
        elif M%len(arry)==0:   #此时杀死最后一人
            arry=arry[:-1]
            return ysf(arry,M)
        else:  #非整数倍时剔除取余位数
            arry=arry[(M%len(arry)):]+arry[:(M%len(arry)-1):]
            return ysf(arry,M)
    else:
        X=M-len(arry)%M
        arry_p = arry + arry[:X ]  # 构建虚拟收尾相接圆圈数组
        arry1=[arry_p[i] for i in range(len(arry_p)) if (i+1)%M!=0]
        arry=arry1[X:]
        return ysf(arry,M)


start=time.clock()
ysf(arry,M)
end=time.clock()
print(end-start)  #测试一下运行效率，效率很高~~

这种方法的效率较高，每次能筛选大概1/M的数据，对于百万千万级数据也会是秒秒钟的时间哦~~

此外对于小数量级的，低效的代码就不贴了；简单思路，也是讲前M-1个数据连接到最后，然后删除前 M个数据就行，一步杀一人，千里怕不行~~哈哈！