牛客网NC67汉诺塔问题:递归算法解析(附完整C++代码)
一、问题背景
汉诺塔(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
六、扩展思考
七、常见误区
忽视递归终止条件导致无限循环
混淆三个柱子的角色转换
错误估计时间复杂度
原创内容 转载请注明出处