递归问题:约瑟夫问题
目录
1 问题描述
这是一个生死攸关的问题!至于如何生死攸关参见《具体数学》1.3节 The Josephus Problem(那里详细的介绍了这个生死攸关的问题之来历)。现在把这个问题做如下数学上的抽象:假设有 n 个人站成一圈,现在要每隔一个删除一个人,直到只有一个人幸存下来。例如 n=10 的情形如图1所示:
Figure 1: n=10的约瑟夫问题
消去的顺序是:2,4 6,8,10,3,7,1,9,于是5幸存下来。问题:确定幸存者的号码 J(n)?
2 约瑟夫问题递归式
因为有 J(10)=5,所以我们猜测有 J(n)=n2,但是一些简单的如同表1的例子否定了这个猜测。
n | 1 | 2 | 3 | 4 | 5 | 6 |
---|---|---|---|---|---|---|
Jn | 1 | 1 | 3 | 1 | 3 | 5 |
不过我们可以大胆猜测, J(n)一定是奇数,因为绕圈走一圈就消去了全部的偶数。如果 n 是偶数,则走一圈后除了仅剩下一半人口并且他们的号码有变化外,我们面临的情形是与刚开始相同的情形,如图2所示:
Figure 2: n为偶数时的约瑟夫问题
如此,规模为 2n 问题就变成了规模为 n 的问题。这个规模为 n 的问题与原来相比只是在人员的序号上有所不同,具体说来就是除了每个人的号码加倍并减去1外, J(2n) 问题和 2J(n)−1问题没有什么区别。即
J(2n)=2J(n)−1,n≥1由上文我们知道 J(10)=5,几乎瞬间我们就会知道 J(20)=2J(10)−1=2∗5−1=9。如此可以瞬间解决所有的 J(5∗2m),m≥1问题, J(5∗2m)=2J(5∗2m−1)+1=2∗2m+1=2m+1+1,这一步隐含了数学归纳法的证明过程。
假设 n 是奇数,与偶数不同的情形在于,转第一圈后就把编号为1的人给杀掉了,第二圈开始是从编号为3的人开始的,第二圈开始后第一个要杀掉的人是5。
Figure 3: n为奇数时的约瑟夫问题
如此, J(2n+1)问题就简化为 2J(n)+1问题,即:
J(2n+1)=2J(n)+1,n≥1综上,约瑟夫问题递归式可以总结为:
J(1)=1J(2n)=2J(n)−1J(2n+1)=2J(n)+13 约瑟夫递归式的解
从约瑟夫递归式可以看出,不同于汉诺塔和披萨饼问题,约瑟夫问题递归式给出的不是 J(n) 和 J(n−1) 之间的递归关系,而是 J(2n) 或者 J(2n−1) 与 J(n) 之间的关系。
有了递归式,我们计算一些较小的值,如表2所示。
n | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Jn | 1 | 1 | 3 | 1 | 3 | 5 | 7 | 1 | 3 | 5 | 7 | 9 | 11 | 13 | 15 | 1 |
显然,从表2可以看出,将 n 按照 2的幂次进行分组或许会出现一些转机。每一组开始的 J(n) 总是等于1。仔细观察上表,如果将 n 写作 2m+l,则 J(n)=J(2m+l)=2l+1,m≥0≤l<2m. 其中 2m是不超过 n 的 2的最大幂,而 l=n−2m。事实上,可以对 m 使用数学归纳法证明:
J(n)=J(2m+l)=2l+1,m≥0≤l<2m如此,我们得出了约瑟夫问题的闭式解。对于 J(100) 因为 100=26+36,所以 J(100)=2∗36+1=73
4 拓展1:二进制与约瑟夫问题
接下来我们针对约瑟夫问题做一些深入的挖掘。在求解约瑟夫问题递归式闭式解的过程中, n 和 J(n) 的以2为基的表示发挥着重要的作用,我们自然要研究以2为基的表示与约瑟夫问题之间的关系。假设 n 的二进制表示为:
n=(bmbm−1…b1b0)2即, n=bm2m+bm−12m−1+b12+b0,其中 bi,i=0,1,…,m−1 为 0 或者 1。 bm=1,注意 n=2m+l,所以:
n=(1bm−1…b1b0)2l=(0bm−1…b1b0)22l=(bm−1…b1b00)22l+1=(bm−1…b1b01)2J(n)=(bm−1…b1b0bm)2即,我们得到了:
J((bmbm−1…b1b0)2)=(bm−1bm−2…b1b0bm)2在计算机程序设计过程中,只需要对 n 的二进制表示循环左移1位即可得到 J(n)!!!这是多么的令人激动啊!在刚开始的时候,我们看约瑟夫问题显得好困难,但是,此刻我们只需要对n 的二进制表示循环左移1位即可得到 J(n)!!! 对一个问题深入分析竟然可以得到如此精妙而简洁的答案!高老头不愧是高老头!
还以 J(100) 为例, 因为 100=(1100100)2,所以 J((1100100)2)=(1001001)2=73 !!!
5 拓展2:更一般的约瑟夫递归式
接下来跟进一步深入挖掘该问题,对约瑟夫递归式做更进一步的推广。如下:
f(1)=αf(2n)=2f(n)+βf(2n+1)=2f(n)+γ可以看出在约瑟夫问题中, α=1,β=−1,γ=1。接下来,我们依然从小入手,得出表3。
n | f(n) |
---|---|
1 | α |
2 | 2α+β |
3 | 2α+ +γ |
4 | 4α+3β |
5 | 4α+2β+γ |
6 | 4α+β+2γ |
7 | 4α+ +3γ |
8 | 8α+7β |
9 | 8α+6β+γ |
从上表我们可以看出, α 的系数是2的幂,且不超过n。 β 的系数则从2的幂减一递减到0,γ 的系数则从0开始递增直到2的幂减一。于是式(1)的解可以表示为:
f(n)=A(n)α+B(n)β+C(n)γ则, A(n),B(n),C(n)可以分别表示为:
A(n)=2mB(n)=2m−1−lC(n)=l其中, n=2m+l,0≤l<2m,n≥1. 对式(13)用数学归纳法可以证明。
联想到之前采用二进制表示约瑟夫问题的解:
J((bmbm−1…b1b0)2)=(bm−1bm−2…b1b0bm)2n 的循环左移即是 J(n) 的解。那么对于式(15) 这个更一般的推广,有没有二进制表示呢? 当然有! 首先式(15) 可以改写为:
f(1)=αf(2n+j)=2f(n)+βj,j=0,1则式(???)可以改写为:
f((bmbm−1…b1b0)2)=2f((bmbm−1…b2b1)2)+βb0=4f((bmbm−1…b3b2)2)+2βb1+βb0=8f((bmbm−1…b4b3)2)+4βb2+2βb1+βb0⋮=2mf((bm)2)+2m−1βbm−1+…+2βb1+βb0=2mα+2m−1βbm−1+…+2βb1+βb0最后,可得:
f((bmbm−1…b1b0)2)=(αβbm−1βbm−2…βb1βb0)2事实上我们对 f(n)的前几个解稍加整理即可看出式 (18) 的精妙。
n | f(n) |
---|---|
1 | α |
2 | 2α +β |
3 | 2α +γ |
4 | 4α + 2β + β |
5 | 4α + 2β + γ |
6 | 4α + 2γ+β |
7 | 4α + 2γ+γ |
在此, 我们有 β0=β,β1=γ. 仍然以 J(100) 为例,因为 100=(1100100)2, 其解为:
(αβbm−1βbm−2…βb1βb0)2=(1β1β0β0β1β0β0)2因为 α=1,β0=β=−1,β1=γ=1 ,所以 式(19)可以重写为:
(1β1β0β0β1β0β0)2=(11−1−11−1−1)2=73注意在此,我们突破了二进制只有0和1的限制,不过这一突破使得约瑟夫的解更加的精炼。
6 推广3:不同基底的约瑟夫递归式
可以沿着推广2的思路走的更远,我们对式12做更进一步修改:
f(j)=αj,1≤j<df(dn+j)=cf(n)+βj,0≤j<d式21有变动基数的解:
f((bmbm−1…b1b0)d)=(αbmβbm−1βbm−2…βb1βb0)c7 推广4:倒数第二个位置
约瑟夫有一个朋友,他站在倒数第二个位置上因而获救。当每隔一个人就有一个人被处死时,倒数第二个幸存者 I(n) 的号码是多少?
每隔一个人就有一个人被处死的约瑟夫问题解为:
J(n)=J(2m+l)=2l+1此时有: 2l+1=n−1→n=2l+2 ,满足此式的 n 总是倒数第二个位置上的人获救。