一、问题背景
汉诺塔(Tower of Hanoi)是经典的递归算法问题,源于一个古老的传说。游戏规则:
- 一次只能移动一个圆盘
- 大圆盘不能放在小圆盘上面
- 所有圆盘从起始柱移动到目标柱
二、算法原理
采用分治思想将问题分解:
- 将n-1个盘子从起始柱移到辅助柱(子问题)
- 将第n个盘子从起始柱移到目标柱(直接操作)
- 将n-1个盘子从辅助柱移到目标柱(子问题)
三、关键点解析
四、完整代码
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
*
*
* @param n int整型
* @return string字符串vector
*/
vector<string> getSolution(int n) {
vector<string> moves;
hanoi(n, "left", "right", "mid", moves);
return moves;
}
// 递归实现汉诺塔移动步骤
// n: 当前要移动的盘子数量
// from: 起始柱子
// to: 目标柱子
// aux: 辅助柱子
// moves: 存储移动步骤的数组
void hanoi(int n, string from, string to, string aux, vector<string>& moves) {
if (n == 1) {
// 基础情况:只有一个盘子时直接移动
moves.push_bACk("move from " + from + " to " + to);
return;
}
// 第一步:将n-1个盘子从起始柱移到辅助柱
hanoi(n - 1, from, aux, to, moves);
// 第二步:将第n个盘子从起始柱移到目标柱
moves.push_back("move from " + from + " to " + to);
// 第三步:将n-1个盘子从辅助柱移到目标柱
hanoi(n - 1, aux, to, from, moves);
}
};
五、示例演示
当n=3时的移动步骤:
- left → right
- left → mid
- right → mid
- left → right
- mid → left
- mid → right
- left → right
六、扩展思考
七、常见误区
- 忽视递归终止条件导致无限循环
- 混淆三个柱子的角色转换
- 错误估计时间复杂度