约瑟夫环问题python解法

现在的位置: 首页 > 编程语言 > 正文

约瑟夫环问题python解法

2019年04月01日 ⁄ 编程语言 ⁄ 共 1568字 ⁄ 字号小中大 ⁄ 评论关闭

约瑟夫环问题：已知n个人（以编号1，2，3...n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到k的那个人被杀掉；他的下一个人又从1开始报数，数到k的那个人又被杀掉；依此规律重复下去，直到圆桌周围的人只剩最后一个。

思路是：当k是1的时候，存活的是最后一个人，当k>=2的时候，构造一个n个元素的循环链表，然后依次杀掉第k个人，留下的最后一个是可以存活的人。代码如下：

class Node():
	def __init__(self,value,next=None):
		self.value=value
		self.next=next

def createLink(n):
	if n<=0:
		return False
	if n==1:
		return Node(1)
	else:
		root=Node(1)
		tmp=root
		for i in range(2,n+1):
			tmp.next=Node(i)
			tmp=tmp.next
		tmp.next=root
		return root

def showLink(root):
	tmp=root
	while True:
		print(tmp.value)
		tmp=tmp.next
		if tmp==None or tmp==root:
			break

def josephus(n,k):
	if k==1:
		print('survive:',n)
		return
	root=createLink(n)
	tmp=root
	while True:
		for i in range(k-2):
			tmp=tmp.next
		print('kill:',tmp.next.value)
		tmp.next=tmp.next.next
		tmp=tmp.next
		if tmp.next==tmp:
			break
	print('survive:',tmp.value)

if __name__=='__main__':
	josephus(10,4)
	print('-----------------')
	josephus(10,2)
	print('-----------------')
	josephus(10,1)
	print('-----------------')

输出结果如下：

-------------------------------------分界线-----------------------------------------

感谢大家建议，第一种方法是直观暴力裸搞，确实不太简洁，下面写出我的第二种方法，求模来搞起，代码少了一些，如下：

def josephus(n,k):
	if k==1:
		print('survive:',n)
		return
	p=0
	people=list(range(1,n+1))
	while True:
		if len(people)==1:
			break
		p=(p+(k-1))%len(people)
		print('kill:',people[p])
		del people[p]
	print('survive:',people[0])

if __name__=='__main__':
	josephus(10,4)
	josephus(10,2)
	josephus(10,1)

运行结果和上面一样。为了进一步对比性能，我用josephus(100000,4)测试，即n=100000，k=4。为了去掉IO消耗的时间干扰，把"kill:"的print注释掉，只输出最后的"survive:"结果，测试结果如下：