约瑟夫环问题应该是都熟悉的,传说著名犹太历史学家夫拉维·约瑟夫在犹太罗马战争期间,约瑟夫和其他40名犹太反抗者被困在了罗马人包围的洞穴。这些犹太人宁可自杀也不愿当俘虏,于是决定围成一个圆圈,并沿着圆圈每隔两个人杀死一个,直到最后只剩两个人为止。约瑟夫和他的一个朋友不想自杀,于是他计算出他和他朋友应该在这个圈子中的位置。

一般的,假设一共有n个人,首先从0号开始报数,每报到m-1的人就自杀,求最后一个存活的人的位置。

最笨的方法就是进行n-1次循环报数,它的时间复杂度是O(mn),下面的代码是这种方法的一种实现,用一个数组的每个元素代表一个人,元素的值表示他是否被杀。

其实,在这n个人中,第一个被杀的人编号一定是(m-1)%n,在第二次报数过程中,编号为(m-1)%n+1的人将变成新的圆圈中的0号,所以可以得到如下的对应关系

可以看出,第一次报数过程中的编号为k的人在新的圆圈的编号为x = (k-(m-1)%n-1)%n,也就是说,在某次报数过程中的编号为x的人的上一次的编号为k = (x+(m-1)%n+1)%n=(x+m)%n。所以,为求最后存活的人的编号f(n),只需要知道他在n-1人中的编号。根据上面的分析,可以得到如下的递归式:

很容易写出它的代码:

这种方法每次计算只能杀一个人,那我们能不能一次多“解决”几个呢?
假设现有0-9十个人,每隔两个杀一个,杀一轮过后(每个人都报了一次数),可以得到新的编号情况:

也就是每一轮都将把编号是m的整数倍减1的人杀掉。可以得到,在一般情况下,新旧编号的对照如下

这个对照关系可以分两部分来看,第一部分是最后剩余的尾数(他们后面没有人被杀),也就是新编号中从0开始的部分。可以看出新旧编号的关系是y = x –⌊n/m⌋m;第二部分就是前面的部分,它们的关系是y = x + n – ⌊n/m⌋m –⌊x/m⌋。这样就可以写代码了。

需要注意最后4行代码,它处理的是编号在第二部分的情况。现在已知y求x,我们知道y = x + rcount –⌊x/m⌋,将这个函数的函数图画出来可以看到,对于不同的x,可能得到相同的y:

也就是当x刚好是m的整数倍时,x-1也是方程的一个解。那怎么做取舍呢?还看n=10,m=3的情况,当x=5和6时,得到的y都是5,但较小的5号已经被杀了。所以就要取较大的6,这就是要if判断的原因(理解了这一点,if ((tmp + 1) + rcount – (tmp + 1)/m == y)就可以写成if (!((tmp + 1)%m))了)。

这种方法的时间复杂度是klog(n),有没有更好到方法呢?《具体数学》中也讨论了这个问题。

为了写方程方便,现在我们将第一个人编号为1。

首先看m=2的情况。
当人数为偶数时,设为2n个,一轮自杀之后,杀掉了所有的偶数编号,1号还是1号,3号成为2号, … ,2n-1号成为n号。所以f(2n) = 2f(n)-1。
当人数为奇数时,设为2n+1,一轮自杀之后,杀掉了所有的偶数编号,2n+1号报数之后,1号自杀,3号成为1号, … ,2n+1号成为n号。所以f(2n) = 2f(n)+1。
于是得到方程组:

f(1) = 1
f(2n) = 2f(n) – 1, n >= 1
f(2n+1) = 2f(n) + 1, n >= 1

列出n=1到16时的解

perfect!设n=2k+l,则f(n)=f(2k+l)=2l+1(可以用归纳法证明)。
当m=3时呢?

screenshot3

没有发现明显的规律。也不能用简单直观的函数来表示。当然,只是我没有发现,谁有好到方法可以一起讨论。

自杀的问题到此结束,现在来思考另一个问题。
我们已经知道方程组:

f(1) = 1
f(2n) = 2f(n) – 1, n >= 1
f(2n+1) = 2f(n) + 1, n >= 1

它的解是f(n)=f(2k+l)=2l+1。
我们将 2k+l用2进制来表示就是n= 2k+l = (bkbk-1…b1b0)2。那么可以得到下列等式:

n = (bkbk-1…b1b0)2, bi=0,1 ,bk=1
l = (0bk-1…b1b0)2
2l = (bk-1…b1b00)2
2l+1 = (bk-1…b1b01)2 = (bk-1…b1b0bk)2

也就是说,f(n)得解是将n的2进制表示左循环移一位得到的数!

将这种方法推广到一般情况会发现更有趣。
现有如下函数关系:

f(1) = α
f(2n + j) = 2f(n) + βj j=0,1 n>=1

则有:

f((bkbk-1…b1b0)2) = 2f((bkbk-1…b1)2) + βb0
= 4f((bkbk-1…b2)2) + 2βb1 + βb0

= 2kf((bk)2) + 2k-1βbk-1 + … + 2βb1 + βb0
= kα + 2k-1βbk-1 + … + 2βb1 + βb0
= (αβbk-1…βb1βb0)2

好,现在推广到更一般的情况。
函数关系如下:

f(j) = αj, 1<= j < d
f(dn + j) = cf(n) + βj, 0 <= j < d, n >= 1

继续用上面的方法,将n用d进制表示有:

f((bkbk-1…b1b0)d)
= cf((bkbk-1…b1)d) + βb0
= c2f((bkbk-1…b2)d) + cβb1 + βb0

= ckf((bk)d) + ck-1βbk-1 + … + cβb1 + βb0
= ckαbk + ck-1bk-1 + … + cβb1 + βb0
= (αbkβbk-1…βb1βb0)c

来看一个例子,现有:

f(1) = 34
f(2) = 5
f(3n) = 10f(n) + 76, n >= 1
f(3n+1) = 10f(n) – 2, n >= 1
f(3n+2) = 10f(n) + 8, n >= 1

这里的d=3,c=10。现在要求f(19),那么将19用3进制表示为(201)3,α2=5,β0=76,β1=-2,所以
f(19) = f((201)3) = (5 76 -2)10 = 1258