算法设计与分析实验

暨南大学本科实验报告专用纸课程名称算法设计与分析成绩评定实验项目名称分治策略与动态规划指导教师李展实验项目编号01实验项目类型设计类实验地点南海楼6楼学生姓名学号2012051351学院信息科学技术学院系计算机系专业软件工程实验时间年月日_一、实验目的：本实验涉及用分治策略和动态规划算法来求解优化组合问题。通过上机实验使学员学会程序的录入和调试；通过实验结果的比较，使学员了解两种算法的主要特点。二、实验内容：第二章实验题必做一一算法分析题1:线性时间选择问题•问题描述给定线性序集中n个元素和一个整数k,1WkWn,要求找出这n个元素中第k小的元素•主要思路及步骤1.把a数组中元素分为5个一组，选每组中位数后分别将他们移向数组头，再用同样的方法选取中位数的中位数x,然后按x把a数组分为两个划分，重复上述过程直至划分中元素个数少于75,返回要求值•算法描述TypeSelect(Typea[],intp,intr,intk){if(r-p<75){用某个简单排序算法对数组a[p:r]排序；returna[p+k-1];};for(inti=0;i<=(r-p-4)/5;i++)将a[p+5*i]至a[p+5*i+4]的第3小元素与a[p+i]交换位置；〃找中位数的中位数，r-p-4即上面所说的n-5Typex=Select(a,p,p+(r-p-4)/5,(r-p+6)/10);inti=Partition(a,p,r,x),j=i-p+1;if(k<=j)returnSelect(a,p,i,k);elsereturnSelect(a,i+1,r,k-j);}输入和输出自行设计数组a的元素的值，要求元素个数不少于80个，并实现以下输出：输出数组a中下标范围从p到p+(r-p-4)/5的元素；输出x的值，判断x是否为数组a中下标范围从p到p+(r-p-4)/5的拟中位数；输出数组a中下标范围从p到r的元素，验证其是否为以x为基准元素的划分。源代码：：#include<stdlib.h>#include<time.h>#include<stdio.h>voidSwap(int*i,int*j){inta;a=*i;*j=a;}//交换函数intPartition(int*a,intp,intr){inti=p,j=r+1;intx=a[p];while(true){while(a[++i]<x&&i<r);while(a[--j]>x);if(i>=j)break;Swap(&a[i],&a[j]);}a[p]=a[j];a[j]=x;returnj;}voidQuickSort(int*a,intp,intr){if(p<r){intq=Partition(a,p,r);QuickSort(a,p,q-1);QuickSort(a,q+1,r);}〃快速排列intPartition_S(int*a,intp,intr,intx,int*count){inti,j=p,temp,z=0;for(i=0;i<=r;i++){if(a[i]!=x)z++;else{temp=a[z];a[z]=a[j];a[j]=temp;j++;z++;(*count)++;}}i=p,j=r+1;while(true){while(a[++i]<x&&i<r);while(a[--j]>x);if(i>=j)break;Swap(&a[i],&a[j]);}a[p]=a[j];a[j]=x;returnj;}〃划分函数intSelect(int*a,intp,intr,intk){if(r-p<75){QuickSort(a,p,r);returna[p+k-1];}inti,j,t;for(i=0;i<=(r-p-4)/5;i++){QuickSort(a,p+5*i,p+5*i+4);inttemp=a[p+i];a[p+i]=a[p+i*5+2];a[p+i*5+2]=temp;}printf("数组a下标p到p+(r-p-4)/5的元素")；for(i=p;i<=p+(r-p-4)/5;i++)printf("%d",a[i]);//输出(1)intx=Select(a,p,p+(r-p-4)/5,(r-p+6)/10);printf("\n拟中位数:％d\n",x);//输出(2)intcount=0;i=Partition_S(a,p,r,x,&count);printf("以％d为基准的划分:",x);for(t=p;t<=r;t++)printf("%d",a[t]);//输出(3)printf("\n\n");j=i-p;if(k<=j)returnSelect(a,p,i-1,k);elseif(count>=1&&j<k&&k<=j+count-1)returna[i];elsereturnSelect(a,i+count,r,k-j-count);

