計算機算法設(shè)計與分析實驗報告

計算機算法設(shè)計與分析實驗報告專業(yè)：軟件技術(shù)學(xué)號：200703520139姓名：覃立煜指導(dǎo)老師：郝麗蕊實驗一：最長公共子序列問題一、實驗?zāi)康呐c要求1、明確子序列公共子序列的概念2、最長公共子序列(LongestCommonSubsequence,簡稱LCS)的概念3、利用動態(tài)規(guī)劃解決最長公共子序列問題二、實驗題：

問題描述：字符序列的子序列是指從給定字符序列中隨意地（不一定連續(xù)）去掉若干個字符（可能一個也不去掉）后所形成的字符序列。令給定的字符序列X=“x0，x1，…，xm-1”，序列Y=“y0，y1，…，yk-1”是X的子序列，存在X的一個嚴(yán)格遞增下標(biāo)序列<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");}

四、實驗結(jié)果實驗二：0-1背包問題實驗?zāi)康呐c要求1、明確0-1背包問題的概念2、利用動態(tài)規(guī)劃解決0-1背包問題問題二、實驗題：0-1背包問題(knapsackproblem)，某商店有n個物品，第i個物品價值為vi，重量(或稱權(quán)值)為wi，其中vi和wi為非負(fù)數(shù),背包的容量為W，W為一非負(fù)數(shù)。目標(biāo)是如何選擇裝入背包的物品，使裝入背包的物品總價值最大，所選商品的一個可行解即所選商品的序列如何？背包問題與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)//求最優(yōu)值{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<<"最優(yōu)值："<<m[1][c]<<endl;cout<<endl;cout<<"*******************************************"<<endl;}inttraceback(int**m,intw[],intc,intn,intx[])//回代，求最優(yōu)解{cout<<"得到的一組最優(yōu)解如下:"<<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<<"請輸入物品個數(shù)和重量上限:";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];//動態(tài)的分配二維數(shù)組for(intp=0;p<n+1;p++){m[p]=newint[c+1];}knapsack(v,w,c,n,m);traceback(m,w,c,n,x);}

四、實驗結(jié)果實驗三：貪心算法背包問題一、實驗?zāi)康呐c要求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("請輸入物品的數(shù)量:");scanf("%d",&num);if(num<=0)printf("物品數(shù)量必須大于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;}

四、實驗結(jié)果實驗四：回溯法裝載問題一、實驗?zāi)康呐c要求1、掌握網(wǎng)球循環(huán)賽日程表的算法；2、初步掌握回溯算法二、實驗題：

問題描述：

有兩艘船，它們的可裝載的貨物重量分別為才c1，c2，給定一批貨物，其重量保存在數(shù)組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<<"輸入物品個數(shù)(小于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;}

四、實驗結(jié)果實驗五：循環(huán)賽日程表一、實驗?zāi)康呐c要求1、掌握網(wǎng)球循環(huán)賽日程表的算法；2、初步掌握分治算法二、實驗題：

問題描述：有n=2^k個運動員要進(jìn)行循環(huán)賽?，F(xiàn)要設(shè)計一個滿足以下要求的比賽日程表：

（1）每個選手必須與其他n-1個選手各賽一次

（2）每個選手一天只能賽一次

（3）循環(huán)賽一共進(jìn)行n-1天三、實驗代碼#include<stdio.h>#include<s