汉诺塔(Tower of Hanoi),又称河内塔,是一个源于印度古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子,在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定,在小圆盘上不能放大圆盘,在三根柱子之间一次只能移动一个圆盘。
假设一共有n个圆盘。
有三根柱子a,b,c,此时他们的状态分别为起始柱,辅助柱,目标柱。
当n==1时很简单,只需要将a中的圆盘放到c中即可。
当n!=1时,如下所示
hanio(n个圆盘,起始柱,辅助柱,目标柱)hanio(n,'a','b','c');
由于大圆盘不能放到小圆盘上面,所以最大的圆盘n必须留到最后,先放入c中,因此需要把n-1个圆盘放到b中,然后就可以将a柱中的第n个圆盘移动到c柱中了。但是要想要达到这个目标,需要先把a中的n-1个圆盘放入b中,因此这三根柱子的状态,a不变,仍然是起始柱,b此时变为了目标柱,而c则是辅助柱。
hanio(n-1,a,c,b);cout<<a<<"-->"<<c;
达到上面的目标后,就可以把a中第n个圆盘移动到c中,那么接下来只需要把b中的n-1个圆盘放到c中即可。而此时柱子的状态就变成了b为起始柱,a为辅助柱,c为目标柱。而其实这个状态和第一步的是一样的,只是数量为n-1罢了。
hanio(n-1,b,a,c);
完整代码:
#include<bits/stdc++.h>using namespace std;void hanio(int n,char a,char b,char c){if(n==1){cout<<a<<"-->"<<c;cout<<endl;return;}else{hanio(n-1,a,c,b);cout<<a<<"-->"<<c;cout<<endl;hanio(n-1,b,a,c); }}int main(){int n;char a,b,c;cin>>n;hanio(n,'a','b','c');cout<<endl;return 0;}
运行结果如下:
3a-->ca-->bc-->ba-->cb-->ab-->ca-->c