JavaScript 解决汉诺塔问题算法

汉诺塔问题描述：

现有三根柱子a、b、c，a 柱上套有若干个圆盘，这些圆盘大小各异，按从大到小的顺序自下而上摆放，如下图所示。现在要把套在 a 柱子上的圆盘全部转移到 c 柱上，并且在移动圆盘时必须遵守以下规则：
1、一次只能移动柱子最上端的一个圆盘
2、小圆盘上不能放大圆盘
将一个圆盘从一根柱子移到另一根柱子，算移动“1次”，那么，将若干个圆盘全部从 a 移到 c 最少需要移动几次呢?

汉诺塔

解决此问题需要借助栈的知识，如下：

栈

引入创建好的 Stack 类。

通过分析可知，这是一种递归，通过栈实现如下：

/** 
 * @param {圆盘数：number} plates 
 * @param {起始柱子 a：string} source 
 * @param {辅助柱子 b：string} helper 
 * @param {目标柱子 c：string} dest 
 * @param {移动步骤集：Array，数组的长度就是移动的次数} moves 
 */
function hanoi(plates, source, helper, dest, moves = []) {
    if (plates <= 0) {
        return moves;
    }
    if (plates === 1) {
        moves.push([source, dest]);
    } else {
        hanoi(plates - 1, source, dest, helper, moves);
        moves.push([source, dest]);
        hanoi(plates - 1, helper, source, dest, moves);
    }
    return moves;
}

// test
console.log(hanoi(4, 'source', 'helper', 'dest')); // 输出结果如下图展示

4个圆盘的汉诺塔移动结果展示