Problem I: 汉诺塔Ⅲ
Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 483 Solved: 353
Description
汉诺塔（又称河内塔）问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。
那些智力题总是要求人们用最少的步骤完成题目中的要求。为什么非要最少呢？这次我们来点特别的，我希望你的程序能够用最多的步数达到要求，而且在此过程中不重复出现任何一种状态。
请联想曾经学过的汉诺塔知识。
Input
输入包含多组数据测试，每组数据只有圆盘数n( 1 <= n <= 12)
Output
对于每组数据输出符合条件的搬盘子的最多次数
Sample Input
1 3 12
Sample Output
2 26 531440
HINT
让我们先来回忆求最小步数的汉塔塔。
通过1个先推理，然后两个，写出每次步数增加的由来，在前两个中找到递推规律，然后到n个。分析n个时，上面n-1个看成整体，
即a[n-1],下面单独一个移动的时候加1.
下面我们来看最多步数（推理方法和最少步数是一样的）
通过同样的推理（不过这里是上面的n-1个整体方块尽可能乱走，这里自己要在纸上画下，很快就懂，不过注意不要动到大盘压小盘...别问我为什么这么说....555
规律是f[n]=3*f[n-1]+2;
下面是源代码：
#include<stdio.h>
long int a[20];
int main(void)
{
int n,i;
a[1]=2;
for(i=1;i<=12;i++)
{
a[i]=3*a[i-1]+2;
}
while(scanf("%d",&n)!=EOF)
{
printf("%ld\n",a[n]);
}
return 0;
}