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)

正如我们所看到的，2、4、6safe在此步骤之后，因为该过程将选择越来越高的值进行消除。

所以再一次，给定一个K你如何确定 if Kwill be safe？

4

2 回答 2

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 ...

这导致序列 1, 2, 4, 8, 14, 20, 28, 40, ...在 OEIS 中找不到（但请参见下面的附录）。

在不计算整个序列的情况下，您可以通过以下方式确定特定数字 K 是否存在：

令 J₁ = K − 1（K 的初始位置）。

  • 如果 J₁>0 和 2|J₁，则在第 1 步消除 K，但如果不是，则其新索引为 J₂ = J₁ − ⌊J₁/2⌋</li>
  • 如果 J₂>0 和 3|J₂，则在第 2 步消除 K，但如果不是，则其新索引为 J₃ = J₂ - ⌊J₂/3⌋</li>
  • 以此类推，直到 K 被消除，或者直到 Ji < i+1，当我们知道 K 存活时。

附录

当我断定这个序列不在 OEIS 中时，我有点仓促。假设我们从 1 而不是 0 开始对位置进行编号。那么我们将得到序列 1、3、7、13、19、27、39，...，即OEIS 序列 A000960，“Flavius Josephus 的筛子”。但是，仍然没有封闭形式的解决方案。

于 2010-11-12T15:13:58.360 回答
2

一种解决方案是在每次迭代时跟踪列表中 K 的索引。

在每一步，我们首先检查 K 的索引是否可被整除。如果是，我们返回 false。否则，我们只需从 K 的索引中减去 K 之前可被 i 整除的元素数（即 K 向左移动了很多次）。

我们继续这样做，直到只剩下一个元素。

于 2010-11-12T12:42:16.370 回答