超牛的Python,简单10行代码解决约瑟夫环

时间：2014-11-05 编辑：简简单单来源：一聚教程网

约瑟夫环（约瑟夫问题）是一个数学的应用问题：已知n个人（以编号1，2，3...n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。通常解决这类问题时我们把编号从0~n-1，最后结果+1即为原问题的解。

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

代码如下

复制代码

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

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

上一个： php Fatal error: Call to undefined function imagecreatefromjpeg()
下一个：当下最主流开源PHP框架的综合性能盘点比较

推荐专题

最新下载

热门教程

超牛的Python,简单10行代码解决约瑟夫环

相关文章

热门栏目

php教程

asp.net教程

手机开发

css教程

网页制作

办公数码

jsp教程