计算机算法设计与分析 期末考试复习资料

《计算机算法设计与分析 期末考试复习资料》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、一、算法设计实例1、快速排序（分治法）intpartition(floata[],intp,intr){inti=p,j=r+1;floatx=a[p];while(1){while(a[++i]=j)break;swap(a[i],a[j]);}a[p]=a[j];a[j]=x;returnj;}voidQuicksort(floata[],intp,intr){//快速排序if(p

2、,p,q-1);Quicksort(a,p+1,r);}}1、归并排序（分治法）voidmergesort(Typea[],intleft,intright){if(left

3、napsack(intn,floatm,floatv[],floatw[],floatx[]){sort(n,v,w)//非递增排序inti;for(i=1;i<=n;i++)x[i]=0;floatc=m;for(i=1;i<=n;i++){if(w[i]>c)break;x[i]=1;c-=w[i];}if(i<=n)x[i]=c/w[i];}1、活动安排问题（贪心算法）voidGreadyselector(intn,Types[],Typef[],boolA[]){//s[i]为活动结束时间，f[j]

4、为j活动开始时间A[i]=true;intj=1;for(i=2;i<=n;i++){if(s[i]>=f[j]){A[i]=true;j=i;}elseA[i]=false;}}1、喷水装置问题（贪心算法）voidknansack(intw,intd,floatr[],intn){//w为草坪长度d为草坪宽度r[]为喷水装置的喷水半径，//n为n种喷水装置，喷水装置的喷水半径>=d/2sort(r[],n);//降序排序count=0;//记录装置数for(i=1;i<=n;i++)x[i]=0;//初始

5、时，所有喷水装置没有安装x[i]=0for(i=1;w>=0;i++){x[i]=1;count++;w=w-2*sqart(r[i]*r[i]-1);}count<<装置数:<x,ints){rectorst(s+1,0);rectorsu(s+1,0);intn=x.size();//st[]是

6、服务数组，st[j]为第j个队列上的某一个顾客的等待时间//su[]是求和数组，su[j]为第j个队列上所有顾客的等待时间sort(x.begin(),x.end());//每个顾客所需要的服务时间升序排列inti=0,j=0;while(i

7、oatbebig(intA[],intn){m=n;sort(A,m);//升序while(m>1){for(i=3;i<=m;i++)if(p

8、0f(i,j)=

9、

10、min{f(i,k)+f(k+1,j)}+su

11、m(i,j)intsum[maxm]intbest[maxm][maxn];intn,stme[maxn];intgetbest();{//初始化，没有合并for(inti=0;i0!sum