算法设计与分析实验

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

2、第k小的元素l 主要思路及步骤1. 把a数组中元素分为5个一组,选每组中位数后分别将他们移向数组头,再用同样的方法选取中位数的中位数x,然后按x把a数组分为两个划分,重复上述过程直至划分中元素个数少于75,返回要求值l 算法描述Type Select(Type a, int p, int r, int k) if (r-p<75) 用某个简单排序算法对数组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-p-4即上面所说

3、的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 <stdlib.h>#include <time.h>#include <stdio.h>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+i<x && i<r);while(a-j>x);if(i>=j)break;Swap(&ai,&aj);ap=

5、aj;aj=x;return j;void QuickSort(int *a, int p, int r)if(p<r)int q=Partition(a,p,r);QuickSort(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)whi

6、le(a+i<x && i<r);while(a-j>x);if(i>=j)break;Swap(&ai,&aj);ap=aj;aj=x;return j;/划分函数int Select(int *a, int p, int r, int k)if(r-p<75)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;

7、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 count=0;i=Partition_S(a,p,r,x,&count);printf("以%d为基准的划分:",x);for(t=p;t<=r;t+)printf("%d &qu

8、ot;,at);/输出(3)printf("nn");j=i-p;if(k<=j) return Select(a,p,i-1,k);else if(count>=1 && j<k && 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, 17

9、50, 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

10、, 636, 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;j<80;j+)printf(" %d",aj);printf("n");printf("第%d小的数是%dn",z, i);return 0;实验截图：l 实验总结基本熟悉线性时间选择算法的结构第三章实验题

11、选做算法实现题2: 二维0-1背包问题（P79 3-4）l 问题描述l 分析与解答要求：给出最优值的递归关系l 算法描述l 输入和输出要求：物品不少于10个，输出最优值数组的全部值和最后的最优解算法实现：#include <stdio.h>int m100100100;int min(int i,int j)return i<j?i:j;int max(int i,int j)return i>j?i:j;void Knapsack(int *v,int *w,int c,int *b,int d,int n)int min(int i,int j);int max(i

12、nt 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且重量不足 for(j=jMax;j<=c;j+) for(k=0;k<=kMax;k+) mnjk=0;/可选物品只有n且体积不足 for(j=wn;j<=c;j+) for(k=bn;k<=d;k+) mnjk=vn;/可选物品只有n且能装下 for(i=n-1;i>1;i-) jMax

13、=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<=d;k+) mijk=max(mi+1jk,mi+1j-wik-bi+vi); m1cd=m2cd; if(c>=w1&&d>=b1) m1cd=max(m1cd,m2c-w1d-b1+v1);void Trac

14、eback(int *w,int c,int *b,int d,int n,int *x) for(int i=1;i<n;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;i<=n;i+) scanf("%d %d %