关于后端:我所知道的十大常用算法之分治算法解决汉诺塔问题

前言需要

本篇算法介绍的十大罕用算法的：分治算法，那么在后面的一些算法文章中就有分治算法的概念

一、什么是分治算法？

简略来说字面意思就是‘分而治之’，就是把一个简单的问题分成两个或者更多的雷同或相似的子问题，再把子问题分成更小的子问题

这种思维是很多高效算法的根底，如：疾速排序、归并排序、博立叶替换等

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

二、分治算法的设计模式

if |P|≤n0  then return(ADHOC(P))

其中|P|示意问题P的规模；n0为一阈值，示意当问题P的规模不超过n0时，问题已容易间接解出，不用再持续合成，ADHOC(P)是该分治法中的根本子算法，用于间接解小规模的问题P。

//将P合成为较小的子问题 P1 ,P2 ,…,Pkfor i←1 to kdo yi ← Divide-and-Conquer(Pi)   递归解决PiT ← MERGE(y1,y2,…,yk)   合并子问题return(T)

因而，当P的规模不超过n0时间接用算法ADHOC(P)求解，否则拆为其余子问题。算法MERGE(y1,y2,…,yk)是该分治法中的合并子算法，用于将P的子问题P1 ,P2 ,…,Pk的相应的解y1,y2,…,yk合并为P的解

三、分治算法最佳实际-汉诺塔

简略盘汉诺塔的演示

1.最简略的时候，只有一个盘，A、B、C塔，只需一步到位

2.简单一点时有两个盘，A、B、C塔，会怎么操作呢？

汉诺塔思路剖析

1.从两种状况来说，咱们能够不论A塔有多少盘，咱们都能够看成二个盘（最上、最下）

2.第一步：将最下面的盘移至B塔
3.第二步：将最上面的盘移至C塔
4.第三步：将B塔上的所有盘移至C塔

汉诺塔代码思路剖析

1.如果只有一个盘的时候，只须要一步到位即可
2.如果咱们盘的数量n，它是 n >= 2的时候，咱们看做两个盘（最上、最下）
2.1第一步：咱们须要将最下面的盘移至B塔
2.2第二步：咱们须要将最上面的盘移至C塔
2.3第三步：咱们须要将B塔上的所有盘移至C塔

//汉诺塔挪动的办法//应用分治算法public static void hanioTower(int num,char a ,char b,char c){    //如果只有一个盘，那么就是挪动一次    if(num == 1){        System.out.println("第1个盘从 " + a + " ->" + c);    }else{        //如果咱们盘的数量n，它是 n >= 2的时候，咱们看做两个盘（最上、最下）        //2.1第一步：咱们须要将最下面的盘移至B塔        hanioTower(num -1,a,c,b);        //2.2第二步：咱们须要将最上面的盘移至C塔        System.out.println("第" + num +"个盘从 " + a +" ->"+ c);        //2.3第三步：咱们须要将B塔上的所有盘移至C塔        hanioTower(num -1 ,b , a , c);    }}

咱们依据不同盘数状况，应用demo 测试看看吧

public static void main(String[] args) {    //只有一个盘的状况    hanioTower(1,'a','b','c');}运行后果如下：第1个盘从 a ->c

public static void main(String[] args) {    //有二个盘的状况    hanioTower(2,'a','b','c');}运行后果如下：第1个盘从 a ->b第2个盘从 a ->c第1个盘从 b ->c

public static void main(String[] args) {    //有三个盘的状况    hanioTower(3,'a','b','c');}运行后果如下：第1个盘从 a ->c第2个盘从 a ->b第1个盘从 c ->b第3个盘从 a ->c第1个盘从 b ->a第2个盘从 b ->c第1个盘从 a ->c