Question

4层汉诺塔15步解法

Answer 1

算法步骤

三阶汉诺塔问题解题步骤

共需7步。

四阶汉诺塔问题解题步骤

共需15步

五阶汉诺塔问题解题步骤

算法采用了分治的思想，利用递归的方式，完成n层汉诺塔的移动。

汉诺塔问题的非递归算法

汉诺塔问题也可以借助非递归算法来解决，有许多种非递归算法可以解决汉诺塔问题，博主认为最常见的是利用递归二叉树，下面列举两种非递归算法。

1.利用二叉递归树

文献[4]指出：汉诺塔问题的递归算法代码与二叉树的中序遍历算法代码十分相似，故采用了二叉树的中序遍历，发现汉诺塔问题的算法步骤正好可以画成一棵完全二叉树，其中序遍历过程就是汉诺塔问题的算法步骤。

函数move(N-1,s,e,t)  N:盘子数  ，s:起始桩   e:目标桩   t:过渡桩