汉诺塔问题的递推关系式是什么?四根柱子时怎样?
哪些公司问过
答案要点
- 递推式 f(n) = 2f(n-1) + 1,边界 f(1) = 1(或 f(0) = 0)
- 推导:先移走上面 n-1 个,再移最大盘,最后把 n-1 个移回
- 通项 f(n) = 2^n - 1,可由归纳法证明
- 最少性:最大盘至少移动一次,此时其余盘必须全在第三根柱上
- 递归实现时间复杂度 O(2^n),递归深度 n
易错点
- 把递推式写成 f(n) = 2f(n-1),漏掉移动最大盘的那一步
- 边界条件写错导致通项不符
- 四柱时直接套用三柱公式
面试官常见追问
- 如果有 4 根柱子会怎样?
- 能否不用递归实现?
- 64 个盘子需要多少步?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。