所以这里是 Josephus problem在维基上。 我遇到的问题是这个问题的线性变化，但为了清楚起见，我将重述整个问题。
(数字 = 自然数)
有一个以下列方式消除数字的过程:
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、6 是安全的，因为该过程将选择越来越高的值进行消除。
再一次，给定一个 K，你如何确定 K 是否安全？
最佳答案
问题并没有说清楚位置 0 处的数字到底发生了什么。在示例中，在第 1 步中，数字 1(位置 0)被消除。但是在第 2 步，数字 2(在位置 0)仍然存在。
为了这个答案的目的，我假设这个例子是错误的，位置 0 的数字总是存在。所以这个例子应该是这样的:
Initial position
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 ...After step 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 ...After step 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₁ = K − 1(K 的初始位置)。
- 如果 J₁>0 和 2|J₁，则 K 在第 1 步被淘汰，但如果不是，则其新索引为 J₂ = J₁ − ⌊J₁/2⌋
- 如果 J2>0 和 3|J2，则 K 在第 2 步被淘汰，但如果不是，则其新索引为 J3 = J2 − ⌊J2/3⌋
- 依此类推，直到 K 被淘汰，或者直到 Ji < i+1，当我们知道 K 存活时。
附录
当我断定这个序列不在 OEIS 中时，我有点仓促。假设我们从 1 而不是 0 开始对位置进行编号。那么我们将得到序列 1, 3, 7, 13, 19, 27, 39, ... 这是 OEIS sequence A000960 ，“弗拉维乌斯·约瑟夫斯的筛子”。不过，仍然没有封闭形式的解决方案。
关于algorithm - 约瑟夫斯谜题的线性变化，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/4164460/