面试题库 › 算法 / 大模型 › 汉诺塔的移动次数与移动步骤

汉诺塔的移动次数与移动步骤

难度 ★☆☆在 2 场真实面经中被问到 方向:算法 / 大模型考点:贪心与回溯

哪些公司问过

3601乐易游戏1

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

答案要点

  1. 最少移动次数 2^n-1,递推式 T(n)=2T(n-1)+1,T(1)=1
  2. 递归三步:n-1 个从起点移到辅助柱,最大盘移到目标柱,n-1 个从辅助柱移到目标柱
  3. 终止条件 n==1 直接移动(或 n==0 返回),每次移动时打印起点和终点
  4. 时间复杂度 O(2^n),递归栈空间 O(n)

易错点

面试官常见追问

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

相关面试题