算法——n阶Hanoi塔问题

问题

假设有3个分别命名为A、B、C的塔座，在塔座A上插有n个直径大小各不相同，从小到大编号为1，2，…，n的圆盘。现要求将塔座A上的n个圆盘移至塔座C上，并按同样的顺序叠排，圆盘移动时必须遵循下列规则：

1. 每次只能移动一个圆盘
2. 圆盘可以插在A，B，C的任一塔座上
3. 任何时刻都不能将一个较大的圆盘压在较小的圆盘之上
   

分析

设A柱上最初的圆盘总数为n，当n=1时，只要移动1次；否则执行以下三步：

1. 用C柱做过渡，将A柱上的（n-1）个盘子移到B柱上；
2. 将A柱上最后一个盘子直接移到C柱上；
3. 用A柱做过渡，将B柱上的（n-1）个盘子移到C柱上。

实现代码

int m=0;//对移动次数进行统计
void move(char A,int n,char C)
{//定义一move方法，将编号为n的圆盘从A移到C
	cout<<++m<<","<<n<<","<<A<<","<<C<<endl;
}
void Hanoi(int n,char A,char B,char C)
{//将塔座A上的n个圆盘按规则搬到C上，B做辅助塔。
	if(n==1)
		move(A,1,C);//将编号为1的圆盘从A移到C
	else
	{
		Hanoi(n-1,A,C,B);//将A上编号为1至n-1的圆盘移到B，C做辅助塔
		move(A,n,C);//将编号为n的圆盘从A移到C
		Hanoi(n-1,B,A,C);//将B上编号为1至n-1的圆盘移到C，A做辅助塔
	}
}