首頁  >  文章  >  後端開發  >  「猴子選大王」 演算法 python實現

「猴子選大王」 演算法 python實現

高洛峰
高洛峰原創
2016-10-18 10:33:154587瀏覽

今天來實現一個約瑟夫環演算法,以下是一道新浪的面試題:

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。主要是因為這樣可以利用字典的索引的優勢

陳述:
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn