問題タブ [josephus]

以下は、ヨセフス問題 (人々が円形に配置され、残りの 1 人になるまで他のすべての人が殺される問題) に対する1 つの解決策です。

しかし、他のすべての人をスキップするのではなく、スキップする数を増やしたらどうなるでしょうか? つまり、10 人を円に並べると、1、3、6、10 という順番で人が殺されました。変更は for ループで行われると思いますがi = i + 2、よくわかりません。

私は紙の上でそれを解決しました。これは削除の順序です。アスタリスクは削除する番号を示します。

考え？

編集： forループのこの変更を試しました：

j = 2 の最初のパスの後、内側のループはすでにリストを 1 つの候補に絞り込んでいるため、外側のループが完了しないため、これは機能しません。

なぜこのエラーが発生し続けるのか理解できないようです! キューを扱うのは初めてです。解決策は簡単で、おそらく基本的なものが欠けていると思います。ガイダンス/ヘルプは大歓迎です：

このコードの元のプロンプトは次のとおりです。 Josephus 問題。古代からのヨセフス問題では、N 人は窮地に立たされており、人口を減らすための次の戦略に同意しています。彼らは円を描いて (0 から N-1 までの番号が付けられた位置に) 配置され、円の周りを進み、1 人だけになるまで M 番目の人を排除します。伝説によると、ヨセフスは排除されるのを避けるためにどこに座るかを考え出しました。コマンド ラインから N と M を取得し、人々が排除される順序を出力する Queue クライアント Josephus を作成します (したがって、Josefus がサークル内のどこに座るかを示します)。

http://en.wikipedia.org/wiki/Josephus_problem ユーザーはサークル内の人数を選択できます。ユーザーは、各人の値を選択できます。ユーザーは、人の死亡のカウント数を選択できます。元。ユーザーが 5 人を選ぶと、5 人に 1 人が死亡します。

私は次のようなことを考えていました - ユーザーは人数を選択します ex- 50 PeopleArray は PeopleArray[50] になります

ユーザーは PeopleArray[50] の要素の値を選択します。50 個の要素に対して 50 個の値を入力する必要があります。

Death User は 3 を選ぶので、3 人に 1 人が死ぬので、どうすればその数字を配列から消去できますか。

問題 ^-配列で上記を行う方法がわからない

編集:少なくともエラーを整理し、コードを更新したようです。しかし、数学はまだうまくいっていないようです。何か案は？

要するに、私は C++ でプログラムを作成しようとしています。このプログラムは、ユーザーに最初のサークル内の人数を入力するように促し、k (カウントされた人数が実行される前に) = 3.

正しい考えだと思いますが、kを 1、2、または 5 以外として入力すると、「Debug Assertion Failed」および「Expression: vector erase iterator outside range」というエラーが表示されます。

そこで私は、有名な Hot Pocket/Josephus の実行問題をシミュレートするために作成者がキューを実装する、データ構造 Python を使用した問題解決を読んでいました。ただし、何度試しても、プログラムによって計算された最後の生存者が私の計算と一致しないため、この実装は正しくないと思います。たとえば、入力 ([0,1,2,3,4],2)) の場合、出力は 1 ではなく 3 であるべきではありませんか? (最初に 2 を削除するため、パターンに従うと、実行は 2,4,1,0,3 で、3 が最後の生存者となる必要があります。) しかし、プログラムの出力は 1 です。

完全な実装は次のとおりです。

それで、私は何を間違っていますか？どんな助けでも大歓迎です。前もって感謝します！

私はジョセフス問題のアルゴリズムを読んでいました。

私は次のアルゴリズムに出くわしました:

そのロジックが理解できませんでした。n=5、k=2 とします。

誰かが例を挙げてこれを説明できますか?

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

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

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

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 はしばらく無視しましょう)。

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