分而治之

既然要讨论分而治之的算法思想，那么首先我们就要弄清楚：分而治之是什么？

有时直接解决一个复杂的问题是相当困难的，往往绞尽脑汁，却无功而返。这时候，不妨换个思路，既然理解一个理解庞大的问题是如此吃力，不如把它看成一些独立，较容易的相同问题，以便逐个击破。ps:举一个不那么恰当的例子：既然找个适合的女朋友是如此困难，不如一步一步来，先学会和女生聊天好了。没错了，这就是分而治之的思想。

作为算法思想，就不得不提到分而治之与递归的关系。用分治法解决问题，原问题被不断分解为较小的子问题，最后求出子问题的解。这与递归思想，简直如出一辙。这是因为如此，它们常常同时应用在算法设计之中，并由此产生许多高效的算法。

汉诺塔问题

空说无凭，作为分治思想的经典问题，我们通过汉诺塔问题来说明实际解决问题中，如何运用分而治之的算法思想。

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

如果尝试直接移动这么多的盘子，恐怕一时感到无从下手。这时采用分治思想，我们来看看当盘子数量少的时候，应该如何解决问题呢？

一个盘子

将盘子从A移动到C：A->C

两个盘子

将最大盘子之前的盘子从A移动到B：A->B

将最大的盘子从A移动到C：A->C

将最大盘子之前的盘子从B移动到C：B->C

三个盘子

如图，虽然三个盘子的搬运就显得略微复杂，但是它们的思想是一致的。

step1:将最大盘子之前的盘子从A移动到B：A->B

A->C

A->B

C->B

step2:将最大盘子从A移动到C：A->C

A->C

step3:将最大盘子之前的盘子从B移动到C：B->C

B->A

B->C

A->C

想到了这样的分解思路之后我们就可以写出相应的程序了。

include <stdio.h>
//计数变量
int count = 1;
//汉诺塔函数
void hanoi(int n, char A, char B, char C);

int main(int argc, const char * argv[]) {
	
//    作为linux C程序运行的预处理
//    if (argc == 2) {
//        const char * N = argv[1];
//        int n = (int)(N[0] - 48);
//        hanoi(n, 'A', 'B', 'C');
//    }else{
//        printf("please input n as number of plates");
//    }
	
//  一般的C程序
	hanoi(3, 'A', 'B', 'C');
	return 0;
}
void hanoi(int n, char A, char B, char C) {
	if (n == 1) {
		//只有一个盘子时，只需要把它从A柱移动到C柱
		printf("第%d次移动，将第%d个盘子移动，从%c移动到%c\n", count++,n,A,C);
	}else{
		//step1:将最大盘子之前的盘子从A移动到B：A->B
		hanoi(n - 1, A, C, B);
		//step2:将最大盘子从A移动到C：A->C
		printf("第%d次移动，将第%d个盘子移动，从%c移动到%c\n", count++,n,A,C);
		//step3:将最大盘子之前的盘子从B移动到C：B->C
		hanoi(n - 1, B, A, C);
	}
}

想要理解上述的递归程序，重点不在于对整个递归过程的推敲，而在于理解分而治之的处理过程。

• step1:将最大盘子之前的盘子从A移动到B：A->B(把冰箱的门打开)
• step2:将最大盘子从A移动到C：A->C(把大象放进去)
• step3:将最大盘子之前的盘子从B移动到C：B->C(把冰箱的门关上)

总结

重复性工作，并不是人类最擅长的部分，而计算机恰恰很擅长这样傻瓜式的重复性工作。编写递归算法，重点在于掌握分而治之的处理过程（怎么把面对的复杂问题，分解成规模更小的相同问题去解决），至于递归的栈调用，就交给傻乎乎的计算机去做吧。

这次我们简单介绍了用分而治之思想去解决经典的汉诺塔问题，今后还会不定时的更新一些算法问题的解决思路，欢迎读者交流看法，分享观点。

---