首页 > 代码库 > 10行Python代码解决约瑟夫环(模拟)

10行Python代码解决约瑟夫环(模拟)

写这篇文章是因为看到别人博客里用了很长一个篇幅(超过50行)去解决一个约瑟夫环问题,而且还是用以简洁著称的python,另外,如果你用X度搜索python 约瑟夫,看到得前几条都是错的,真是好悲剧。

总的来说,就是误人子弟。

虽然,用模拟去解决这个约瑟夫环问题效率是很低的,但是,这更容易理解。

先上代码。

def josephus(n,k):
    link=range(1,n+1) 
    ind=0
    for loop_i in range(n-1):
        ind = (ind+k)% len(link) 
        ind-=1
        print 'Kill:',link[ind]
        del link[ind]
        if ind==-1: # the last element of link
            ind=0
    print 'survice :',link[0]
   

if __name__ == '__main__':

    josephus(100000,300)
    print '-'*30
    josephus(10,5)
    print '-'*30
    josephus(10,1)


可以看到,整个函数也就是只有十行。

思路非常简单,按模来找到要删除得位置,但是,主要到下标从0开始和数字从1开始是有一些不一样得,另外,py的del后,下标会增1,所以要减回去。

正确看是

del link[ind-1]

ind-=1

但是,因为两者都需要后退1,所以直接ind-=1就OK了。

另外要主要得是,来到环尾部,即py的-1(这点就是最好的地方,py得tuple 和list 支持负下标),删除后,开始就要变成0

如果你认为我写错了,一定要评论给我指出,不想误人子弟。

10行Python代码解决约瑟夫环(模拟)