乐趣区

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

jiezi

前言需要

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

一、什么是分治算法？

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

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

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

二、分治算法的设计模式

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

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

// 将 P 合成为较小的子问题 P1 ,P2 ,…,Pk
for i←1 to k
do yi ← Divide-and-Conquer(Pi)   递归解决 Pi
T ← 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 塔

更多盘的汉诺塔演示

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

那么依据咱们的思路剖析，此时咱们应该是分成看做二个盘（最上、最下）

那么第一步：咱们先将最下面的塔移至 B 塔



接下来执行第二步：将最上面的盘移至 C 塔

接下来第三步：将 B 塔上的所有盘移至 C 塔



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

那么依据咱们的思路剖析，此时咱们应该是分成看做二个盘（最上、最下）

那么第一步：咱们先将最下面的塔移至 B 塔







接下来执行第二步：将最上面的盘移至 C 塔

接下来第三步：将 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








退出移动版