算法介绍分治法是一个很重要的算法。字面解释就是“分而治之”，就是把一个复杂的问题分成两个或多个相同或相似的子问题，再把子问题分成更小的子问题……直到最后的子问题可以可以简单直接地解决。问题的解决方案是子问题的解决方案的组合。这种技术是很多高效算法的基础，比如排序算法（快速排序、归并排序）、傅里叶变换（fastFouriertransform）……一些可以用分支算法求解的经典图：二分查找、大整数乘法,boardcover,mergesort,quicksort,lineartimeselection,closestpairproblem,roundrobinschedule,汉诺塔。分治算法的基本步骤分治法在递归的每一层上都有三个步骤：分解：将原问题分解为若干个较小的、独立的、与原问题相同的子问题求解：若干个子问题如果规模小且容易求解，则直接求解，否则递归求解各个子问题Merge：将各个子问题的解组合成原问题的解分而治之（P）算法的模式如下图所示，其中|P|代表问题P的规模，n0是一个阈值，表示当问题p的规模不超过n0时，这个问题很容易直接解决，不需要继续分解。ADHOC(P)是分治算法中的基本子算法，用于直接求解小规模问题P。因此，当P的规模不超过n0时，直接用ADHOC(P)求解。算法MERGE(y1,y2,...yk)是分治法中的合并子算法，用于合并子问题P1,P2对应的解y1,y2...yk,...Pk的P转化为P的解。分而治之算法实践——河内塔将64个金圆盘从下到上按大小顺序放在一根柱子上，从下往上重新排到另一根柱子上按大小顺序排列，并规定，圆盘不能在小圆盘上放大，一次只能在三个柱子之间移动一个圆盘。思路分析：如果有一个盘子，A->C，如果n>=2个盘子，我们总可以把它看成是两个盘子，一个是最下面的盘子，一个是上面的所有盘子：先把最多的Move把上面所有的圆盘从A移到B，把最下面的一个圆盘从A移到C，把B塔里的所有圆盘从B移到C。packagecom.xie.algorithm;publicclassHanoitower{publicstaticvoidmain(String[]args){hanoiTower(3,'A','B','C');/***第一个磁盘来自A->C*第二个磁盘来自A->B*第一个磁盘从C->B*第三个磁盘从A->C*第一个磁盘从B->A*第二个磁盘从B->C*第一个磁盘从A->C*/}publicstaticvoidhanoiTower(intnum,chara,charb,charc){//如果只有一个磁盘if(num==1){System.out.println("第一个磁盘来自"+a+"->"+c);}else{//如果是n>=2个盘，我们总可以把它看成是两个盘，一个是最下面的盘，一个是上面的所有盘//1。首先将最上面的圆盘从A移动到B，移动过程会用到ChanoiTower(num-1,a,c,b);//2。将最下面的圆盘从A移动到CSystem.out.println("第"+num+"个圆盘来自"+a+"->"+c);//3.将B塔中的所有磁盘从B移动到C，并使用A塔hanoiTower(移动过程中的num-1,b,a,c);}}}【编者推荐】虚拟服务器管理6大优秀实践15技术趋势引领2021年软件开发行业发展太牛逼了，SpringCloud微服务架构细节我看过了|附采访题中国三大电信运营商纽交所是否退市亏损？
