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

......word资料...实验项目1：蛮力法与分治法应用1、目的与要求：实验目的：了解蛮力法和分治法的基本思想，学会运用蛮力法和分治法解决实际系统设计应用中碰到的问题。实验要求：用蛮力法实现选择、冒泡排序，或旅行商问题、背包问题等问题（任选其中之一）。用分治法实现合并排序或快速排序。要求写出算法的伪代码描述，并编写程序实现之，相关算法放在函数实现，主程序给出测试用例，要设计足够多的相关测试用例，验证程序的正确性。注意观察程序执行结果和运行的时间。实验报告要求给出问题定义及算法的伪代码描述，程序设计的代码，算法的测试用例及结果，并分析算法的时间效率，回答指导书中的思考题。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<r)s=Partition(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++或其他程序设计语言编写程序实现之，并设计相关的测试用例，验证程序的正确性。测试用例要求达到30个数据以上，或程序生成100个以上的数据，验证并说明程序的正确性。上述实验项目是一般要求，的如学生水平较高，上述这些程序已经掌握，可以设计其他难度较高问题的算法和程序。如：hanoi塔问题。最后要求结合实验体会，分析算法的时间效率。实验思考题：1、蛮力法的优缺点是什么？适用什么情况？2、分治法的基本思想是什么？适用什么情况？说明分治法的优点和局限性。实验代码：#include<iostream>usingnamespacestd;inlinevoidSwap(int&x,int&y)//交换x,y{ inttemp=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&&i<r); //将<x的元素交换到左边区域 while(a[--j]>x); //将>x得元素交换到右边区域 if(i>=j)break; Swap(a[i],a[j]);//交换a[i],a[j] } a[p]=a[j]; a[j]=x; returnj;//返回划分点}voidQuickSort(inta[],intp,intr)//利用递归进行快速排序{ if(p<r) { intq=Partition(a,p,r);//Partition返回划分点j，此处使q=jq为分裂点 QuickSort(a,p,q-1); //对左半段排序 QuickSort(a,q+1,r); //对右半段排序 }}intmain(){ intlen; cout<<"请输入数组长度:"; cin>>len; int*a=newint[len];//动态生成一个长度为len的数组 cout<<"请输入一个数组:"; for(inti=0;i<len;i++)//输入数组 cin>>a[i]; QuickSort(a,0,len-1);//对数组进行快排 cout<<"排序后的数组是:"; for(intj=0;j<len;j++) cout<<a[j]<<"";//输出数组 cout<<endl; delete[]a; return0;}测试结果图：图1：图2：

图3：30组数据测试图：

合并排序代码：//递归实现合并排序#include"stdafx.h"#include<iostream>usingnamespacestd;inta[]={10,5,9,4,3,7,8};intb[7];template<classType>voidMerge(Typec[],Typed[],intl,intm,intr);template<classType>voidMergeSort(Typea[],intleft,intright);intmain(){for(inti=0;i<7;i++){cout<<a[i]<<"";}cout<<endl;MergeSort(a,0,6);for(inti=0;i<7;i++){cout<<a[i]<<"";}cout<<endl;}template<classType>voidMerge(Typec[],Typed[],intl,intm,intr){inti=l,j=m+1,k=l;while((i<=m)&&(j<=r)){if(c[i]<=c[j]){d[k++]=c[i++];}else{d[k++]=c[j++];}}if(i>m){for(intq=j;q<=r;q++){d[k++]=c[q];}}else{for(intq=i;q<=m;q++){d[k++]=c[q];}}}template<classType>voidMergeSort(Typea[],intleft,intright){if(left<right){inti=(left+right)/2;MergeSort(a,left,i);MergeSort(a,i+1,right);Merge(a,b,left,i,right);//合并到数组b//复制回数组afor(intg=left;g<=right;g++){a[g]=b[g];}}}测试结果图：图1：图2：

图3：30组数据测试图：分治法的基本思想：任何一个可以用计算机求解的问题所需的计算时间都与其规模N有关。问题的规模越小，越容易直接求解，解题所需的计算时间也越少。例如，对于n个元素的问题，当n=1时，不需任何计算；当n=2时，只要作一次比较即可排序好；当n=3时只要做3次比较即可，…。而当n较大时，问题就不那么容易处理了。要想直接解决一个规模较大的问题，有时是相当困难的。适用什么情况？分治法所能解决的问题一般具有以下几个特征：1)该问题的规模缩小到一定的程度就可以容易地解决2)该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质。3)利用该问题分解出的子问题的解可以合并为该问题的解；4)该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。上述的第一条特征是绝大多数问题都可以满足的，因为问题的计算复杂性一般是随着问题规模的增加而增加；第二条特征是应用分治法的前提它也是大多数问题可以满足的，此特征反映了递归思想的应用；第三条特征是关键，能否利用分治法完全取决于问题是否具有第三条特征