实验项目1：蛮力法与分治法应用

《实验项目1：蛮力法与分治法应用》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、实验项目1：蛮力法与分治法应用1、目的与要求：实验目的：了解蛮力法和分治法的基本思想，学会运用蛮力法和分治法解决实际系统设计应用中碰到的问题。实验要求：用蛮力法实现选择、冒泡排序，或旅行商问题、背包问题等问题（任选其中之一）。用分治法实现合并排序或快速排序。要求写出算法的伪代码描述，并编写程序实现之，相关算法放在函数内实现，主程序给出测试用例，要设计足够多的相关测试用例，验证程序的正确性。注意观察程序执行结果和运行的时间。实验报告要求给出问题定义及算法的伪代码描述，程序设计的代码，算法的测试用例及结果，并分析算法的时间效率，回答指导书中的思考题。2、实验内容：（2）用分治法实现快速排

2、序、合并排序算法。本实验主要是用分治法实现合并排序，快速排序程序等。合并排序算法描述：MergeSort(A[0...p-1])//input待排序数组A[0..n-1]//output非降序排列的数组A[0..n-1]if(n>1){//至少有2个元素CopyA[0..n/2-1]toB[0..n/2-1];CopyA[n/2..n-1]toC[0..n/2-1];MergeSort(B[0..n/2-1]);MergeSort(C[0..n/2-1]t);Merge(B,C,A);//复制回数组a快速排序算法描述：QuickSort(A[1..r]){if(l

3、tion(A[l,r]);//s是分裂位置QuickSort(A[l..s-1]);//对左半段排序QuickSort(A[s+1,r);//对右半段排序}Partition(A[l..r]){p=A[[l];i=l;j=r+1;repeatedrepeatedi=i+1;untilA[i]>p//将>=x的元素交换到左边区域repeatedi=i+1;untilA[i]>p//<=x的元素交换到右边区域Swap(A[i],A[j])Untili>jSwap(A[i]=a[j]);Swap(A[l],A[j])returnj;要求先给出算法的伪代码，然后用C++或其他程序设计语言编写

4、程序实现之，并设计相关的测试用例，验证程序的正确性。测试用例要求达到30个数据以上，或程序生成100个以上的数据，验证并说明程序的正确性。上述实验项目是一般要求，的如学生水平较高，上述这些程序已经掌握，可以设计其他难度较高问题的算法和程序。如：hanoi塔问题。最后要求结合实验体会，分析算法的时间效率。实验思考题：1、蛮力法的优缺点是什么？适用什么情况？2、分治法的基本思想是什么？适用什么情况？说明分治法的优点和局限性。实验代码：#includeusingnamespacestd;inlinevoidSwap(int&x,int&y)//交换x,y{inttemp

5、=x;x=y;y=temp;}intPartition(inta[],intp,intr)//通过一趟排序将要排序的数据分割成独立的两部分//Partition以确定一个基准元素a[q]对子数组a[p:r]进行划分{inti=p,j=r+1;intx=a[p];//一部分的所有数据都比另外一部分的所有数据都要小while(true){while(a[++i]x);//将>x得元素交换到右边区域if(i>=j)break;Swap(a[i],a[j]);//交换a[i],a[j]}a[p]=a[j];a[j]=x

6、;returnj;//返回划分点}voidQuickSort(inta[],intp,intr)//利用递归进行快速排序{if(p>len;int*a=newint[len];//动态生成一个长度为len的数组cout<<"请输入一个数组:";for(inti=0;i

7、入数组cin>>a[i];QuickSort(a,0,len-1);//对数组进行快排cout<<"排序后的数组是:";for(intj=0;jusingnamespacestd;int