汉诺塔问题
有三根杆子A,B,C。A杆上有N个(N>1)穿孔圆环,盘的尺寸由下到上依次变小。要求按下列规则将所有圆盘移至C杆:
每次只能移动一个圆盘;大盘不能叠在小盘上面。
提示:可将圆盘临时置于B杆,也可将从A杆移出的圆盘重新移回A杆,但都必须遵循上述两条规则。
问:如何移?最少要移动多少次?
为了解决这个问题,不妨假设已经知道怎样移动N-1个圆环了。现在,为了把起点盘上的圆环移动到目标盘,需要做如下操作:
1、把N-1个圆环从起点盘移动到(当前)没有任何圆环的过度盘;
2、把最后一个圆环从起点盘移动到目标盘;
3、把N-1个圆环从国度盘移动到目标盘(模仿1和2的操作方法来实现)。
可以借助网友的图示,如果三个圆盘的话:
如果四个圆盘的话:
代码实现如下:
void hannoi(int n, char A, char B, char C){ if (n == 1) { //把最后一个圆环从起点盘移动到目标盘 cout << "移动圆盘" << n << "从盘" << A << "盘" << C << endl; } else { hannoi(n - 1, A, C, B); //把N-1个圆环从起点盘移动到(当前)没有任何圆环的过度盘;通过B、C盘在此函数调用中调用位置的互换,来实现把N-1个圆环从A盘到B盘的转移【A--B】。 cout << "移动圆圈" << n << "从盘" << A << "盘" << C << endl; hannoi(n - 1, B, A, C); // 把N-1个圆环从过渡盘移动到目标盘(模仿1和2的操作方法来实现);通过A、B盘在此函数调用中位置的互换,来实现N-1个圆环从B盘到C盘的转移【B--C】。 }}
若输入n=3,则结果如下:
记不住想下面的口诀:递归-句子-递归。
两个盘子:先把小的由A移到B(ACB递归),然后把大的由A移到C(AC句子),然后把小的由B移到C(BAC递归)。