分治算法介绍

  1. 分治法是一种很重要的算法。字面上的解释是‘分而治之’，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题。。。。直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。这个技巧是很多高效算法的基础

  2. 分治算法可以求解一些经典问题

    • 二分搜索
    • 大整数算法
    • 棋盘覆盖
    • 合并排序
    • 快速排序
    • 线性时间选择
    • 最接近点对问题
    • 循环赛日程表
    • 汉诺塔

  3. 代码实现

    public class 汉诺塔 {
        public static void main(String[] args) {
            hanoiTower(5, 'a', 'b', 'c');

        }
        public static void hanoiTower(int num,char a, char b,char c){
            if(num == 1){
                System.out.println("第1个盘从"+a+"->"+c);
            }else {
                /*
                如果我们有n>=2情况，我们总是可以看做是两个盘 最下面的一个盘 上面的所有盘
                先把最上面的所有盘A->B,移动过程会使用到C
                把最下面的盘A->C
                把B塔的所有盘从B->C,移动过程使用到a塔
                 */
                hanoiTower(num-1,a,c,b);
                System.out.println("第"+num+"个盘从"+a+"->"+c);
                hanoiTower(num-1, b, a, c);
            }
        }
    }