2012 公園內(nèi)道路設(shè)計問題 程序設(shè)計

西工大2012 B題公園內(nèi)道路設(shè)計問題 程序設(shè)計問題一編程functionE=Kruskal(w)%圖論最小生成樹Kruskal避圈算法(使用時根據(jù)題目修改w和n)%w為鄰接矩陣w=xlsread('distance.xls')[m,n]=size(w);k=1;fori=1:n-1forj=i+1:nifw(i,j)~=0x(1,k)=w(i,j);%記錄邊x(2,k)=i;%記錄起點x(3,k)=j;%記錄終點k=k+1;endendendk=k-1;%統(tǒng)計邊數(shù)k為邊數(shù)%步驟一%冒泡法給邊的大小排序fori=1:kforj=i+1:kifx(1,i)>x(1,j)a=x(1,i);x(1,i)=x(1,j);x(1,j)=a;a=x(2,i);x(2,i)=x(2,j);x(2,j)=a;a=x(3,i);x(3,i)=x(3,j);x(3,j)=a;endendend%給各點標(biāo)號賦初值fori=1:nl(i)=i；end%初始時選91加入集合EE(1,1)=x(1,1);%￡矩陣的第一行記錄最小生成樹的邊長E(2,1)=x(2,1);%E矩陣的第二行記錄邊的起點E(3,1)=x(3,1);%E矩陣的第三行記錄邊的終點a=min([l(E(2,1)),l(E(3,1))]);l(E(2,1))=a;l(E(3,1))=a;b=1;%記錄E中邊數(shù)fori=2:k%步驟四ifb==n-1%如果樹中邊數(shù)達到n-1break%算法終止end%步驟二ifl(x(2,i))~=l(x(3,i))%如果兩頂點標(biāo)號不同b=b+1; %將這條邊加入￡E(1,b)=x(1,i);E(2,b)=x(2,i);E(3,b)=x(3,i);%步驟三forj=1:n %對于所有頂點ifl(j)==max([l(E(2,b)),l(E(3,b))])%如果該頂點的標(biāo)號，等于=，新加入邊中的頂點標(biāo)號較大的值l(j)=min([l(E(2,b)),l(E(3,b))]);%將其改為較小的那一個以避圈endendendEndE問題二編程(1)求解問題二中兩個交叉點時M、N點最優(yōu)位置的C++源程序：#include<iostream>//兩個交叉點#include<cmath>usingnamespacestd;intmain(){doubleA[6][2],D[2][6];A[0][0]=20;A[0][1]=0;A[1][0]=50;A[1][1]=0;A⑵[0]=160;A[2][1]=0;A[3][0]=120;A[3][1]=100;A[4][0]=35;A[4][1]=100;A[5][0]=10;A[5][1]=100;doubleB[2][2],B0[2][2];doubled15,d015,d16,d016,d25,d025,d26,d026,d27,d027,d35,d035,d36,d036,d37,d037;d015=141.421;d016=101.119;d025=122.066;d026=101.119;d027=107.703;d035=107.703;d036=160.078;d037=180.278;B[0][0]=65;B[0][1]=55;B[1][0]=105;B[1][1]=60;doublek1,k2,k3,k4;doubles0=500,s=0;doublem;for(k1=-10;k1<=10;k1=k1+1){for(k2=-10;k2<=10;k2=k2+1){for(k3=-10;k3<=10;k3=k3+1){for(k4=-10;k4<=10;k4=k4+1){D[0][1]=sqrt((B[0][0]+k1-A[1][0])*(B[0][0]+k1-A[1][0])+(B[0][1]+k2-A[1][1])*(B[0][1]+k2-A[[1]));D[0][0]=D[0][1]+30;D[0][2]=sqrt((B[0][0]+k1-A[2][0])*(B[0][0]+k1-A[2][0])+(B[0][1]+k2-A[2][1])*(B[0][1]+k2-A[[1]));D[0][3]=sqrt((B[0][0]+k1-A[3][0])*(B[0][0]+k1-A[3][0])+(B[0][1]+k2-A[3][1])*(B[0][1]+k2-A[[1]));D[0][4]=sqrt((B[0][0]+k1-A[4][0])*(B[0][0]+k1-A[4][0])+(B[0][1]+k2-A[4][1])*(B[0][1]+k2-A[[1]));D[0][5]=D[0][4]+25;D[1][1]=sqrt((B[1][0]+k3-A[1][0])*(B[1][0]+k3-A[1][0])+(B[1][1]+k4-A[1][1])*(B[1][1]+k4-A[[1]));D[1][0]=D[1][1]+30;D[1]⑵=sqrt((B[1][0]+k3-A⑵[0])*(B[1][0]+k3-A⑵[0])+(B[1][1]+k4-A⑵[1])*(B[1][1]+k4-A[[1]));D[1][3]=sqrt((B[1][0]+k3-A[3][0])*(B[1][0]+k3-A[3][0])+(B[1][1]+k4-A[3][1])*(B[1][1]+k4-A[[1]));D[1][4]=sqrt((B[1][0]+k3-A[4][0])*(B[1][0]+k3-A[4][0])+(B[1][1]+k4-A[4][1])*(B[1][1]+k4-A[[1]));D[1][5]=D[1][4]+25;m=sqrt((B[0][0]+k1-B[1][0]-k3)*(B[0][0]+k1-B[1][0]-k3)+(B[0][1]+k2-B[1][1]-k4)*(B[0][1]+k2-B[1][1]-k4));d15=D[0][0]+D[1][3]+m;d16=D[0][0]+D[0][4];d25=D[0][1]+D[1][3]+m;d26=D[0][1]+D[0][4];d27=D[0][1]+D[0][5];d35=D[1][2]+D[1][3];d36=D[1][2]+D[0][4]+m;d37=D[1][2]+D[0][5]+m;if(d15<=1.4*d015)if(d16<=1.4*d016)if(d25<=1.4*d025)if(d26<=1.4*d026)if(d27<=1.4*d027)if(d35<=1.4*d035)if(d36<=1.4*d036)if(d37<=1.4*d037){s=d26+d35+m;if(s<s0){s0=s;B0[0][0]=B[0][0]+k1;B0[0][1]=B[0][1]+k2;B0[1][0]=B[1][0]+k3;B0[1][1]=B[1][1]+k4;}}}}}}cout<<B0[0][0]<<","<<B0[0][1]<<endl;cout<<B0[1][0]<<","<<B0[1][1]<<endl;cout<<s0<<endl;return0;}問題二編程(2)問題二中交替迭代算法求最優(yōu)解的源程序：#include<stdio.h>#include<cmath>voidmain(){doublemx=65,my=58,nx=107,ny=65,mn,m2,m6,n5,no,s0=255.738,ans,s=500;doubleX[2][2];doubles12=30,s16=101.119,s15=141.421,s25=122.066,s26=101.119,s27=107.703,s36=160.078,s37=180.278,s35=107.703;doublep2x=50,p2y=0,p3x=160,p3y=0,pox=161,poy=30,p5x=120,p5y=100,p6x=35,p6y=100;doublek1,k2,k3,k4;doubleo3=30.017;doublemn0,m20,m60,n50,no0;inti,j;for(k1=-20;k1<=20;k1=k1+0.5){for(k2=-20;k2<=20;k2=k2+0.5){for(k3=-20;k3<=20;k3=k3+0.5){for(k4=-20;k4<=20;k4=k4+0.5){mn=sqrt((mx+k1-nx-k3)*(mx+k1-nx-k3)+(my+k2-ny-k4)*(my+k2-ny-k4));m2=sqrt((mx+k1-p2x)*(mx+k1-p2x)+(my+k2-p2y)*(my+k2-p2y));m6=sqrt((mx+k1-p6x)*(mx+k1-p6x)+(my+k2-p6y)*(my+k2-p6y));n5=sqrt((nx+k3-p5x)*(nx+k3-p5x)+(ny+k4-p5y)*(ny+k4-p5y));no=sqrt((nx+k3-pox)*(nx+k3-pox)+(ny+k4-poy)*(ny+k4-poy));if(m6+mn+m2+n5+no<s0){if(m2+mn+n5<1.4*s25){if(o3+no+mn+m6<1.4*s36){if(o3+no+mn+m6+25<1.4*s37){if(m2+m6<1.4*s26){if(m2+m6+25<1.4*s27){if(o3+no+n5<1.4*s35){if(s12+m2+m6<1.4*s16){if(s12+m2+mn+n5<1.4*s15){ans=mn+m6+m2+no+n5;if(ans<s){s=ans;X[0][0]=mx+k1;X[0][1]=my+k2;X[1][0]=nx+k3;X[1][1]=ny+k4;mn0=mn;m20=m2;m60=m6;n50=n5;no0=no;}}}}}}}}}}}}}}printf("最小距離”)；printf("%lf\n",s);printf("各個點對應(yīng)的距離mnm2m6n5no\n");printf("%lf\n",mn0);printf("%lf\n",m20);printf("%lf\n",m60);printf("%lf\n",n50);printf("%lf\n",no0);printf("\n對應(yīng)的M,N的坐標(biāo)\n");for(i=0;i<2;i++){for(j=0;j<2;j++){printf("%lf\n",X[i][j]);}}}問題三編程#include<iostream>//在兩個點的最有基礎(chǔ)上繼續(xù)優(yōu)化#include<cmath>usingnamespacestd;intmain(){doubleQ[3]⑵,Q0[3][2]={0},d1,d2,d3,N⑵,C⑵,D⑵,s,s0=500;inti,j;N[0]=107;//NCD三點的坐標(biāo)N[1]=65;C[0]=160;C[1]=0;D[0]=200;D[1]=50;Q[0][0]=140;//給出與湖相交的點的坐標(biāo)初始值Q[0][1]=65;Q[1][0]=160;Q[1][1]=45;Q⑵[0]=165;Q⑵[1]=50;doublek1,k2,k3,m1,m2;for(k1=0;k1<=20;k1=k1+0.1)//以步長為0.1遍歷for(k2=-20;k2<=5;k2=k2+0.1)for(k3=0;k3<=5;k3=k3+0.1){d1=sqrt((Q[0][0]-N[0])*(Q[0][0]-N[0])+(Q[0][1]-k1-N[1])*(Q[0][1]-k1-N[1]));d2=sqrt((Q[1][0]+k2-C[0])*(Q[1][0]+k2-C[0])+(Q[1][1]-C[1])*(Q[1][1]-C[1]));d3=sqrt((Q⑵[0]-D[0])*(Q⑵[0]-D[0])+(Q⑵[1]-k3-D[1])*(Q⑵[1]-k3-D[1]));if(d1+d2+d3<147.9)//判斷是否小于原值if(d1+d2+Q[0][1]-k1-45+Q[1][0]+k2-140<113.448)//判斷是否滿足3到其他點的條件{if(d2+d3+165-Q[1][0]-k2+Q⑵[1]-k3-45<89.6)//是否滿足3到4的條件{s=d1+d2+d3;if(s<s0){s0=s;//記錄當(dāng)前最有路徑長度m1=d1+d2+Q[0][1]-k1-45+Q[1][0]+k2-140;m2=d2+d3+165-Q[