三根柱子汉诺塔的递归求法

可以用来打印实际的盘子挪动过程

C++ 代码

’‘’
void func(int n,string from,string mid,string to)
{
//只有一个圆盘时，我们直接从from移动到to。
if(n==1)
{
cout<<(“move from “+from+” to “+to)<<endl;
ret++;
}
else{
//对于前N-1个圆盘来说，目标是“中间”,前N个圆盘的”to”变成这里的”mid”;
func(n-1,from,to,mid);
func(1,from,mid,to);
func(n-1,mid,from,to);
}
}

三根柱子的递推解法

C++ 代码

int func2(int n){
//当只有一个盘子的时候，可以直接放过去
dp[1]=1;
for(int i=2;i<=n;i++)
{
dp[i]=2*dp[i-1]+1;
}
return dp[n];
}

四根柱子的递推解法，思路需要记住，借助了求三根柱子的思路以及具体的求解值

’‘’

using namespace std;

const int N = 15;

int main()
{
//f数组定义有四根柱子时的操作数
//d数组定义有三根柱子时的操作数
int d[N], f[N];
d[1]=1;
for(int i=2;i<N;i++)
{
d[i]=2*d[i-1]+1;
}

memset(f, 0x3f, sizeof f);
//只有一个盘子的时候，不用移动
f[0] = 0;
for (int i = 1; i <= 12; i ++ )
    for (int j = 0; j < i; j ++ )
    //当我们放i个盘子的时候，对于前j个盘子，我们放它的时候可以随便放，即四根柱子每根都可以
    //但是当我们放j->i的(i-j)根柱子时，这时只能放在三根柱子上，因为(i-j)根柱子比我们已经放好的柱子要大，不能放到那根上面
    //当我们把那j根柱子，放到目标柱子上时，我们又是可以都放在四根柱子上，因为此时，它比其它的都小
    //四根需要取min，而三根不需要取min的原因是，三根的最小次数即它的实际次数，即只能在三根之间操作着放，而四根就能减少操作次数
    //所以取min
        f[i] = min(f[i], f[j] * 2 + d[i - j]);

for (int i = 1; i <= 12; i ++ ) cout << f[i] << endl;
return 0;

}

’‘’