今日はジョセフ リング アルゴリズムを実装します。これは 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)
注: ここではリストではなく辞書が使用されています。 。主な理由は、辞書の索引を活用できるからです