具体数学-第1课(递归求解实际问题)

关注公众号【算法码上来】,每日算法干货马上就来!

这学期提前选修了研究生的课程:具体数学、人工智能前沿、NLP讨论班,就随便记记具体数学每一节课所学的东西吧。

第一节课讲的都是一些很简单的东西,这里就一带而过了。

汉诺塔问题


这是个老生常谈的问题了,n个盘子,3个柱子的汉诺塔问题,最少移动次数记为$T(n)$。
那么\[T(n)=2T(n-1)+1\]
边界条件为$T(0)=0$。
解出\[T(n)=2^n-1\]
验证可以采用数学归纳法,这里就不多说了。

直线分割平面问题


这也是个高中问题了,n条直线最多分割平面为几部分,记为$L(n)$。
那么\[L(n)=L(n-1)+n\]
边界条件为$L(0)=1$。
解出\[L(n)=n(n+1)/2+1\]

这题有个扩展,n个V型最多分割平面为几部分?
解决思路如下:

如上图所示,将V型补全(红色虚线部分),那么就转化为了$2n$条直线划分平面数,那么n个V型划分数只要减去$2n$就行了,所以答案为:
\[Z(n)=L(2n)-2n=2n^2-n+1\]

约瑟夫环问题


这个问题暴力求解的话模拟就行了,复杂度是$O(n^2)$的,这里探索一种直接求解的方法。
分两种情况讨论:
当有$2n$个人时,踢掉$n$个人之后,情况如下图所示

观察对应关系可以得出
\[J(2n)=2J(n)-1\]
同理,当有$2n+1$个人时,踢掉$n+1$个人之后,情况如下图所示

观察对应关系可以得出
\[J(2n+1)=2J(n)+1\]
边界条件为
\[J(1)=1\]
这个递推式很难求解,但是枚举出前面几项可以发现,如果令$n=2^m+l$,其中$2^m$是小于等于$n$的最大2的幂,那么
\[J(n)=2l+1\]
正确性可以通过数学归纳法求证。

第一节课就讲了这么多,约瑟夫环还有很多问题值得探讨,下节课继续。。。


   转载规则


《具体数学-第1课(递归求解实际问题)》 韦阳 采用 知识共享署名 4.0 国际许可协议 进行许可。
 上一篇
具体数学-第2课(成套方法求解递归式) 具体数学-第2课(成套方法求解递归式)
关注公众号【算法码上来】,每日算法干货马上就来! 今天主要讲了关于递推式和求和的一些方法,主要是成套方法。 约瑟夫环推广上一节课说到,约瑟夫环问题的解是\[f(n) = 2l + 1\]其中$n = {2^m} + l$将$n$写成二
2018-03-05
下一篇 
毕业论文代码实现思路 毕业论文代码实现思路
关注公众号【算法码上来】,每日算法干货马上就来! 一个寒假就写了个基本的代码,难受啊,整理一下思路吧,好久不看代码头都大了。 数据预处理 首先使用的是PTB数据集,原始的数据是长这样的:(S (NP-SBJ (NNP Ms.) (NN
2018-02-26
  目录