计算机算法设计与分析实验报告.docx
- 文档编号:9110142
- 上传时间:2023-05-17
- 格式:DOCX
- 页数:18
- 大小:122.56KB
计算机算法设计与分析实验报告.docx
《计算机算法设计与分析实验报告.docx》由会员分享,可在线阅读,更多相关《计算机算法设计与分析实验报告.docx(18页珍藏版)》请在冰点文库上搜索。
计算机算法设计与分析实验报告
计算机算法设计与分析实验报告
专业:
软件技术
学号:
************
姓名:
覃立煜
*******
实验一:
最长公共子序列问题
一、实验目的与要求
1、明确子序列公共子序列的概念
2、最长公共子序列(LongestCommonSubsequence,简称LCS)的概念
3、利用动态规划解决最长公共子序列问题
二、实验题:
问题描述:
字符序列的子序列是指从给定字符序列中随意地(不一定连续)去掉若干个字符(可能一个也不去掉)后所形成的字符序列。
令给定的字符序列X=“x0,x1,…,xm-1”,序列Y=“y0,y1,…,yk-1”是X的子序列,存在X的一个严格递增下标序列
例如,X=“ABCBDAB”,Y=“BCDB”是X的一个子序列。
给定两个序列A和B,称序列Z是A和B的公共子序列,是指Z同是A和B的子序列。
问题要求已知两序列A和B的最长公共子序列。
三、实验代码
#include
#include
#include
#defineSize100
voidLCSLength(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 {scanf("%c",&x[i]); if(x[i]! ='\0')i++; } i=1; printf("输入y的成员(不用空格,直接输入字符串): \n"); while(i {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 #include #include intmin(intw,intc) {inttemp; if(w else temp=c; returntemp; } intmax(intw,intc) { inttemp; if(w>c)temp=w; else temp=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<<"最优值: "< cout< cout<<"*******************************************"< } inttraceback(int**m,intw[],intc,intn,intx[])//回代,求最优解 { cout<<"得到的一组最优解如下: "< for(inti=1;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< } cout< returnx[n]; } voidmain() {intn,c; int**m; cout<<"请输入物品个数和重量上限: "; cin>>n>>c; int*v=newint[n+1]; cout<<"请输入价值(v[i]): "< for(inti=1;i<=n;i++) cin>>v[i]; int*w=newint[n+1]; cout<<"请输入重量(w[i]): "< for(intj=1;j<=n;j++) cin>>w[j]; int*x=newint[n+1]; m=newint*[n+1];//动态的分配二维数组 for(intp=0;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 三、实验代码 #include"iostream.h" #include"stdio.h" #include 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 {if(low==empty) {while((data[high].benefit/data[high].weight {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 {low++;} if(data[low].benefit/data[low].weight {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 {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 {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 {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 usingnamespacestd; template classLoading{ friendTypeMaxLoading(Type[],Type,int,int[]); private: voidBacktrack(inti); intn, *x, *bestx; Type*w, c, cw, bestw, r; }; template voidLoading : 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 TypeMaxLoading(Typew[],Typec,intn,intbestx[]) {Loading 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< returnX.bestw; } voidmain() {intw[100],c,n,bestx[6]; cout<<"输入物品个数(小于100): "; cin>>n; cout<<"输入"< "; for(inti=1;i cin>>w[i]; cout<<"输入第一艘轮船的载重量: "; cin>>c; cout< "< } 四、实验结果 实验五: 循环赛日程表 一、实验目的与要求 1、掌握网球循环赛日程表的算法; 2、初步掌握分治算法 二、实验题: 问题描述: 有n=2^k个运动员要进行循环赛。 现要设计一个满足以下要求的比赛日程表: (1)每个选手必须与其他n-1个选手各赛一次 (2)每个选手一天只能赛一次 (3)循环赛一共进行n-1天 三、实验代码 #include #include #defineMAX1024 inta[MAX][MAX]; voidCopy(inttox,inttoy,intfromx,intfromy,intn) {inti,j; for(i=0;i {for(j=0;j {a[tox+i][toy+j]=a[fromx+i][fromy+j]; } } } voidTable(intk,inta[][MAX]) {inti,n=1< for(i=0;i {a[0][i]=i+1; } for(intr=1;r {for(i=0;i {Copy(r,i+r,0,i,r); Copy(r,i,0,i+r,r); } } } voidOut(inta[][MAX],intn) {inti,j; for(i=0;i {for(j=0;j {printf("%3d",a[i][j]); }printf("\n"); }printf("\n"); } intmain() {inti; for(i=0;i<5;i++) {intlen=1< Table(i,a); Out(a,len); }return0; } 四、实验结果
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 计算机 算法 设计 分析 实验 报告