代码之家 › 专栏 › 技术社区 › Rohan Monga

约瑟夫难题的线性变化

josephus algorithm

1

Rohan Monga · 技术社区 · 14 年前

所以这里是 Josephus problem 在维基上。我遇到的问题是这个的线性变化,但为了清楚起见,我将重述整个问题。

(数字=自然数)

有一个过程正在以以下方式消除数字:

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

你也得到了一个数字 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 在这一步之后,因为过程将选择越来越高的值进行消除。

所以再一次,给 千 如何确定 千 将 安全的 ?

2 回复 | 直到 11 年前

1

2

Gareth Rees 14 年前

这个问题并不能说明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=K 1(K的初始位置)。

如果J>0和2 | J,则在步骤1中消除K,但如果不是,则其新索引为J=J J/2
如果J>0和3 | J,则在步骤2中消除K,但如果不是,则其新指数为J=J J/3
等等,直到K被消除,或者直到Ji<i+1,当我们知道K生存下来。

附录

当我断定这个序列不在OEIS中时,我有点仓促。假设我们把位置从1开始编号,而不是从0开始。然后我们得到序列1,3,7,13,19,27,39。。。那就是 OEIS sequence A000960 “弗拉维乌斯约瑟夫斯的筛子”。不过,仍然没有封闭形式的解决方案。

2

MAK 14 年前

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

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

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