Date:2012-10-26
约瑟夫问题很老很老的问题啦....
问题描述:
约瑟夫环是一个数学的应用问题:已知n个人(以编号1,2,3...n分别表示)围坐在一张圆桌周围。从编号为k的人开始报数,数到m的那个人出列;他的下一个人又从1开始报数,数到m的那个人又出列;依此规律重复下去,直到圆桌周围的人全部出列
或者这么说:
用户输入m,n值,从1至N开始顺序循环数数,每数到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)