PS：本文为转载文章，原文可读性会更好，文末有原文链接文章介绍1、2分治算法的步骤1、3用分治算法解决汉诺塔问题1、分治算法1、1分治算法基本介绍对于多个相似的子问题，将将子问题分解为多个更小的子问题，直到最终的子问题可以用最简单的方式直接求解，原问题的解就是子问题解的组合；我们看到二分查找、棋盘模型、归并排序、快速排序、汉诺塔等经典算法被应用到分而治之算法中。1.2步骤（1）分解分治算法，将原问题分解为N个更小的、独立的、形式与原问题相同的子问题。(2)求解，如果子问题规模较小，直接求解；如果规模较大，则递归求解。(3)合并，将各个子问题的解合并为原问题的解。1.3用分而治之算法解决汉诺塔问题为了理解汉诺塔问题，我先画一张图，如图1；从下到上，从大到小依次放置N个（图1中为3个）金盘（如图1所示）；游戏的目标是将A杆上的所有金盘移到C杆上，并保持原来的顺序堆叠起来；操作规则：一次只能移动一个盘子，移动过程中大盘子始终在三根杆的底部，小盘子在顶部。在操作过程中，可以将板放置在A、B和C中。在任何一极。为了更好的总结汉诺塔的规律，我们先以图1为例。根据游戏规则，我们最终的结果是把所有的杆子从A移到杆子C。从下到上的顺序是3、2、1对；好吧，我们现在分3步移动盘子。(1)以B极为传递极。这一步，我们终于要把1号盘和2号盘拿到B极，才能把3号盘从A极转移到C极，对吧？先把1号盘放在C极，再把2号盘放在B极，再把1号盘从C极拿到B极。此时，经过这一步，结果如图2；图（2）直接从3号盘中取出A杆，套在C杆上。经过这一步，结果如图3;图（3）使用A杆作为传递杆。我们这一步的最终目标是要把B极上的圆盘1和2带到C极对吧？先从B极走1号盘到A极，再从B极走2号盘到C极，最后从A极走1号盘到C极，完成这一步的画面如图4；图不错，现在总结一下这三步，第一步移动3次，第二步移动1次，第三步移动3次，总共移动7次，那么得出结论总步数等于2的n次方，再负1等于7，其中n表示一开始A极上的板数。这里我们推断一下，n代表一开始A杆上的板数。当n为1时，只需要移动一次，对吧？也就是说直接拿盘子到C杆上就行了；当n大于1时，你需要像上面说的那样分3步移动盘子，对吧？第一步和第三步的步数是一样的吧？第二步只需要移动一次。根据总步数等于2的n次方再减1的规则，（2^n表示2的n次方）第一步和第三步走的次数都是(2^n-2)/2。当n大于1时，汉诺塔问题是一个递归问题，其规则如下：第一次用B极作为转移极，将1到n-1的盘子移动到该极B、再从A极取第n极板到C极；第二次以A极为传递极，将1至n-2极板移至A极，再将n-1极板从B极移至C极；第三次以B极为过渡极，将1至n-3的板材接至B极，再将n-2的板材从A极接至C极；以此类推……直到1号板被带到C极。好了，我们用Java代码来实现一下（1）新建一个Test类：packagecom.xiaoer.demo；publicclassTest{publicstaticvoidmain(String[]args){hanoi(3,'A','B','C');}/**@paramn表示盘数@parama为起始pole，也就是从这个杆子上取的板放在其他的杆子上@paramb是传递杆子，不一定是字母b传递杆子，只要是第三个参数，只要是第三个参数,就是传递杆@paramc目标杆，也就是从其他杆子上拿下来的盘子放在这个杆子上*/publicstaticvoidhanoi(intn,chara,charb,charc){if(n==1){System.out.println(a+"-->"+c);}else{/***第一步，一开始n为3时，直接将板1和2移动到B极；*推理，当n大于1且为其他数时，直接将板1移至(n-1)移至极B**/hanoi(n-1,a,c,b);/***第二步，一开始n为3时，直接拿3号盘到C极；*推理，当n大于1且为其他数时，直接将platen移动到C极*/System.out.println(a+"-->"+c);/***第三步，当一开始n为3时，直接从B极拿板1和2到C极；*推理，当n大于1且为其他数时，直接将盘子1运到(n-1)从MovebarA到barC*/hanoi(n-1,b,a,c);}}}的程序运行结果如下；图片
