汉诺塔问题
这是个老生常谈的问题了，n个盘子，3个柱子的汉诺塔问题，最少移动次数记为 
。
那么 
边界条件为 
。
解出 
验证可以采用数学归纳法，这里就不多说了。
直线分割平面问题
这也是个高中问题了，n条直线最多分割平面为几部分，记为 
。
那么 
边界条件为 
。
解出 
这题有个扩展，n个V型最多分割平面为几部分？
解决思路如下：
如上图所示，将V型补全（红色虚线部分），那么就转化为了 2n 条直线划分平面数，那么n个V型划分数只要减去 2n 就行了，所以答案为：
约瑟夫环问题
这个问题暴力求解的话模拟就行了，复杂度是 
的，这里探索一种直接求解的方法。
分两种情况讨论：
当有 2n 个人时，踢掉 n 个人之后，情况如下图所示
观察对应关系可以得出
同理，当有 2n+1 个人时，踢掉 n+1 个人之后，情况如下图所示
观察对应关系可以得出
边界条件为
这个递推式很难求解，但是枚举出前面几项可以发现，如果令 
，其中 
是小于等于 n 的最大2的幂，那么
正确性可以通过数学归纳法求证。
第一节课就讲了这么多，约瑟夫环还有很多问题值得探讨，下节课继续。。。
