共计 2016 个字符，预计需要花费 6 分钟才能阅读完成。
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);
}}
}
程序运行后果如下所示；
图片
