四根汉诺塔问题依靠三根汉诺塔问题来求解,多了一种选择,可以一开始选择j根块随机移出去,然后剩下的i-j根变成了三根柱子的汉诺塔问题。
f表示四根柱子的最少移动次数,d表示三根柱子的最少移动次数。
三根柱子的汉诺塔问题求解是,将i-1块移到另一根,将最后一块移到目标柱子,将剩下n-1块移到目标,总共f[i]=f[i-1]*2+1
#include<iostream>
#include<cstring>
using namespace std;
const int N=15;
//分别表示四根柱子和三根柱子的最少移动数量
int f[N],d[N];
int main(){
d[1]=1;
for(int i=2;i<=12;i++){
d[i]=d[i-1]*2+1;
}
memset(f,0x3f,sizeof f);
f[1]=1;
for(int i=2;i<=12;i++){
for(int j=1;j<i;j++){
f[i]=min(f[i],f[j]*2+d[i-j]);
}
}
for(int i=1;i<=12;i++) cout<<f[i]<<endl;
return 0;
}