汉诺塔问题--递归解决

1. 每次只能从一个柱子的最上面移动一个碟子到另外一个柱子上。

2. 不能将大碟子放到小碟子的上面。

问题是，如何在这样的移动规则得到最少的移动步数。

虽然这个问题看起来是一个很复杂的问题，但是，抽象出来，并没有想象中的那么难。

首先，三个柱子分别记为a,b,c，我们已知的条件（或称为分析思路）是：

1.第一个目标肯定是把最大的那个碟子放在c柱子上；

2.最后一步肯定是把最小的那个碟子放在c柱子上；

3.最开始，a柱子放着所有碟子，最终肯定是c柱子放着所有碟子，那么，b柱子的使命就是起到一个中转站的作用；

现在有了已知条件，开始分析问题，抽象数据。现在假设有n个碟子，abc三个柱子，将要移动S(n)步（最终想要的结果）。第一个入手点，就是把最大的那个碟子放在C柱子上。首先将n-1个碟子从a移动到b柱子上，然后将最下面的碟子移动到柱子c，最后再将n-1个碟子移动到c。它是s(n)的子问题，s(n-1)。在中间的过程，只是中转站不同而已，有时候是b，有时候是a，除了借助的柱子和目的柱子不一样，其他的都是一样的。这样我们就可以

那么，s(n)与s(n-1)之间的关系又是怎么样的呢？首先需要将a->b,n-1个碟子，然后b->c,n-1个碟子，最后把碟子移动到c上。

s(n-1)是两次，最后移动一次，因此得到一个这样的推导关系: S(n) = 2S(n - 1) +1。

    再考虑一种初始的情况，假定只有一个碟子需要移动，我们直接将碟子从a移动到c，那么需要的步骤是1步。因此可以说S(1) = 1。

最后用递归的方式解决这个问题。