PS：本文系转载文章，浏览原文可读性会更好，文章开端有原文链接
目录
1、分治算法
1、1 分治算法的根本介绍 1、2 分治算法的步骤 1、3 用分治算法解决汉诺塔问题1、分治算法
1、1 分治算法的根本介绍
分治算法思维就是“分而治之”，将一个简单的问题分为多个类似的子问题，又把子问题分为多个更小的子问题，直到最初子问题能够用最简略的形式间接求解，原问题的解就是为子问题解的合并；咱们见到的二分搜寻啊，棋盘模型啊，合并排序啊，疾速排序啊，汉诺塔等经典算法，就是使用到分治算法的。
1、2 分治算法的步骤
（1）合成，将原问题合成为 N 个规模较小，互相独立，与原问题模式雷同的子问题。
（2）解决，如果子问题规模较小，那么间接求解；如果规模较大，那么递归求解。
（3）合并，将各个子问题的解合并为原问题的解。
1、3 用分治算法解决汉诺塔问题
为了能了解汉诺塔问题，我先来画一张图，如图1所示；
图片
有三根杆(编号A、B、C)，在 A 杆自下而上、由大到小按程序搁置 N （这里图1的为3个）个金盘(如图1)；游戏的指标是把A杆上的金盘全副移到C杆上，并仍放弃原有程序叠好；操作规定：每次只能挪动一个盘子，并且在挪动过程中三根杆上都始终保持大盘在下，小盘在上，操作过程中盘子能够置于A、B、C任一杆上。
为了更好的总结汉诺塔的规定，咱们先用图1的来进行举例，依照游戏的规定，咱们最终的后果是从 A 杆上全副挪动到 C 杆上，从下而上盘的程序是3、2、1 对不对；好，咱们当初分3个步骤来挪动盘子。
（1）将 B 杆作为直达杆，这一步咱们最终先将 1、2 号盘拿到 B 杆上，能力将 3 号盘从 A 杆拿到 C 杆上对不对？先将 1 号盘拿到 C 杆上，再将 2 号盘拿到 B 杆上，又从 C 杆上拿走 1 号盘到 B 杆上，这时候操作完这一步骤失去如图2所示；
图片
（2）从 A 杆上间接从 3 号盘取出拿到 C 杆上，执行完这一步骤失去如图3所示；
图片
（3）将 A 杆作为直达杆，这一步咱们的最终目标是将 B 杆上的 1、2 号盘拿到 C 杆上对不对？先从 B 杆上把 1 号盘拿到 A 杆上，再从 B 杆上把 2 号盘拿到 C 杆上，最初从 A 杆上把 1 号盘拿到 C 杆上，执行完这一步骤失去如图4所示；
图片
好，咱们当初对这3个步骤进行总结一下，第一步骤挪动了3次，第二步骤挪动了1次，第三步骤挪动了三次，就总共挪动了7次，那么就得出总共挪动的次数就等于2的 n 次方之后再减1就等于7，其中 n 示意一开始 A 杆上盘子的个数。
这里咱们推理一下，n 示意一开始 A 杆上盘子的个数，当 n 为1的时候，只须要挪动一次对不对？也就是间接将这个盘子拿到 C 杆上就好了；当 n 大于1的时候，就须要依照下面所说的分3个步骤来挪动盘子对不对？其中第一步骤和第三步骤挪动的次数是雷同的对不对？而第二步骤只须要挪动一次，依据总共挪动的次数就等于2的 n 次方之后再减1这个规定失去，(2^n 示意2的n次方）第一步骤和第三步骤挪动的次数就均为 (2^n - 2) / 2 。
当 n 大于1时，汉诺塔问题是一个递归问题，它的规定是这样的：第一次以 B 杆为直达杆，将1到n-1号的盘子搬到 B 杆上，而后从 A 杆上把 n 号的盘子拿到 C 杆上；第二次以 A 杆为直达杆，将1到n-2号的盘子搬到 A 杆上，而后从 B 杆上把 n-1 号的盘子拿到 C 杆上；第三次以 B 杆为直达杆，将1到 n-3号的盘子拿到 B 杆上，而后从 A 杆上把 n-2 号的盘子拿到 C 杆上；以此这样类推上来......直到把1号盘子拿到 C 杆上。
好，咱们用 Java 代码实现一把
（1）新建一个 Test 类：
package com.xiaoer.demo;
public class Test {
public static void main(String[] args) {
hanoi(3,'A','B','C');}
/**
- @param n 示意盘子的个数
- @param a 起始杆，也就是从这个杆子上拿的盘子放到其余杆子上
- @param b 直达杆，不肯定字母b就是直达杆，只有是第三个参数，只有是第三个参数，
- 只有是第三个参数，就是直达杆
- @param c 指标杆，也就是从其余杆子上拿的盘子放到这根杆子上
*/
public static void hanoi(int n, char a, char b, char c) {
if (n == 1) { System.out.println(a + "-->" + c);}else { /** * 第一步骤，当 n 一开始为3的时候，间接把1、2 号盘子挪动到B杆上； * 推理，当n大于1并为其余数时，间接把1到（n-1）号盘子挪动到B杆上 * */ hanoi(n - 1, a, c, b); /** * 第二步骤，当n一开始为3的时候，间接把3号盘子拿到C杆上； * 推理，当n大于1并为其余数时，间接把n号盘子挪动到C杆上 */ System.out.println(a + "-->" + c); /** * 第三步骤，当n一开始为3的时候，间接从B杆上把1、2号盘子拿到C杆上； * 推理，当n大于1并为其余数时，间接把1到（n-1）号盘子从A杆挪动到C杆上 */ hanoi(n - 1, b, a, c);}}
}
程序运行后果如下所示；
图片