约瑟夫问题.doc

Josephus 约瑟夫问题
假设n个竞赛者排成一个环形,依次顺序编号1,2,…,n。从某个指定的第1号开始,沿环计数,每数到第m个人就让其出列,且从下一个人开始重新计数,继续进行下去。这个过程一直进行到所有的人都出列为止。最后出列者为优胜者。
无论是用链表实现还是用数组实现来解约瑟夫问题都有一个共同点:要模拟整个游戏过程,不仅程序写起来比较麻烦,而且时间复杂度高达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
变换后就完完全全成为了(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],程序也是很简单:
« POJ-2103 Jackpot 容斥原理–位运算–统计bin中1的个数
线段树小结»
约瑟夫问题小结
约瑟夫问题,不多解释了,n个人,围绕成一个圈,数k退一。。
求最后一个人有公式,中间的人一般只能用模拟
POJ-1012
模拟可过,但是有更好的办法,由于要消除最后一半的人,所以有办法:
摘自:./JudgeOnline/showmessage?message_id=133610
=(p+m-1)%rest+1
<k就break,此时剩下的人rest等于k就成功
,m是k+1的整数倍或者k+1的整数倍加1,这样会提高不少
已经说的很好了
1是利用了将杀掉的这个人从队列里去除,剩下的人向前面充填。。虽然对于一般情况并不适合,但是可以解这道题。。。
2很显然易见
3是利用了最后两个人,只能是GG...GBX,或者GG...GXB(其中G代表好人,X代表这次杀死的,B代表坏人),因此m只能是(k+1)的整数倍,或者(k+1)的整数倍+1
POJ-2244
只能爆搜把。。没什么好办法
POJ-2984
具体数学上的,就是数1的个数,比如为m,然后m个1的二进制就可以了
此题充分显示了BigInteger的强大
POJ-2939
->------------
| |
---------
这样的环状,必然是环内的被杀掉了,然后就用hash把,普通的map会超时,此题充分显示了HashMap的强大
POJ-3750
简单模拟,清早一水
POJ-2800
O(n)的效率会超时,可以压缩到sqrt(k),原理是k%i=k-k/i*i,并且除数和被除数一定有一个<=sqrt(k)。所以可以压缩到sqrt(k)的效率
POJ-2359
又是一水题。。
POJ-1781
2984的简化版,BigInteger都不用了
POJ-3517
水题,注意初始位置小于0的话,要用mod
POJ-2886
Sempr的好题,和约瑟夫没有本质关系,用到的是线段数和反素数。据说有人用树状数组+二分水过,也挺好。。
注意这句话挺阴的:The children are numbered from 1 to N in clockwise order
hdu-3089
约瑟夫问题,人数较多,k较小,可以见下面的优化办法。
下面讲解优化办法,转自:uecanhui/ar