分治算法

一、基本概念二、算法步骤及问题举例三、分治算法解决汉诺塔问题代码实现

一、基本概念

分治算法的基本思想是将一个规模为N的问题分解为K个规模较小的子问题，这些子问题相互独立且与原问题性质相同。求出子问题的解，就可得到原问题的解。

当我们求解某些问题时，由于这些问题要处理的数据相当多，或求解过程相当复杂，使得直接求解法在时间上相当长，或者根本无法直接求出。对于这类问题，我们往往先把它分解成几个子问题，找到求出这几个子问题的解法后，再找到合适的方法，把它们组合成求整个问题的解法。如果这些子问题还较大，难以解决，可以再把它们分成几个更小的子问题，以此类推，直至可以直接求出解为止。这就是分治策略的基本思想。

二、算法步骤及问题举例

通常我们把分治算法分为三步进行实现。

分解：将原问题分解成若干个规模较小，互相独立，与原问题形式相同的子问题。解决：若子问题规模较小且容易被解决则直接解决，否则递归的解各个子问题。合并：将各个子问题的解合并为原问题的解。

这里我们以汉诺塔问题为例：

相传在古印度圣庙中，有一种被称为汉诺塔(Hanoi)的游戏。该游戏是在一块铜板装置上，有三根杆(编号A、B、C)，在A杆自下而上、由大到小按顺序放置64个金盘(如下图)。游戏的目标：把A杆上的金盘全部移到C杆上，并仍保持原有顺序叠好。操作规则：每次只能移动一个盘子，并且在移动过程中三根杆上都始终保持大盘在下，小盘在上，操作过程中盘子可以置于A、B、C任一杆上。

对于这样一个问题，任何人都不可能直接写出移动盘子的每一步，现在我们将这个问题分解。

假设现在只有两个盘子，大小从小到大进行编号1，2。那我们很容易的可以得到一个从A杆移到C杆的步骤：1->B,2->C,1->C接着我们假设有三个盘子，大小从小到大进行编号1，2，3。经过分析，我们以然可以容易的得到从A杆移到C杆的步骤：1->C,2->B,1->B,3->C,1->A,2->C,1->C

  随着盘子的增加，移动步骤也会增多，但是我们可以发现一个问题，我们的移动步骤遵循一个规律，我们始终是将1到n-1个盘子先放到B，再将最大的盘子移动到C，然后一直循环这个过程。   简单来说，不管有多少个盘子，我们都可以将其看成是两个盘子，即1到n-1这个盘子和第n个盘子，然后递归的将1到n-1这个盘子放到B，再将最大的盘子n放到C，最后将1到n-1这个盘子放到C。

三、分治算法解决汉诺塔问题代码实现

/** * 分治算法Davide-and-Conquer * 解决汉诺塔问题 * @author dankejun * @create 2020/9/1810:01 */ public class HannoTower { public static void main(String[] args) { hannoTower(3,'A','B','C'); } public static void hannoTower(int num, char a, char b, char c) { //如果只有一个盘 if (num == 1) { System.out.println("第1个盘从 " + a + "->" + c); } else { //如果n>=2，我们总可以看作是两个盘，最下面的一个盘和上面的所有盘 //1.先把最上面的所有盘A->B hannoTower(num - 1, a, c, b); //2.把最下面的盘A->C System.out.println("第" + num + "个盘从 " + a + "->" + c); //3.把B塔所有盘移动到C hannoTower(num-1,b,a,c); } } }

测试结果：