计算机算法设计与分析实验报告

计算机算法设计与分析实验报告专业：软件技术学号：200703520139姓名：覃立煜指导老师：郝丽蕊实验一：最长公共子序列问题一、实验目的与要求1、明确子序列公共子序列的概念2、最长公共子序列(LongestCommonSubsequence,简称LCS)的概念3、利用动态规划解决最长公共子序列问题二、实验题：

问题描述：字符序列的子序列是指从给定字符序列中随意地（不一定连续）去掉若干个字符（可能一个也不去掉）后所形成的字符序列。令给定的字符序列X=“x0，x1，…，xm-1”，序列Y=“y0，y1，…，yk-1”是X的子序列，存在X的一个严格递增下标序列<i0，i1，…，ik-1>，使得对所有的j=0，1，…，k-1，有xij=yj。例如，X=“ABCBDAB”，Y=“BCDB给定两个序列A和B，称序列Z是A和B的公共子序列，是指Z同是A和B的子序列。问题要求已知两序列A和B的最长公共子序列。三、实验代码#include<stdlib.h>#include<stdio.h>#include<string.h>#defineSize100voidLCSLength(intm,intn,char*x,char*y,intc[Size][Size],intb[Size][Size]){inti,j;for(i=1;i<=m+1;i++)c[i][0]=0;for(i=1;i<=n+1;i++)c[0][i]=0;for(i=1;i<=m+1;i++)for(j=1;j<=n+1;j++){if(x[i]==y[j]){c[i][j]=c[i-1][j-1]+1;b[i][j]=0;}elseif(c[i-1][j]>=c[i][j-1]){c[i][j]=c[i-1][j];b[i][j]=1;}else{c[i][j]=c[i][j-1];b[i][j]=2;}}}voidLCS(inti,intj,char*x,intb[Size][Size]){if(i==0||j==0)return;if(b[i][j]==0){LCS(i-1,j-1,x,b);printf("%c",x[i]);}elseif(b[i][j]==1)LCS(i-1,j,x,b);elseLCS(i,j-1,x,b);}main(){intm,n,i;intc[Size][Size],b[Size][Size];charx[Size],y[Size];printf("输入序列x的长度(小于100):");scanf("%d",&m);printf("输入序列y的长度(小于100):");scanf("%d",&n);i=1;printf("输入x的成员(不用空格,直接输入字符串):\n");while(i<m+2){scanf("%c",&x[i]);if(x[i]!='\0')i++;}i=1;printf("输入y的成员(不用空格,直接输入字符串):\n");while(i<n+2){scanf("%c",&y[i]);if(y[i]!='\0')i++;}LCSLength(m,n,x,y,c,b); printf("最长公共子序列:\n");LCS(m+1,n+1,x,b);printf("\n");}

四、实验结果实验二：0-1背包问题实验目的与要求1、明确0-1背包问题的概念2、利用动态规划解决0-1背包问题问题二、实验题：0-1背包问题(knapsackproblem)，某商店有n个物品，第i个物品价值为vi，重量(或称权值)为wi，其中vi和wi为非负数,背包的容量为W，W为一非负数。目标是如何选择装入背包的物品，使装入背包的物品总价值最大，所选商品的一个可行解即所选商品的序列如何？背包问题与0-1背包问题的不同点在于，在选择物品装入背包时，可以只选择物品的一部分，而不一定要选择物品的全部。可将这个问题形式描述如下：约束条件为：举例:

若商店一共有5类商品，重量分别为：3，4，7，8，9价值分别为：4，5，10，11，13则：所选商品的最大价值为24所选商品的一个序列为：00011三、实验代码#include<iostream.h>#include<iomanip.h>#include<string.h>intmin(intw,intc){inttemp;if(w<c)temp=w;elsetemp=c;returntemp;}intmax(intw,intc){inttemp;if(w>c)temp=w;elsetemp=c;returntemp;}voidknapsack(intv[],intw[],intc,intn,int**m)//求最优值{intjmax=min(w[n]-1,c);for(intj=0;j<=jmax;j++)m[n][j]=0;for(intjj=w[n];jj<=c;jj++)m[n][jj]=v[n];for(inti=n-1;i>1;i--){//递归部分jmax=min(w[i]-1,c);for(intj=0;j<=jmax;j++)m[i][j]=m[i+1][j];for(intjj=w[i];jj<=c;jj++)m[i][jj]=max(m[i+1][jj],m[i+1][jj-w[i]]+v[i]);}m[1][c]=m[2][c];if(c>=w[1])m[1][c]=max(m[1][c],m[2][c-w[1]]+v[1]);cout<<"最优值："<<m[1][c]<<endl;cout<<endl;cout<<"*******************************************"<<endl;}inttraceback(int**m,intw[],intc,intn,intx[])//回代，求最优解{cout<<"得到的一组最优解如下:"<<endl;for(inti=1;i<n;i++)if(m[i][c]==m[i+1][c])x[i]=0;else{x[i]=1;c-=w[i];}x[n]=(m[n][c])?1:0;for(inty=1;y<=n;y++){cout<<setw(5)<<x[y];}cout<<endl;returnx[n];}voidmain(){intn,c;int**m;cout<<"请输入物品个数和重量上限:";cin>>n>>c;int*v=newint[n+1];cout<<"请输入价值(v[i]):"<<endl;for(inti=1;i<=n;i++)cin>>v[i];int*w=newint[n+1];cout<<"请输入重量(w[i]):"<<endl;for(intj=1;j<=n;j++)cin>>w[j];int*x=newint[n+1];m=newint*[n+1];//动态的分配二维数组for(intp=0;p<n+1;p++){m[p]=newint[c+1];}knapsack(v,w,c,n,m);traceback(m,w,c,n,x);}

