汉诺塔的移动次数与移动步骤
哪些公司问过
3601乐易游戏1
答案要点
- 最少移动次数 2^n-1,递推式 T(n)=2T(n-1)+1,T(1)=1
- 递归三步:n-1 个从起点移到辅助柱,最大盘移到目标柱,n-1 个从辅助柱移到目标柱
- 终止条件 n==1 直接移动(或 n==0 返回),每次移动时打印起点和终点
- 时间复杂度 O(2^n),递归栈空间 O(n)
易错点
- 递归调用时把辅助柱和目标柱参数顺序写反
- 把移动次数说成 2^n 或 n^2
- 忽略 n 很大时结果规模指数爆炸、输出不可行
面试官常见追问
- 汉诺塔的递推关系式是什么,怎么推出 2^n-1?
- 能不用递归实现吗?
- 如何只求第 k 步移动的是哪个盘?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。