【数学】一些递归问题模型

一些递归问题模型

汉诺塔

这里是三桩汉诺塔,设$T_n$为一根移动到另一根的最小步数。
显然最优解法就是:
先把$n-1$个小盘移到中间,然后移动大盘,最后再移动小盘,总花费$T_n=2T_{n-1}+1$
证明:
可以用归纳法,不过还有一个巧妙地证明:
给递归式两边加上$1$,然后证明就很显然了。

平面上的直线

设$L_n$为最大分割数。
第$n(n>0)$条直线使得区域数增加$k$个,当且仅当其对$k$个已有区域进行分割,而进行分割当且仅当其在$k-1$个不同区域与有前面$n-1$个不同的点,显然$k\leq n$,有

L_0=1\quad
L_n=L_{n-1}+n

证明:
归纳法或者将这个柿子展开,然后取前缀和,正反排列前缀和,然后就可以看到解了。

约瑟夫问题

显然有

J(1)=1\quad
J(2n)=2J(n)-1;n\geq 1\quad
J(2n+1)=2J(n)+1;n\geq 1\quad

递归式的解就是$J(2^m+l)=2l+1$,$2^m$为不超过$n$的最大值,$l$为其二之差。
也等于二进制循环移动

J((b_mb_{m-1}…b_1b_0)_2)=((b_{m-1}…b_1b_0b_m)_2)

发布者:Cinema

成功的道路并不狭窄,因为大部分人都在颓废。

留下评论

电子邮件地址不会被公开。 必填项已用*标注