四、实验结果实验三：贪心算法背包问题一、实验目的与要求1、掌握背包问题的算法2、初步掌握贪心算法二、实验题：

问题描述：与0-1背包问题相似，给定n种物品和一个背包。物品i的重量是wi，其价值为vi，背包的容量为c。与0-1背包问题不同的是，在选择物品i装入背包时，背包问题的解决可以选择物品i的一部分，而不一定要全部装入背包，1<i<n。三、实验代码#include"iostream.h"#include"stdio.h"#include<cstdlib>structstone{intname;intweight;//物品的剩余重量intweight_t;//物品的重量floatbenefit;//物品的价值//floatb;};voidsort(stone*data,intnum){if(num<1)return;intlow=0,high=num;stonekey_s=data[low];floatkey=(float)key_s.benefit/key_s.weight;intempty=low;while(low<high){if(low==empty){while((data[high].benefit/data[high].weight<key)&&(high>low)){high--;}if(data[high].benefit/data[high].weight>=key){data[low]=data[high];empty=high;}}elseif(high==empty){while((data[low].benefit/data[low].weight>=key)&&(low<high)){low++;}if(data[low].benefit/data[low].weight<key){data[high]=data[low];empty=low;}}}data[empty]=key_s;if(empty>1)sort(data,empty-1);if(num-empty-1>0)sort(data+empty+1,num-empty-1);}voidinputstone(stone*bag,intnum){for(inti=0;i<num;i++){bag[i].name=i+1;printf("请输入第%d号物品的重量:",i+1);scanf("%d",&bag[i].weight);if(bag[i].weight<=0){printf("物品的重量必须大于0!\n");}printf("请输入第%d号物品的价值:",i+1);scanf("%f",&bag[i].benefit);if(bag[i].benefit<=0){printf("物品的价值必须大于0!\n");}bag[i].weight_t=bag[i].weight;}}intmain(intargc,char*argv[]){inti;intnum=0;intweight=0;floatbenefit=0;stone*bag;do{printf("请输入背包可容纳的重量:");scanf("%d",&weight);if(weight<=0)printf("背包可容纳的重量必须大于0!\n");}while(weight<=0);do{printf("请输入物品的数量:");scanf("%d",&num);if(num<=0)printf("物品数量必须大于0!\n");}while(num<=0);bag=newstone[num];inputstone(bag,num);sort(bag,num-1);for(i=0;i<num&&weight>0;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->weight/temp->weight_t));break;}}printf("物品种类放入的比例每单位效益\n");for(i=0;i<num;i++){stone*temp=bag+i;printf("%d类物品",temp->name);printf("\t\t%.2f\t\t",(temp->weight_t-temp->weight)/(float)temp->weight_t);printf("%.4f\n",temp->benefit/(float)temp->weight_t);}printf("总效益:%.2f",benefit);deletebag;getchar();system("PAUSE");returnEXIT_SUCCESS;return0;}

四、实验结果实验四：回溯法装载问题一、实验目的与要求1、掌握网球循环赛日程表的算法；2、初步掌握回溯算法二、实验题：

问题描述：

有两艘船，它们的可装载的货物重量分别为才c1，c2，给定一批货物，其重量保存在数组w【i】中了，问这批货物能否用此两艘船送出。三、实验代码#include<iostream>usingnamespacestd;template<classType>classLoading{ friendTypeMaxLoading(Type[],Type,int,int[]); private: voidBacktrack(inti); intn,*x, *bestx; Type*w, c, cw, bestw, r; };template<classType>voidLoading<Type>::Backtrack(inti){ if(i>n){ if(cw>bestw){for(intj=1;j<=n;j++)bestx[j]=x[j];bestw=cw;} return;} r-=w[i]; if(cw+w[i]<=c){ x[i]=1; cw+=w[i]; Backtrack(i+1); cw-=w[i];} if(cw+r>bestw){ x[i]=0; Backtrack(i+1);} r+=w[i];}template<classType>TypeMaxLoading(Typew[],Typec,intn,intbestx[]){Loading<Type>X; X.x=newint[n+1]; X.w=w; X.c=c; X.n=n; X.bestx=bestx; X.bestw=0; X.cw=0; X.r=0; for(inti=1;i<=n;i++) X.r+=w[i]; X.Backtrack(1); delete[]X.x; cout<<"所取物品："; for(i=1;i<=n;i++) cout<<bestx[i]<<""; returnX.bestw;}voidmain(){ intw[100],c,n,bestx[6]; cout<<"输入物品个数(小于100)："; cin>>n; cout<<"输入"<<n<<"个物品重量："; for(inti=1;i<n+1;i++) cin>>w[i]; cout<<"输入第一艘轮船的载重量："; cin>>c; cout<<endl<<"最大装载重量为："<<MaxLoading(w,c,n,bestx)<<endl;}

四、实验结果实验五：循环赛日程表一、实验目的与要求1、掌握网球循环赛日程表的算法；2、初步掌握分治算法二、实验题：

问题描述：有n=2^k个运动员要进行循环赛。现要设计一个满足以下要求的比赛日程表：

（1）每个选手必须与其他n-1个选手各赛一次

（2）每个选手一天只能赛一次

（3）循环赛一共进行n-1天三、实验代码#include<stdio.h>#include<s