約瑟夫斯益智的線性變化

因此，這裏是維基上的Josephus problem。我遇到的問題是線性變化，但爲了清晰起見，我會重申整個問題。約瑟夫斯益智的線性變化

（數=自然數）

有是消除以下方式號碼的方法：

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

同時，也給出了一些K，你要確認如果這個數字K將消除其存活。

E.g. （假定索引從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)

正如我們可以看到2,4,6-是safe此步驟之後，由於處理將用於消除被選擇更高和更高的值。

因此，再次給出K如何確定K將是safe？

來源

2010-11-12 Rohan Monga

在第一個代碼片段的'while'循環中'i'是否增加？ – MAK 2010-11-12 12:39:09

woops :)固定。 – 2010-11-12 13:04:21

您的示例中存在不一致。在你的第一步中（消除2的倍數的位置）消除位置0處的數字。但是在第二步中（消除位置3處的倍數），位置0處的數字仍然存在。你能否澄清這是否是故意的？ – 2010-11-12 13:19:55

這個問題並沒有清楚地說明位置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 ...

這導致序列1，2， 4，8，14，20，28，40，...這是not found in OEIS（但請參閱下面的附錄）。

這裏是你將如何確定某一特定數量K生存，不計算整個序列：

讓J 1 = K - 1（初始的K位置）。

K被在步驟1中除去，如果J 1> 0且2 | J 1，但如果沒有，其新的索引是J 2 = J 1 - ⌊J₁/2⌋
K被消除，在步驟2，如果J 2> 0和3 | J 2，但如果不是，其新的指數是J 3 = J 2 - ⌊J2 /3⌋
等等，直到任何K被消除，或者直到Ji < i + 1，當我們知道K倖存下來。

附錄

我是有點倉促，當我的結論是，這個順序是不是在OEIS。假設我們編號從1開始而不是0的位置。然後我們得到序列1,3,7,13,19,27,39，...這是OEIS sequence A000960，「Flavius Josephus的篩子」。儘管如此，仍然沒有封閉的解決方案。

來源

2010-11-12 15:13:58

那些'地板看起來很奇怪:) 感謝OEIS，我不知道。 – 2010-11-12 20:07:59

是的，有些字體似乎有這些括號錯誤的位置。至於OEIS，請參閱我的附錄。 – 2010-11-13 07:46:20

謝謝@Gareth。 OEIS似乎是一個很好的資源，你的答案似乎也有效，我希望我可以+1兩次。 – 2010-11-13 09:54:29

一個解決方案是在每次迭代時跟蹤列表中K的索引。

在每一步，我們首先檢查K的索引是否可以被整除。如果是，我們將返回false。否則，我們只需從K的索引中減去K之前可被i整除的元素數（即K向左多次移位）。

我們繼續這樣做直到剩下一個元素。

來源

2010-11-12 12:42:16 MAK

約瑟夫斯益智的線性變化

回答

相關問題