算法设计与分析实验(第2、3章)11页

1、暨南大学本科实验报告专用纸(附页)暨南大学本科实验报告专用纸课程名称 算法设计与分析 成绩评定 实验项目名称 分治策略与动态规划 指导教师 李展 实验项目编号 01 实验项目类型 设计类 实验地点 南海楼6楼学生姓名 陈奕豪 学号 2012051351 学院 信息科学技术学院 系 计算机系 专业 软件工程 实验时间 年 月 日 一、 实验目的：本实验涉及用分治策略和动态规划算法来求解优化组合问题。通过上机实验使学员学会程序的录入和调试；通过实验结果的比较，使学员了解两种算法的主要特点。二、 实验内容：第二章实验题必做算法分析题1: 线性时间选择问题l 问题描述给定线性序集中n个元素和一个整数k

2、, 1kn, 要求找出这n个元素中第k小的元素l 主要思路及步骤1. 把a数组中元素分为5个一组,选每组中位数后分别将他们移向数组头,再用同样的方法选取中位数的中位数x,然后按x把a数组分为两个划分,重复上述过程直至划分中元素个数少于75,返回要求值l 算法描述Type Select(Type a, int p, int r, int k) if (r-p75) 用某个简单排序算法对数组ap:r排序; return ap+k-1; ; for ( int i = 0; i=(r-p-4)/5; i+ ) 将ap+5*i至ap+5*i+4的第3小元素 与ap+i交换位置; /找中位数的中位数，r

3、-p-4即上面所说的n-5 Type x = Select(a, p, p+(r-p-4)/5, (r-p+6)/10); int i=Partition(a,p,r, x), j=i-p+1; if (k=j) return Select(a,p,i,k); else return Select(a,i+1,r,k-j);l 输入和输出自行设计数组a的元素的值，要求元素个数不少于80个，并实现以下输出：（1）输出数组a中下标范围从p到p+(r-p-4)/5的元素；（2）输出x的值，判断x是否为数组a中下标范围从p到p+(r-p-4)/5的拟中位数；（3）输出数组a中下标范围从p到r的元素，验

4、证其是否为以x为基准元素的划分。源代码：:#include #include #include void Swap(int *i,int *j)int a;a=*i;*i=*j;*j=a;/交换函数int Partition(int *a, int p, int r)int i=p,j=r+1;int x=ap;while(true)while(a+ix & ix);if(i=j)break;Swap(&ai,&aj);ap=aj;aj=x;return j;void QuickSort(int *a, int p, int r)if(pr)int q=Partition(a,p,r);Qui

5、ckSort(a,p,q-1);QuickSort(a,q+1,r);/快速排列int Partition_S(int *a, int p, int r, int x,int *count)int i,j=p,temp,z=0;for(i=0;i=r;i+)if(ai!=x)z+;elsetemp=az;az=aj;aj=temp;j+;z+;(*count)+;i=p,j=r+1;while(true)while(a+ix & ix);if(i=j)break;Swap(&ai,&aj);ap=aj;aj=x;return j;/划分函数int Select(int *a, int p, i

6、nt r, int k)if(r-p75)QuickSort(a,p,r);return ap+k-1;int i,j,t;for(i=0;i=(r-p-4)/5;i+)QuickSort(a,p+5*i,p+5*i+4);int temp=ap+i;ap+i=ap+i*5+2;ap+i*5+2=temp;printf(数组a下标p到p+(r-p-4)/5的元素);for(i=p;i=p+(r-p-4)/5;i+)printf(%d ,ai);/输出(1)int x=Select(a,p,p+(r-p-4)/5,(r-p+6)/10);printf(n拟中位数:%dn,x);/输出(2)int

7、 count=0;i=Partition_S(a,p,r,x,&count);printf(以%d为基准的划分:,x);for(t=p;t=r;t+)printf(%d ,at);/输出(3)printf(nn);j=i-p;if(k=1 & jk & k=j+count-1)return ai;elsereturn Select(a,i+count,r,k-j-count);int main()int i,n,j;int a80=1059,1285,50,32, 788, 651, 106, 42, 67, 7, 1287, 395, 412, 132, 213, 398, 1750, 40

8、6, 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,

9、 103, 1018, 1099, 479, 465, 346, 1720;printf(输入k的值:);scanf(%d,&n);int z=n;i=Select(a,0,79,n);QuickSort(a,0,79);/排序,方便查看结果for(j=0;j80;j+)printf( %d,aj);printf(n);printf(第%d小的数是%dn,z, i);return 0;实验截图：l 实验总结基本熟悉线性时间选择算法的结构第三章实验题选做算法实现题2: 二维0-1背包问题（P79 3-4）l 问题描述l 分析与解答要求：给出最优值的递归关系l 算法描述l 输入和输出要求：物品不少

10、于10个，输出最优值数组的全部值和最后的最优解算法实现：#include int m100100100;int min(int i,int j)return ij?i:j;void Knapsack(int *v,int *w,int c,int *b,int d,int n)int min(int i,int j);int max(int i,int j); int i,j,k; int jMax=min(wn-1,c);/可选物品只有nint kMax=min(bn-1,d);/同上 for(j=0;j=jMax;j+) for(k=kMax;k=d;k+) mnjk=0;/可选物品只有n

11、且重量不足 for(j=jMax;j=c;j+) for(k=0;k=kMax;k+) mnjk=0;/可选物品只有n且体积不足 for(j=wn;j=c;j+) for(k=bn;k1;i-) jMax=min(wi-1,c); kMax=min(bi-1,d); for(j=0;j=jMax;j+) for(k=0;k=d;k+) mijk=mi+1jk; for(j=0;j=c;j+) for(k=0;k=kMax;k+) mijk=mi+1jk; for(j=wi;j=c;j+) for(k=bi;k=w1&d=b1) m1cd=max(m1cd,m2c-w1d-b1+v1);void Traceback(int *w,int c,int *b,int d,int n,int *x) for(int i=1;in;i+) if(micd=mi+1cd) xi=0; else xi=1; c-=wi; d-=bi; xn=(mncd) ? 1:0;int main() int n,c,d,i; printf(请输入物品个数、背包容量、背包容积:); scanf(%d %d %d,&n,&c,&d); int v100,w100,b100,x100; printf(请输入每个物品的价值、重量、体积：n); for(i=1