介绍
分治算法的思想是 “ 分而治之 ” ，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题......知道最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。这个技巧是很多高效算法的基础
分治算法基本思想
分治法在每一层递归上都有三个步骤
1.分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题
2.解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题
3.合并：将各个子问题的解合并为原问题的解
分治算法实例——汉诺塔问题
思路分析
1.如果只有一个盘 A -> C
2.如果有 n >= 2 的情况，我们总是可以看作两个部分，一部分是最下面的盘，一部分是上面的所有盘
①先把上面的所有盘 A -> B
②把最下面的盘 A -> C
③把 B 塔的所有盘 B -> C
代码实现
public class Hanoitower {public static void main(String[] args) {hanoiTower(5,'A', 'B', 'C');}//汉诺塔的移动方法//使用分治算法public static void hanoiTower(int num, char a, char b, char c) {if (num == 1) {System.out.println("第 1 个盘从" + a + "->" + c);} else {/*如果有 n >= 2 的情况，我们总是可以看作两个部分，一部分是最下面的盘，一部分是上面的所有盘*///①先把上面的所有盘 A -> BhanoiTower(num - 1, a, c, b);//②把最下面的盘 A -> CSystem.out.println("第 " + num + " 个盘从" + a + "->" + c);//③把 B 塔的所有盘 B -> ChanoiTower(num - 1, b, a, c);}}
}