常用的十大算法-分治算法

常用的十大算法-分治算法 分治算法

分治算法从字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或者更多的相同的问题或相似的问题，再把子问题分成更小的子问题，直到最后子问题可以简单的求解，原问题的解即子问题的解合并。如排序算法（快速排序，归并排序），傅里叶变换，分治算法可以求解的一些经典问题。

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

1、二分搜索
2、大数整除法
3、棋盘覆盖
4、合并排序
5、快速排序
6、线性时间选择
7、最接近点对问题
8、循环赛日程表
9、汉诺塔

分治算法的基本步骤

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

package algorithm;


public class HanoiTower {
    public static void main(String[] args) {
        hanoiTower(3, 'A', 'B', 'C');
    }

    
    public static void hanoiTower(int num, char a, char b, char c) {
        //只有一个盘子
        if (num == 1) {
            System.out.println(a + "=>" + c);
        } else {
            //当n>=2时，可以看成最下面的盘和上面的盘(n-1)
            //1、把 n-1个盘先移动到从A->B,移动过程会使用到C
            hanoiTower(num - 1, a, c, b);
            //2、把最下面的盘从A->C
            System.out.println(a + "=>" + c);
            //3、把B柱的所有盘从B->C，移动过程会使用到
            hanoiTower(num - 1, b, a, c);
        }
    }

}