分治算法解决汉诺塔问题（Java实现） java

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所示；
图片
【分治算法解决汉诺塔问题（Java实现）】好，我们现在对这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); }

}
}
程序运行结果如下所示；
图片