面试题库 › C++ / 后端 › 汉诺塔问题的递推关系式是什么?四根柱子时怎样?

汉诺塔问题的递推关系式是什么?四根柱子时怎样?

难度 ★★☆在 2 场真实面经中被问到 方向:C++ / 后端

哪些公司问过

快手13601

常见岗位:机器学习算法(泛)、C/C++ 软件开发

答案要点

  1. 递推式 f(n) = 2f(n-1) + 1,边界 f(1) = 1(或 f(0) = 0)
  2. 推导:先移走上面 n-1 个,再移最大盘,最后把 n-1 个移回
  3. 通项 f(n) = 2^n - 1,可由归纳法证明
  4. 最少性:最大盘至少移动一次,此时其余盘必须全在第三根柱上
  5. 递归实现时间复杂度 O(2^n),递归深度 n

易错点

面试官常见追问

完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。