汉诺塔问题(Hanoi)

汉诺塔问题(Hanoi)

一、汉诺塔问题

有三根杆子A，B，C。A杆上有N个(N>1)穿孔圆盘，盘的尺寸由下到上依次变小。要求按下列规则将所有圆盘移至C杆： 每次只能移动一个圆盘； 大盘不能叠在小盘上面。 提示：可将圆盘临时置于B杆，也可将从A杆移出的圆盘重新移回A杆，但都必须遵循上述两条规则。

二、解法

解法的基本思想是递归。假设有A、B、C三个塔，A塔有N块盘，目标是把这些盘全部移到C塔。那么先把A塔顶部的N-1块盘移动到B塔，再把A塔剩下的大盘移到C，最后把B塔的N-1块盘移到C。 每次移动多于一块盘时，则再次使用上述算法来移动。

思路： Hanoi（n,a,b,c），这里表示将个n盘子借助b移动到c

如果n=1，那么可以直接1：a->c

如果n=2，那么可以先把a柱上的n-1个盘子移动到b,Hanoi（n-1,a,c,b）,就是将1号盘子从a借助c移动到b，此时a只剩下2号一个盘子了，可以直接从a->c,那么此时n-1个盘子在b上，而a柱是空的，我们可以从b借助a把这n-1个盘子移动到c，Hanoi（n-1,b,a,c）是个递归的过程

输入

输入为一个整数后面跟三个单字符字符串。

整数为盘子的数目，后三个字符表示三个杆子的编号。

输出

输出每一步移动盘子的记录。一次移动一行。

每次移动的记录为例如3:a->b 的形式，即把编号为3的盘子从a杆移至b杆。

我们约定圆盘从小到大编号为1, 2, …n。即最上面那个最小的圆盘编号为1，最下面最大的圆盘编号为n。

样例输入

3 a b c
           

样例输出

1:a->c
2:a->b
1:c->b
3:a->c
1:b->a
2:b->c
1:a->c
           

#include <iostream>
#include <cstring>
using namespace std; 

/* run this program using the console pauser or add your own getch, system("pause") or input loop */
void Hanoi(int n,char a,char b,char c){
	if(n==1){
		cout<<n<<":"<<a<<"->"<<c<<endl;
	}else{
		Hanoi(n-1,a,c,b);
		cout<<n<<":"<<a<<"->"<<c<<endl;
		Hanoi(n-1,b,a,c);
	}
}
int main(int argc, char** argv) {
	int n;
	char a,b,c;
	while(cin>>n>>a>>b>>c){
		Hanoi(n,a,b,c);
	}
	return 0;
}