十种常用的算法

分治算法

一：分治算法介绍

1）：分治算法是一种很重的算法，在字面上解释就是“分而治之”，就是将一个复杂的问题先分成两个或者更多的相同或者是相似的子问题，再把子问题分成更小的子问题。。。。直到最后的子问题可以简单直接求解，原问题的解即子问题的解的合并。这个技巧 是很多高效算法的基础，如排序算法（快速排序，归并排序等）。傅里叶变换等
2）：分治算法可以求解一些经典问题：

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

二：分治算法的步骤

分治算法在每一层的递归上都有三个步骤
1）：分解：将原问题分解成若干个规模较小，相互独立，与原问题形式相同的子问题
2）：解决：若子问题的规模较小而且容易被解决则直接解决，否则递归地解决各个子问题
3）：合并：将各个子问题的解合并位原问题的解

三：分治算法的实践——汉诺塔

汉诺塔介绍：
汉诺塔问题是源于印度古老传说的一个益智游戏。大梵天创造世界的时候创造了三根金刚石柱，在一根柱子上从下向上按照大小顺序摞着64片黄金圆盘，大梵天命令婆罗门把圆盘从下面按照大小顺序重新摆放在另一根柱子上，并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。

汉诺塔思路分析：
我们假设这三根金刚石柱为A,B,C
1）：当只有一个盘：从A->C
当我们有n>=2个盘的时候，我们总是可以看作两个盘，最底下的是一个盘，其余的为另一个盘。
1）：我们先将上面的盘移动到B：A->B
2）：把下面的盘移动到C：A->C
3）：在把B塔上的盘移动到C：B->C

四：代码实现

package 分治算法;

/*
    分治算法经典例题：汉诺塔
 */
public class HannuoTower {
    public static void main(String[] args) {
        hannuoTower(5,'A','B','C');

    }

    /**
     *
     * @param num   表示有多少的盘子
     * @param a     表示第A根柱子
     * @param b     表示第B根柱子
     * @param c     表示第C根柱子
     */
    public static void hannuoTower(int num,char a,char b,char c){
        if (num == 1){
            //表示只有一个盘子，那么就是直接从A柱到C柱
            System.out.println("第1个盘子从"+a+"->"+c);
        }else { //表示num>1
            //第一步将最底下盘子以上的盘子从A移动到B柱，过程中会使用到C柱
            hannuoTower(num-1,a,c,b);
            //第2步将最底下的盘子移动到C柱
            System.out.println("第"+(num)+"个盘子从"+a+"->"+c);
            //第三步将B柱的盘子移动到C柱，过程中会用到A柱
            hannuoTower(num-1,b,a,c);
        }


    }

}