递归

具体数学第一章通过三个例子由易到难给我们描绘了递归的思想。

汉诺塔

给定nn个圆盘组成的塔,圆盘按照大小递减的方式套在三根柱子中的一根上。要求移动的过程中较大的圆盘不能放置在较小的圆盘上,求最优解法次数。

我们引入如下记号:
Tn{T_n}:将nn个圆盘从一根柱子移动到另一根的最少移动次数,显然T0=0,T1=1{T_0=0,T_1=1}
移动3个圆盘的获胜思路,是首先将两个圆盘移动到中间,然后移动第三个圆盘,最后再移动剩下的两个放到它上面。
同理,我们可以将这种思想推理到nn
首先把n1n-1个小的圆盘移动到一个不同的柱子上,需要Tn1T_{n-1}次移动
然后移动最大圆盘,需要1次
最后再把那n1n-1个小圆盘移到最大圆盘上,需要Tn1T_{n-1}次移动。
这样最多需要2Tn1+12T_{n-1}+1次,即

Tn2Tn1+1,(n>0){T_n}{\quad}{\leq}{\quad}{2T_{n-1}+1} ,(n>0)

同时我们从里一个方面思考:
我们迟早必须移动最大的那个圆盘,当我们做这步时,那n1n-1个小圆盘已经在某根柱子上了,说明我们已经至少花了Tn1T_{n-1}次移动,如果不是最优移动,我们移动最大盘的时候可能会多于1次,移动完最大盘之后,还需要把剩下的n1n-1个圆盘移到最大盘之上,也需要Tn1T_{n-1}次移动,从而我们得到

Tn2Tn1+1,(n>0){T_n}{\quad}{\geq}{\quad}{2T_{n-1}+1} ,(n>0)

结合起来,我们得到递归式:

T0=0Tn=2Tn1+1,(n>0)T_0=0 \\ T_n=2T_{n-1}+1,(n>0)

经过找规律我们可以得到最终的表达式:

Tn=2n1,(n0)T_n=2^n-1,(n\geq0)

我们可以用数学归纳法简单证明它是正确的
T0=201T_0=2^0-1,假设Tn1T_{n-1}成立,对n>0n>0
Tn=2Tn1+1=2(2n11)+1=2n1T_n=2T_{n-1}+1=2(2^{n-1}-1)+1=2^n-1

平面上的直线

直线划分区域

每次增加一条直线,最多增加n1n-1个交点,也就是nn个区域
L0=1Ln=Ln1+nL_0=1,L_n=L_{n-1}+n
根据递归式累加求和可得最终结论Ln=n(n+1)2+1n0L_n=\frac{n(n+1)}{2}+1,n\geq0
LINE

折线划分区域

推法一:
每次增加折线,相当于将22倍的直线交叉相消,也就是每个折线看成是两条直线,但是少了一半。因此每一条折线比两条直线分割的面的部分少22
Zn=L2n2n=2n2n+1n0Z_n=L_{2n}-2n=2n^2-n+1,n\geq0
推法二:
交点决定了射线和线段的条数,进而决定了新增的区域数。当有n1n-1条折线时,假设区域数为Zn1Z_{n-1}。为了使增加的区域最多,则折线的两边的线段要和n1n-1条折线的边,即2(n1)2(n-1)条线段相交。线段数也就增加4(n1)4(n-1),区域数也就增加4(n1)+24(n-1)+2,但要注意的是,折线本身相邻的两线段只能增加一个区域。所以最终的区域增加数为4n34n-3
所以递推式为
Zn=Zn1+4n3Z_n=Z_{n-1}+4n-3 化简的最终结果也和上面一样。
LINE2
斜线划分区域

约瑟夫环

从围成标有记号11nn的圆圈,每隔一个删去一个人,求最后留下来的是几号。

首先我们分奇偶性考虑得出一下两个结论:

偶数时:留下奇数序号下的人,场上人数缩小一半,变为奇数
偶数是:留下出来1之外的奇数序号下的人,场上人数缩小一半,变为偶数

第二点我们可以发现新下标编号和老下表编号的关系(见下图蓝红色下标):

fold=2fnew1f_{old}=2f_{new}-1, 场上人数为偶数变为奇数时
fold=2fnew+1f_{old}=2f_{new}+1, 场上人数为奇数变为偶数时

结合以上两点,我们可以根据初始编号以及人数反推回原始编号,从而得出递归表达式:

J1=1J_1=1
J2n=2Jn1n1J_{2n}=2J_{n}-1,n\ge1
J2n+1=2Jn+1n1J_{2n+1}=2J_{n}+1,n\ge1
Josephus

递归代码:
    public static Integer ans = 1;
    public static Integer Joseph(Integer n){
        if(n == 1){
            return ans;
        }else{
            if(n % 2 == 0){
                ans = 2 * Joseph(n / 2) - 1;
            }else{
                ans = 2 * Joseph(n / 2) + 1;
            }
        }
        return ans;
    }
nn 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
JnJ_{n} 1 1 3 1 3 5 7 1 3 5 7 9 11 13 15 1
同时我们可以进一步求出递推式:

n=2m+ln=2^m+l
J(2m+l)=2l+1,m0,01<2mJ(2^m+l)=2l+1,m{\ge}0,0{\le}1<2^m

再更近一步从位运算的角度思考:

n=(bmbm1b1b0)2n=(b_mb_{m-1}{\cdots}b_1b_0)_2
n=2m+ln=2^m+lbmb_m位为1,即:
n=(1bm1b1b0)2n=(1b_{m-1}{\cdots}b_1b_0)_2
l=(0bm1b1b0)2l=(0b_{m-1}{\cdots}b_1b_0)_2
22倍对应位运算中左移一位
2l=(bm1b1b00)22l=(b_{m-1}{\cdots}b_1b_00)_2
2l+1=(bm1b1b01)22l+1=(b_{m-1}{\cdots}b_1b_01)_2
J(n)=(bm1b1b0bm)2J(n)=(b_{m-1}{\cdots}b_1b_0b_{m})_2
也就是最终证明了:
J((bmbm1b1b0)2)=(bm1b1b0bm)2J((b_mb_{m-1}{\cdots}b_1b_0)_2)=(b_{m-1}{\cdots}b_1b_0b_{m})_2
也就是nn向左循环移动一位得到JnJ_n

Q.E.D.