北邮算法设计和分析第三章实验报告.docx
- 文档编号:17912162
- 上传时间:2023-08-04
- 格式:DOCX
- 页数:25
- 大小:280.41KB
北邮算法设计和分析第三章实验报告.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;k
k])*(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(m m=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;i printf("%d",goods1[i].weight); printf("\n物品价值: \n"); for(i=0;i printf("%d",goods1[i].value); printf("\n\n第二组背包数据: \n"); printf("背包容量: %d物品数量: %d\n物品重量: \n",bag2,number2); for(i=0;i printf("%d",goods2[i].weight); printf("\n物品价值: \n"); for(i=0;i printf("%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;i if(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;i if(x[i]==1) printf("物品%-2d重量%-2d价值%
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 算法 设计 分析 第三 实验 报告