“猴子选大王” 算法 python实现

高洛峰
Libérer: 2016-10-18 10:33:15
original
4582 Les gens l'ont consulté

今天来实现一个约瑟夫环算法,下面是一道新浪的面试题:

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)
Copier après la connexion

注意:这里用到了字典,而不是list。主要是因为这样可以利用字典的索引的优势

Étiquettes associées:
source:php.cn
Déclaration de ce site Web
Le contenu de cet article est volontairement contribué par les internautes et les droits d'auteur appartiennent à l'auteur original. Ce site n'assume aucune responsabilité légale correspondante. Si vous trouvez un contenu suspecté de plagiat ou de contrefaçon, veuillez contacter admin@php.cn
Tutoriels populaires
Plus>
Derniers téléchargements
Plus>
effets Web
Code source du site Web
Matériel du site Web
Modèle frontal
À propos de nous Clause de non-responsabilité Sitemap
Site Web PHP chinois:Formation PHP en ligne sur le bien-être public,Aidez les apprenants PHP à grandir rapidement!