《计算机算法设计与分析实验报.pdf》由会员分享，可在线阅读，更多相关《计算机算法设计与分析实验报.pdf（12页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、计算机算法设计与分析实验报告专业：软件技术学号：200703520139 姓名：覃立煜指导老师：郝丽蕊实验一：最长公共子序列问题一、实验目的与要求1、明确子序列公共子序列的概念2、最长公共子序列(Longest Common Subsequence,简称 LCS)的概念3、利用动态规划解决最长公共子序列问题二、实验题：问题描述：字符序列的子序列是指从给定字符序列中随意地（不一定连续）去掉若干个字符（可能一个也不去掉）后所形成的字符序列。令给定的字符序列X=“x0，x1，,，xm-1”，序列 Y=“y0，y1，,，yk-1”是 X 的子序列，存在X 的一个严格递增下标序列，使得对所有的j=0，1
2、，,，k-1，有 xij=yj。例如，X=“ABCBDAB”，Y=“BCDB”是 X 的一个子序列。给定两个序列A 和 B，称序列Z 是 A 和 B 的公共子序列，是指Z 同是 A 和 B 的子序列。问题要求已知两序列A 和 B 的最长公共子序列。三、实验代码#include#include#include#define Size 100 void LCSLength(int m,int n,char*x,char*y,int cSizeSize,int bSizeSize)int i,j;for(i=1;i=m+1;i+)ci0=0;for(i=1;i=n+1;i+)c0i=0;for(i=
3、1;i=m+1;i+)for(j=1;j=cij-1)cij=ci-1j;bij=1;else cij=cij-1;bij=2;void LCS(int i,int j,char*x,int bSizeSize)if(i=0|j=0)return;if(bij=0)LCS(i-1,j-1,x,b);printf(%c,xi);else if(bij=1)LCS(i-1,j,x,b);else LCS(i,j-1,x,b);main()int m,n,i;int cSizeSize,bSizeSize;char xSize,ySize;printf(输入序列 x 的长度(小于 100):);sc
4、anf(%d,&m);printf(输入序列 y 的长度(小于 100):);scanf(%d,&n);i=1;printf(输入 x 的成员(不用空格,直接输入字符串):n);while(im+2)scanf(%c,&xi);if(xi!=0)i+;i=1;printf(输入 y 的成员(不用空格,直接输入字符串):n);while(in+2)scanf(%c,&yi);if(yi!=0)i+;LCSLength(m,n,x,y,c,b);printf(最长公共子序列:n);LCS(m+1,n+1,x,b);printf(n);四、实验结果实验二：0-1 背包问题一、实验目的与要求1、明确
5、0-1 背包问题的概念2、利用动态规划解决0-1 背包问题问题二、实验题：0-1 背包问题(knapsack problem)，某商店有 n 个物品，第 i 个物品价值为vi，重量(或称权值)为 wi，其中 vi 和 wi 为非负数,背包的容量为 W，W为一非负数。目标是如何选择装入背包的物品，使装入背包的物品总价值最大，所选商品的一个可行解即所选商品的序列如何？背包问题与0-1 背包问题的不同点在于，在选择物品装入背包时，可以只选择物品的一部分，而不一定要选择物品的全部。可将这个问题形式描述如下：niiixv1max约束条件为：举例:若商店一共有5 类商品，重量分别为：3，4，7，8，9 价
6、值分别为：4，5，10，11，13 则：所选商品的最大价值为24 所选商品的一个序列为：0 0 0 1 1 三、实验代码#include#include#include int min(int w,int c)int temp;if(wc)temp=w;else temp=c;return temp;void knapsack(int v,int w,int c,int n,int*m)/求最优值 int jmax=min(wn-1,c);for(int j=0;j=jmax;j+)mnj=0;for(int jj=wn;jj1;i-)/递归部分jmax=min(wi-1,c);for(int
7、 j=0;j=jmax;j+)mij=mi+1j;for(int jj=wi;jj=w1)m1c=max(m1c,m2c-w1+v1);cout 最优值：m1cendl;coutendl;cout*endl;int traceback(int*m,int w,int c,int n,int x)/回代，求最优解 cout 得到的一组最优解如下:endl;for(int i=1;in;i+)if(mic=mi+1c)xi=0;else xi=1;c-=wi;xn=(mnc)?1:0;for(int y=1;y=n;y+)coutsetw(5)xy;coutendl;return xn;void
8、main()int n,c;int*m;coutnc;int*v=new intn+1;cout 请输入价值(vi):endl;for(int i=1;ivi;int*w=new intn+1;cout 请输入重量(wi):endl;for(int j=1;jwj;int*x=new intn+1;m=new int*n+1;/动态的分配二维数组for(int p=0;pn+1;p+)mp=new intc+1;knapsack(v,w,c,n,m);traceback(m,w,c,n,x);四、实验结果实验三：贪心算法背包问题一、实验目的与要求1、掌握背包问题的算法2、初步掌握贪心算法二、实
9、验题：问题描述：与0-1 背包问题相似，给定n 种物品和一个背包。物品i 的重量是wi，其价值为 vi，背包的容量为c。与 0-1 背包问题不同的是，在选择物品i 装入背包时，背包问题的解决可以选择物品i 的一部分，而不一定要全部装入背包，1 i n。三、实验代码#include iostream.h#include stdio.h#include struct stone int name;int weight;/物品的剩余重量int weight_t;/物品的重量float benefit;/物品的价值/float b;void sort(stone*data,int num)if(num
10、1)return;int low=0,high=num;stone key_s=datalow;float key=(float)key_s.benefit/key_s.weight;int empty=low;while(lowhigh)if(low=empty)while(datahigh.benefit/datahigh.weightlow)high-;if(datahigh.benefit/datahigh.weight=key)datalow=datahigh;empty=high;else if(high=empty)while(datalow.benefit/datalow.we
11、ight=key)&(lowhigh)low+;if(datalow.benefit/datalow.weight1)sort(data,empty-1);if(num-empty-10)sort(data+empty+1,num-empty-1);void inputstone(stone*bag,int num)for(int i=0;inum;i+)bagi.name=i+1;printf(请输入第%d 号物品的重量:,i+1);scanf(%d,&bagi.weight);if(bagi.weight=0)printf(物品的重量必须大于0!n);printf(请输入第%d 号物品的价
12、值:,i+1);scanf(%f,&bagi.benefit);if(bagi.benefit=0)printf(物品的价值必须大于0!n);bagi.weight_t=bagi.weight;int main(int argc,char*argv)int i;int num=0;int weight=0;float benefit=0;stone*bag;do printf(请输入背包可容纳的重量:);scanf(%d,&weight);if(weight=0)printf(背包可容纳的重量必须大于0!n);while(weight=0);do printf(请输入物品的数量:);scanf
13、(%d,&num);if(num=0)printf(物品数量必须大于0!n);while(num=0);bag=new stonenum;inputstone(bag,num);sort(bag,num-1);for(i=0;i0;i+)stone*temp=bag+i;if(weight=temp-weight)weight-=temp-weight;temp-weight=0;benefit+=temp-benefit;continue;else temp-weight-=weight;weight=0;benefit+=(temp-benefit*(1-(float)temp-weigh
14、t/temp-weight_t);break;printf(物品种类放入的比例每单位效益n);for(i=0;iname);printf(tt%.2ftt,(temp-weight_t-temp-weight)/(float)temp-weight_t);printf(%.4fn,temp-benefit/(float)temp-weight_t);printf(总效益:%.2f,benefit);delete bag;getchar();system(PAUSE);return EXIT_SUCCESS;return 0;四、实验结果实验四：回溯法装载问题一、实验目的与要求1、掌握网球循环赛
15、日程表的算法；2、初步掌握回溯算法二、实验题：问题描述：有两艘船，它们的可装载的货物重量分别为才c1，c2，给定一批货物，其重量保存在数组 w【i】中了，问这批货物能否用此两艘船送出。三、实验代码#include using namespace std;template class Loading friend Type MaxLoading(Type,Type,int,int);private:void Backtrack(int i);int n,*x,*bestx;Type*w,c,cw,bestw,r;template void Loading:Backtrack(int i)if(i
16、n)if(cwbestw)for(int j=1;j=n;j+)bestxj=xj;bestw=cw;return;r-=wi;if(cw+wibestw)xi=0;Backtrack(i+1);r+=wi;template Type MaxLoading(Type w,Type c,int n,int bestx)LoadingX;X.x=new intn+1;X.w=w;X.c=c;X.n=n;X.bestx=bestx;X.bestw=0;X.cw=0;X.r=0;for(int i=1;i=n;i+)X.r+=wi;X.Backtrack(1);delete X.x;cout所取物品：
17、;for(i=1;i=n;i+)coutbestxi;return X.bestw;void main()int w100,c,n,bestx6;coutn;cout输入 n 个物品重量：;for(int i=1;iwi;coutc;coutendl 最大装载重量为：MaxLoading(w,c,n,bestx)endl;四、实验结果实验五：循环赛日程表一、实验目的与要求1、掌握网球循环赛日程表的算法；2、初步掌握分治算法二、实验题：问题描述：有n=2k 个运动员要进行循环赛。现要设计一个满足以下要求的比赛日程表：（1）每个选手必须与其他n-1 个选手各赛一次（2）每个选手一天只能赛一次（3）
18、循环赛一共进行n-1 天三、实验代码#include#include#define MAX 1024 int aMAXMAX;void Copy(int tox,int toy,int fromx,int fromy,int n)int i,j;for(i=0;in;i+)for(j=0;jn;j+)atox+itoy+j=afromx+ifromy+j;void Table(int k,int aMAX)int i,n=1 k;for(i=0;in;i+)a0i=i+1;for(int r=1;rn;r=1)for(i=0;in;i+=2*r)Copy(r,i+r,0,i,r);Copy(r,i,0,i+r,r);void Out(int aMAX,int n)int i,j;for(i=0;in;i+)for(j=0;jn;j+)printf(%3d,aij);printf(n);printf(n);int main()int i;for(i=0;i5;i+)int len=1 i;Table(i,a);Out(a,len);return 0;四、实验结果