汉诺塔Ⅲ

题目说要求所需的最大步数，先举n=1时候的例子，很明显就是先跳到中间那个柱子上，再跳到第三个柱子上，只需要两步，从这里就可以得出我们是依靠中间那个塔来增加我们的步数。
那如果n=2呢，结果如下图

其实把这两个盘看成一个整体，我们也就是把他运到了中间那个柱子上（第四步），然后再运到右边那个柱子上（第八步）。
再看n=3的时候，结果如下图

我们再移动上面两个盘的时候，就可以将其视为一个整体，就可以发现在1 2两步的时候和n=2的时候的第4步和第8步是一样的（把最下面那个最大的盘忽略了，再来看图就很容易看出来了），也就是说明n=3的时候的1 2两步的步数和n=2的时候的总步数是一样的，如图下去，我们移动最下面一个盘的时候当然只需要一步，再以此类推，发现a[3]=3 *a[2]+2。
那么其实到这里递推式也很明显了，n=4的时候，也就是把n=3的时候将视为整体的两个盘变为三个盘，递推式也就是a[n]=3 *a[n-1]+2。

所以学到这里，递推其实并没有想象的这么难，只可能是因为做到的题目比较少，每次看到新的题目的时候就会毫无头绪，但其实很大一部分递推的题目都是一个意思，无非就是将上一步的结果视为整体用到下一步，递推并没有想象的这么难吧，我一开始对递推也是毫无头绪的捏，题目写多了就会啦，虽然期末考可能并不能写到第七题第八题的样子，但是现在了解递推的规律和中心思想，早晚都会用到的。

#include<stdio.h>
int main()
{
    int n, sum, t, i, j, m, r, sum1, sum2, max;
    while (scanf("%d", &t) != EOF)
    {
        sum = 2;
        for (i = 1; i < t; i++)
        {
            sum = sum * 3 + 2;
        }
        printf("%d\n", sum);
    }
    return 0;
}