题目描述 Description
题目描述 Description
汉诺塔问题（又称为河内塔问题），是一个大家熟知的问题。在A，B，C三根柱子上，有n个不同大小的圆盘（假设半径分别为1-n吧），一开始他们都叠在我A上（如图所示），你的目标是在最少的合法移动步数内将所有盘子从A塔移动到C塔。
游戏中的每一步规则如下：
1. 每一步只允许移动一个盘子（从一根柱子最上方到另一个柱子的最上方）
2. 移动的过程中，你必须保证大的盘子不能在小的盘子上方（小的可以放在大的上面，最大盘子下面不能有任何其他大小的盘子）
如对于n=3的情况，一个合法的移动序列式：
1 from A to C
2 from A to B
1 from C to B
3 from A to C
1 from B to A
2 from B to C
1 from A to C
给出一个数n，求出最少步数的移动序列
输入描述 Input Description
一个整数n
输出描述 Output Description
第一行一个整数k，代表是最少的移动步数。
接下来k行，每行一句话，N from X to Y，表示把N号盘从X柱移动到Y柱。X,Y属于{A,B,C}
样例输入 Sample Input
3
样例输出 Sample Output
7
1 from A to C
2 from A to B
1 from C to B
3 from A to C
1 from B to A
2 from B to C
1 from A to C
数据范围及提示 Data Size & Hint
n<=10
题解：
在纸上画，发现基本规律：
- 目标一定，最短路径有且只有一条。
- 如果要把A中n个圆盘移动到C，必须把A中最下面的移动到C。要实现这一步，前一步必须是：A只剩最后一个元素，B中为A的前n-1个元素, C为空。
百度百科：汉诺塔
可以找到关于步数的函数： 1 n =1
f（n）
2 x f(n-1) - 1 n>=1
（理解汉诺塔的递归原理后，很容易得到这样的结论）：
画图分析：
最小递归：n=1，f（1）。
n=2，实际是
第一步：调用f（1）先将1移动 到B//基于发现的基本规律2.
第二部：将A中最后一个元素移动到C，作为C的最里面的元素。
第三部：此时，A为空，B为1，C为2。即又要调用f（1），只是这次B为源，C为目标，A作为临时储存器。
n = 3，
第一步：f（2），源为A，目标C
第二步：将3从A移动到C。
第三部：f（2），源为B，目标C
n = n，
第一步：f（n-1），源为A，目标C
第二步：将n从A移动到C。
第三部：f（n-1），源为B，目标C
这样关于步数的函数显然易见。
针对本题输出要求，用vector保存元素来输出。
#include#include #include #include #include using namespace std;void remove(int n, vector & src, vector & mid, vector & aim);int main(){ vector a,b,c; /*标示a、b、c塔。*/ a.push_back("A"); b.push_back("B"); c.push_back("C"); / int n; cin >> n; cout << pow(2, n) - 1 << endl;//输出最小步数 /*填充塔A*/ string str; ostringstream oss; for (int i = n; i > 0; i--) { oss.str(""); oss << i; str = oss.str(); a.push_back(str); } // remove(n, a, b, c); return 0;}void remove(int n, vector & src, vector & mid, vector & aim)//a 被移动者，b为储存器，c为目标。{ if (n == 1){ //此时a中只有一个元素1（不算名称a[0]）,把他移动到aim string temp = src.back(); src.pop_back(); aim.push_back(temp); cout << 1 << " from " << src[0] << " to " << aim[0] << endl; } else { //将前n-1个元素 放到中间存储器中。 remove(n - 1, src, aim, mid); //将src中最后一个元素 直接移到目标底部。 string temp = src.back(); src.pop_back(); aim.push_back(temp);//把a的最后一个元素移动到c中。 cout << temp << " from " << src[0] << " to " << aim[0] << endl; //再将中间存储器中的所有元素（有n-1）个全部移到 没有目标储存器中。 remove(n - 1, mid, src, aim); }};