十种常用算法之分治算法（java版）

十种常用算法之分治算法（java版）

本文讲解：分治算法的理解和代码实现

1、分治算法的介绍

1、基本介绍

2、基本步骤

3、分治算法

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

• 再来看这个
  

2、分治算法的应用案例 （1）汉诺塔的思想

• 当只有一个盘的时候，会直接把盘从A柱子移动到C柱子就OK了
• 当有两个盘子的时候呢？是不是先把上面个盘子移动到B柱子，然后再移动地下的大盘到C，再转义B柱子上的
  
• 当有三个盘子呢？自己好好想一下，要把上面两个分为一个整体，进行处理，（不能把上面个一整一次性拿走）
  
• 当有四个盘子的时候一样的，要把上面三个分为一个整体进行处理（不能把上面个一整一次性拿走）
  
• 。。。。。。。。。。。。。。。。等

（2）上面思想分析

• 如果只有一个盘：则A到C即可
• 如果有两个或以上的盘子的时候：总是看作两个盘，最下面个盘子和上面的一部分盘。
  • 把最上面的整体一定到B柱子
  • 把最下面个盘子移动到C柱子
  • 把B的其他盘移动到C柱子

（3）代码实现

还是比较好理解的，千万不要用64去测试啊，我电脑跑了几分钟没有跑出个结果。

public class Hanoitower {
    public static void main(String[] args) {
        hanoitwer(5,'A','B','C');
    }


    
    public static void hanoitwer(int num,char a, char b, char c) {
        //如果只有一个盘的时候
        if (num == 1) {
            System.out.println("第1个盘从：" + a + "->" + c);
        } else {//如果不是一个盘子的时候
            //1、第一步，把最下面个的上面部分当做一个整体从A柱子移动到B柱子
            //进行递归处理 中间移动过程会用到C柱子，目的是A移动到B
            hanoitwer(num - 1,a,c,b);
            //2、把最下面的一个移动到C柱子
            System.out.println("第" + num + "个盘子：" + a + "->" + c);
            //3、把B上的盘子一定到C，此过程是把B上的移动到C，中间会用到A柱子
            hanoitwer(num - 1,b,a,c);
        }
     }
}

• 还是要回归我们的分，主要是要会分，把上面的分开，然后当做一个子问题，进行重新递归排。