Hit9 Blog Wiki Project Links Archives Resumé
Page: First UP Pre Next Back

约瑟夫问题过程模拟

Fork me on GitHub

允许转载, 但转载请注明出处

Date:2012-10-26

约瑟夫问题很老很老的问题啦....

问题描述:

约瑟夫环是一个数学的应用问题:已知n个人(以编号123...n分别表示)围坐在一张圆桌周围。从编号为k的人开始报数,数到m的那个人出列;他的下一个人又从1开始报数,数到m的那个人又出列;依此规律重复下去,直到圆桌周围的人全部出列

或者这么说:

用户输入m,n值,从1N开始顺序循环数数,每数到M输出该数值,直至全部输出

下面是模拟的python代码,很好理解:

描述:

b=[1,1,...,1] (init b as a list of n times 1 elems)
a=0 # a is counter,always from 1 to m
cycle loop b until b has only one 1 elem:
    get index k and value v.
    if v is 1 (1 for alive,0 for died):
        counter a plus itself one
        if a==m:
            elem on index v died => b[k]=0
            reset counter a to 0
        print once b to look at state this time

代码:

#--coding:utf-8--

m, n = 7, 10

a = 0 # 记录正在报的数字

b = [1]*n

while sum(b) > 1:#最后剩下一个人
    try:
        k, v = i.next()
        if v:
            a = a+1
            if a == m:
                b[k] = 0
                a = 0
            print 'a:', a ,  b  #0 表示已经死掉, 1表示还每死掉
    except:
        i = enumerate(b)

Support:mkdwiki