問題タブ [josephus]

Josephus ゲームでいくつかの問題が発生しています。私の最初の問題は、各ラウンドで排除された人の左側にいる人からカウントを開始する方法がわからないことです (ゲームは時計回りに進みます)。正しく削除されますが、削除された人の右側の人からカウントが開始されます。私の 2 番目の問題は、各ラウンドで排除された人物を印刷する方法がわからないことです。アルゴリズムの大部分はダウンしていますが、これらの細かい詳細を理解することはできません。どんな助けでも大歓迎です！

100人が輪になって並んでいるとします。1 人から 14 人まで数えて、その人をサークルから外します。カウント順に従って、再度カウントし、14 人目を削除します。繰り返す。最後に立っている人は誰ですか?

これを解決するためにあらゆることを試しましたが、デッド ループでは機能していないようです。

セグメント ツリーを使用して、Joseph Flavius 問題を解決したいと考えています。単純なシミュレーション (つまり、並べられたリスト) はO(n^2). 私が達成したいのは、セグメントツリーから取得した特定の距離の配列にジャンプすることです。つまり、セグメントツリーは削除された要素の数に関する情報を保持し、ツリーから情報を取得すると、O(1) で削除する次の要素を見つけることができます。問題は、Joseph Flavius 問題で機能するようにセグメント ツリーに情報を保存する方法がわからないことです。

各ノードに保持される何らかの追加の値はありますか? しかし、次の要素に関するクエリを作成するにはどうすればよいでしょうか?

ジョセフス問題 (またはジョセフス順列) は、特定のカウント アウト ゲームに関連する理論的な問題です。

人々は処刑されるのを待って輪になって立っています。カウントは円の最初の点から始まり、円を時計回りに進みます。指定された数の人がスキップされた後、次の人が実行されます。手順は、次の人から始めて、同じ方向に進み、同じ数の人をスキップして、残りの人が 1 人だけ残るまで繰り返され、解放されます。たとえば、n=10 の場合、削除の順序は 2、4、6、8、10、3、7、1、9、5 です。

最初に、最初にサークル内の人数 n が与えられます。上記の条件と制約を念頭に置いて消去の順序を指定します。

簡単に言えば、配列や連結リストなどのデータ構造を使用せずに、死のパターンを出力します。

循環リストを使用して、ジョセフスの問題に従って、最後に立っている人の出力を与えるプログラムを作成する必要があります。ほとんどの場合は機能しているようですが、シリーズに入ると、7（人）1（開始位置）、3（キルカウント）になります。キルの途中でスローされます（リストが2357のとき）。番号に続いてコードを数回調べましたが、この反復で5ではなく3をキルする理由がわかりません。

私の友人は、円の中に人が座っているヨセフス問題について教えてくれました。41番人1は刀を持っており、右隣の人を殺し、次の人に刀を渡す。これは、生き残った人が1人になるまで続きます。私はPythonでこの解決策を思いつきました：

しかし、それは人にしか機能しません42。どうすればよいですか、またはコードをどのように変更すれば、たとえば100, 1000サークル内のより多くの人が機能するようになりますか?

Josephusの問題を調べて、さまざまな解決策を見てきましたが、少し調整した後に私の答えが正しいのか、それとも最初から始めるべきなのか知りたいです。