Pythonで実装された「猿が王を選ぶ」アルゴリズム

今日はジョセフ リング アルゴリズムを実装します。これは Sina からのインタビューの質問です。

m 匹のサルが円の中に座っており、時計回りに 1 から m まで番号が付けられています。次に、1 番の猿から時計回りに数え始め、n 番目の猿が出てきます。次に、出てきた猿の次の位置からもう一度数えます。これを 1 匹だけ残るまで繰り返します。王。次の機能を実装するプログラムを設計して作成します:

(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)

注: ここではリストではなく辞書が使用されています。 。主な理由は、辞書の索引を活用できるからです