汉诺塔
汉诺塔II hdu1207：
先说汉若塔I（经典汉若塔问题），有三塔，A塔从小到大从上至下放有N个盘子，现在要搬到目标C上，
规则小的必需放在大的上面，每次搬一个，求最小步数。这个问题简单，DP：a[n]=a[n-1]+1+a[n-1],先把
上面的n-1个放在B上，把最大的放在目标C上，再把N-1个放回到C上即可。
网上的一种最优解法如下：（1）将x(1<=x<=n)个盘从a柱依靠b,d柱移到c柱，这个过程需要的步数为F[x];（2）将a柱上剩下的n-x个盘依靠b柱移到d柱（注：此时不能够依靠c柱，因为c柱上的所有盘都比a柱上的盘小）些时移动方式相当于是一个经典汉诺塔，即这个过程需要的步数为2^(n-x)-1（证明见再议汉诺塔一）；（3）将c柱上的x个盘依靠a,b柱移到d柱上，这个过程需要的步数为F[x];第（3）步结束后任务完成。故完成任务所需要的总的步数F[n]=F[x]+2^(n-x)-1+F[x]=2*F[x]+2^(n-x)-1;但这还没有达到要求，题目中要求的是求最少的步数，易知上式，随着x的不同取值，对于同一个n，也会得出不同的F[n]。即实际该问题的答案应该min{2*F[x]+2^(n-x)-1},其中1<=x<=n;在用高级语言实现该算法的过程中，我们可以用循环的方式，遍历x的各个取值，并用一个标记变量min记录x的各个取值中F[n]的最小值。
#include"stdio.h"#include"string.h"#include"math.h"#define N 66#define Inf 0x7fffffffint main(){__int64 i,j,min,f[N]={0,1,3};;for(i=3;i<N;i++){min=Inf;for(j=1;j<i;j++){if(min>2*f[j]+pow(2.0,1.0*i-j)-1) //pow的返回值会超出64位，不能强制转换为整数min=2*f[j]+pow(2.0,1.0*i-j)-1; //注意两个参数应该都为double型！！}f[i]=min;}while(scanf("%I64d",&i)!=-1){printf("%I64d\n",f[i]);}return 0;}
汉若塔III hdu2064：
先把上面的N-1个移动到C(必然有这个状态)，在把最大的移到B，再把N-1移到到A，把最大的移到C，再把N-1个移到C。
递推公式：f[n]=f[n-1]+1+f[n-1]+1+f[n-1]; 即f[n]=3*f[n-1]+2;
#include"stdio.h"#include"string.h"#include"math.h"#define N 36int main(){__int64 n,i,f[N]={2};for(i=1;i<N;i++){f[i]=3*f[i-1]+2;}while(scanf("%I64d",&n)!=-1){printf("%I64d\n",f[n-1]);}return 0;}
汉若塔IV HDU 2077
在汉若塔3的基础上，改条件：允许最大的盘子放到最上面（只允许最大的放在最上面）当然最后需要的结果还是盘子从小到大排在最右边。
A,B,C三个塔，方程：ans[n]=ab[n-1]+1+1+bc[n-1]. (ab表示a到b)
DP思路：先把n-1个搬到b,再用俩步般最大的到C，再把n-1个从B到C。这里又要求出ac[n]和bc[n]：求其递推方程：bc[n]=bc[n-1]+1+ac[n-1]，（1式）
会发现bc[n]方程和ab[n]一样的。所以总方程ans[n]=2*bc[n-1]+2. （2式）
#include"stdio.h"#include"string.h"#include"math.h"#define N 21int main(){int i,T;__int64 ac[N],bc[N],ans[N];ac[1]=2;bc[1]=1;for(i=2;i<N;i++){ac[i]=3*ac[i-1]+2;bc[i]=bc[i-1]+ac[i-1]+1;ans[i]=2*bc[i-1]+2;}ans[1]=2;scanf("%d",&T);while(T--){scanf("%d",&i);printf("%I64d\n",ans[i]);}return 0;}
汉若塔V HDU1995
在经典汉若塔问题上附加问题：求出N个盘子时，第K号盘子的移动次数。
思路，一想就是二维DP，DP[n][i]=dp[n-1][i]*2(1=<i<n),dp[n][n]=1;
最大盘只移动一次，上面盘子先移到B塔，一次，最后由B到目标C又一次.。
#include"stdio.h"#include"string.h"#include"math.h"#define N 61int main(){__int64 i,j,f[N][N];f[1][1]=f[2][2]=1;f[2][1]=2;for(i=3;i<N;i++){f[i][i]=1;for(j=1;j<i;j++){f[i][j]=2*f[i-1][j];}}int T,n,m;scanf("%d",&T);while(T--){scanf("%d%d",&n,&m);printf("%I64d\n",f[n][m]);}return 0;}
汉若塔VI HDU1996
每个盘从小到大每个都有3种选择，共3^n。
#include"stdio.h"#include"string.h"#include"math.h"#define N 61int main(){int T,n;scanf("%d",&T);while(T--){scanf("%d",&n);printf("%.0f\n",pow(3.0,n*1.0));}return 0;}
