汉诺塔

晚上休息的时候，旁边的哥们在玩原神。本来一切都应该平静度过的，直到他在原神中遇到了汉诺塔问题。

打程序设计竞赛的我们当然对这个问题再熟悉不过了。这个经典的可以用递推/递归/动态规划…解决的问题。

题目如下

题目

汉诺塔（又称河内塔）问题是源于印度的一个古老传说。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着 64 片黄金圆盘。大梵天 命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一 根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱 子之间一次只能移动一个圆盘。 现在如果告诉你金片的数目 n，并按以上要求移动金片并完成任务，你能计算出需要移动金片多少次吗？

作为ACMer的我们想要用最优解来解决汉诺塔问题，不过求解最优解的步数对我们来讲易如反掌，真正做这个步骤居然有点卡了。

所以，汉诺塔问题的最优解具体该怎么操作呢？

我们先来看看最优解的步数是怎么来的：

首先当n为1时很明显步数是1，直接移动过去就可以了。

当n=2时，则相当于需要把上面的1移动到中间，再把下面的2移动到最右边，然后再移动1到右边，总步数=1+1+1=3。

当n=3时，同样利用上面的思想，此时相当于要把3上面的1、2移动到中间，再把下面的3移动到右边，再把中间的1、2移动到右边。很明显把1、2移动到任何一个地方都是3步（上面已经计算过），当此时总步数=3+1+3 = 7。

…

注意上面我们用了递推与分治的思想，只要n>2，我就可以把问题拆分成把上面n-1个圆盘移动到中间和把最下面的移动到最右边。我们不用关心已经解决的问题的细节，只要利用它的结果就能递推出任意n的最优解步数。递推公式

fn=2∗fn−1+1。

为什么这样是最优的呢，因为这种方法下我们的每一步都是在为达到目的做贡献，没有多余的一步。另外，每一步的前一步都是最优解，由此递推的下一步同样也是最优解。

知道了这个最优解的求解过程，想要实现最优解也不难了。对于人脑来讲，这是一个递归问题，考虑如下图的问题：

自上而下的思考：要把5个圆盘移动到最右边，也就是要把最上面的4个圆盘先移动到中间，此时问题变为n=4，我们继续向下思考,n=4时相当于先把上面三个移动到右边（为什么是右边，因为我们要把4个圆盘移动到中间），此时问题规模变为n=3，继续向下直到n=1时便可以开始操作从而回归问题规模了。接下来的操作就很清晰了：每次都把问题拆分成更易于解决的子问题求解。因为过程比较繁琐我就不画图了。

由此，不断的分解问题，你就可以通过最少的步数解决汉诺塔问题了，这个方法很好理解也很好实施，快去试试吧！不过你大脑那点内存可能会递归过深…毕竟当n稍微大一点的时候，最优步数的数字是巨大的。