今天來實現一個約瑟夫環演算法,以下是一道新浪的面試題:
m隻猴子圍坐成一個圈,按順時針方向從1到m編號。然後從1號猴子開始沿著順時針方向從1開始報數,報到n的猴子出局,再從剛出局猴子的下一個位置重新開始報數,如此重複,直至剩下一個猴子,它就是大王。設計並編寫程序,實現以下功能:
(1)要求由使用者輸入開始時的猴子數m、報數的最後一個數n。
(2)給出當選猴王的初始編號。
這題是典型的約瑟夫環問題,「猴子選大王」問題。
注意:本實例在python2.7下測試通過,未在python3下測試,有興趣的同學可以到群裡交流
直接上代碼:
#!/usr/bin/python # coding=utf-8 # 约瑟夫环算法 之 猴子选王 问题 def king(m,n): dd = {} #生成一个字典 p = 1 while(p<=m): dd[p] = p p = p+1 j = 1 while(len(dd) >1): for k,v in dd.items(): if(j == n): del dd[k] j = 1 else: j = j+1 return dd print king(6,2)
注意:這裡用到了字典,而不是list。主要是因為這樣可以利用字典的索引的優勢