算法（Java实现）—— 分治算法

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了算法（Java实现）—— 分治算法，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1872字，纯文字阅读大概需要3分钟。

内容图文

分治算法

分治算法的设计模式

基本思想

把复杂问题分解成若干互相独立容易求解的子问题

经典问题

1. 二分搜索

2. 大整数乘法

3. 棋盘覆盖

4. 合并排序

5. 快速排序

6. 线性时间选择

7. 最接近点对问题

8. 循环赛日程表

9. 汉诺塔

基本步骤

1. 分解：将原问题分解成若干规模小的，相互独立，与原问题形式相同的子问题

2. 解决：将子问题规模较小而容易被解决则直接解决，否则递归的解各个子问题

3. 合并：将各个子问题的解合并成原问题的解

设计模式

Divide-and-Conquer(P){
    if |p| <= n~0
        then return(ADHOC(p))
    //将 p分解为较小的子问题p1，p2，p3...pk
    for i<---1 to k
        do yi<---Divide-and-COnquer(pi) //递归解决pi
    T <---MERGE(y1,y2,...,yk)//合并子问题
    return（T)
}
?
?

• |p|表示问题p的规模

• n0为阈值，表示当问题p的规模不超过n0时，问题已容易直接接触，不必再继续分解

• ADHOC（p）时该分治法中的基本子算法，用于直接解小规模的问题p

• 因此，当p的规模不超过n0时直接用算法ADHOC（p）求解

分治法解决汉诺塔实例

思路分析

1. 如果只有一个盘，A - >C

2. 如果盘n > = 2，总是可看作两个盘1.下面的盘，2.上面的所有盘

3. 先把最上面的盘A - > B

4. 把最下边的盘A - > C

5. 把B塔的所有盘从B - > C

代码实现

package com.why.divide_and_conquer_algorithm;
?
import java.util.concurrent.CountDownLatch;
?
/**
 * @Description TODO 分治法解决汉诺塔问题
 * @Author why
 * @Date 2020/11/13 15:34
 * Version 1.0
 **/
public class HanoiTower {
    public static void main(String[] args) {
        hanoiTower(5,'A','B','C');
    }
?
    /**
     * 汉诺塔的移动方法
     * 使用分治算法
     * @param num
     * @param a
     * @param b
     * @param c
     */
    public static void hanoiTower(int num,char a,char b,char c){
        //如果只有一个盘
        if(num == 1){
            System.out.println("第1个盘从 "+ a + "->" + c);
        }else {
            //最上面的盘A->B，移动过程会使用到c
            hanoiTower(num - 1,a,c,b);
            //最下边的盘A->C
            System.out.println("第"+ num + "个盘从 " + a + "->" + c);
            //把B塔的虽有盘从 B -> C 移动过程使用到a塔
            hanoiTower(num - 1,b,a,c);
        }
?
    }
}

 

内容总结

以上是互联网集市为您收集整理的算法（Java实现）—— 分治算法全部内容，希望文章能够帮你解决算法（Java实现）—— 分治算法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---