大家好，我是被白菜拱的猪。

一个热爱学习废寝忘食头悬梁锥刺股，痴迷于girl的潇洒从容淡然coding handsome boy。

文章目录

一、写在前言二、分治算法（一）内容介绍（二）汉诺塔问题1、思路讲解2、代码实现 三、结束语

一、写在前言

数据结构内容大体已经学的差不多，终于迈进了算法的大门，下面将学习几个常见的算法思想，好了闲话不多说，今天让我们走进分治算法的世界。

二、分治算法

（一）内容介绍

分治分治就是分而治之，把一个复杂大的问题分解成一个个小小的问题，然后在去解决这些的小的问题就简单许多了，然后最后在将这些小的问题的解构建成原问题的解。看到这里我们脑海里不免跳出一个词-“递归”，我们前面像什么前序遍历啊，这就是拆解成一个个子树，先去遍历那些子树，一个个子树遍历完了，最终这颗大树也就遍历完了。

它的英文名很好的说明了这个问题，divide and conquer，先divide然后在conquer就是征服战胜解决它。

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

我们下面通过汉诺塔问题来具体说明什么是分治算法。

（二）汉诺塔问题

1、思路讲解

假如有三个柱子A，B，C。假如只有一个我们就直接从A移到C了，那么多个呢？我们把圆盘总看成两部分，最下面的一个盘和最上面的所以盘，我们最上面的所有盘从A移到B，把最下面的一个盘从A移到C，在把B移到C，这就是分，使用递归，最上面的又在分成两部分，然后在重复这样的过程。我们使用递归，往往只针对于眼前，这样就好理解，把里面的分出来的个体在去当做整体。这样说出来比较抽象，奈何语言表达能力太差，见谅。

2、代码实现

talk is shit，show me the code

package com.codingboy.algorithm.divideandconquer; /** * @author: ljl * @date: 2020/9/3 10:23 * @description: 分治算法求解汉诺塔问题 */ public class HanoiTower { public static void main(String[] args) { hanoiTower(5,'A','B','C'); } //num代表盘子数，a，b，c代表柱子,c代表目标盘 public static void hanoiTower(int num,char a,char b,char c) { if (num == 1) { //假如只有一个圆盘，我们直接将圆盘从a移到c，我们最终的目的就是c System.out.println("第"+num+"圆盘从"+ a +"移到" + c); }else { //分成两个盘，最下面一个和上面的所有的圆盘 //先移动最上面的盘，从a移到b hanoiTower(num - 1,a,c,b); //在移动最后一个盘 System.out.println("第"+num+"圆盘从"+ a +"移到" + c); //最后将b上面的圆盘移动到c hanoiTower(num - 1,b,a,c); } } }

三、结束语

可能仅仅通过汉诺塔这一个例子还不能理解分支算法的精髓，日后还得多加练习。