迭代版 Hanoi 塔算法

February 08, 2019

递归版的 Hanoi 塔算法:

function hanoi(n, src, dst, tmp) {
  if (n > 0) {
    hanoi(n - 1, src, tmp, dst);
    console.log(`move disk ${n} from ${src} to ${dst}`);
    hanoi(n - 1, tmp, dst, src);
  }
}

这个递归形式像极了二叉树的中序遍历,

如上示意图,从根节点出发,往节点的“上面”分支走(同时将沿途节点入栈),走到没有上分支的节点结束。(此节点就位于整个示意图的最上面,即首先访问)从栈顶弹出此节点访问,转入此节点的下分支,然后再将这个下分支展开(展开后的最上面点即示意图从上往下第二的点)

栈中每个“节点”其实就是模拟一次函数调用。

从某节点获取上下分支的根节点:

const goUp = ({ n, src, dst, tmp }) => n > 1 && ({
  n: n - 1,
  src,
  dst: tmp,
  tmp: dst,
});

const goDown = ({ n, src, dst, tmp }) => n > 1 && ({
  n: n - 1,
  src: tmp,
  dst: dst,
  tmp: src,
});

算法如下,

function hanoi(n, src, dst, tmp) {
  const stack = [];
  let curr = { n, src, dst, tmp };
  while (true) {
    while (curr) {
      stack.push(curr);
      curr = goUp(curr);
    }
    if (stack.length === 0) {
      break;
    }
    const hn = stack.pop();
    console.log(`move disk ${hn.n} from ${hn.src} to ${hn.dst}`);
    curr = goDown(hn);
  }
}