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

原文链接：

具体数学-第1课 - WeiYang Bloggodweiyang.com

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

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

汉诺塔问题

这是个老生常谈的问题了，n个盘子，3个柱子的汉诺塔问题，最少移动次数记为

。 那么

边界条件为

。 解出

验证可以采用数学归纳法，这里就不多说了。

直线分割平面问题

这也是个高中问题了，n条直线最多分割平面为几部分，记为

。 那么

边界条件为

。 解出

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

如上图所示，将V型补全（红色虚线部分），那么就转化为了

条直线划分平面数，那么n个V型划分数只要减去

就行了，所以答案为：

约瑟夫环问题

这个问题暴力求解的话模拟就行了，复杂度是

的，这里探索一种直接求解的方法。 分两种情况讨论： 当有

个人时，踢掉

个人之后，情况如下图所示

观察对应关系可以得出

同理，当有

个人时，踢掉

个人之后，情况如下图所示

观察对应关系可以得出

边界条件为

这个递推式很难求解，但是枚举出前面几项可以发现，如果令

，其中

是小于等于

的最大2的幂，那么

正确性可以通过数学归纳法求证。

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