如何python解約瑟夫環問題

這篇文章將為大家詳細講解有關如何python解約瑟夫環問題，文章內容質量較高，因此小編分享給大家做個參考，希望大家閱讀完這篇文章后對相關知識有一定的了解。

        約瑟夫環問題：已知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:"結果，測試結果如下：

結果表明，第一種循環鏈表的方式比第二種取模運算的方式要快，由于比例不是線性的，不能說是幾倍，而且這個測試和python內部實現有關，換作C語言O3優化后結果就不一定一樣了，所以測試結果不能說明什么哈~

關于如何python解約瑟夫環問題就分享到這里了，希望以上內容可以對大家有一定的幫助，可以學到更多知識。如果覺得文章不錯，可以把它分享出去讓更多的人看到。