math - Josephus p‌r‌o‌b‌le‌mにおける回帰関係

Question

ジョセフスの問題は、次の再帰によって解決できます。

 josephus(n, k) = (josephus(n - 1, k) + k-1) % n + 1
 josephus(1, k) = 1

この再帰関係はどのように導き出されたのでしょうか?

Answer 1

josephus(n, k) = (josephus(n - 1, k) + k-1) % n + 1 ...... (1)

簡単に言えば、式の「+1」から始めます。これは、繰り返しの 1 回の繰り返しが既に行われていることを意味します。これで、n-1 人/要素が残ります。k 間隔で n-1 個の要素を再帰的に処理する必要があります。しかし、ここでは、最後に削除する要素が k 番目の位置にあったため、そこから続行します。したがって、k-1 が追加されます。さらに、この追加により、配列のインデックスが混乱する可能性があります。したがって、 %n は配列インデックスを境界内に保つために行われます。それが明快で十分に精巧であることを願っています:)。

Answer 2

この段落はウィキペディアから十分です..

インデックスが 1 から始まる場合、最初の人から s シフトした人は ((s-1)\bmod n)+1 の位置にいます。ここで、n は人の総数です。生存者の位置を f(n,k) とします。k 番目の人が殺された後、n-1 の円が残り、元の問題で番号が (k\bmod n)+1 だった人から次のカウントを開始します。残りの円での生存者の位置は、1 から数え始めると f(n-1,k) になります。(k\bmod n)+1 から開始するという事実を考慮してこれをシフトすると、繰り返しが得られます

f(n,k)=((f(n-1,k)+k-1) \bmod n)+1,\text{ with }f(1,k)=1\,,