1

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

（数=自然数）

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

i=2
while 1:
    remove numbers that are *placed* at positions divisible by i
    i+=1

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

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

1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16 ...
0,1,2,3,4,5,6,7,8, 9,10,11,12,13,14,15 ...  (indices)

After step 1 ( elimination at i=2 )
2,4,6,8,10,12,14,16 ... 
0,1,2,3, 4, 5, 6, 7 ... (indices)

After step 2 (elimination at i=3 )
2,4,6,10,12,16 ... ( 8 and 14 got removed cause they were at index 3 and 6 resp. )
0,1,2, 3, 4, 5 ... (indices)

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

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

4

2 に答える 2

2

1つの解決策は、反復ごとにリスト内のKのインデックスを追跡することです。

すべてのステップで、最初にKのインデックスがで割り切れるかどうかを確認します。そうである場合、falseを返します。それ以外の場合は、Kのインデックスからiで割り切れるKの前の要素の数を単純に減算します（つまり、Kはその回数だけ左にシフトされます）。

要素が1つだけ残るまで、これを続けます。

于 2010-11-12T12:42:16.370 に答える
2

この質問では、位置0の番号がどうなるかを正確に明確にすることはできません。この例では、ステップ1で、番号1（位置0）が削除されます。しかし、ステップ2では、番号2（位置0）が存続します。

この回答の目的のために、例は誤りであり、位置0の番号は常に存続すると仮定します。したがって、例は次のようになります。

初期位置

 Number    1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 ...
 Position  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 ...

ステップ1の後：

 Number    1  2  4  6  8 10 12 14 16 18 20 22 24 26 28 30 32 ...
 Position  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 ...

ステップ2の後：

 Number    1  2  4  8 10 14 16 20 22 26 28 32 34 38 40 44 46 ...
 Position  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 ...

これにより、OEISにはないシーケンス1、2、4、8、14、20、28、40、...が生成されます（ただし、以下の補遺を参照してください）。

シーケンス全体を計算せずに、特定の数Kが存続するかどうかを判断する方法は次のとおりです。

J₁=K− 1（Kの初期位置）とします。

  • J₁＆gt;0および2|J₁の場合、ステップ1でKが削除されますが、そうでない場合、その新しいインデックスはJ₂= J₁−⌊J₁/2⌋</li>です。
  • Kはステップ2でJ₂＆gt;0および3|J₂の場合は削除されますが、そうでない場合、その新しいインデックスはJ3 = J²−⌊J₂/3⌋</li>です。
  • Kが削除されるまで、またはKが存続することがわかったときにJi <i + 1になるまで、以下同様に続きます。

補遺

このシーケンスがOEISにないという結論に達したとき、私は少し急いでいました。たとえば、0ではなく1から始まる位置に番号を付けたとします。次に、シーケンス1、3、7、13、19、27、39、...を取得します。これはOEISシーケンスA000960、「フラウィウス・ヨセフスのふるい」です。ただし、閉じた形のソリューションはまだありません。

于 2010-11-12T15:13:58.360 に答える