本文实例讲述了Java分治法与二分搜索算法。分享给大家供大家参考,具体如下:
1、分治法
分治法的基本思想是将一个规模为n的问题分解为k个规模较小的子问题,这些子问题相互独立且与原问题相同。递归的解这些子问题,然后将各子问题的解合并得到原问题的解。
分治法所能解决的问题一般具有以下几个特征:
1) 该问题的规模缩小到一定的程度就可以容易地解决
2) 该问题可以分解为若干个规模较小的相同问题,即该问题具有最优子结构性质。
3) 利用该问题分解出的子问题的解可以合并为该问题的解;
4) 该问题所分解出的各个子问题是相互独立的,即子问题之间不包含公共的子子问题。
分治法的基本步骤:
分治法在每一层递归上都有三个步骤:
分解:将原问题分解为若干个规模较小,相互独立,与原问题形式相同的子问题;
解决:若子问题规模较小而容易被解决则直接解,否则递归地解各个子问题;
合并:将各个子问题的解合并为原问题的解。
它的一般的算法设计模式如下:
Divide-and-Conquer(P)if |P|≤n0then return(ADHOC(P))//将P分解为较小的子问题 P1 ,P2 ,...,Pkfor i←1 to kdo yi ← Divide-and-Conquer(Pi) △ 递归解决PiT ← MERGE(y1,y2,...,yk) △ 合并子问题return(T)
免责声明:
① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。
② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341
软考中级精品资料免费领
- 历年真题答案解析
- 备考技巧名师总结
- 高频考点精准押题
- 资料下载
- 历年真题
193.9 KB下载数265
191.63 KB下载数245
143.91 KB下载数1148
183.71 KB下载数642
644.84 KB下载数2756
相关文章
发现更多好内容- Uncomtrade数据库免费版本查询指南
- Java Lombok 使用为何不生效及解决办法(java lombok使用不生效怎么解决)
- 如何有效修复uncomtrade数据库
- Java 中接口与抽象类的区别究竟有哪些?(java中接口和抽象类的区别是什么)
- 如何高效地部署 Java 应用程序?(如何部署Java应用程序)
- Java 类的访问控制顺序究竟是怎样的?(java类的访问控制顺序是什么)
- 如何轻松解决 java exe4j 安装问题?(如何解决java exe4j安装问题)
- 如何在 Java 中向 MySQL 数据库添加数据?(java怎么向mysql数据库中添加)
- 如何获取 Java 枚举类的值?(java枚举类的值怎么获取)
- 如何在 Java 中向数据库添加一条数据?(java怎么向数据库添加一条数据)