本文主要是介绍具体数学--围圈杀人游戏，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
UTF8gbsn
Intro
这个约瑟夫问题稍微有些复杂。是一群人排成一个圈，已一个人为1号然后编号。然后隔一个人杀掉一个。知道最后剩下一人。问题是问剩下的一个人的编号是多少？我们还是按照三步走的策略来看这个问题。
Step1
从简单特例出发，假如 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 1,2,3,4,5,6,7,8,9,10 1,2,3,4,5,6,7,8,9,10排成一个圈。那么被杀掉的人的顺序是2,
4, 6, 8, 10, 3, 7, 1, 9。最后幸存者是5号。
Step2
我们很自然的从奇数，偶数的方向上来考虑这个问题。当n是偶数的时候。第一轮杀人之后剩下的全是奇数。比如 n = 2 k n=2k n=2k,那么第一轮剩下的人为
even
1 , 3 , 5 , . . . , 2 k − 1 → 1 , 2 , 3 , . . . , k 1,3,5,...,2k-1 \rightarrow 1,2,3,...,k 1,3,5,...,2k−1→1,2,3,...,k
从这个映射表可以看书。k个人参与游戏的结果 j ( k ) j(k) j(k)和2k个人参与游戏的结果之间有着一定的关系
j ( 2 k ) = 2 j ( k ) − 1 , k ⩾ 1 j(2k)=2j(k)-1, k\geqslant 1 j(2k)=2j(k)−1,k⩾1
odd
对于 n = 2 k + 1 n=2k+1 n=2k+1的情况来看。这个时候我们可以发现杀掉一轮之后剩下的人为 3 , 5 , . . . , 2 k + 1 3,5,...,2k+1 3,5,...,2k+1。那么我们来看看对应关系
3 , 5 , . . . , 2 k + 1 → 1 , 2 , 3 , . . . , k 3,5,...,2k+1 \rightarrow 1,2,3,...,k 3,5,...,2k+1→1,2,3,...,k
所以，我们可以从上面的映射中得出
j ( 2 k + 1 ) = 2 j ( k ) + 1 , k ⩾ 1 j(2k+1)=2j(k)+1,k\geqslant 1 j(2k+1)=2j(k)+1,k⩾1
conclusion
J ( 1 ) = 1 J ( 2 n ) = 2 J ( n ) − 1 for n ⩾ 1 J ( 2 n + 1 ) = 2 J ( n ) + 1 for n ⩾ 1 \begin{aligned} J(1) &=1 & & \\ J(2 n) &=2 J(n)-1 & & \text { for } n \geqslant 1 \\ J(2 n+1) &=2 J(n)+1 & & \text { for } n \geqslant 1 \end{aligned} J(1)J(2n)J(2n+1)=1=2J(n)−1=2J(n)+1 for n⩾1 for n⩾1
Step3
在我们得出递推公式之后，我们不妨列举几个简单的例子。
通过观察这个数列。我们可以得出如下公式
J ( 2 m + h ) = 2 h + 1 , for m ⩾ 0 and 0 ⩽ h < 2 m \mathrm{J}\left(2^{\mathrm{m}}+h\right)=2 \mathrm{h}+1, \quad \text { for } \mathrm{m} \geqslant 0 \text { and } 0 \leqslant h<2^{\mathrm{m}} J(2m+h)=2h+1, for m⩾0 and 0⩽h<2m
这里出现了二进制形式。我们自然想到利用二进制来解决上面的公式。
n = b m 2 m + b m − 1 2 m − 1 + ⋯ + b 1 2 + b 0 \mathrm{n}=\mathrm{b}_{\mathrm{m}} 2^{\mathrm{m}}+\mathrm{b}_{\mathrm{m}-1} 2^{\mathrm{m}-1}+\cdots+\mathrm{b}_{1} 2+\mathrm{b}_{0} n=bm2m+bm−12m−1+⋯+b12+b0
推理过程如下
n = ( 1 b m − 1 b m − 2 … b 1 b 0 ) 2 h = ( 0 b m − 1 b m − 2 … b 1 b 0 ) 2 2 h = ( b m − 1 b m − 2 … b 1 b 0 0 ) 2 2 h + 1 = ( b m − 1 b m − 2 … b 1 b 0 1 ) 2 J ( n ) = ( b m − 1 b m − 2 … b 1 b 0 b m ) 2 \begin{aligned} \mathrm{n} &=\left(1 \mathrm{b}_{\mathrm{m}-1} \mathrm{b}_{\mathrm{m}-2} \ldots \mathrm{b}_{1} \mathrm{b}_{0}\right)_{2} \\ \mathrm{h} &=\left(0 \mathrm{b}_{\mathrm{m}-1} \mathrm{b}_{\mathrm{m}-2} \ldots \mathrm{b}_{1} \mathrm{b}_{0}\right)_{2} \\ 2h &=\left(\mathrm{b}_{\mathrm{m}-1} \mathrm{b}_{\mathrm{m}-2} \ldots \mathrm{b}_{1} \mathrm{b}_{0} \mathrm{0}\right)_{2} \\ 2 \mathrm{h}+1 &=\left(\mathrm{b}_{\mathrm{m}-1} \mathrm{b}_{\mathrm{m}-2} \ldots \mathrm{b}_{1} \mathrm{b}_{0} 1\right)_{2} \\ \mathrm{J}(\mathrm{n}) &=\left(\mathrm{b}_{\mathrm{m}-1} \mathrm{b}_{\mathrm{m}-2} \ldots \mathrm{b}_{1} \mathrm{b}_{0} \mathrm{b}_{\mathrm{m}}\right)_{2} \end{aligned} nh2h2h+1J(n)=(1bm−1bm−2…b1b0)2=(0bm−1bm−2…b1b0)2=(bm−1bm−2…b1b00)2=(bm−1bm−2…b1b01)2=(bm−1bm−2…b1b0bm)2
结论是
J ( ( b m b m − 1 … b 1 b 0 ) 2 ) = ( b m − 1 … b 1 b 0 b m ) 2 \mathrm{J}\left(\left(\mathrm{b}_{\mathrm{m}} \mathrm{b}_{\mathrm{m}-1} \ldots \mathrm{b}_{1} \mathrm{b}_{0}\right)_{2}\right)=\left(\mathrm{b}_{\mathrm{m}-1} \ldots \mathrm{b}_{1} \mathrm{b}_{0} \mathrm{b}_{\mathrm{m}}\right)_{2} J((bmbm−1…b1b0)2)=(bm−1…b1b0bm)2
上面的公式就是我们最终的解。这个解，是非常容易用程序实现的。接下来我们来看看两个特殊的解。
-
J ( n ) = n J(n)=n J(n)=n,那么n是多少的时候 J ( n ) = n J(n)=n J(n)=n?我们不妨来看看迭代J会怎么样。比如
J ( J ( J ( . . . J ( 10101011 0 2 ) ) ) ) J(J(J(...J(101010110_2)))) J(J(J(...J(1010101102))))
假如我们迭代无限次。最终上面式子会变成多少？聪明的读者已经看出来了。因为J实际上是一个把第一位非0拿到尾部的一个操作。
J ( 10101011 0 2 ) = 1010110 1 2 ⇒ J ( 1010110 1 2 ) = 101101 1 2 ⇒ J ( 101101 1 2 ) = 11011 1 2 . . . J(101010110_2)=10101101_2 \Rightarrow J(10101101_2)=1011011_2 \Rightarrow J(1011011_2)=110111_2 ... J(1010101102)=101011012⇒J(101011012)=10110112⇒J(10110112)=1101112...J ( J ( J ( . . . J ( 10101011 0 2 ) ) ) ) = 1111 1 2 J(J(J(...J(101010110_2))))=11111_2 J(J(J(...J(1010101102))))=111112
这个 1111 1 2 11111_2 111112是一个不动点。也就是说J(11111)=11111.由此可见只要n的二进制表示形式为全1，那么n就是一个不动点。而 J ( n ) = n J(n)=n J(n)=n -
J ( n ) = n / 2 J(n)=n/2 J(n)=n/2,我们根据递通项公式来看看如何，找满足条件 J ( n ) = n / 2 J(n)=n/2 J(n)=n/2的所有n.我们不难发现
J ( n ) = n / 2 2 h + 1 = ( 2 m + h ) / 2 h = 1 3 ( 2 m − 2 ) \left. \begin{aligned} J(n)&=n/2\\ 2h+1=(2^m+h)/2\\ h=\frac{1}{3}(2^m-2) \end{aligned} \right. J(n)2h+1=(2m+h)/2h=31(2m−2)=n/2由此可见只要 2 m − 2 2^m-2 2m−2能被3整除。那么 2 m + 1 3 ( 2 m − 2 ) = 2 m + h = n 2^m+\frac{1}{3}(2^m-2)=2^m+h=n 2m+31(2m−2)=2m+h=n就是满足 J ( n ) = n / 2 J(n)=n/2 J(n)=n/2的解。而我们来看 2 m − 2 2^m-2 2m−2这样的数在什么情况下能被3整除？我们这里不给出证明，以后会讲到这一部分内容。现在只是给出结论。也就是当m为奇数的时候 2 m − 2 2^m-2 2m−2就能被3整除。所以，我们可以得出下表。
由此可见只要确定m为奇数所有的 J ( n ) = n / 2 J(n)=n/2 J(n)=n/2的n，都可以确定出来。也可以通过二进制形式弄出来。注意这里的逻辑是，根据奇数的m计算出 h = 1 3 ( 2 m − 2 ) h=\frac{1}{3}(2^m-2) h=31(2m−2)，然后就确定出了 n = 2 m + h n=2^m+h n=2m+h
extend
clairvoyant
扩展问题，我们的递推公式为。
J ( 1 ) = 1 J ( 2 n ) = 2 J ( n ) − 1 for n ⩾ 1 J ( 2 n + 1 ) = 2 J ( n ) + 1 for n ⩾ 1 \begin{aligned} J(1) &=1 & & \\ J(2 n) &=2 J(n)-1 & & \text { for } n \geqslant 1 \\ J(2 n+1) &=2 J(n)+1 & & \text { for } n \geqslant 1 \end{aligned} J(1)J(2n)J(2n+1)=1=2J(n)−1=2J(n)+1 for n⩾1 for n⩾1
这是一大类问题的特例。下面这种是这一大类问题的一般形式。
f ( 1 ) = α f ( 2 n ) = 2 f ( n ) + β , for n ⩾ 1 f ( 2 n + 1 ) = 2 f ( n ) + γ , for n ⩾ 1 \begin{aligned} f(1) &=\alpha & & \\ f(2 n) &=2 f(n)+\beta, & & \text { for } n \geqslant 1 \\ f(2 n+1) &=2 f(n)+\gamma, & & \text { for } n \geqslant 1 \end{aligned} f(1)f(2n)f(2n+1)=α=2f(n)+β,=2f(n)+γ, for n⩾1 for n⩾1
还是按照三步走，这一步是先简单的特列写出来
我们很容易得出一个简单的公式
f ( n ) = A ( n ) a + B ( n ) β + C ( n ) γ \mathrm{f}(\mathrm{n})=\mathrm{A}(\mathrm{n}) \mathrm{a}+\mathrm{B}(\mathrm{n}) \beta+\mathrm{C}(\mathrm{n}) \gamma f(n)=A(n)a+B(n)β+C(n)γ
其中
A ( n ) = 2 m B ( n ) = 2 m − 1 − h C ( n ) = h \begin{array}{l}{\mathrm{A}(\mathrm{n})=2^{\mathrm{m}}} \\ {\mathrm{B}(\mathrm{n})=2^{\mathrm{m}}-1-h} \\ {\mathrm{C}(n)=h}\end{array} A(n)=2mB(n)=2m−1−hC(n)=h
method
证明上面的式子，只需要归纳法即可。但是如何要计算上面的式子，却不是那么直观。我们是根据简单的例子，靠直觉在构造形式，然后用归纳法证明。所以这种做法实际上需要一定的敏锐程度的人才能找到解决方案。但是如果不那么敏锐和聪明的人如何来解决这个问题呢？作者在这里提出了另一种方法步骤。首先让我们来回归一下这个一般化的问题。
f ( 1 ) = α f ( 2 n ) = 2 f ( n ) + β , for n ⩾ 1 f ( 2 n + 1 ) = 2 f ( n ) + γ , for n ⩾ 1 \begin{aligned} f(1) &=\alpha & & \\ f(2 n) &=2 f(n)+\beta, & & \text { for } n \geqslant 1 \\ f(2 n+1) &=2 f(n)+\gamma, & & \text { for } n \geqslant 1 \end{aligned} f(1)f(2n)f(2n+1)=α=2f(n)+β,=2f(n)+γ, for n⩾1 for n⩾1
我们对于上面的公式有三个参数。 α , β , γ \alpha,\beta,\gamma α,β,γ,我们自然可以设通项公式为
f ( n ) = A ( n ) α + B ( n ) β + C ( n ) γ f(n)=A(n)\alpha+B(n)\beta+C(n)\gamma f(n)=A(n)α+B(n)β+C(n)γ
我们如何来求解三个参数呢？注意首先要确定上面的等式的参数是啥？ A ( n ) , B ( n ) , C ( n ) A(n),B(n),C(n) A(n),B(n),C(n)是目标参数。为了求出这三个参数，我们可以靠特殊的 α , β , γ \alpha,\beta,\gamma α,β,γ来求出 A ( n ) , B ( n ) , C ( n ) A(n),B(n),C(n) A(n),B(n),C(n)
-
先把 B ( n ) , C ( n ) B(n),C(n) B(n),C(n)消除，来求参数 A ( n ) A(n) A(n).我们可以设 α = 1 , β = γ = 0 \alpha=1,\beta=\gamma=0 α=1,β=γ=0.这样我们就可以得到
f ( n ) = α A ( n ) f(n)=\alpha A(n) f(n)=αA(n)A ( 1 ) = 1 A ( 2 n ) = 2 A ( n ) , for n ⩾ 1 A ( 2 n + 1 ) = 2 A ( n ) , for n ⩾ 1 \begin{aligned} \mathrm{A}(1) &=& 1 \\ \mathrm{A}(2 \mathrm{n}) &=2 \mathrm{A}(\mathrm{n}), & & \text { for } \mathrm{n} \geqslant 1 \\ \mathrm{A}(2 \mathrm{n}+1) &=2 \mathrm{A}(\mathrm{n}), & & \text { for } \mathrm{n} \geqslant 1 \end{aligned} A(1)A(2n)A(2n+1)==2A(n),=2A(n),1 for n⩾1 for n⩾1
从上面的公式来看。我们按照前面的方法。列举17来个特例，就能提出结论。
A ( n ) = A ( 2 m + h ) = 2 m A(n)=A(2^m+h)=2^m A(n)=A(2m+h)=2m -
下面我们看看特殊的 f ( n ) f(n) f(n),加入 f ( n ) = 1 f(n)=1 f(n)=1
1 = α 1 = 2 ⋅ 1 + β 1 = 2 ⋅ 1 + γ \begin{aligned} \mathbf{1} &=\alpha \\ \mathbf{1} &=2 \cdot 1+\beta \\ \mathbf{1} &=2 \cdot 1+\gamma \end{aligned} 111=α=2⋅1+β=2⋅1+γ我们得出结论
A ( n ) − B ( n ) − C ( n ) = f ( n ) = 1 A(n)-B(n)-C(n)=f(n)=1 A(n)−B(n)−C(n)=f(n)=1
-
再看我们看看特殊的 f ( n ) f(n) f(n),加入 f ( n ) = n f(n)=n f(n)=n
1 = α 2 n = 2 ⋅ n + β 2 n + 1 = 2 ⋅ n + γ \begin{aligned} 1 &=\alpha \\ 2 \mathrm{n} &=2 \cdot \mathrm{n}+\beta \\ 2 \mathrm{n}+1 &=2 \cdot \mathrm{n}+\gamma \end{aligned} 12n2n+1=α=2⋅n+β=2⋅n+γ
通过上面的式子我们，可以得到如下等式
A ( n ) + C ( n ) = n \mathrm{A}(\mathrm{n})+\mathrm{C}(\mathrm{n})=\mathrm{n} A(n)+C(n)=n
最后，我们总结结论。
A ( n ) = 2 m A ( n ) − B ( n ) − C ( n ) = 1 A ( n ) + C ( n ) = n \begin{aligned} A(n) &=2^{m} \\ A(n)-B(n)-C(n) &=1 \\ A(n)+C(n) &=n \end{aligned} A(n)A(n)−B(n)−C(n)A(n)+C(n)=2m=1=n
这就是前面的我们使用观察法弄出来的公式。而在这里我们是用的一种方法论的东西。我们用特殊 α , β , γ \alpha,\beta,\gamma α,β,γ来求出参数 A ( n ) , B ( n ) , C ( n ) A(n),B(n),C(n) A(n),B(n),C(n).这种方法，对于解是线性参数的线性组合的方式更有效 f ( n ) = A ( n ) α + B ( n ) β + C ( n ) γ f(n)=A(n)\alpha+B(n)\beta+C(n)\gamma f(n)=A(n)α+B(n)β+C(n)γ。
binary solution
那么对于一般的形式我们可不可以有类似二进制的解？答案是肯定的。我们可以这么来变换形式
f ( 1 ) = α f ( 2 n + j ) = 2 f ( n ) + β j , for j = 0 , 1 and n ⩾ 1 \begin{aligned} f(1) &=\alpha \\ f(2 n+j) &=2 f(n)+\beta_{j}, \quad \text { for } j=0,1 \text { and } \quad n \geqslant 1 \end{aligned} f(1)f(2n+j)=α=2f(n)+βj, for j=0,1 and n⩾1
其中， β 0 = β , β 1 = γ \beta_0=\beta,\beta_1=\gamma β0=β,β1=γ.
f ( ( b m b m − 1 , … b 1 b 0 ) 2 ) = 2 f ( ( b m b m − 1 … b 1 ) 2 ) + β b 0 = 4 f ( ( b m b m − 1 ⋅ ⋅ b 2 ) 2 ) + 2 β b 1 + β b 0 = 2 m f ( ( b m ) 2 ) + 2 m − 1 β b m − 1 + ⋯ + 2 β b 1 + β b 0 = 2 m α + 2 m − 1 β b m − 1 + ⋯ + 2 β b 1 + β b 0 \begin{aligned} f\left(\left(b_{m} b_{m-1}, \ldots b_{1} b_{0}\right)_{2}\right) &=2 f\left(\left(b_{m} b_{m-1} \ldots b_{1}\right)_{2}\right)+\beta_{b_{0}} \\ &=4 f\left(\left(b_{m} b_{m-1} \cdot \cdot b_{2}\right)_{2}\right)+2 \beta_{b_{1}}+\beta_{b_{0}} \\ &=2^{m} f\left(\left(b_{m}\right)_{2}\right)+2^{m-1} \beta_{b_{m-1}}+\cdots+2 \beta_{b_{1}}+\beta_{b_{0}} \\ &=2^{m} \alpha+2^{m-1} \beta_{b_{m-1}}+\cdots+2 \beta_{b_{1}}+\beta_{b_{0}} \end{aligned} f((bmbm−1,…b1b0)2)=2f((bmbm−1…b1)2)+βb0=4f((bmbm−1⋅⋅b2)2)+2βb1+βb0=2mf((bm)2)+2m−1βbm−1+⋯+2βb1+βb0=2mα+2m−1βbm−1+⋯+2βb1+βb0
注意当是二进制的时候，我们的 α , β i \alpha,\beta_i α,βi都需要是0或1。如果我们允许 α , β i \alpha,\beta_i α,βi
超越0,1我们就可以写成以下形式
f ( ( b m b m − 1 . . . b 1 b 0 ) 2 ) = ( α β b m − 1 β b m − 2 … β b 1 β b 0 ) 2 f\left(\left(b_{m} b_{m-1}... b_{1} b_{0}\right)_{2}\right)=\left(\alpha \beta_{b_{m-1}} \beta_{b_{m-2}} \ldots \beta_{b_{1}} \beta_{b_{0}}\right)_{2} f((bmbm−1...b1b0)2)=(αβbm−1βbm−2…βb1βb0)2
extend the previous extension
我们现在来看更为一般的扩展
f ( j ) = α j , for 1 ⩽ j < d f ( d n + j ) = c f ( n ) + β j , for 0 ⩽ j < d and n ⩾ 1 \begin{aligned} f(j)=\alpha_{j}, & \text { for } 1 \leqslant j<d \\ f(d n+j)=c f(n)+\beta_{j}, & \text { for } 0 \leqslant j<d \text { and } n \geqslant 1 \end{aligned} f(j)=αj,f(dn+j)=cf(n)+βj, for 1⩽j<d for 0⩽j<d and n⩾1
按照相同的逻辑，我麽可以推出。
f ( ( b m b m − 1 … b 1 b 0 ) d ) = ( α b m β b m − 1 β b m − 2 … β b 1 β b 0 ) c f\left(\left(b_{m} b_{m-1} \ldots b_{1} b_{0}\right)_{d}\right)=\left(\alpha_{b_{m}} \beta_{b_{m-1}} \beta_{b_{m-2}} \ldots \beta_{b_{1}} \beta_{b_{0}}\right)_{c} f((bmbm−1…b1b0)d)=(αbmβbm−1βbm−2…βb1βb0)c
这是最后我们得到的结论。可见从最初的问题，我们一层一层的扩展。最终得出上面这个等式。这是非常有趣的结果。
The End
现在，我们最终得到公式是具有非常一般性的结论。大家有兴趣的可以反复读读具体数学[1]这个部分的内容。非常精彩。
References
[1] Ronald L. Graham, Donald E. Knuth, O. P. (n.d.). Concrete
mathematics. In Concrete. page(8-16)
这篇关于具体数学--围圈杀人游戏的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
