具体数学-第1课(递归求解实际问题)
原文链接:
具体数学-第1课 - WeiYang Blog这学期提前选修了研究生的课程:具体数学、人工智能前沿、NLP讨论班,就随便记记具体数学每一节课所学的东西吧。
第一节课讲的都是一些很简单的东西,这里就一带而过了。
汉诺塔问题
这是个老生常谈的问题了,n个盘子,3个柱子的汉诺塔问题,最少移动次数记为 。
那么
边界条件为 。
解出
验证可以采用数学归纳法,这里就不多说了。
直线分割平面问题
这也是个高中问题了,n条直线最多分割平面为几部分,记为 。
那么
边界条件为 。
解出
这题有个扩展,n个V型最多分割平面为几部分?
解决思路如下:
如上图所示,将V型补全(红色虚线部分),那么就转化为了 条直线划分平面数,那么n个V型划分数只要减去 就行了,所以答案为:
约瑟夫环问题
这个问题暴力求解的话模拟就行了,复杂度是 的,这里探索一种直接求解的方法。
分两种情况讨论:
当有 个人时,踢掉 个人之后,情况如下图所示
观察对应关系可以得出
同理,当有 个人时,踢掉 个人之后,情况如下图所示
观察对应关系可以得出
边界条件为
这个递推式很难求解,但是枚举出前面几项可以发现,如果令 ,其中 是小于等于 的最大2的幂,那么
正确性可以通过数学归纳法求证。
第一节课就讲了这么多,约瑟夫环还有很多问题值得探讨,下节课继续。。。
算法码上来 文章被收录于专栏
公众号「算法码上来」。godweiyang带你学习算法,不管是编程算法,还是深度学习、自然语言处理算法都一网打尽,更有各种计算机新鲜知识和你分享。别急,算法码上来。