intmain(){inti,n,j;inta[80]={1059,1285,50,32,788,651,106,42,67,7,1287,395,412,132,213,398,1750,406,1834,703,210,1102,1210,1092,161,1736,578,965,1037,881,1754,813,268,558,1961,1271,776,146,544,1921,514,1049,636,1275,1415,1294,929,765,472,187,1575,194,1342,1309,1026,1836,502,1412,289,161,137,1943,367,1163,1047,896,132,1375,428,655,94,111,636,103,1018,1099,479,465,346,1720};printf("输入k的值:")；scanf("%d",&n);intz=n;i=Select(a,0,79,n);QuickSort(a,0,79);//排序,方便查看结果for(j=0;j<80;j++)printf("%d",a[j]);printf("\n");printf("第％d小的数是%d\n",z,i);return0;}实验截图：I'C:\Users\Sony\Documents\TencentFiles\336571263\Fil?Recv\VC6.0green\MyPrqjects\ddf...[1=1|回脸*的蜀？rzr数组a下标pgjp+Cr-p-4>/5的兀素788673957031092965813047655111479缺中位洪(KS以76S为基准的划分H3611139547950265570367398465406132323671612101372132895781617132194268776346弱8104976513095021636103944124284265147214654426826828934655703761102116317501?54501871065147651921127514151271196117549291294173610261037134215758811210110214121836128518341?5011631943105913091092896137510491047128796510188137887761099172073242506794103106111132132137146161161187194210213E3673953984064124284654724795025145445585786366366515776788813881896929965101810261037104710491059109210991210127112?51285128712941309134213751412141515751720173618341836192119431961冒小的数是1蹈Pressanykeytocontinue—•实验总结基本熟悉线性时间选择算法的结构第三章实验题选做一一算法实现题2:二维0-1背包问题(P793-4)•问题描述•分析与解答要求：给出最优值的递归关系•算法描述•输入和输出要求：物品不少于10个，输出最优值数组的全部值和最后的最优解算法实现：#include<stdio.h>intm[100][100][100];intmin(inti,intj){returni<j?i:j;}intmax(inti,intj){returni>j?i:j;}voidKnapsack(int*v,int*w,intc,int*b,intd,intn)m<—hmiminr-hi5-<—hj)」m<—hmax(m<—hi5-<—hj)」m<-hLjrimjMaxHmm(wa—lo)7fKr咨曹取汩司nm<-hkMaxHmm(ba?d)7f^kforaHoAnjMax++)for(knkMaxRcndR++)m『n三=kH07回咨ssn汩司n皿MMnm河for{jHjMaxAHO++)for(kHORAHkMaxR++)m『n三=kH07回咨ssn汩司n皿w弟『河foraHwaAho++)for(knba」k9d」k++)m『n三=kHvmm回咨ssn汩司n皿睬淋-Hfor(H-nrv-Li!(jMaxnmimwE—Lc)；kMaxnmimbE—Ld)；for5rpjAHjMax++)for(knoRcndR++)mEu=kllmH+l」EK」for(j=0;j<=c;j++)for(k=0;k<=kMax;k++)m[i][j][k]=m[i+1][j][k];for(j=w[i];j<=c;j++)for(k=b[i];k<=d;k++)m[i][j][k]=max(m[i+1][j][k],m[i+1][j-w[i]][k-b[i]]+v[i]);}m[1][c][d]=m[2][c][d];if(c>=w[1]&&d>=b[1])m[1][c][d]=max(m[1][c][d],m[2][c-w[1]][d-b[1]]+v[1]);}voidTraceback(int*w,intc,int*b,intd,intn,int*x){for(inti=1;i<n;i++){if(m[i][c][d]==m[i+1][c][d])x[i]=0;elsex[i]=1;c-=w[i];d-=b[i];}}x[n]=(m[n][c][d])?1:0;}intmain(){intn,c,d,i;printf("请输入物品个数、背包容量、背包容积:，scanf("%d%d%d",&n,&c,&d);intv[100],w[100],b[100],x[100]