实验项目1:蛮力法与分治法应用.doc_第1页
实验项目1:蛮力法与分治法应用.doc_第2页
实验项目1:蛮力法与分治法应用.doc_第3页
实验项目1:蛮力法与分治法应用.doc_第4页
实验项目1:蛮力法与分治法应用.doc_第5页
已阅读5页,还剩6页未读 继续免费阅读

下载本文档

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

文档简介

实验项目1:蛮力法与分治法应用1、 目的与要求: 实验目的:了解蛮力法和分治法的基本思想,学会运用蛮力法和分治法解决实际系统设计应用中碰到的问题。 实验要求:用蛮力法实现选择、冒泡排序,或旅行商问题、背包问题等问题(任选其中之一)。用分治法实现合并排序或快速排序。要求写出算法的伪代码描述,并编写程序实现之,相关算法放在函数内实现,主程序给出测试用例,要设计足够多的相关测试用例,验证程序的正确性。注意观察程序执行结果和运行的时间。实验报告要求给出问题定义及算法的伪代码描述,程序设计的代码,算法的测试用例及结果,并分析算法的时间效率,回答指导书中的思考题。 2、 实验内容:(2) 用分治法实现快速排序、合并排序算法。本实验主要是用分治法实现合并排序,快速排序程序等。 合并排序算法描述:MergeSort ( A0.p-1 ) / input 待排序数组 A0.n-1 / output 非降序排列的数组 A0.n-1 if ( n1 ) /至少有2个元素 Copy A0. n/2-1 to B0. n/2-1 ; Copy An/2.n-1 to C0. n/2-1 ; MergeSort ( B0. n/2-1 ); MergeSort (C0. n/2-1 t); Merge (B, C, A); /复制回数组a 快速排序算法描述: QuickSort ( A1. r ) if (l p / 将= x的元素交换到左边区域 repeated i=i+1; until Ai p / j Swap( Ai = aj ); Swap( Al, Aj ) return j;要求先给出算法的伪代码,然后用C+或其他程序设计语言编写程序实现之,并设计相关的测试用例,验证程序的正确性。测试用例要求达到30个数据以上,或程序生成100个以上的数据,验证并说明程序的正确性。上述实验项目是一般要求,的如学生水平较高,上述这些程序已经掌握,可以设计其他难度较高问题的算法和程序。如:hanoi 塔问题。最后要求结合实验体会,分析算法的时间效率。实验思考题:1、蛮力法的优缺点是什么? 适用什么情况? 2、分治法的基本思想是什么?适用什么情况?说明分治法的优点 和局限性。实验代码:#includeusing namespace std;inline void Swap(int &x,int &y) /交换x,yint temp=x;x=y;y=temp;int Partition(int a,int p,int r) /通过一趟排序将要排序的数据分割成独立的两部分/Partition 以确定一个基准元素aq 对子数组ap:r进行划分int i=p,j=r+1;int x=ap;/一部分的所有数据都比另外一部分的所有数据都要小while(true)while(a+ix&ir);/将x);/将x得元素交换到右边区域if(i=j) break;Swap(ai,aj); /交换ai,ajap=aj;aj=x;return j; /返回划分点void QuickSort(int a,int p,int r) /利用递归进行快速排序if(pr)int q=Partition(a,p,r); /Partition返回划分点j,此处使q=j q为分裂点QuickSort(a,p,q-1);/对左半段排序QuickSort(a,q+1,r);/对右半段排序int main() int len;coutlen;int *a=new intlen; /动态生成一个长度为len的数组cout请输入一个数组: ; for(int i=0;iai;QuickSort(a,0,len-1); /对数组进行快排cout排序后的数组是:;for(int j=0;jlen;j+)coutaj ; /输出数组coutendl;delete a; return 0;测试结果图:图1:图2:图3:30组数据测试图:合并排序代码: /递归实现合并排序 #include stdafx.h #include using namespace std; int a = 10,5,9,4,3,7,8; int b7; template void Merge(Type c,Type d,int l,int m,int r); template void MergeSort(Type a,int left,int right); int main() for(int i=0; i7; i+) coutai ; coutendl; MergeSort(a,0,6); for(int i=0; i7; i+) coutai ; coutendl; template void Merge(Type c,Type d,int l,int m,int r) int i = l,j = m + 1,k = l; while(i=m)&(j=r) if(cim) for(int q=j; q=r; q+) dk+ = cq; else for(int q=i; q=m; q+) dk+ = cq; template void MergeSort(Type a,int left,int right) if(leftright) int i = (left + right)/2; MergeSort(a,left,i); MergeSort(a,i+1,right); Merge(a,b,left,i,right);/合并到数组b /复制回数组a for(int g=left; g=right; g+) ag = bg; 测试结果图:图1:图2:图3:30组数据测试图:分治法的基本思想:任何一个可以用计算机求解的问题所需的计算时间都与其规模N有关。问题的规模越小,越容易直接求解,解题所需的计算时间也越少。例如,对于n个元素的问题,当n=1时,不需任何计算;当n=2时,只要作一次比较即可排序好;当n=3时只要做3次比较即可,。而当n较大时,问题就不那么容易处理了。要想直接解决一个规模较大的问题,有时是相当困难的。适用什么情况?分治法所能解决的问题一般具有以下几个特征:1) 该问题的规模缩小到一定的程度就可以容易地解决2) 该问题可以分解为若干个规模较小的相同问题,即该问题具有最优子结构性质。3) 利用该问题分解出的子问题的解可以合并为该问题的解;4) 该问题所分解出的各个子问题是相互独立的,即子问题之间不包含公共的子问题。上述的第一条特征是绝大多数问题都可以满足的,因为问题的计算复杂性一般是随着问题规模的增加而增加;第二条特征是 应用分治法的前提它也是大多数问题可以满足的,此特征反映了递归思想的应用;第三条特征是关键,能否利用分治法完全取决于问题是否具有第三条特征,如果具 备了第一条和第二条特征,而不具备第三条特征,则可以考虑用贪心法或动态规划法。第四条特征涉及到分治法的效率,如果各子问题是不独立的则分治法要做许多不必要的工作,重复地解公

温馨提示

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

评论

0/150

提交评论