北邮 算法设计与分析第三章实验报告.docx
《北邮 算法设计与分析第三章实验报告.docx》由会员分享，可在线阅读，更多相关《北邮 算法设计与分析第三章实验报告.docx（25页珍藏版）》请在冰点文库上搜索。
北邮算法设计与分析第三章实验报告
算法设计与分析第三章程序作业
源程序代码
1.最长公共子序列
#include
#include
#defineN1000
inte[N][N],f[N][N];
voidLCSLength（intm,intn,char*x,char*y,intc[][N],intb[][N]）//构造数组b[i][j]
{
inti,j;
for（i=1;i<=m;i++）
c[i][0]=0;//初始化,Y[j]为空时
for（i=1;i<=n;i++）
c[0][i]=0;//初始化，X[i]为空时
for（i=1;i<=m;i++）//两重循环，自下而上，//计算子问题{X（i）,Y（j）}
for（j=1;j<=n;j++）{
if（x[i]==y[j]）
{//情况1
c[i][j]=c[i-1][j-1]+1;
b[i][j]=1;
}
elseif（c[i-1][j]>=c[i][j-1]）
{//情况2
c[i][j]=c[i-1][j];
b[i][j]=2;
}
else//情况3
{
c[i][j]=c[i][j-1];
b[i][j]=3;
}
}
}
voidLCS（inti,intj,char*x,intb[][N]）
{
if（i==0||j==0）
return;
if（b[i][j]==1）
{
LCS（i-1,j-1,x,b）;
printf（"%c",x[i]）;
/*第1种情况下，X（i）和Y（j）的最长公共子序列由X（i-1）和
Y（j-1）的解LCS（i-1,j-1,x,b），加上位于最后的X[i]
组成*/
}
elseif（b[i][j]==2）
LCS（i-1,j,x,b）;
else
LCS（i,j-1,x,b）;//其它2种情况下，原问题解等于子问题解
}
main（）
{
charA[N],B[N],C[N],D[N];
inta=1,b=1,c=1,d=1;
charch;
inti;
FILE*fp;
if（（fp=fopen（"最长公共子序列输入数据.txt","r"））==NULL）//打开文件失败
printf（"Can'topenfile"）;
else
{//读取文件内容
ch=fgetc（fp）;
ch=fgetc（fp）;
ch=fgetc（fp）;
ch=fgetc（fp）;
ch=fgetc（fp）;
while（ch!
='B'&&ch!
=EOF）
{
A[a]=ch;
a++;
ch=fgetc（fp）;
while（ch=='\n'）
ch=fgetc（fp）;
}
a--;
ch=fgetc（fp）;
ch=fgetc（fp）;
ch=fgetc（fp）;
ch=fgetc（fp）;
while（ch!
='C'&&ch!
=EOF）
{
B[b]=ch;
b++;
ch=fgetc（fp）;
while（ch=='\n'）
ch=fgetc（fp）;
}
b--;
ch=fgetc（fp）;
ch=fgetc（fp）;
ch=fgetc（fp）;
ch=fgetc（fp）;
while（ch!
='D'&&ch!
=EOF）
{
C[c]=ch;
c++;
ch=fgetc（fp）;
while（ch=='\n'）
ch=fgetc（fp）;
}
c--;
ch=fgetc（fp）;
ch=fgetc（fp）;
ch=fgetc（fp）;
ch=fgetc（fp）;
while（ch!
=EOF）
{
D[d]=ch;
d++;
ch=fgetc（fp）;
while（ch=='\n'）
ch=fgetc（fp）;
}
d--;
}
fclose（fp）;
printf（"文件读取完成\n"）;
/*for（i=0;i<=a;i++）
printf（"%c",A[i]）;
printf（"\n"）;
for（i=0;i<=b;i++）
printf（"%c",B[i]）;
printf（"\n"）;
for（i=0;i<=c;i++）
printf（"%c",C[i]）;
printf（"\n"）;
for（i=0;i<=d;i++）
printf（"%c",D[i]）;
printf（"\n"）;*/
printf（"\n\n\nA和B的最长公共子序列为：
\n"）;
LCSLength（a,b,A,B,e,f）;
LCS（a,b,A,f）;
printf（"\n\n\nC和D的最长公共子序列为：
\n"）;
LCSLength（c,d,C,D,e,f）;
LCS（c,d,C,f）;
printf（"\n\n\nA和D的最长公共子序列为：
\n"）;
LCSLength（a,d,A,D,e,f）;
LCS（a,d,A,f）;
system（"pause"）;
return0;
}
2.最大子段和
#include
#include
#defineN400
voidMaxSum（intn,int*a）
{
intsum=0,b=0;
inti,x1=0,y1=0,x=0,y=0;
for（i=1;i<=n;i++）
{
if（b>0）
{
b+=a[i];
y1=i;
}
else
{
b=a[i];
x1=i;
}
if（b>sum）
{
sum=b;
x=x1;
y=y1;
}
}
printf（"\n该序列的最大子段和的位置为从第%d个到第%d个",x+1,y+1）;
printf（"\n该序列的和最大子段为：
\n"）;
for（i=x;i<=y;i++）
printf（"%d",a[i]）;
printf（"\n它们的和为%d\n",sum）;
}
main（）
{
intA[N],B[N];
inta=0,b=0;
inti;
FILE*fp1,*fp2;
if（（fp1=fopen（"最大子段和输入数据-序列1.txt","r"））==NULL）//打开文件失败
printf（"Can'topenfile1"）;
else//读取文件内容
{
for（i=0;!
feof（fp1）;i++）
fscanf（fp1,"%d\n",&A[i]）;
a=i-1;
}
if（（fp2=fopen（"最大子段和输入数据-序列2.txt","r"））==NULL）//打开文件失败
printf（"Can'topenfile2"）;
else
{
for（i=0;!
feof（fp2）;i++）
fscanf（fp2,"%d\n",&B[i]）;
b=i-1;
}
fclose（fp1）;
fclose（fp1）;
printf（"文件读取成功\n\n\n"）;
printf（"对于最大子段和输入数据-序列1"）;
MaxSum（a,A）;//计算最大子段和
printf（"\n\n对于最大子段和输入数据-序列2"）;
MaxSum（b,B）;
//for（i=0;i<=b;i++）
//printf（"%d",B[i]）;
system（"pause"）;
return0;
}
3.凸多边形最优三角剖分
#include
#include
#include
#defineN30
#defineEARTH_RADIUS6378.137
structBase{//基站结构体
intENODEBID;//基站标识
floatLONGITUDE;//基站经度
floatLATITUDE;//基站纬度
intNUM;//基站k-dist距离
};
voidreadfile（structBase*base,intn）//读取文件函数
{
FILE*fp;
inti=0;
if（n==21）
fp=fopen（"21个基站凸多边形数据.csv","rb"）;
else
fp=fopen（"29个基站凸多边形数据.csv","rb"）;
if（fp==NULL）//打开文件失败
printf（"Can'topenfile"）;
else
{
while（EOF!
=fscanf（fp,"%d,%f,%f,%d",&base[i].ENODEBID,&base[i].LONGITUDE,&base[i].LATITUDE,&base[i].NUM））
{//将数据读入结构体数组
i++;
//printf（"%d\n",i）;
}
//printf（"文件读入成功\n\n\n"）;
}
fclose（fp）;
}
floatrad（floatLatOrLon）
{
returnLatOrLon*3.14/180.0;
}
floatdistance（structBase*base,inta,intb）//求两个基站间的距离
{
floats;
floatradLat1,radLat2,radlng1,radlng2;
radLat1=rad（base[a].LATITUDE）;
radLat2=rad（base[b].LATITUDE）;
radlng1=rad（base[a].LONGITUDE）;
radlng2=rad（base[b].LONGITUDE）;
//利用正弦余弦公式求距离
if（radLat1==radLat2&&radlng1==radlng2）
s=0;
else
{
s=acos（cos（radLat1）*cos（radLat2）*cos（radlng1-radlng2）+sin（radLat1）*sin（radLat2））;
s=s*EARTH_RADIUS;
s=round（s*1000）;
}
returns;
}
floatweight（structBase*base,inta,intb,intc）
{
floats,s1,s2,s3;
s1=distance（base,a,b）;
s2=distance（base,b,c）;
s3=distance（base,a,c）;
//s=distance（base,a,b）+distance（base,b,c）+distance（base,a,c）;
s=s1+s2+s3;
returns;
}
floatMinWeightTriangulation（structBase*base,intn,floatt[][N],ints[][N]）
{
inti,j,r,k;
floatu=0;
for（i=1;i<=n;i++）
t[i][i]=0;
for（r=2;r<=n;r++）//r为当前计算的链长（子问题规模）
for（i=1;i<=n-r+1;i++）//n-r+1为最后一个r链的前边界
{
j=i+r-1;//计算前边界为r，链长为r的链的后边界
t[i][j]=t[i+1][j]+weight（base,i-1,i,j）;//将链ij划分为A（i）*（A[i+1:
j]）这里实际上就是k=i
s[i][j]=i;
for（k=i+1;kk]）*（A[k+1:
j]）
{
u=t[i][k]+t[k+1][j]+weight（base,i-1,k,j）;
if（u{
t[i][j]=u;
s[i][j]=k;
}
}
}
returnt[1][n];
}
voidTraceback（inti,intj,ints[][N]）
{
if（i==j）
return;
Traceback（i,s[i][j],s）;
Traceback（s[i][j]+1,j,s）;
printf（"三角剖分顶点：
V%d,V%d,V%d\n",i-1,j,s[i][j]）;
}
main（）
{
inti;
floatt[N][N];
ints[N][N];
structBasebase21[N];//结构体（N宏定义）
structBasebase29[N];//结构体（N宏定义）
readfile（base21,21）;//将数据从文件中读到结构体中
readfile（base29,29）;//将数据从文件中读到结构体中
printf（"文件读入成功\n\n\n"）;
//for（i=0;i<=28;i++）
//printf（"%6d%.3f%.5f%d\n",base29[i].ENODEBID,base29[i].LONGITUDE,base29[i].LATITUDE,base29[i].NUM）;
printf（"凸21多边形的最优三角剖分值为%f",MinWeightTriangulation（base21,20,t,s））;
printf（"最优三角剖分结构为：
\n"）;
Traceback（1,20,s）;//s[i][j]记录了Vi-1和Vj构成三角形的第3个顶点的位置
printf（"凸29多边形的最优三角剖分值为%f",MinWeightTriangulation（base29,28,t,s））;
printf（"最优三角剖分结构为：
\n"）;
Traceback（1,28,s）;//s[i][j]记录了Vi-1和Vj构成三角形的第3个顶点的位置
system（"pause"）;
return0;
}
4.01背包问题
#include
#include
#defineN100
structGoods{
intweight;//物品重量
intvalue;//物品价值
};
intknapsack（structGoods*goods,intbag,intnumber,intp[][2],inthead[]）
{
intleft=0,right=0,next=1,i,j,k,m,y;
p[0][0]=0;
p[0][1]=0;
head[number+1]=0;
head[number]=1;
for（i=number;i>=1;i--）{
k=left;
for（j=left;j<=right&&p[j][0]+goods[i-1].weight<=bag;j++）{
y=p[j][0]+goods[i-1].weight;
m=p[j][1]+goods[i-1].value;
while（k<=right&&p[k][0]p[next][0]=p[k][0];
p[next][1]=p[k][1];
next++;
k++;
}
if（k<=right&&p[k][0]==y）{
if（mm=p[k][1];
}
k++;
}
if（m>p[next-1][1]）{
p[next][0]=y;
p[next][1]=m;
next++;
}
while（k<=right&&p[k][1]<=p[next-1][1]）{
k++;
}
}
while（k<=right）{
p[next][0]=p[k][0];
p[next][1]=p[k][1];
next++;
k++;
}
left=right+1;
right=next-1;
head[i-1]=next;
}
returnnext;
}
voidtraceback（structGoods*goods,intnumber,inthead[],intp[][2],intx[]）
{
intj=p[head[0]-1][0],m=p[head[0]-1][1];
inti,k,a;
for（i=1;i<=number;i++）
{
x[i]=0;
a=1;
//for（k=3450;k<=head[i]-1&&a==1;k++）
for（k=head[i+1];k<=head[i]-1&&a==1;k++）
{
if（p[k][0]+goods[i-1].weight==j&&p[k][1]+goods[i-1].value==m）
{
x[i]=1;
j=p[k][0];
m=p[k][1];
a=0;
}
}
}
}
main（）
{
intbag1,bag2;//背包容量
intnumber1,number2;//物品数目
inti,n;
intp[20000][2];
inth[N],x[N];
structGoodsgoods1[N],goods2[N];
FILE*fp;
charch='0';
if（（fp=fopen（"附件4.背包问题输入数据.txt","r"））==NULL）//打开文件失败
printf（"Can'topenfile"）;
else//读入背包和物品信息
{
fseek（fp,18,SEEK_CUR）;
fscanf（fp,"%d",&bag1）;//背包1容量
fseek（fp,18,SEEK_CUR）;
ch='0';
for（i=0;ch!
='\n';i++）{
fscanf（fp,"%d",&goods1[i].weight）;//物品重量
ch=fgetc（fp）;
}
number1=i;
ch='0';
fseek（fp,14,SEEK_CUR）;
for（i=0;ch!
='\n'&&ch!
=EOF;i++）
{
fscanf（fp,"%d",&goods1[i].value）;//物品价值
ch=fgetc（fp）;
}
if（number1!
=i）{
printf（"读取数据出错，程序将退出！
\n"）;
system（"pause"）;
}
fseek（fp,22,SEEK_CUR）;
fscanf（fp,"%d",&bag2）;//背包1容量
fseek（fp,18,SEEK_CUR）;
ch='0';
for（i=0;ch!
='\n';i++）{
fscanf（fp,"%d",&goods2[i].weight）;//物品重量
ch=fgetc（fp）;
}
number2=i;
ch='0';
fseek（fp,14,SEEK_CUR）;
for（i=0;ch!
='\n'&&ch!
=EOF;i++）
{
fscanf（fp,"%d",&goods2[i].value）;//物品价值
ch=fgetc（fp）;
}
if（number2!
=i）{
printf（"读取数据出错，程序将退出！
\n"）;
system（"pause"）;
}
}
printf（"文件读取成功\n"）;
/*打印文件的信息*/
printf（"\n\n第一组背包数据：
\n"）;
printf（"背包容量：
%d物品数量：
%d\n物品重量：
\n",bag1,number1）;
for（i=0;iprintf（"%d",goods1[i].weight）;
printf（"\n物品价值：
\n"）;
for（i=0;iprintf（"%d",goods1[i].value）;
printf（"\n\n第二组背包数据：
\n"）;
printf（"背包容量：
%d物品数量：
%d\n物品重量：
\n",bag2,number2）;
for（i=0;iprintf（"%d",goods2[i].weight）;
printf（"\n物品价值：
\n"）;
for（i=0;iprintf（"%d",goods2[i].value）;
n=knapsack（goods1,bag1,number1,p,h）;
traceback（goods1,number1,h,p,x）;//确定放入的物品
//打印结果
printf（"\n\n第一组：
\n背包重量为：
%d背包价值为：
%d\n",p[n-1][0],p[n-1][1]）;
printf（"放入的物品为：
\n"）;
for（i=1;iif（x[i]==1）
printf（"物品%-2d重量%-2d价值%d\n",i,goods1[i-1].weight,goods1[i-1].value）;
//第二组数据
n=knapsack（goods2,bag2,number2,p,h）;
traceback（goods2,number2,h,p,x）;
printf（"\n\n第二组：
\n背包重量为：
%d背包价值为：
%d\n",p[n-1][0],p[n-1][1]）;
printf（"放入的物品为：
\n"）;
for（i=1;iif（x[i]==1）
printf（"物品%-2d重量%-2d价值
升级会员 