题目大意

　　解有四个塔的汉诺塔问题，并输出1~12个塔时的最少移动步数

题目分析

　　设f[i]为有i个圆盘，四个塔时的最少移动步数，d[i]为有i个圆盘，三个塔时的最少移动步数。

　　先来求d数组：

　　d<=1时：d[0]=0,d[1]=1；

　　d>=2时：d[i]=d[i-1]*2+1;

　　证明：有i个盘子时，先花费d[i-1]的时间把i-1个盘子移到B柱上，然后花费1的时间把最后一个盘子从A柱移到C柱，然后再花费d[i-1]的时间把i-1个盘子从B柱上移到C柱上；所以d[i]=d[i-1]*2+1；

　　然后考虑f数组：

　　i==1时：f[1]=1;

　　i>=2时：f[i]=min(f[i],f[j]*2+d[i-j])(1<=i<=12，1<=j<i)

　　证明：有i个盘子时，花费f[j]的时间把A塔上的j个盘子移到B塔上(余下的A、C、D三根柱子形成一个三塔的子问题)，然后花费d[i-j]把A柱上剩余的i-j个圆盘移到D柱上(又恢复为A,B,C,D四塔问题)，最后花费f[j]的时间把B柱上的j个圆盘放置在D塔上，所以f[i]=min(f[i],f[j]*2+d[i-j])(1<=i<=12，1<=j<i)；

Code

#include<iostream>
#include<cstring>
#include<cstdio>
#define sco 20
using namespace std;
int d[sco],f[sco];
int main(){
    memset(d,127,sizeof(d));
    memset(f,127,sizeof(f));
    d[1]=f[1]=1;
    for(int i=2;i<=12;++i)d[i]=d[i-1]*2+1;
    for(int i=1;i<=12;++i){
        for(int j=1;j<i;++j){
            f[i]=min(f[i],f[j]*2+d[i-j]);
        }
        printf("%d\n",f[i]);
    }
    return 0;
}

YBTOJ：奇怪汉诺塔