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

'Monkey chooses the king' algorithm implemented in python

Oct 18, 2016 am 10:33 AM

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

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

Hot Article

R.E.P.O. Energy Crystals Explained and What They Do (Yellow Crystal)
2 weeks ago By 尊渡假赌尊渡假赌尊渡假赌
Repo: How To Revive Teammates
4 weeks ago By 尊渡假赌尊渡假赌尊渡假赌
Hello Kitty Island Adventure: How To Get Giant Seeds
3 weeks ago By 尊渡假赌尊渡假赌尊渡假赌

Hot Article

R.E.P.O. Energy Crystals Explained and What They Do (Yellow Crystal)
2 weeks ago By 尊渡假赌尊渡假赌尊渡假赌
Repo: How To Revive Teammates
4 weeks ago By 尊渡假赌尊渡假赌尊渡假赌
Hello Kitty Island Adventure: How To Get Giant Seeds
3 weeks ago By 尊渡假赌尊渡假赌尊渡假赌

Hot Article Tags

Notepad++7.3.1

Notepad++7.3.1

Easy-to-use and free code editor

SublimeText3 Chinese version

SublimeText3 Chinese version

Chinese version, very easy to use

Zend Studio 13.0.1

Zend Studio 13.0.1

Powerful PHP integrated development environment

Dreamweaver CS6

Dreamweaver CS6

Visual web development tools

SublimeText3 Mac version

SublimeText3 Mac version

God-level code editing software (SublimeText3)

How to Use Python to Find the Zipf Distribution of a Text File How to Use Python to Find the Zipf Distribution of a Text File Mar 05, 2025 am 09:58 AM

How to Use Python to Find the Zipf Distribution of a Text File

How to Download Files in Python How to Download Files in Python Mar 01, 2025 am 10:03 AM

How to Download Files in Python

How Do I Use Beautiful Soup to Parse HTML? How Do I Use Beautiful Soup to Parse HTML? Mar 10, 2025 pm 06:54 PM

How Do I Use Beautiful Soup to Parse HTML?

Image Filtering in Python Image Filtering in Python Mar 03, 2025 am 09:44 AM

Image Filtering in Python

How to Work With PDF Documents Using Python How to Work With PDF Documents Using Python Mar 02, 2025 am 09:54 AM

How to Work With PDF Documents Using Python

How to Cache Using Redis in Django Applications How to Cache Using Redis in Django Applications Mar 02, 2025 am 10:10 AM

How to Cache Using Redis in Django Applications

Introducing the Natural Language Toolkit (NLTK) Introducing the Natural Language Toolkit (NLTK) Mar 01, 2025 am 10:05 AM

Introducing the Natural Language Toolkit (NLTK)

How to Perform Deep Learning with TensorFlow or PyTorch? How to Perform Deep Learning with TensorFlow or PyTorch? Mar 10, 2025 pm 06:52 PM

How to Perform Deep Learning with TensorFlow or PyTorch?

See all articles