Eight Day 递归-汉诺塔

问题阐述：

相传在古印度圣庙中，有一种被称为汉诺塔(Hanoi)的游戏。该游戏是在一块铜板装置上，有三根杆(编号A、B、C)，在A杆自下而上、由大到小按顺序放置64个金盘(如图1)。游戏的目标：把A杆上的金盘全部移到B杆上，并仍保持原有顺序叠好。 *** 作规则：每次只能移动一个盘子，并且在移动过程中三根杆上都始终保持大盘在下，小盘在上， *** 作过程中盘子可以置于A、B、C任一杆上。

代码实现

思路：

将n-1个盘子从A借助B移动到C上；

再将最后的盘子移动到B上；

最后将C上的n-1个盘子借助A移动到B上。

代码实现：

#include 
/**
 * Hanoi.
 */
void hanoi(int paraN, char paraSource, char paraDestination, char paraTransit) {
	if (paraN <= 0) {
		return;
	} else {
		hanoi(paraN-1, paraSource, paraTransit, paraDestination);//将 n - 1个盘从S 通过D 移动到 T 
		printf("%c->%c\n", paraSource, paraDestination);//将 最下面一个盘 移动到D 
		hanoi(paraN-1, paraTransit, paraDestination, paraSource);//将在T 上的n-1个盘，通过S移动到D上，目的完成。 
	}//Of if
}//Of hanoi 


/**
 * Test the hanoi function.
 */
void hanoiTest() {
	printf("---- hanoiTest begins. ----\n");
	printf("3 plates\n");
	hanoi(3, 'A', 'B', 'C');//将三个盘子从A柱子上移动到B(其中借助了C);
	printf("5 plates\n");
	hanoi(5, 'A', 'B', 'C'); 
	printf("---- hanoiTest ends. ----\n");
}  
int main(void) {
	hanoiTest(); 
	return 0;
}

总结 ：

很多复杂的问题可以划分为一些小问题，一步一步从简单到困难解决。

在汉诺塔问题就是典型利用递归思想，移动n个盘子你不知道这么移动，你可以先移动n-1个，类推下去，直到移动一个盘子。