软件工程算法之分治法_第1页
软件工程算法之分治法_第2页
软件工程算法之分治法_第3页
软件工程算法之分治法_第4页
软件工程算法之分治法_第5页
已阅读5页，还剩1页未读， 继续免费阅读

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

1、 对于一个程序员来说，算法是必不可少的。现在的算法五花八门，让人有点找不到北，不过归根结底，也就那么几类，其他算法都是这些算法的优化或者派生。    今天就跟大家说说分治法。【算法本质】    分治法是得益于“大禹治水”的思想研究得来的算法。本质为“分而治之”。俗一点就是“大事化小，小事化了”。【设计思想】    将一个难以直接解决的大问题分解成一些规模较小的相同问题以便各个击破，分而治之。如果规模为n的问题，可以分解成k个子问题，1<k<=n，这些子问题相互独立切与原问题相同，分治法产生的子

2、问题，往往是原问题的较小模式，这就为递归技术提供了方便。【算法递归步骤】    （一）分解。将原问题分解成一系列子问题。    （二）求解。递归地求解各子问题。若子问题足够小，则直接求解。    （三）合并。将子问题的解合并成原问题的解。【沙场点兵】这是一道软考题。QUICKSORT函数为快速排序，PARTITION函数作用为对数组A排序，并返回枢轴元素位置下标。举一个实例：对数组A= 9，3，5，8，7 进行排序。跟着代码走，现在p=0,r=4，所以p<r，执行q=PARTITION(A

3、，p，r)，进入第一次排序。x=Ar=7，i=p-1=-1，j的变化从p-r-1，即0-3。循环体内，比较Aj与x的值： j=0时，Aj=9>x。j=1进入下次循环，如图； j=1时，Aj=3<x，i=i+1=0，交换Ai和Aj。j=2进入下次循环，如图； j=2时，Aj=8>x，j=3进入下次循环，如图； j=3时，Aj=4<x，i=i+1=2，交换Ai和Aj，如图。j=4>r-1，退出循环； 根据分治算法，由枢轴元素为界限，把原数组划分为2组，枢轴元素左边的元素>枢轴元素>枢轴元素右边的元素。所以，我们现在要做的就是把x的值与i+1所在位置的元素进行交换。即Ai+1与Ar交换。 最后把枢轴元素的下标返回给q，即q=2。第一趟排序完成。然后执行QUICKSORT（A，p，q-

人人文库> 全部分类> 教育资料 > 课件下载

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论