题目描述
汉诺塔问题,条件如下:
1、这里有A、B、C和D四座塔。
2、这里有n个圆盘,n的数量是恒定的。
3、每个圆盘的尺寸都不相同。
4、所有的圆盘在开始时都堆叠在塔A上,且圆盘尺寸从塔顶到塔底逐渐增大。
5、我们需要将所有的圆盘都从塔A转移到塔D上。
6、每次可以移动一个圆盘,当塔为空塔或者塔顶圆盘尺寸大于被移动圆盘时,可将圆盘移至这座塔上。
请你求出将所有圆盘从塔A移动到塔D,所需的最小移动次数是多少。
河内塔.jpg
汉诺塔塔参考模型
输入格式
没有输入
输出格式
对于每一个整数n(1≤n≤12
),输出一个满足条件的最小移动次数,每个结果占一行。
样例
输入样例:
没有输入
输出样例:
参考输出格式
算法1
1.三塔的话都应该知道,若n个盘从A通过B移动到C,需要2的n次方-1 步,
2.四塔,(1)先把前j个盘从A通过B,D盘移动到C盘(或者前j个盘从A盘通过C,D盘移动到C盘),这都需要f[j]步
(2)然后把A盘上剩余的i-j个盘从A通过B移动到D盘,因为第i个盘最大,C塔上最上面一层是最小的盘,所以C盘不能动,你就相当于i-j个盘从A通过B移动到D盘变成了三塔情况,直接用公式2的n次方-1 (1<<(i-j)-1)
(3)最后把在C盘上的j个盘通过B盘,A盘移动到D盘,需要f[j]步
(4)总步数加到一块 f[j]+(1<<(i-1)-1)+f[j]=f[j]*2+(1<<(i-j))-1)
3.本题通过改变j的个数来判定最小需要的步数,这里把f[13]数组中各元素初始化为较大的数0x3f,i相同时,每次j变化时f[i]就更新为最小的那个值
C++ 代码
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
int main() {
int f[13];
memset(f,0x3f,sizeof(f));//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+(1<<(i-j))-1);
}
}
for (int i = 1; i <= 12; ++i) {
cout<<f[i]<<endl;
}
return 0;
}