問題タブ [josephus]

私はヨセフスの問題を解決しようとしています、そして私は動作するコードを持っています。

今、私はそれを書き直して次のような結果を得たいと思います：

---

これどうやってするの？

循環リンクリストを使用して、よく知られているヨセフスの問題を実装することになっているJavaのコードに取り組んでいます。ヨセフス問題に関する情報は次のとおりです。http：//en.wikipedia.org/wiki/Josephus_problem

ジョセフスクラスを作成するために与えられた学生クラスとドライバークラスがあります。

これが学生クラスです：http：//pastebin.com/4YgSA7CM

これがDriverクラスです：http：//pastebin.com/Nb08Dtqk

これらのクラスはどちらも変更できません。

ゼロから始めて、ヨセフス問題を効果的に使用する循環リンクリストを使用するヨセフスクラスを作成する必要がありました。

これが、コンパイラエラーのない完成したJosephusクラスです。

私のstartJosephusメソッドは私が信じる主な問題です。しかし、完全にはわかりません。上記のコード内のstartJosephusメソッドは次のとおりです。

これが私のJosephusクラスを実行するときに実行されているものです：http：//pastebin.com/5GnChgYd

出力が生成することになっているものは次のとおりです：http：//pastebin.com/Qr5dCZJp

また、この出力を生成するために使用される2つの入力ファイルは次のとおりです。

StudentList1.txt： http: //pastebin.com/ysjevQ8u

StudentList2.txt： http: //pastebin.com/r2YeppNm

私が得ている出力と私が得ているはずの出力に基づくと、ヨセフスの問題は始まっておらず、殺し屋をシミュレートしていないようです。しかし、コードの何が問題なのかわかりません。循環リンクリストであるため、私のコードにテールを付けることはできません。私がここで間違っていることについて何か考えはありますか？すべてのPastebinリンクについて申し訳ありませんが、ここで提示しているすべてのコードを整理するためのより良い方法のように思えました。あなたの考えを聞いてみたいです。

これは、無限ループの問題を修正した後に発生する新しいランタイムエラーです。助言がありますか？？？？これらすべてのヌルポインタ例外とは何ですか

質問へのリンクはUVA-1394: And There Was Oneです。
単純なアルゴリズムは、配列全体をスキャンし、最後に停止する各反復で k 番目の要素をマークすることです。これには O(n^2) 時間がかかります。
私は代替アルゴリズムを検索し、O(N lgN) 時間の解決策として遅延伝播を使用してツリーをセグメント化することを指摘した中国のブログに出くわしました。 セグメント ツリーを調べた後、O(N lgN) 時間のアルゴリズムを作成しようとしましたが、役に立ちませんでした。

---

私の質問は次のとおり
です。 1. セグメント ツリーを使用して、希望の実行時間を取得できますか?
2. はいの場合、それらの使用方法を教えてください。
3. セグメント ツリーと「zkw」セグメント ツリーは同じですか? - 彼はブログで zkw セグメント ツリーについて言及しています。
更新:上記の問題は Josephus 問題の例です。

私はデータ構造クラスに所属しており、インストラクターから提供されたサンプルデータを再現できません。問題は、ユーザーが指定したメンバー数、ステップ間隔、および開始位置に関する古典的なヨセフス問題です。

具体的には、23歳から5カウントオフの99人は、84人を最後の男として残す必要があると言われています。

私が思いついたのは：65です。入力は99人で、5から23の間隔で開始したのではないかと思い、もう一度走りました。これにより、42が生成されました。

私の割り当てソリューションには循環リンクリストが含まれますが、このcコードはすべての場合で同じ出力を生成します。

再度、感謝します。

同じ問題のセットを解決するために次のコードを見てください。問題に言及することが目的に役立つとは思わない、それはヨセフス問題のさらに別の反復です：

解決策1：

このソリューションは、累積1.0912秒で指定された10個のテストケースを解決し、4360KiBのメモリを消費します。

解決策2：解決策2：

このソリューションは、同じ10個のテストケースを合計1.0497秒と640KiBのメモリで解決します。

Python n00bである私は疑問に思っていましたが、オンラインジャッジによると、両方で同じポイントを獲得していますが、ソリューション2が1よりも高速で、メモリ効率がはるかに高い理由は何ですか？時間差は非常に少なく聞こえるかもしれませんが、同時に、c / c ++ / perlの送信よりもさらに高速で、最速のソリューションで私を最初にランク付けします

このスクリーンショットは役に立ちますか？

説明： 処刑されるのを待っている人々が輪になって立っています。カウントアウトは、円のあるポイントで始まり、円の周りを固定方向に進みます。各ステップで、一定数の人がスキップされ、次の人が実行されます。排除は、自由を与えられた最後の人だけが残るまで、円の周りを進みます（処刑された人が取り除かれるにつれてますます小さくなります）。

私はこの「ヨセフスの問題」をグーグルで検索しました。ウィキペディアのヒットにより、動的計画法の解決策f(n,k)=((f(n-1,k)+k-1) mod n)+1, with f(1,k)=1が得られました。しかし、これは最後の生存者しか得られません。どうすれば人々のシーケンスを実行させることができますか？たとえば、p（5、3）={3,1,5,2,4}。

また、O(nlogn)解決策の代わりに解決策はありO(nk)ますか？

わかりました、私はクヌースの具体的な数学に苦労しており、まだ理解していない例がいくつかあります.

J(n) = 2*J(n/2) - 1

第一章からです。具体的には、具体的な数学に精通している可能性のある人のために、ヨセフス問題を解決します。解決策はありますが、説明はまったくありません。イテレーション法で解いてみました。これがこれまでに思いついたものです

J(n) = (2^k)*J(n/(2^k)) - (2^k - 1)

そして、私はここで立ち往生しています。ヘルプやヒントをいただければ幸いです。

私はしばらく試してみましたが、以下のプログラムで N を入力として取り、最後に死ぬ兵士が 13 番目 (N>13) になるように M を生成する方法がわかりません。

結果はこれと同じになるはずです（しかし、私はそれを理解していないため、リンクされたリストでそれが必要です）:>.

ジョセフス問題に慣れていない場合:

N 人の兵士が輪になって立っています。彼らは全員処刑され、1 から始まり M ずつ移動します。以下のコードは、N と M を要求し、最後に立っているプレイヤーを生成します。

N=17;M=7 としましょう。出力は 13 である必要があります。上記のプログラムは 2 を生成します (何が起こるでしょうか? 1 からではなく M からカウントを開始するため、1,8,15 の代わりに ...... 7 を削除します)。 ,14......) これは私があなたの助けを必要とするところです (リンクされたリストは私にとってまだ難しい概念であるため)。これを変更するにはどうすればよいですか？