In Python implementierter Algorithmus „Der Affe wählt den König'.

Heute werden wir einen Joseph-Ring-Algorithmus implementieren. Das Folgende ist eine Interviewfrage von Sina:

m Affen sitzen im Kreis, nummeriert von 1 bis m im Uhrzeigersinn. Beginnen Sie dann mit dem Zählen von Affe Nr. 1 im Uhrzeigersinn ab 1. Der Affe, der n meldet, ist draußen, und beginnen Sie dann mit dem Zählen von der nächsten Position des Affen, der gerade ausgestiegen ist. Wiederholen Sie dies, bis nur noch ein Affe übrig ist ist der König. Entwerfen und schreiben Sie ein Programm zur Implementierung der folgenden Funktionen:

(1) Der Benutzer muss die Anzahl der Affen m am Anfang und die letzte gemeldete Anzahl n eingeben.

(2) Geben Sie die Anfangsnummer des gewählten Affenkönigs an.

Diese Frage ist ein typisches Joseph-Ring-Problem, das „Affe wählt den König“-Problem.

Hinweis: Dieses Beispiel hat den Test unter Python2.7 bestanden, wurde jedoch nicht unter Python3 getestet.

Gehen Sie direkt zum 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)

Hinweis: Hier wird ein Wörterbuch verwendet, keine Liste. Hauptsächlich, weil dadurch der Index des Wörterbuchs