Home > Backend Development > Python Tutorial > 'Monkey chooses the king' algorithm implemented in python

'Monkey chooses the king' algorithm implemented in python

高洛峰
Release: 2016-10-18 10:33:15
Original
4609 people have browsed it

Today we will implement a Joseph Ring algorithm. Here is an interview question from Sina:

m monkeys sit in a circle, numbered from 1 to m clockwise. Then start counting from monkey No. 1 in a clockwise direction from 1, and the n monkey is out. Then count again from the next position of the monkey who just got out. Repeat this until there is only one monkey left, which is the king. Design and write a program to implement the following functions:

(1) The user is required to input the monkey number m at the beginning and the last number n reported.

(2) Give the initial number of the elected Monkey King.


This question is a typical Joseph Ring problem, the "monkey chooses the king" problem.

Note: This example passed the test under python2.7, but was not tested under python3. Interested students can communicate in the group

Go directly to the code:

#!/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)
Copy after login

Note: A dictionary is used here, not a list. Mainly because this can take advantage of the index of the dictionary

source:php.cn
Statement of this Website
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn
Popular Tutorials
More>
Latest Downloads
More>
Web Effects
Website Source Code
Website Materials
Front End Template