一、什么是分治算法
分治（Divide and Conquer）算法，字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似问题的子问题，再把子问题分成更小的子问题 …… 直到最后子问题可以简单的直接求值，原问题的解即子问题的解的合并。
分治法在每一层递归上都有三个步骤：
- 分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题；
- 解决：若子问题规模较小而容易被解决则直接解。否则递归地解各个子问题；
- 合并：将各个子问题的解合并为原问题的解；
二、汉诺塔问题
汉诺塔问题有三个柱子，在一个柱子上从下往上按照大小顺序摆放 64 片黄金圆盘。要求我们从下面开始按大小顺序重新摆放在另一哥柱子上。并且规定，在小圆盘上不能放大圆盘，在三个柱子之间一次只能移动一个圆盘。
汉诺塔问题的解决思路：
- 先把上面的盘从 A 移动到 B；
- 将最下面的盘从 A 移动到 C；
- 在把 B 上的所有盘从 B 移动移动 C；
#include <stdio.h>
int main(void)
{
HanoiTower(10,'a','b','c');
return 0;
}
/**
* @brief 汉诺塔问题
*
* @param num 要移动的盘子个数
* @param a 第一个柱子
* @param b 第二个柱子
* @param c 第三个柱子
*/
void HanoiTower(int num,char a,char b,char c)
{
// 如果只有一个盘
if(num == 1)
{
printf("第 1 个盘从 %c → %c\n",a,c);
}
else
{
// 如果 n>=2，我们总是可以看做两个盘，最下边的一个盘和上面的所有盘
// 1. 把上面的盘 a→b，移动过程会使用c
HanoiTower(num-1,a,c,b);
// 2. 把最下面的盘 b→c
printf("第 %d 个盘从 %c → %c\n",num,a,c);
// 3. 把b中所有的盘 b→c，移动过程会使用C
HanoiTower(num-1,b,a,c);
}
}