20

編集: n は人数です。k は、排除される k 番目の人物です。したがって、k=2 の場合、2 人ごとに排除されます。

int josephus(int n, int k)
{
 if (n == 1)
  return 1;
else
   return (josephus(n - 1, k) + k-1) % n + 1;
}

コードは可能な限りシンプルです。しかし、どういうわけか私はこの問題を理解できません (正直言って少し恥ずかしいです)。

私がそれを理解しようとしている方法は、

  1. josephus(n,k) は、サイズ n およびステップ サイズ k の母集団の最終解を与えます。
  2. josephus(n,k) は、josephus(n-1,k) の解がわかれば計算できます。それは私の意見では、動的計画法の「最適な部分構造のプロパティ」です。
  3. 数値が n を超えた場合に、再び 1 からカウントを開始するように MOD N を実行する必要があることがわかりました (つまり、円でカウントしているように加算が動作するようにします)。しかし、なぜこの「k-1」を追加したのでしょうか?

主な問題は、josephus(n-1,k) の正しい解がわかっている場合、josephus(n,k) の解をどのように計算するかということです。効果的にもう 1 人を人口に追加し、どういうわけかこの k-1 値を追加すると、正しい解が得られます (mod はしばらく無視しましょう)。

問題の各ステップで最適な部分構造のプロパティがどのように保持されているかを誰かに説明してもらえますか?

4

2 に答える 2

36

この解決策を私にとって意味のあるものにした重要な洞察は次のとおりです。 の結果は、ヨセフスの生存者である数としてではなく、ヨセフスの生存者である数のインデックスjosephus(n, k)と考えるのが最善です。たとえば、電話をかけると、5 つの輪の中から生き残った人のインデックスがわかります。josephus(5, 2)

その直感を念頭に置いて、具体的な例を見て、ヨセフス問題がどのように機能するかを考えてみましょう。知りたいとしましょうjosephus(n, 2)。次のように n 人が並んでいると想像できます。

1 2 3 4 5 ... n

最初に起こることは、ここに示されているように、人物 1 が人物 2 を殺すことです。

1 X 3 4 5 ... n

ここで、次の形式の部分問題が残ります: n-1 人が残っており、1 人おきに殺され、最初に刺すのは人 3 です。つまり、次のような形をした人々の輪が残っています。

3 4 5 ... n 1

josephus(n - 1, 2)ここで、 n - 1 人がいるので、 を再帰的に呼び出すとします。これにより、n - 1 人の列で誰が生き残るかのインデックスが返されます。生き残る人のインデックスがあり、最初の人が誰であるかもわかっている場合、どの人が残るかを判断できます。その方法は次のとおりです。

この行の開始者は、最後に処刑された人の直後に来る人です。josephus(n - 1, 2)これは人 3 になります。4 人の輪の中の生存者の 1 インデックス位置は josephus(n - 1, 2) - 1したがって、必要に応じてリングを一周して、最終的な位置に到達するために、前方の位置を歩くことができます。つまり、生存者は位置によって与えられます

 (3 + josephus(n - 1, 2) - 1) % n

ただし、この上記の式には問題があります。実際に1インデックスを使用している場合、最後の生存者が位置nにある場合はどうなりますか? その場合、誤って回答として位置 0 が返されますが、実際には位置 n が必要です。これを修正するために、mod を使用して 1 インデックスでラップアラウンドするトリックを使用します。内側の量 (1 インデックスの位置) を取り、1 を引いてゼロ インデックスの位置を取得します。その量を n で変更して、インデックスがゼロの位置をラップします。最後に、ラップアラウンドされた 1 つのインデックス付きの位置を取得するために 1 つ追加します。それは次のようになります。

(3 + josephus(n - 1, 2) - 2) % n + 1

したがって、ここでの -2 項は、2 つの独立した -1 から来ています。最初の -1 はjosephus(n - 1, 2)、1 つのインデックス付きインデックスを返すためです。したがって、適切な数の位置だけ前進するには、前進する必要がありjosephus(n - 1, 2) - 1ます。2 番目の -1 は、0 インデックスではなく 1 インデックスを使用しているという事実から来ています。

これを一般化して、k = 2 だけでなく、任意の k に対しても機能するようにしjosephus(n, k)ます。その場合、人 1 は人 k を刺し、次のような配列を残します。

1 2 3 ... k-1 X k+1 ... n

基本的に、人 k+1 が最初に来るという部分問題を解決する必要があります。

k+1 k+2 ... n 1 2 ... k-1

したがってjosephus(n - 1, k)、n - 1 人の輪の 1 インデックスの生存者を計算して、その数のステップだけ前方にシフトします。

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

ラップアラウンドするケースを考慮する必要があるため、n で mod する必要があります。

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

ただし、1 インデックスなので、内側の量から 1 を引き、最後に 1 を加えるというトリックを使用する必要があります。

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

これは次のように単純化されます

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

これはと同等です

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

ソリューションコードのように。

要約すると、k-1 項は、位置 k+1 から開始しjosephus(n - 1, k) - 1、適切な量を前方にシフトするために追加し、次に 1 を減算し、最後に 1 を追加して正しいラップアラウンドを行うことから生じます。

お役に立てれば！

于 2015-08-02T20:22:24.270 に答える
0

k 番目が削除された後 (最初の k-1 が最後まで回転された後)、開始位置が k だけシフトされているため、位置を k-1 だけ調整する必要があります。つまり、初期位置 pos は pos-k になります。k = 3 の場合、(n-1,k) が pos = 2 を返した場合、元の位置は pos + k = 5 になるはずです。

mod(n) にする必要があるため、式の k を k-1 に置き換えます。 k = (k-1) % n + 1

于 2021-08-18T20:12:38.700 に答える