分治算法那些事

想必大家通过算法的名字就已经明白了，这个算法的过程，一个是分，一个是治。那么我为什么要使用这种算法呢？因为当前的问题是我们使用现有的方法是解决不了的，所以我们需要将一个复杂的问题分成两个或者是更多个相同或相似的子问题，然后再一我们已有的方法去解决。因此，我们要先分，再治，最后再合并。

可能大家觉得有一点抽象，这个算法的本质就是我们将复杂的问题简单化使用辅助工具来解决。在这个算法中，我们的工具，那就是递归。
下面我给大家讲解一下这个算法的典型例题汉诺塔。

有三根杆子A，B，C。A杆上有N个(N>1)穿孔圆盘，盘的尺寸由下到上依次变小。要求按下列规则将所有圆盘移至C杆： 每次只能移动一个圆盘； 大盘不能叠在小盘上面。 提示：可将圆盘临时置于B杆，也可将从A杆移出的圆盘重新移回A杆，但都必须遵循上述两条规则。

问：如何移？最少要移动多少次？

在这道题中，我们可以看出，需要将最左边的盘子全部移到最右边，而且要与最左边的盘子保持一样的顺序，那么这里就会体现到我们分治算法的思想，分而治之。而中间的b就是我们解决这道题的重要途径，我们需要利用b来作为一个中间的桥梁。我们拿三个盘子举例子，首先我们需要将第一个盘子放到c上，然后再将第二个盘子放到b上，再将第一个盘子也放到b上，然后将第三个盘子放到c上，然后将第一个盘子放到a上，再将第二个盘子放到c上，再将第一个盘子放到c上。代码如下：

@Test
    public void test(){
        hanNouTower(3,'a','b','c');
    }
    public void hanNouTower(int count,char a ,char b, char c){
        if(count==1){
            System.out.println("第1个盘子从"+a+"移动到了"+c);
        }else{
            hanNouTower(count-1,a,c,b);
            System.out.println("第"+count+"个盘子从"+a+"移动到了"+c);
            hanNouTower(count-1,b,a,c);
        }
    }