2

剰余は剰余を与え、このコードはヨセファス問題の生存者を与えることを知っています。n mod k = 0 の場合、開始カウント ポイントがサークルの最初から始まり、n mod k = 1 の場合、サークルの開始直前の人がその実行ラウンドを生き延びたというパターンに気付きました。 .

この再帰がモジュラスを使用して最後の男を見つける方法と、 josephus(n-1,k) が実際に参照しているものを理解していません。最後に処刑された人を指しているのか、それともサークルの特定のラウンドの最後の生存者を指しているのか?

 def josephus( n, k):
  if n ==1:
    return 1
  else:
    return ((josephus(n-1,k)+k-1) % n)+1
4

2 に答える 2

5

この回答は、ヨセフス問題の要約であり、次の質問に対する回答でもあります。

  1. 何をjosephus(n-1,k)指していますか？
  2. モジュラス演算子は何に使用されていますか?

これを呼び出すjosephus(n-1,k)と、k 番目の人ごとに合計 n-1 回実行したことになります。(ジョージ・トムリンソンのコメントに合わせて変更)

The recursion keeps going until there is 1 person standing, and when the function returns itself to the top, it will return the position that you will have to be in to survive. The modulus operator is being used to help stay within the circle (just as GuyGreer explained in the comments). Here is a picture to help explain:

 1 2
6   3
 5 4

Let the n = 6 and k = 2 (execute every 2nd person in the circle). First run through the function once and you have executed the 2nd person, the circle becomes:

 1 X
6   3
 5 4

Continue through the recursion until the last person remains will result in the following sequence:

 1 2      1 X      1 X      1 X      1 X      X X
6   3 -> 6   3 -> 6   3 -> X   3 -> X   X -> X   X
 5 4      5 4      5 X      5 X      5 X      5 X

When we check the values returned from josephus at n we get the following values:

n = 1 return 1
n = 2 return (1 + 2 - 1) % 2 + 1 = 1
n = 3 return (1 + 2 - 1) % 3 + 1 = 3
n = 4 return (3 + 2 - 1) % 4 + 1 = 1
n = 5 return (1 + 2 - 1) % 5 + 1 = 3
n = 6 return (3 + 2 - 1) % 6 + 1 = 5

Which shows that josephus(n-1,k) refers to the position of the last survivor. (1)

モジュラス演算子を削除すると、11 番目の位置が返されることがわかりますが、ここには 6 つしかないため、モジュラス演算子はカウントを円の境界内に保つのに役立ちます。(2)

于 2014-02-12T20:11:26.030 に答える
2

最初の質問は上記のコメントで回答済みです。

2 番目の質問に答えるには、最後の生存者の位置を指しています。

j(4,2) を考えてみましょう。

アルゴリズムを使用すると、

j(4,2)=(j(3,2)+1)%4)+1  
j(3,2)=(j(2,2)+1)%3)+1  
j(2,2)=(j(1,2)+1)%2)+1  
j(1,2)=1

など 

j(2,2)=((1+1)%2)+1=1  
j(3,2)=((1+1)%3)+1=3  
j(4,2)=((3+1)%4)+1=1

j(2,2) のテーブルは

1 2  
1 x

したがって、j(2,2) は確かに 1 です。

j(3,2) に対して、

1 2 3  
1 x 3  
x x 3

したがって、必要に応じて j(3,2) は 3 です。

最後に、j(4,2) は

1 2 3 4  
1 x 3 4  
1 x 3 x  
1 x x x

これは、必要に応じて j(4,2)=1 であることを示しています。

于 2014-02-12T20:38:19.307 に答える