北邮 算法设计与分析第三章实验报告Word格式.docx
《北邮 算法设计与分析第三章实验报告Word格式.docx》由会员分享，可在线阅读，更多相关《北邮 算法设计与分析第三章实验报告Word格式.docx（25页珍藏版）》请在冰点文库上搜索。
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）//打开文件失败
Can'
topenfile"
）;
{//读取文件内容
ch=fgetc（fp）;
while（ch!
='
B'
&
ch!
=EOF）
A[a]=ch;
a++;
while（ch=='
\n'
）
a--;
C'
B[b]=ch;
b++;
b--;
D'
C[c]=ch;
c++;
c--;
D[d]=ch;
d++;
d--;
fclose（fp）;
文件读取完成\n"
/*for（i=0;
=a;
i++）
A[i]）;
\n"
for（i=0;
=b;
B[i]）;
=c;
C[i]）;
=d;
D[i]）;
*/
\n\n\nA和B的最长公共子序列为：
LCSLength（a,b,A,B,e,f）;
LCS（a,b,A,f）;
\n\n\nC和D的最长公共子序列为：
LCSLength（c,d,C,D,e,f）;
LCS（c,d,C,f）;
\n\n\nA和D的最长公共子序列为：
LCSLength（a,d,A,D,e,f）;
LCS（a,d,A,f）;
system（"
pause"
return0;
2.最大子段和
#defineN400
voidMaxSum（intn,int*a）
intsum=0,b=0;
inti,x1=0,y1=0,x=0,y=0;
for（i=1;
if（b>
0）
b+=a[i];
y1=i;
b=a[i];
x1=i;
if（b>
sum）
sum=b;
x=x1;
y=y1;
\n该序列的最大子段和的位置为从第%d个到第%d个"
x+1,y+1）;
\n该序列的和最大子段为：
for（i=x;
=y;
%d"
a[i]）;
\n它们的和为%d\n"
sum）;
intA[N],B[N];
inta=0,b=0;
FILE*fp1,*fp2;
if（（fp1=fopen（"
最大子段和输入数据-序列1.txt"
topenfile1"
else//读取文件内容
!
feof（fp1）;
fscanf（fp1,"
%d\n"
&
A[i]）;
a=i-1;
if（（fp2=fopen（"
最大子段和输入数据-序列2.txt"
topenfile2"
feof（fp2）;
fscanf（fp2,"
B[i]）;
b=i-1;
fclose（fp1）;
文件读取成功\n\n\n"
对于最大子段和输入数据-序列1"
MaxSum（a,A）;
//计算最大子段和
\n\n对于最大子段和输入数据-序列2"
MaxSum（b,B）;
//for（i=0;
//printf（"
3.凸多边形最优三角剖分
math.h>
#defineN30
#defineEARTH_RADIUS6378.137
structBase{//基站结构体
intENODEBID;
//基站标识
floatLONGITUDE;
//基站经度
floatLATITUDE;
//基站纬度
intNUM;
//基站k-dist距离
};
voidreadfile（structBase*base,intn）//读取文件函数
inti=0;
if（n==21）
fp=fopen（"
21个基站凸多边形数据.csv"
rb"
else
29个基站凸多边形数据.csv"
if（fp==NULL）//打开文件失败
while（EOF!
=fscanf（fp,"
%d,%f,%f,%d"
base[i].ENODEBID,&
base[i].LONGITUDE,&
base[i].LATITUDE,&
base[i].NUM））
{//将数据读入结构体数组
i++;
//printf（"
i）;
文件读入成功\n\n\n"
}
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;
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;
floatMinWeightTriangulation（structBase*base,intn,floatt[][N],ints[][N]）
inti,j,r,k;
floatu=0;
t[i][i]=0;
for（r=2;
r<
r++）//r为当前计算的链长（子问题规模）
=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;
k<
i+r-1;
k++）//将链ij划分为（A[i:
k]）*（A[k+1:
j]）
u=t[i][k]+t[k+1][j]+weight（base,i-1,k,j）;
if（u<
t[i][j]）
t[i][j]=u;
s[i][j]=k;
returnt[1][n];
voidTraceback（inti,intj,ints[][N]）
if（i==j）
Traceback（i,s[i][j],s）;
Traceback（s[i][j]+1,j,s）;
三角剖分顶点：
V%d,V%d,V%d\n"
i-1,j,s[i][j]）;
}
floatt[N][N];
ints[N][N];
structBasebase21[N];
//结构体（N宏定义）
structBasebase29[N];
//结构体（N宏定义）
readfile（base21,21）;
//将数据从文件中读到结构体中
readfile（base29,29）;
//将数据从文件中读到结构体中
=28;
%6d%.3f%.5f%d\n"
base29[i].ENODEBID,base29[i].LONGITUDE,base29[i].LATITUDE,base29[i].NUM）;
凸21多边形的最优三角剖分值为%f"
MinWeightTriangulation（base21,20,t,s））;
最优三角剖分结构为：
\n"
Traceback（1,20,s）;
//s[i][j]记录了Vi-1和Vj构成三角形的第3个顶点的位置
凸29多边形的最优三角剖分值为%f"
MinWeightTriangulation（base29,28,t,s））;
Traceback（1,28,s）;
4.01背包问题
#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;
=right&
p[j][0]+goods[i-1].weight<
=bag;
y=p[j][0]+goods[i-1].weight;
m=p[j][1]+goods[i-1].value;
while（k<
p[k][0]<
y）{
p[next][0]=p[k][0];
p[next][1]=p[k][1];
next++;
k++;
}
if（k<
p[k][0]==y）{
if（m<
p[k][1]）{
m=p[k][1];
}
if（m>
p[next-1][1]）{
p[next][0]=y;
p[next][1]=m;
p[k][1]<
=p[next-1][1]）{
}
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;
=number;
x[i]=0;
a=1;
//for（k=3450;
=head[i]-1&
a==1;
k++）
for（k=head[i+1];
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;
intbag1,bag2;
//背包容量
intnumber1,number2;
//物品数目
inti,n;
intp[20000][2];
inth[N],x[N];
structGoodsgoods1[N],goods2[N];
FILE*fp;
charch='
0'
;
附件4.背包问题输入数据.txt"
else//读入背包和物品信息
fseek（fp,18,SEEK_CUR）;
fscanf（fp,"
%d"
bag1）;
//背包1容量
ch='
i++）{
fscanf（fp,"
goods1[i].weight）;
//物品重量
ch=fgetc（fp）;
number1=i;
fseek（fp,14,SEEK_CUR）;
=EOF;
goods1[i].value）;
if（number1!
=i）{
printf（"
读取数据出错，程序将退出！
system（"
fseek（fp,22,SEEK_CUR）;
bag2）;
goods2[i].weight）;
number2=i;
goods2[i].value）;
if（number2!
文件读取成功\n"
/*打印文件的信息*/
\n\n第一组背包数据：
背包容量：
%d物品数量：
%d\n物品重量：
bag1,number1）;
number1;
goods1[i].weight）;
\n物品价值：
goods1[i].value）;
\n\n第二组背包数据：
bag2,number2）;
number2;
goods2[i].weight）;
goods2[i].value）;
n=knapsack（goods1,bag1,number1,p,h）;
traceback（goods1,number1,h,p,x）;
//确定放入的物品
//打印结果
\n\n第一组：
\n背包重量为：
%d背包价值为：
p[n-1][0],p[n-1][1]）;
放入的物品为：
if（x[i]==1）
物品%-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）;
\n\n第二组：
物品%-2d重量%-2d价值
升级会员 