首页 > 代码库 > 汉诺塔的简单递归思想
汉诺塔的简单递归思想
最近在校招打酱油，闲得没事想起了大一学过的汉诺塔，不过那时只知道玩游戏，一次性3~7个玩过了，还是有成就感的呵呵。游戏链接：http://www.7k7k.com/swf/335.htm。
看了网上很多递归方法，像
1 #include<stdio.h> 2 3 void move(int n,char a,char b,char c) 4 { 5 if(n==1) 6 printf("\t%c->%c\n",a,c); 7 else 8 { 9 move(n-1,a,c,b); 10 printf("\t%c->%c\n",a,c); 11 move(n-1,b,a,c); 12 } 13 } 14 15 main() 16 { 17 int n; 18 printf("please input the number："); 19 scanf("%d",&n); 20 move(n,‘a‘,‘b‘,‘c‘); 21 }
是最多的，如果觉得难以理解，就看看我下午自己搞的递归吧。
代码不需要全部贴出来，只贴重要的。
1 char string1[6] = "left"; 2 char string2[6] = "mid"; 3 char string3[6] = "right"; 4 int i = 1;
先定义3个字符串和整数i，用于后面的显示。
1 void exchangeSTR(char string1[],char string2[]) { 2 char x[6]; 3 strcpy(x,string1); 4 strcpy(string1,string2); 5 strcpy(string2,x); 6 }
字符串交换函数，用于两个字符串的交换。
1 void wtw(char string1[],char string2[]) { 2 cout << i++ << ‘.‘ << ‘ ‘ << string1 << " -> " << string2 << endl << endl; 3 }
定义打印语句格式。
1 void RootOfMove(char string1[],char string2[],char string3[]) { 2 wtw(string1,string2); 3 wtw(string1,string3); 4 wtw(string2,string3); 5 }
此功能函数的作用是：打印出当块数为2时的具体步骤，这是递归产生的基本条件。
1 void TowerOfHanoi(int n) { 2 if (n == 1) { 3 wtw(string1,string3); 4 }else if (n == 2) { 5 RootOfMove(string1,string2,string3); 6 }else { 7 exchangeSTR(string2,string3); 8 TowerOfHanoi(n-1); 9 exchangeSTR(string2,string3); 10 wtw(string1,string3); 11 exchangeSTR(string1,string2); 12 TowerOfHanoi(n-1); 13 exchangeSTR(string1,string2); 14 } 15 }
这是核心函数，将在main函数中调用。
当n为1时，按照wtw函数打印出左至右的步骤；
当n为2时，按照RootOfMove函数打印出相应的步骤；
当n为3时，（无论n是多少，请视作2部分，最下面的一个和它上面的n-1个，因此，步骤也视为RootOfMove中的3步）
1、交换string2和string3的值，也就是交换"mid"和"right"，再执行，为什么呢？因为当n为2时，执行TowerOfHanoi(2)函数后，所有的木块都到了右边，以此为参照，我们先无视最下面那一块，操作上面2块，只不过不是把他们移到右边，而是中间！这个操作和TowerOfHanoi(2)很类似，只需要把TowerOfHanoi(2)右边和中间有关的操作互换就能实现！所以在交换后，再执行TowerOfHanoi(2)就可以把上面2块移到中间。（该步骤相当于RootOfMove中的wtw(string1,string2)）
2、把最下面的1块移到右边，由于之前string3的值换了，所以要和string2换回来。（该步骤相当于RootOfMove中的wtw(string1,string3)）
3、把中间的2块移到右边，先交换string1和string2，原因和1同理，TowerOfHanoi(2)能实现从左到右，调换左边和中间有关的操作就可以实现从中到右。最后字符串换回来。（该步骤相当于RootOfMove中的wtw(string2,string3)）
这样一来，一个简单的递归就完成了。
运行效果图，再也不用怕汉诺塔了！
汉诺塔的简单递归思想