北邮 算法设计与分析_第三章实验报告

源程序代码

1. 最长公共子序列

#include

#include #define N 1000

int e[N][N],f[N][N];

void LCSLength(int m,int n,char *x,char *y,int c[][N],int b[][N])//构造数组b[i][j] {

int i,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; }

else if(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; } } }

void LCS(int i,int j,char *x,int b[][N]) {

if (i==0||j==0) return; if (b[i][j]==1) {

LCS(i-1,j-1,x,b); printf(\"%c\

/*第1种情况下，X(i)和Y(j)的最长公共子序列由X(i-1)和 Y(j-1)的解LCS(i-1, j-1, x, b)，加上位于最后的X[i]

组成 */ } else if(b[i][j]==2) LCS(i-1,j,x,b); else

LCS(i,j-1,x,b); //其它2种情况下，原问题解等于子问题解 } main() {

char A[N],B[N],C[N],D[N];

int a=1,b=1,c=1,d=1; char ch; int i; FILE * fp;

if((fp=fopen(\"最长公共子序列输入数据.txt\打开文件失败

printf(\"Can't open file \"); 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\ printf(\"\\n\"); for(i=0;i<=b;i++) printf(\"%c\ printf(\"\\n\"); for(i=0;i<=c;i++) printf(\"%c\ printf(\"\\n\");

for(i=0;i<=d;i++) printf(\"%c\ 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\"); return 0; }

2. 最大子段和

#include #include

#define N 400

void MaxSum(int n,int *a) {

int sum=0,b=0; int i,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个\

printf(\"\\n该序列的和最大子段为：\\n\"); for(i=x;i<=y;i++) printf(\"%d \

printf(\"\\n它们的和为 %d \\n\ } main() {

int A[N],B[N]; int a=0,b=0; int i;

FILE *fp1,*fp2;

if((fp1=fopen(\"最大子段和输入数据-序列1.txt\打开文件失败

printf(\"Can't open file1 \");

else //读取文件内容 {

for(i=0;!feof(fp1);i++)

fscanf(fp1,\"%d\\n\

a=i-1; }

if((fp2=fopen(\"最大子段和输入数据-序列2.txt\打开文件失败

printf(\"Can't open file2 \"); else {

for(i=0;!feof(fp2);i++)

fscanf(fp2,\"%d\\n\

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 \ system(\"pause\"); return 0; }

3. 凸多边形最优三角剖分

#include #include #include #define N 30

#define EARTH_RADIUS 6378.137

struct Base{//基站结构体 int ENODEBID;//基站标识 float LONGITUDE;//基站经度 float LATITUDE;//基站纬度 int NUM;//基站k-dist距离 };

void readfile(struct Base * base,int n) //读取文件函数 {

FILE * fp; int i=0; if(n==21)

fp=fopen(\"21个基站凸多边形数据.csv\ else

fp=fopen(\"29个基站凸多边形数据.csv\

if(fp==NULL)//打开文件失败 printf(\"Can't open file \"); else {

while(EOF!=fscanf(fp,\"%d,%f,%f,%d\NGITUDE,&base[i].LATITUDE,&base[i].NUM))

{//将数据读入结构体数组 i++;

//printf(\"%d\\n\ }

// printf(\"文件读入成功！！！\\n\\n\\n\"); } fclose(fp); }

float rad(float LatOrLon) {

return LatOrLon * 3.14/180.0; }

float distance(struct Base * base,int a,int b)//求两个基站间的距离

{ float s;

float radLat1,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); } return s; }

float weight(struct Base * base,int a,int b,int c) {

float s,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; return s;

}

float MinWeightTriangulation(struct Base * base,int n,float t[][N],int s[][N])

{

int i,j,r,k; float u=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{

u=t[i][k]+t[k+1][j]+weight(base,i-1,k,j); if(u{

t[i][j]=u; s[i][j]=k; } } } return t[1][n]; }

void Traceback(int i,int j,int s[][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\-1,j,s[i][j]); } main() {

int i;

float t[N][N]; int s[N][N];

struct Base base21[N];//结构体（N宏定义） struct Base base29[N];//结构体（N宏定义）

readfile(base21,21);//将数据从文件中读到结构体中 readfile(base29,29);//将数据从文件中读到结构体中 printf(\"文件读入成功！！！\\n\\n\\n\"); // for(i=0;i<=28;i++) //

printf(\"%6d %.3f %.5f %d\\n\DE,base29[i].LATITUDE,base29[i].NUM);

printf(\"凸

21多边形的最优三角剖分值

为 %f\

printf(\"最优三角剖分结构为： \\n\");

Traceback(1,20,s); //s[i][j]记录了Vi-1和Vj构成三角形的第3个顶点的位置

printf(\"凸

29多边形的最优三角剖分值

为 %f\

printf(\"最优三角剖分结构为： \\n\");

Traceback(1,28,s); //s[i][j]记录了Vi-1和Vj构成三角形的

第3个顶点的位置

system(\"pause\"); return 0; }

4. 01背包问题

#include #include #define N 100

struct Goods{

int weight;//物品重量 int value;//物品价值 };

int knapsack(struct Goods *goods,int head[]) {

int left=0,right=0,next=1,i,j,k,m,y;

p[0][0]=0;

bag,int p[][2],int number,int

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]if(k<=right&&p[k][0]==y){ }

if(m>p[next-1][1]){

p[next][0]=y; if(mm=p[k][1]; p[next][0]=p[k][0]; p[next][1]=p[k][1]; next++; k++;

}

}

}

}

p[next][1]=m; next++;

while(k<=right&&p[k][1]<=p[next-1][1]){ } k++;

while(k<=right){ }

left=right+1; right=next-1; head[i-1]=next; p[next][0]=p[k][0]; p[next][1]=p[k][1]; next++; k++;

return next;

void traceback(struct Goods *goods,int number,int head[],int p[][2],int x[])

{

int j=p[head[0]-1][0],m=p[head[0]-1][1]; int i,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() {

int bag1,bag2;//背包容量 int number1,number2;//物品数目 int i,n; int p[20000][2]; int h[N],x[N];

struct Goods goods1[N],goods2[N]; FILE *fp;

char ch='0';

if((fp=fopen(\"附件4.背包问题输入数据.txt\打开文件失败

printf(\"Can't open file \"); else //读入背包和物品信息 {

fseek(fp,18,SEEK_CUR);

fscanf(fp,\"%d\背包1容量 fseek(fp,18,SEEK_CUR); ch='0';

for(i=0;ch!='\\n';i++){

fscanf(fp,\"%d\物品重量

ch=fgetc(fp);

} number1=i; ch='0';

fseek(fp,14,SEEK_CUR); for(i=0;ch!='\\n'&&ch!=EOF;i++)

{

fscanf(fp,\"%d\物品价值 ch=fgetc(fp); } if(number1!=i){

printf(\"读取数据出错，程序将退出！\\n\"); system(\"pause\");

}

fseek(fp,22,SEEK_CUR);

fscanf(fp,\"%d\背包1容量

fseek(fp,18,SEEK_CUR); ch='0';

for(i=0;ch!='\\n';i++){

fscanf(fp,\"%d\物品重量

ch=fgetc(fp);

} number2=i; ch='0';

fseek(fp,14,SEEK_CUR); for(i=0;ch!='\\n'&&ch!=EOF;i++)

{

fscanf(fp,\"%d\物品价值 ch=fgetc(fp); } if(number2!=i){

printf(\"读取数据出错，程序将退出！\\n\"); system(\"pause\");

}

}

printf(\"文件读取成功！！！\\n\");

/*打印文件的信息 */ printf(\"\\n\\n第一组背包数据：\\n\");

printf(\"背包容量： %d 物品数量： %d\\n物品重量：\\n\ for(i=0;iprintf(\"%d \ printf(\"\\n物品价值： \\n\"); for(i=0;iprintf(\"%d \

printf(\"\\n\\n第二组背包数据：\\n\");

printf(\"背包容量： %d 物品数量： %d\\n物品重量：\\n\ for(i=0;iprintf(\"%d \ printf(\"\\n物品价值： \\n\"); for(i=0;iprintf(\"%d \

n=knapsack(goods1,bag1,number1,p,h);

traceback(goods1,number1,h,p,x); //确定放入的物品 //打印结果

printf(\"\\n\\n第一组：\\n背包重量为：%d 背包价值为：%d\\n\-1][0],p[n-1][1]); printf(\"放入的物品为： \\n\"); for(i=1;iprintf(\"物品%-2d 重量%-2d 价

值%d\\n\-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\-1][0],p[n-1][1]); printf(\"放入的物品为： \\n\"); for(i=1;iprintf(\"物品%-2d

重量%-2d

价

值%d\\n\-1].weight,goods2[i-1].value); system(\"pause\"); return 0; }

运行结果

1. 最长公共子序列

2. 最大子段和

3. 凸多边形最优三角剖分

4. 01背包问题