問題タブ [josephus]

私は最近、Josephus 問題はデータ構造を使用して O(n) で解決できると主張するフォーラムに出くわしました。ここでの明確な選択は循環リンクリストですが、ウィキペディアで数学的な再帰的/反復的なジョセフスアルゴリズムを実行しない限り、O(kn) または O(n^2) でのみ実行できると主張します。まず最初に、循環リンク リストには、検索 O(n)、削除 O(1)、追加 O(1) というプロパティがあります。これは、delete が特定のノードであり、append が head または tail を置き換えていることを前提としています。

ノードの循環リストがある場合、次のように開始点から削除するノードを見つけることができます。

n = 6 ノード

k = 3 番目のノードごとに削除

開始点: ノード #0

ノード: 0、1、2、3、4、5

(k + StartingPoint - 1) % n を使用して、削除するノードを計算できます。開始点 = 0 の場合、(3 + 0 - 1) % 6 = 2 となります。ここで、3 が開始点になります。(3 + 3 - 1) % 5 = 0、シフトすると元の 5 ノードになります (つまり、元の 2 がなくなったので、数値は 0,1,2,3,4 になります)。これが基本的に、数学的バージョンがどのように機能するかです。リンクされたリストの場合、どのノードを同様に削除する必要があるかを導き出すことができます。問題は、このノードに移動する必要があることです。リンクされたリストには O(n) 検索があり、これが問題です。したがって、このノードに移動して削除すると、n = n-1 になります。次のインデックスを見つけ、O(n) 検索を行い、n = n_original - 2 を取得します。これは、n + (n-1) + (n-2) + ... = O(n^2) になります。

二重にリンクされた循環リストがある場合、ノードが後ろから近づいていれば、一周する必要はありません。それでも、これは、k が n より小さい場合は O(k) 検索であり、k が n より大きい場合は O(n) 検索です (開始した場所に到達する前に n ノードしか移動できないため、k が小さい場合、 k を遠ざけるだけで、まだ開始した場所には到達しません)。

とにかく、私のポイントは、O(n) のデータ構造を介してこれを行う方法がわからないということです。ウィキペディアの解決策は、再帰の力を示す O(n) の非常に洗練された数学的方法です (純粋にコール スタックによって古い開始点を追跡するなど) が、実際のオブジェクトを削除すると、O( n)。露骨に尋ねるだけでなく、これを理解しようとする試みを表示したかったので、データ構造を使用して O(n) でこれを行う方法を知っている人はいますか? ありがとう！

ですから、これが与えられた質問です。

あなたは 100 脚の椅子が円形に並んだ部屋にいます。椅子には 1 から 100 までの番号が付けられています。

ある時点で、椅子 #1 の人は退席するように求められます。椅子 #2 の人はスキップされ、椅子 #3 の人は退席するよう求められます。1 人を飛ばして次の人に退場を求めるこのパターンは、生存者が 1 人残るまで円を回り続けます。

で、たどり着いた答えがこれです。私はこれが正しい答えだと信じています.紙の上でも約10回行い、毎回74を思いつきました. これはひっかけ問題か何かですか？ここからどうすればいいのかわからないからです。

これがjsfiddle http://jsfiddle.net/cQUaH/です

与えられた位置と人数で次の生存者を見つけたい。

そこの最後のビットを、生き残った位置の正確な番号に置き換えるだけです。プログラムは生存者が見つかるまで実行されます。すべてが真と偽の観点からなので、答えとして位置を与える方法がわかりません。ありがとうございました！

このヨセフス問題の実装のどこが不十分なのですか? ジョセフス問題に慣れていない人のために説明すると、目標は循環リンク リストから 3 つおきのエントリを 1 つだけになるまで削除することです。この例では、すべての「mth」値を削除しています。

私はいつも、リストの最後の番号を答えにしています。私はこれが正しくないことを知っています。

私はJosephus 問題(割り当ての別の部分) に取り組んできましたが、私たちがやるべきことは、2 つの変数mとを与えることですn。mは開始時のプレーヤーをn表し、プレーヤーの数を表します。mプログラムが適切なプレーヤーで開始し、適切な数のスペースをスキップするように、変数を配置する場所を見つけるのに問題があります。

が 2 で 6 人のプレイヤーがいた場合m、プレイヤー 2 から開始し、プレイヤー 3 にパスされ、プレイヤー 3 を排除してプレイヤー 4 に移動し、プレイヤー 5 にパスして排除するというように、1 人のプレイヤーが残るまで続きます。これは私が得たいと思っている出力です:

代わりに、私が持っているコードを使用すると、

に置き換えint i = 1; i <= n; i++て、正しい番号int i = m; i <= n; i++から始めるという考えがありましたが、次のようiになります。

mまた、5 人のプレイヤーしか追加されなかった理由もわかっていますが、正しい数のプレイヤーを追加するためにどこに行けばよいかはよくわかりません。アイデア/ヒントをいただければ幸いです。

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

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

次のコードで使用されている ADT はどれですか。どのようにその結論に達しますか? 私はそれが循環リンクリストであるという直感を持っていますが、その理由について正確な理由はありません.