9

Pythonのリストを使用してJosepheusの問題を解決できるかどうかを知りたいと思いました。

簡単に言えば、ヨセフスの問題は、事前にわかっているスキップパラメータを使用して実行が処理された場合に安全な円形配置の位置を見つけることです。

たとえば、次のような円形の配置と3のスキップパラメータが与えられた場合、人々は安全な位置と位置[1,2,3,4,5,6,7]で実行されます。3,6,2,7,5,14

私はしばらくの間リストを使用してこれを解決しようと試みてきましたが、インデックスの位置は私が扱うのが難しいようになります。

 a=[x for x in range(1,11)]
 skip=2
 step=2
 while (len(a)!=1):
   value=a[step-1]
   a.remove(value)
   n=len(a)
   step=step+skip
   large=max(a)
   if step>=n:        
      diff=abs(large-value)
      step=diff%skip
   print a

コードスニペットで質問を更新しましたが、私のロジックが正しくないと思います。

4

8 に答える 8

18

簡単に言うと、 を使用list.pop(i)して、各被害者をループで削除 (および被害者の ID を取得) することができます。次に、インデックスのラップについて心配する必要があります。これは、スキップされたインデックス mod を残りの囚人の数にするだけで実行できます。

すると、問題の解決策は次のようになります

def josephus(ls, skip):
    skip -= 1 # pop automatically skips the dead guy
    idx = skip
    while len(ls) > 1:
        print(ls.pop(idx)) # kill prisoner at idx
        idx = (idx + skip) % len(ls)
    print('survivor: ', ls[0])

テスト出力:

>>> josephus([1,2,3,4,5,6,7], 3)
3
6
2
7
5
1
survivor:  4
于 2012-09-16T07:10:12.937 に答える