問題タブ [josephus]

最近の求人応募の一環として、この問題の解決策をコーディングするように依頼されました。

与えられた、

• n=円の中に立っている人の数。
• k=毎回カウントする人数

各人には、一意の（増分）IDが与えられます。最初の人（最も低いID）から始めて、1からkまで数え始めます。

次に、kの人が削除され、円が閉じます。次の残りの人（排除された人に続く）は1からカウントを再開します。このプロセスは、勝者である1人だけが残るまで繰り返されます。

ソリューションは以下を提供する必要があります。

• サークルから削除された順序での各人のID
• 勝者のID。

パフォーマンスの制約：

• できるだけ少ないメモリを使用してください。
• ソリューションを可能な限り高速に実行します。

何年も前からCSコースで同じようなことをしたことを思い出しましたが、このテストの時点では詳細を思い出せませんでした。私は今、それが複数の解決策を伴うよく知られた古典的な問題であることに気づきました。（一部の人は単に「ウィキペディア」の答えかもしれないので、まだ名前で言及しません）。

私はすでに解決策を提出しているので、私のために答えてくれる人を絶対に探していません。私は少し後でそれを提供します/他の人がいくつかの答えを提供した場合。

この質問をするための私の主な目標は、要件と制約を考慮して、私のソリューションが他のソリューションとどのように比較されるかを確認することです。

（「クラシック」ソリューションの一部が無効になる可能性があるため、要件に注意してください。）

これがウィキのヨセフス問題です。私が抱えている問題はこれの線形変化ですが、明確にするために問題全体を言い換えます。

（数=自然数）

次の方法で数字を削除するプロセスがあります。

また、番号が与えられます。この番号が消去後も存続Kするかどうかを確認する必要があります。K

例（インデックスが0から始まると仮定）

ご覧のとおりsafe、プロセスは除去のためにより高い値を選択するため、2、4、6はこのステップの後にあります。

繰り返しになりますが、Kどのように決定するのですか？Ksafe

ロバート・セドウィックによるアルゴリズム、次のリンクで、リンクされたリストは配列を使用して表現できることが言及されました

http://flylib.com/books/en/3.55.1.34/1/

図 3.8、ここで 5 が私の理解から削除された場合、値 5 が削除されると、次の 4 はインデックス 6 に変更される必要があります。私は図の論理に従っていません。誰でも私を助けてください。

ありがとう！

先週、Facebook ハッカーカップのラウンド 1b に参加しました。

問題の 1 つは、基本的にヨセフス問題でした。

以前にジョセフス問題を離散数学の問題として研究したことがあるので、基本的に再帰を取得する方法を理解しています。

しかし、n の最大値が 10^12 だったので、Facebook Hacker Cup ではうまくいきませんでした。k の最大値は 10^4 でした。

ウィキペディアでは、k が小さく、n が大きい場合のアプローチについて言及しています。基本的に、1 回のラウンドから人を削除してから、番号を付け直します。しかし、それはあまり説明されておらず、なぜ再番号付けが機能するのか理解できません。

ソリューションのサンプル作業ソース コードを見ましたが、最後の部分がまだわかりません。

私が本当に理解していないのは、res-=n%k（およびその後の行）から始まる部分です。それが結果を調整する方法であることをどのように導き出しますか?

誰かがこれがどのように導出されたかの背後にある理由を示すことができますか? またはそれを派生させるリンクですか？(UVA やトップコーダー フォーラムに関する情報は見つかりませんでした)

テーブルの周りに5人のメンバーが座っています。重要な値は、テーブルの周りに座っているメンバーの数です。したがって、キー値は5になります。テロリストは、あなたが5人のメンバーであるため、最初のメンバーから数え、5人と数えられた人は射殺されるとメンバーに言いました。彼は数え、5人目が死にます。もう一度彼は5まで数え、1人目が死亡します。もう一度数え、3人目が死亡し、2人と4人が残っています。最後に4人が5人として数えられ、最後に2人が残ります。

同じように、7人で試してみると答えは8になります。8人で答えは4になります。

コンピュータが人を正しく撃つことができるようにこれの公式を設定する方法。

メンバーにトークン値を与えることで循環リンクリストになっているのではないかと思いますが、方程式にたどり着くことができませんでした。したがって、キー値を与えることによって、生きる人が決定されます。

私はHaskellとFPに出くわし、その可能性に驚愕しました。そして、私の中の古い数学オタクは、実際の有用な目的のために素朴なコードを書くのに問題はありませんでした。しかし、すべての読書にもかかわらず、私はまだいくつかの驚くべきパフォーマンスのボトルネックにぶつからないようにする方法を理解するのに本当に苦労しています。

そのため、単純な実装を使用して非常に短いコードを記述し、少し変更を加えて、パフォーマンスがどのように応答するかを確認します。そして、これは私が本当に理解することができない1つの例です...私は、ナイーブなリストの実装で意図的に、ヨセフス問題の解決策を見つけるこの関数を書きました。

後者は190ミリ秒で実行され、RTSによると63％の生産性があります。

それから私が最初に試したかったのは、（長さの兵士-1）を削除し、それをデクリメント整数に置き換えることでした。

実行時間は最大900ミリ秒に跳ね上がり、生産性は16％に低下し、上記の単純なコードの47倍のメモリを使用します。そこで、厳密な評価を追加し、Int型を強制し、グローバル変数などを削除するなどの試みを行いましたが、あまり役に立ちませんでした。そして、私はこの減速を理解することができません。

パフォーマンス関連の記事や投稿をふるいにかけましたが、これについてのヒントが得られていないようです。まだHaskellの初心者である私は何か大きなものを見逃しているに違いありません...この1つの追加されたパラメーター（事前に噛まれた計算...）はどのようにして速度をそれほど低下させることができますか？

PS：ヨセフスが本当に3000人の兵士と一緒にいたなら、彼らは自殺する必要はなかっただろうと私は知っています...

私はカウンターを人へのタグ、つまり排除を開始する位置として使用します。

削除方法に問題があります。リストが空になるまで常に呼び出す必要があります。

私はVC++に非常に新しいです。昨日、私のVC ++インストラクターからこのコードが提供され、exeとして作成するように依頼されました。どこから始めてどこで終わるのかわかりません。この単一のファイルをexeファイルにする方法。VisualStudioでこの作業コードを貼り付ける方法と場所。私の質問があまりにも馬鹿げているように聞こえたら、ごめんなさい。でも私。この単一のファイルからexeを作成するのを手伝ってください。ちなみにこれはヨセフスサークルアルゴリズムです

ジョセフスの問題は、次の再帰によって解決できます。

この再帰関係はどのように導き出されたのでしょうか?

Pythonのリストを使用してJosepheusの問題を解決できるかどうかを知りたいと思いました。

簡単に言えば、ヨセフスの問題は、事前にわかっているスキップパラメータを使用して実行が処理された場合に安全な円形配置の位置を見つけることです。

たとえば、次のような円形の配置と3のスキップパラメータが与えられた場合、人々は安全な位置と位置[1,2,3,4,5,6,7]で実行されます。3,6,2,7,5,14

私はしばらくの間リストを使用してこれを解決しようと試みてきましたが、インデックスの位置は私が扱うのが難しいようになります。

コードスニペットで質問を更新しましたが、私のロジックが正しくないと思います。