报数题的通解

 

首先为ca981的认真钻研精神鼓掌，如果你不介意的话，我有下面几点comments:

 

1）你的关于Y_跳跃的公式中的最后的sum求和项可以用等比级数求和公式化简，从而Y_跳跃的公式可化简如下

 

Y_跳跃= M + (p –J₀)M^k + J₀M^k-1  - 1

 

2）这个报数问题与The Josephus Problem 在周期M=2 时是一致的，但在M > 2 时不完全一样，The Josephus Problem每轮的淘汰率是1/M，而你的报数问题每轮的淘汰率是(M-1)/M; 即每轮报数中每M人有(M-1)人被淘汰。

 

3）给定M，你的报数问题通解的closed formula 应该能得到。For example, 当M=3时通解是:

3t – 2 * 3^⎿log ₃ ^{((3t-1)/2)⏌} when 人数 N=2t,
3t+ 3/2 – ½ * 3^⎿log ₃ ^(6t)⏌ when 人数 N=2t+1.

这与你的算法通解应该是等价的。我是借鉴The Josephus Problem的书本手段，与你的“从后往前推”的思路在本质上是一样的，但在处理细节上不同，相对容易写出通解的closed formula。

对于一般情况，给定M , 写N= (M-1)t +i，0 ≤ i ≤ M-1, 通解的closed formula 应该能得到(in terms of M，t and i).

 

所有跟帖： 

• 谢谢！你这样化简很好，公式漂亮多了 -ca981- ♂ (194 bytes) () 12/24/2013 postreply 07:28:38

• 共勉！ -6700417- ♂ (51 bytes) () 12/24/2013 postreply 07:50:29