4.9 Hanoi（汉诺）塔问题。

大家好，欢迎来到IT知识分享网。

二、汉诺塔问题思路

2、汉诺塔两个盘子

 3、汉诺塔三个盘子

 ②将编号为 n 的盘子从 A 移动到C

 ③将 n– 1 个盘子从 B 移动到C

在此过程中，步骤①③ 明显是个递归调用

过程：建立hanoi（n,a,b,c)由于第一步移动A->C，所以采用hanoi（1,a,c,b)代表move（a,c）便于理解。建立函数就采用特殊顺序，不采用a,b,c顺序，hanoi（1,a,c,b)，这样就很好理解了。1个盘子时候，hanoi（1,a,c,b)，就是move（a,c).  假如有n个，第一步先把n-1从a移动到b，就是hanoi（n-1,a,b,c).第二步把第n个从a移动到c，就是move（a,c）这一步是不会变化的。第三步，就是把n-1个在从b移动到c上，就是hanoi（n-1,b,c,a).

比如：2个盘子时候，先把n-1个盘子从a移动到b，也就是hanoi（1,a,b,c)，对应就是move（a,b），第二步move（a,c）不变。第三步，就是把n-1个在从b移动到c上，就是hanoi（1,b,c,a)，对应move（b,c）。与实际能对应上。

答案：

#include <iostream> using namespace std; int main() { int n; int hanoi(int,char,char,char); int move(char,char); cout<<"please enter n："; cin>>n; hanoi(n,'A','C','B'); return 0; } int hanoi(int n,char A,char C,char B) { int move(char x,char y); if(n==1) { move(A,C); } else if(n>1) { hanoi(n-1,A,B,C); move(A,C); hanoi(n-1,B,C,A); } return 0; } int move(char x,char y) { cout<<x<<"->"<<y<<endl; return 0; }