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

高洛峰
リリース: 2016-10-18 10:33:15
オリジナル
4599 人が閲覧しました

今日はジョセフ リング アルゴリズムを実装します。これは 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)
ログイン後にコピー

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

ソース:php.cn
このウェブサイトの声明
この記事の内容はネチズンが自主的に寄稿したものであり、著作権は原著者に帰属します。このサイトは、それに相当する法的責任を負いません。盗作または侵害の疑いのあるコンテンツを見つけた場合は、admin@php.cn までご連絡ください。
人気のチュートリアル
詳細>
最新のダウンロード
詳細>
ウェブエフェクト
公式サイト
サイト素材
フロントエンドテンプレート