经典汉诺塔
#include<iostream>
using namespace std;
int k=1;
void hanuo(int n,char a,char b,char c)
{
if(n==1)
cout<<k++<<'.'<<a<<"-->"<<c<<endl;
else
{
hanuo(n-1,a,c,b);
cout<<k++<<'.'<<a<<"-->"<<c<<endl;
hanuo(n-1,b,a,c);
}
}
int main()
{
int n;
cin>>n;
hanuo(n,'a','b','c');
}
汉诺塔（港台：河内塔）是根据一个传说形成的数学问题：
有三根杆子A，B，C。A杆上有 N 个 (N>1) 穿孔圆盘，盘的尺寸由下到上依次变小。要求按下列规则将所有圆盘移至 C 杆：
每次只能移动一个圆盘；
大盘不能叠在小盘上面。
提示：可将圆盘临时置于 B 杆，也可将从 A 杆移出的圆盘重新移回 A 杆，但都必须遵循上述两条规则。
问：如何移？最少要移动多少次？
汉诺塔的本质是3个栈
维基的定义只简单提到了汉诺塔的规则, 但是并没有揭示它的本质. 下面我们来分析它的本质.1.每次只能移动1个盘:
也就说不能两个盘一齐移动, 必须按顺序1个1个套在柱子上, 而且只能从柱子的上方套入, 也能只能从柱子的上方取出.这明显就是1个先进后出的线性结构了, 因为出入口只有1个啊, 柱子的下方是不能放入和取出盘子的.
先进后出的线性结构就是栈了, 套入柱子和取出盘子就是对应的压栈和出栈动作. 如果读者之前没有了解过栈的话, 个人建议先去了解下栈, 然后再往下看.
2. 大盘不能套在小盘上面
代表这3个栈中, 如果不是空栈, 那么压栈的元素必须比栈顶元素小, 然后才允许压栈. 这就保证栈里面的元素是从小到大排序的.
总结: 汉诺塔的本质就是3个栈, 而且压栈的元素必须比栈顶元素(如果存在)小.- 下面我们来写递归函数。
首先，题目要求求的是如何操作，那么我们就必须写一个输出操作语句的函数。
这个操作语句必须说明：第几步将哪个盘子从哪个柱子移动到哪个柱子上（这样人类才知道怎样移动盘子嘛）
这里，我们定义这个函数的函数名为move。
接下来，我们来确定这个函数的参数列表。
显然，为了说明第几步将哪个盘子从哪个柱子移动到哪个柱子上，我们参数列表至少应该包含：
id，表示被移动的盘子的序号。
from，表示从哪个柱子上移动这个编号为id的盘子
to，表示移动到哪个柱子上
那么这个函数的函数头就确定了： void move(int id, char from, char to) // 打印移动方式：编号，从哪个盘子移动到哪个盘子 那么函数体呢？
唯一的难点就是如何记录这是操作的第几步。
注意到，每次操作必须输出移动方式且仅能输出一次，那么显然，我们已经printf的当前总数不就是第几次操作了嘛
我们开一个全局变量用于记录printf的次数即可
所以函数体中就只有这一个语句： printf ("step %d: move %d from %c->%c\n", ++cnt, id, from, to);
合并起来就是：
void move(int id, char from, char to) // 打印移动方式：编号，从哪个盘子移动到哪个盘子
{
printf ("step %d: move %d from %c->%c\n", ++cnt, id, from, to);
} 敲黑板：
递归函数怎么写呢?
我们先来想一下我们人类应该怎样操作吧。
我们每次操作都会这样问自己：我们需要将哪个柱子上的多少个盘子通过哪个柱子移动到哪个柱子上呢？
我们必须也只能用这么几个参数：
需要移动的盘子的总数，3个柱子。
所以函数头为： void hanoi(int n, char x, char y, char z)
其中，n代表盘子总数，x，y，z代表柱子
hanoi(n, x, y, z)的意思就是：将n个在x柱子上的盘子通过y这个柱子移动到z这个柱子上。
那不就完了！
hanoi(n, 'A', 'B', 'C')就是这道问题的答案！ 那么这一步的前一步是什么？ 记住了，在求解f(n, other variables)的时候，我们直接默认f(n - 1, other variables)已经完了就可以了！这个在前面已经解释过了，在此不再鳌述。 我们将n-1个盘子当作一个整体：这就是类似于分治求解子问题的思想
那么，前一步也就是f(n - 1, other variables)显然是先将n -1 个在A柱子上的盘子通过C柱移动到B柱上，再将在A柱子上的编号为n的盘子移动到C柱上，再将B柱子上的n-1个盘子通过A柱移动到C柱上，over
