josephus环公式法
Josephus(约瑟夫)问题的数学方法(转)2010-06-25 3:08Josephus问题
1. 问题的由来
Josephus问题是以10世纪的著名历史学家Flavius Josephus命名的. 据说, Josephus如果没有数学才能, 他就不会在活着的时候出名! 在犹太人和古罗马人战争期间, 他是陷 如罗马人陷阱的41个犹太反抗者之一. 反抗者宁死不做俘虏, 他们决定围成一个圆圈,且围绕圆圈来进行, 杀死所有第3个剩下的人直到没有一个人留下. 但是, Josephus和一个不告发的同谋者感到自杀是愚蠢的行为, 所以以他快速计算出在此恶性循环中他和他的朋友应该站的地方. 因此, 他们活了下来...
2. 平凡的解法
我 们用一个循环连表来模拟他们的行为。为了省事，我直接找了一个一个java代码：
class Josephus
{
static class Node
{
int val; Node next;
Node(int v) { val = v; }
}
public static void main(String[] args)
{
int N = Integer.parseInt(args[0]);
int M = Integer.parseInt(args[1]);
Node t = new Node(1);
Node x = t;
for (int i = 2; i <= N; x = (x.next=new Node(i++)));
x.next = t;
while (x != x.next)
{
for (int i = 1; i < M; i++) x = x.next;
x.next = x.next.next;
}
Out.println( "Survivor is " + x.val);
}
}
3. 递归公式
喜欢这个问题的朋友肯定不满足上面的方法，很想知道更简单的算法。
其实Josephus问题中的序列确实存在递归 的公式。但是递归公式的推导
比较麻烦，我就直接给出结果。如果想了解详细过程可以查阅相关资料。
假设有n个人，每次杀第m个 人，则k为第k个被杀死的人...
j1: x <- k*m
j2: if(x <= n) 输入结果x
j3: x <- floor((m*(x-n)-1) / (m-1)), goto j1
以C语言实现如下：
unsigned josephus(unsigned m, unsigned n, unsigned k)
{
unsigned x = km;
while(x <= n) x = (m*(x-n)-1)/(m-1);
return x;
}
4. m为2的情况
现在考虑一种m为2的特殊情形。
这时候有更简单的递归公式：
x = 2*n + 1 - (2*n+1-2*k)*2^log2((2*n)/(2*n+1-2*k))
其中，log2((2*n)/(2*n+1-2*k)) 为计算(2*n)/(2*n+1-2*k)以2为底的对数，
结果向下取整数。
联系 2^log2((2*n)/(2*n+1-2*k))整体，可以理解为将(2*n)/(2*n+1-2*k)向下
舍取到2的幂。有些地方把这中 运算称为地板函数，我们定义为flp2，下面是
C语言的实现：
unsigned flp2(unsigned x)
{
unsigned y;
do { y = x; x &= x-1; }while(x);
return y;
}
其中x &= x-1;语句是每次把x二进制最右边的1修改为0，直到最左边的1为止.
这种方法也可以用来计算x二进制中1 的数目，当x二进制中1的数目比较小的
时候算法的效率很高。
m为2的代码实现:
unsigned josephus2k(unsigned n, unsigned k)
{
unsiged t = (n<<1) - (k<<1) + 1;
return (n<<1)+1 - t*flp2((n<<1)/t);
}
5. m为2的情况, k为n的情形
该问题一般都是计算最
后一个被杀的人的位置。
现在考虑更为特殊的，m为2 的情况, k为n的情形。
令k=n可以化简前边m=2的公式：
x = 2*n + 1 - (2*n+1-2*n)*2^log2((2*n)/(2*n+1-2*n))
即，x = 2*n + 1 - 2^log2(2*n)
从 二进制的角度可以理解为：
将n左移1位（即乘以2），然后将最右端设置为1（既加1），
最后将左端的1置为0（既减去2*n的向下取的2 的幂）。
更简单的描述是将n的二进制表示循环右移动一位!
例如: n为1011001 -> 0110011 -> 110011
用代码实现为：
unsigned josephus2n(unsigned n)
{
return ((n-flp2(n))<<1)|1;
}
===================
class Josephus
{
static class Node
{
int val; Node next;
Node(int v) { val = v; }
}
public static void main(String[] args)
{
int N = Integer.parseInt(args[0]);
int M = Integer.parseInt(args[1]);
Node t = new Node(1);
Node x = t;
for (int i = 2; i <= N; x = (x.next=new Node(i++)));
x.next = t;
while (x != x.next)
{
for (int i = 1; i < M; i++) x = x.next;
x.next = x.next.next;
}
Out.println("Survivor is " + x.val);
}
}
unsigned josephus(unsigned m, unsigned n, unsigned k)
{
unsigned x = km;
while(x <= n) x = (m*(x-n)-1)/(m-1);
return x;
}
unsigned flp2(unsigned x)
{
unsigned y;
do { y = x; x &= x-1; }while(x);
return y;
}
unsigned josephus2n(unsigned n)
{
return ((n-flp2(n))<<1)|1;
}
unsigned josephus2k(unsigned n, unsigned k)
{
unsiged t = (n<<1) - (k<<1) + 1;
return (n<<1)+1 - t*flp2((n<<1)/t);
}
无论是用链表实现还是用数组实现都有一个共同点：要模拟整个游戏过程，不仅程序写起来比较烦，而且时间复杂度高达O(nm)，当n，m非常大(例如上百万，上千万)的时候，几 乎是没有办法在短时间内出结果的。我们注意到原问题仅仅是要求出最后的胜利者的序号，而不是要读者模拟整个过程。因此如果要追求效率，就要打破常规，实施 一点数学策略。
为了讨论方便，先把问题稍微改变一下，并不影响原意：
问题描述：n个人（编号0~(n-1))，从0开始报数，报 到(m-1)的退出，剩下的人继续从0开始报数。求胜利者的编号。
我们知道第一个人(编号一定是m%n-1) 出列之后，剩下的n-1个人组成了一个新的约瑟夫环（以编号为k=m%n的人开始）:
k k+1 k+2 ... n-2, n-1, 0, 1, 2, ... k-2
并且从k开始报0。
现在我们把他们的编号做一下转换：
k --> 0
k+1 --> 1
k+2 --> 2
...
...
k-2 --> n-2
k-1 --> n-1
变换后就完完全全成为了(n-1)个人报数的子问题，假如我们知道这个子问题的解：例如x是最终的胜利者，那么根据 上面这个表把这个x变回去不刚好就是n个人情况的解吗？！！变回去的公式很简单，相信大家都可以推出来：x‘=(x+k)%n
如何知道 (n-1)个人报数的问题的解？对，只要知道(n-2)个人的解就行了
。(n-2)个人的解呢？当然是先求(n-3)的情况 ---- 这显然就是一个倒推问题！好了，思路出来了，下面写递推公式：
令f[i]表示i个人玩游戏报m退出最后胜利者的编号，最后的结果自然是 f[n]
递推公式
f[1]=0;
f[i]=(f[i-1]+m)%i; (i>1)
有了这个公 式，我们要做的就是从1-n顺序算出f[i]的数值，最后结果是f[n]。因为实际生活中编号总是从1开始，我们输出f[n]+1
由于是 逐级递推，不需要保存每个f[i]，程序也是异常简单：
＃i nclude
main()
{
int n, m, i, s=0;
printf ("N M = "); scanf("%d%d", &n, &m);
for (i=2; i<=n; i++) s=(s+m)%i;
printf ("The winner is %d\n", s+1);
}
这 个算法的时间复杂度为O(n)，相对于模拟算法已经有了很大的提高。算n，m等于一百万，一千万的情况不是问题了。可见，适当地运用数学策略，不仅可以让 编程变得简单，而且往往会成倍地提高算法执行效率。
在网上看到这个，好像就是wywcgs高人 说的约瑟夫问题的高效解法！这个方法太妙了！
想到我们学校的4022-Recursive Survival。想应该可以用这个方法解决。
刚 开始没太细想，就直接这个方法，结果肯定超时（两个数的范围在2^63-1）。
就想这个约瑟夫问题的高效解法关键是找到第n跟n-1的递推关系 x‘=(x+k)%n。它是每次去掉第一个人，在构成
一个新队列，而且队列有一定的规律 k k+1 k+2 ... n-2, n-1, 0, 1, 2, ... k-2。
而这道题是每2个人去掉一个，如果从整个队列1 2 3 ...... n,来考虑，把整个队列都数一遍的话，剩下的是：
1 3 5 7 ...... n-1 (n为偶数，且下一次相当于从1开始重新数)
1 3 5 7 ...... n (n为奇数，且下一个去掉的是1，也就是说相当于从3开始数)。
由此得到关于n的递推公式
n=2*f(n/2)-1(n 为偶数);
n=2*f(n/2)+1(n为奇数).
这样即使n=2^63-1,最多也只要63次递归.
当时，觉得已经想的差不 多了，一提交，还是超时呢！
一细想，忘了考虑m,the times of the function nested。
如果 m=2^63-1,这么做是没法想像的。就如果n=1时，m就不需要考虑，直接就可以出来.
如果n递减也比较快可以出来（只是自己认为如此）。如 果n个人时剩下的是n,那就要把m都用完。
所以加了个判断语句就OK呢！
结果真的给AC呢，用了0.03秒。
不过看了别人的提交 纪录，只用了0.00秒，而且我的占用内纯是别人的好几倍。
可能是我的函数递归调用时是耗用的时间占了大部分。还没想到如何把这个递归用一个表来代替，这样可能更好些！