算法上机实验报告

第页实验一最近点对问题实验内容与要求已知平面上分布着点集P中的n个点p1,p2,...pn，点i的坐标记为(xi,yi)，1≤i≤n。两点之间的距离取其欧式距离，记为问题：找出一对距离最近的点。注：允许两个点位于同一个位置，此时两点之间的距离为0要求：用分治法实现最近点对的问题。算法设计（1）首先将所有的点按照x坐标排序。排序过程需要O(nlogn)的时间，不会从整体上增加时间复杂度的数量级。（2）划分：由于点已经按x坐标排序，所以空间上可以“想象”画一条垂线，作为分割线，将平面上的点集分成左、右两半PL和PR。如下图所示：ddLdCdR分割线PLPR记,dL:PL中的最近点对距离；dR:PR中的最近点对距离；dC:跨越分割线的最近点对距离。则，最近的一对点或者在PL中，或者在PR中，或者一个在PL中而另一个在PR中（跨越分割线）。设点按它们的y坐标排序，如果pi和某个pj的y坐标相差大于δ，那么这样的pi可以终止计算，继续处理pi+1。算法描述如下：fori=1tonumPointsInStripdoforj=i+1tonumPointsInStripdoifpiandpj'sy-coordinatesdifferbymorethanδbreak;elseifdist(pi,pj)<δδ=dist(pi,pj);1.3实验结果与分析实验数据：（1）点对数目：6（2）点对坐标：（1,3）（2,5）（3,12）（5,8）（6,9）（7,15）运行结果：如图显示的是最近点对<5.00,8.00><6.00,9.00>的距离为1.411.4编程技术与方法纵观整个过程，首先要对X坐标排序时间为O（NlogN），这是分治之前的预处理。然后问题分成了N/2规模，然后用Q（N）的复杂度得到中间的最近点对，然后可以在常数时间内得到最终的点对与最近值。So。。。T（N）=2T（N/2）+O（N），可以得到该算法的时间为O（NlogN）,在用分治法之前首先对Y坐标进行冒泡排序，将左右|d|范围里的点按Y值排序，然后依次从每个点出发做水平线，并在其之上d的距离做水平线，这样得到了一个2d*d的矩形，显然，在此矩形之外的点无需开率啦，可以证明，矩形内最多容下8个点（包括自己本身）。所以意味着在排好序的Y坐标点中，只需要考虑其后的7个点就行了，此外已有人证明了事实上只需要考虑其后的4个点就行啦。可见，这些的时间复杂度最多Q（N）。1.5源程序及注释#include<stdio.h>#include<stdlib.h>#include<math.h>#defineMAXLEN200intinit(float*x,float*y,int*ind){intn,i;while(1==scanf("%d",&n)){if(n>1)break;printf("ninvalid!\n");}for(i=0;i<n;i++){scanf("%f%f",x+i,y+i);ind[i]=i;}returnn;}voidpre_sort(float*x,float*y,int*ind,intn){//mustfinishinO(nlogn)buthereusingnormorlsortmethod//bubblesortinti,j;inttmp;floattmp_y,tmp_x;for(i=0;i<n;i++)for(j=n-1;j>i;j--)if(x[j-1]>x[j]){//swapxtmp_x=x[j-1];x[j-1]=x[j];x[j]=tmp_x;//swapytmp_y=y[j-1];y[j-1]=y[j];y[j]=tmp_y;//swapindnoneednow!/*tmp=ind[j-1];ind[j-1]=ind[j];ind[j]=tmp;*/}for(i=0;i<n;i++)for(j=n-1;j>i;j--)if(y[j-1]>y[j]){//swapytmp_y=y[j-1];y[j-1]=y[j];y[j]=tmp_y;//swapindtmp=ind[j-1];ind[j-1]=ind[j];ind[j]=tmp;}}floatget_pair_len(floatx1,floaty1,floatx2,floaty2){returnsqrt((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1));}voidfind_closest_pair(intst,inted,float*x,float*y,int*ind,float*closest,float*x1,float*y1,float*x2,float*y2){//keycodeif(ed-st==1){//only2point*closest=get_pair_len(x[ind[0]],y[0],x[ind[1]],y[1]);*x1=x[ind[0]];*y1=y[0];*x2=x[ind[1]];*y2=y[1];}elseif(ed-st==2){//only3pointfloatlen;*closest=get_pair_len(x[ind[0]],y[0],x[ind[1]],y[1]);*x1=x[ind[0]];*y1=y[0];*x2=x[ind[1]];*y2=y[1];len=get_pair_len(x[ind[0]],y[0],x[ind[2]],y[2]);if(len<*closest){*closest=len;*x1=x[ind[0]];*y1=y[0];*x2=x[ind[2]];*y2=y[2];}len=get_pair_len(x[ind[1]],y[1],x[ind[2]],y[2]);if(len<*closest){*closest=len;*x1=x[ind[1]];*y1=y[1];*x2=x[ind[2]];*y2=y[2];}}else{//atleast4pointsinti,cl,cr,ct;intmid;floatt_c1,t_c2;floatt_c1_x1,t_c1_y1,t_c1_x2,t_c1_y2;floatt_c2_x1,t_c2_y1,t_c2_x2,t_c2_y2;float*yl,*yr,*yct;int*indl,*indr,*indct;mid=(st+ed)/2;yl=(float*)malloc((mid-st+1)*sizeof(float));indl=(int*)malloc((mid-st+1)*sizeof(int));yr=(float*)malloc((ed-mid)*sizeof(float));indr=(int*)malloc((ed-mid)*sizeof(int));if(!yl||!yr||!indl||!indr)exit(-2);//nonenoughmmfor(i=0,cl=0,cr=0;i<=ed-st;i++){//storenewordery&indif(ind[i]<=mid){yl[cl]=y[i];indl[cl]=ind[i];cl++;}else{yr[cr]=y[i];indr[cr]=ind[i];cr++;}}//dividedfind_closest_pair(st,mid,x,yl,indl,&t_c1,&t_c1_x1,&t_c1_y1,&t_c1_x2,&t_c1_y2);find_closest_pair(mid+1,ed,x,yr,indr,&t_c2,&t_c2_x1,&t_c2_y1,&t_c2_x2,&t_c2_y2);if(t_c1<t_c2){*closest=t_c1;*x1=t_c1_x1;*y1=t_c1_y1;*x2=t_c1_x2;*y2=t_c1_y2;}else{*closest=t_c2;*x1=t_c2_x1;*y1=t_c2_y1;*x2=t_c2_x2;*y2=t_c2_y2;}//gettheclosestpairbetweenthetwopart(L&R)intv,ve;floatclosest_tmp;floatpart_line=(x[mid]+x[mid+1])/2.0;yct=(float*)malloc((ed-st+1)*sizeof(float));indct=(int*)malloc((ed-st+1)*sizeof(int));//getalltheyintherectfor(i=0,ct=0;i<=ed-st;i++)if(x[ind[i]]>part_line-*closest&&x[ind[i]]<part_line+*closest){yct[ct]=y[i];indct[ct]=ind[i];ct++;}//checkfollowedthe4pointsif(ct>1){for(i=0;i<ct-1;i++){ve=(i+4<ct-1?i+4:ct-1);v=i+1;while(v<=ve&&yct[v]-yct[i]<=*closest){closest_tmp=get_pair_len(x[indct[i]],yct[i],x[indct[v]],yct[v]);if(closest_tmp<*closest){*closest=closest_tmp;*x1=x[indct[i]];*y1=yct[i];*x2=x[indct[v]];*y2=yct[v];}v++;}}}free(yl);free(yr);free(indl);free(indr);free(yct);free(indct);}}intmain(){floatX[MAXLEN],Y[MAXLEN];intIND[MAXLEN],n;n=init(X,Y,IND);floatclosest,x1,y1,x2,y2;pre_sort(X,Y,IND,n);find_closest_pair(0,n-1,X,Y,IND,&closest,&x1,&y1,&x2,&y2);printf("theclosestvalueis:%-4.2f(%-4.2f,%-4.2f)(%-4.2f,%-4.2f)\n",closest,x1,y1,x2,y2);return0;}实验二大整数乘法2.1实验内容与要求利用分治法设计一个计算两个n位的大整数相乘的算法，要求计算时间低于O(n2)。大整数（biginteger）：位数很多的整数，普通的计算机不能直接处理，如：9834975972130802345791023498570345显然，这样的整数普通的计算机和程序语言是无法直接表示的。大整数运算：给定两个n位的整数I，J,加、减法：可以用O(n)的时间计算出I+J和I-J，即使I、J是大整数；乘法：若I、J超过普通计算机可以表示的数据范围，怎么计算IxJ?如I=9834975972135791023498570345J=34324500180989723478923450232.2算法设计要求两个位数为n的整数A和B的乘积AxB。如果用普通的乘法的话，要用n2次乘法和n-1次加法，所以时间复杂度是O(n2)。如果把A分解成A=a*10n/2+b把B分解成B=c*10n/2+d那么AxB=(a*10n/2+b)x(c*10n/2+d)=ac*10n+(ad+bc)*10n/2+bd=ac*10n+((a+b)(c+d)-ac-bd)*10n/2+bd这样的话是3次乘法6次加法，当然，可以递归计算ac,bd,(a+d)(c+d)由此可以产生下面递推公式：T(n)=3T(n/2)+bn;n>1T(n)=d;n=1bd是大于0的常量。根据主定理T(n)=n1.59(1.59=log23)算法实现：//大整数乘法publicclassMultiplication{/***@paramargs*/publiclongmutiply(longa,longb){longn=getDigitsNum(a);//位数if(n<4)returna*b;longal=a%(int)Math.pow(10,n/2);//每个数字分成两部分longau=a/(int)Math.pow(10,Math.ceil(n/2));longbl=b%(int)Math.pow(10,n/2);longbu=b/(int)Math.pow(10,Math.ceil(n/2));longac=mutiply(au,bu);//aclongbd=mutiply(al,bl);//bdlongabcd=mutiply(au+al,bu+bl);//(a+b)*(c+d)longr=ac*(long)Math.pow(10,2*(n/2))+(abcd-acbd)*(long)Math.pow(10,n/2)+bd;returnr;}//计算位数,a与b的位数必须相等。时间复杂度是O(n)publicintgetDigitsNum(longa){inti=0;while(a>0){i++;a=a/10;}returni;}publicstaticvoidmain(String[]args){//TODOAuto-generatedmethodstublonga=1683527,b=1528719;longresult=newMultiplication().mutiply(a,b);System.out.println(a*b);System.out.println(result);}}2.3实验结果与分析实验测试数据：1111111111*1111111111123456789*999888666555222程序运行结果：（1）（2）经计算器验算，计算结果均正确说明程序具有可行性。2.4编程技术与方法利用分治法进行编程时往往计算量过大时就会溢出，此时采取数组的方式来存放数据，并且将其以字符串的形式存储并输出，每四位存储在一个数组中由高到低，并且将进位作为一个单独的数组在下一个高位数组中进行运算时加进去，其输出数组由高位到地位组成一个新的字符串，该字符串显示的结果就是运算的结果了！2.5源程序及注释#include<stdio.h>#include<string.h>voida2d(intx[],chara[]){inti,j;for(i=0;i<500;i++)x[i]=0;j=strlen(a)-1;for(i=0;j>=0;j--,i++)x[i]=a[j]-'0';}intmy_len(intx[]){inti;for(i=499;i>=0&&x[i]==0;i--);returni<0?0:i;}voidmulti(intx[],inty[]){intsum[500]={0},i,j,k,lx=my_len(x),ly=my_len(y);for(i=0;i<=lx;i++)for(j=0;j<=ly;j++)sum[i+j]+=x[i]*y[j];for(i=0;i<499;i++){sum[i+1]+=sum[i]/10;sum[i]%=10;x[i]=sum[i];}}intmain(){inti,x[500],y[500];chara[500],b[500];while(scanf("%s%s",a,b)!=EOF){a2d(x,a);a2d(y,b);multi(x,y);i=my_len(x);for(;i>=0;i--)printf("%d",x[i]);puts("");}return0;}实验三单源点3.1实验内容与要求给定一个带权有向图G=（V,E），其中每条边的权是非负实数，给定V中的一个定点，称为源。计算从源到所有定点的最短路长度。这里的路的长度是指路上个边权之和。这个问题称之为单源点最短路径。利用贪心算法设计一个程序来实现单源点最短距离的求取。3.2算法设计Dijkstra算法是解单源最短路径的一个贪心算法其基本思想是，设置顶点集合S并不断的做贪心选择来扩充这个集合。一个顶点属于S当且仅当从源点到该顶点的最短路径长度已知。初值时，S中仅含有源，设u是G中某一个顶点，把从源到u且中间只经过S中的顶点的路径（称为特殊路径）长度用数组dist记录，Dijkstra算法每次从V-S中取出具有最短特殊路径长度的顶点u，将u添加到S中，同时对数组dist做必要的修改，一旦S中包含了V中所有的顶点，dist就记录了从源到所有其他顶点的最短路径长度。3.3实验结果与分析测试数据：实验运行结果：其中57表示这是一个有5个顶点7条边组成的有向带权图，0到1的距离为100其余以此类推，输入源点0，则其单源点最短路径和距离分别为：0-1路径为0-4-3-1距离为700-2路径为0-2距离为30其余以此类推，经手动验证，说明程序具有可行性，结果正确。3.4编程技术与方法该实验实现的主要方法是Dijkstra算法，试验程序中主要利用数组来存储其有向带权图的邻接矩阵，利用数组来进行矩阵的一些运算。为了求出最短路径，Dijkstra就提出了以最短路径长度递增，逐次生成最短路径的算法。譬如对于源顶点V0，首先选择其直接相邻的顶点中长度最短的顶点Vi，那么当前已知可得从V0到达Vj顶点的最短距离dist[j]=min{dist[j],dist[i]+matrix[i][j]}。根据这种思路：假设存在G=<V,E>，源顶点为V0，U={V0},dist[i]记录V0到i的最短距离，path[i]记录从V0到i路径上的i前面的一个顶点。1.从V-U中选择使dist[i]值最小的顶点i，将i加入到U中；2.更新与i直接相邻顶点的dist。(dist[j]=min{dist[j],dist[i]+matrix[i][j]})3.直到U=V，停止。3.5源程序及注释/*Dijkstra求单源最短路径2015.6.17*/#include<iostream>#include<stack>#include<stdlib.h>#defineM100#defineN100usingnamespacestd;typedefstructnode{intmatrix[N][M];//邻接矩阵intn;//顶点数inte;//边数}MGraph;voidDijkstraPath(MGraphg,int*dist,int*path,intv0)//v0表示源顶点{inti,j,k;bool*visited=(bool*)malloc(sizeof(bool)*g.n);for(i=0;i<g.n;i++)//初始化{if(g.matrix[v0][i]>0&&i!=v0){dist[i]=g.matrix[v0][i];path[i]=v0;//path记录最短路径上从v0到i的前一个顶点}else{dist[i]=INT_MAX;//若i不与v0直接相邻，则权值置为无穷大path[i]=-1;}visited[i]=false;path[v0]=v0;dist[v0]=0;}visited[v0]=true;for(i=1;i<g.n;i++)//循环扩展n-1次{intmin=INT_MAX;intu;for(j=0;j<g.n;j++)//寻找未被扩展的权值最小的顶点{if(visited[j]==false&&dist[j]<min){min=dist[j];u=j;}}visited[u]=true;for(k=0;k<g.n;k++)//更新dist数组的值和路径的值{if(visited[k]==false&&g.matrix[u][k]>0&&min+g.matrix[u][k]<dist[k]){dist[k]=min+g.matrix[u][k];path[k]=u;}}}}voidshowPath(int*path,intv,intv0)//输出最短路径上的各个顶点{stack<int>s;intu=v;while(v!=v0){s.push(v);v=path[v];}s.push(v);while(!s.empty()){cout<<s.top()<<"";s.pop();}}intmain(intargc,char*argv[]){intn,e;//表示输入的顶点数和边数while(cin>>n>>e&&e!=0){inti,j;ints,t,w;//表示存在一条边s->t,权值为wMGraphg;intv0;int*dist=(int*)malloc(sizeof(int)*n);int*path=(int*)malloc(sizeof(int)*n);for(i=0;i<N;i++)for(j=0;j<M;j++)g.matrix[i][j]=0;g.n=n;g.e=e;for(i=0;i<e;i++){cin>>s>>t>>w;g.matrix[s][t]=w;}cin>>v0;//输入源顶点DijkstraPath(g,dist,path,v0);for(i=0;i<n;i++){if(i!=v0){showPath(path,i,v0);cout<<dist[i]<<endl;}}}return0;}实验四最优二分检索树4.1实验内容与要求. 实现最优二分检索树算法，计算各C(i,j)、R(i,j)、W(i,j)的值，并推导树的形态4.2算法设计最优二分检索树算法描述及流程图：在计算时，首先计算所有使得j-i=1的C[i][j]，其中C[i][i]=0，且W[i][i]=Q[i](0=<i<=n)，接着计算使得j-i=2的C[i][j]，在计算期间，记下每根树的根结点Tij开始开始主函数main求出树形态函数Root（）开始开始定义：内部结点概率值数组P[N];外部结点概率值Q[N+1];成本C[N+1][N+1]，定义：内部结点概率值数组P[N];外部结点概率值Q[N+1];成本C[N+1][N+1]，W[N+1][N+1];根R[N+1][N+1]（全局变量）实参m，n表示树实参m，n表示树Tmn输入结点数目n，以及内部结点概率值P[n];外部结点概率值Q[n+1];输入结点数目n，以及内部结点概率值P[n];外部结点概率值Q[n+1];i=0;N m=nY左右子树为空，输出*W[i][i]Q[i],R[i][[i]C[i][i]0左右子树为空，输出*W[i][i]Q[i],R[i][[i]C[i][i]0W[i][i+1]Q[i]+Q[i+1]+P[i+1]ii+1printf("%d",R[m][n]);输出当前结点Root(m,R[m][n]-1);printf("%d",R[m][n]);输出当前结点Root(m,R[m][n]-1);递归调用左子树Root(R[m][n],n);递归调用右子树i=i+1Ni=n W[i][i]=Q[i],R[i][[i]=C[i][i]YW[i][i]=Q[i],R[i][[i]=C[i][i]格式化输出，调用函数Root（）输出树的形态格式化输出，调用函数Root（）输出树的形态m=m+1m=1m=m+1m=1Yi=0j=i+mi=0j=i+mYm=n+1NW[i][j]=W[i][j-1]+P[j]+Q[j]寻找k满足C[i][k-1]+C[k][j]取最小R[i][j]=k,C[i][j=W[i][j]+C[i][k-1]+C[k][j]W[i][j]=W[i][j-1]+P[j]+Q[j]寻找k满足C[i][k-1]+C[k][j]取最小R[i][j]=k,C[i][j=W[i][j]+C[i][k-1]+C[k][j]i=i+1i=i+1实验结果与分析（1）按照如图输入得到的结果如下（其中最后树形态输出采用的是先序遍历，且外部结点用*表示）：（2）按照如图输入得到的结果如下（其中最后树形态输出采用的是先序遍历，且外部结点用*表示）：试验运行结果均正确说明程序具有可行性时间及空间复杂度分析由于采用二维定大小数组存储W及C，因此所需要的空间复杂度为O(N*N)；在计算时，找有m个节点的最优树的时间复杂度为O(n*n)（n表示输入结点的个数，与N不一定相同）。此外，在构造树的形态函数Root（）中，时间复杂度为O（n*log源程序及注释#include<stdio.h>#defineN100#defineMAX65535voidRoot(intm,intn);//求出树的形态intR[N+1][N+1];voidmain(void){ floatP[N];//内部结点概率值 floatQ[N+1];//外部结点概率值 floatC[N+1][N+1];//成本 floatW[N+1][N+1]; inti=0; intj=0; intm=0; intk=0; intk1=0; floatmin=0; intn;//结点数目 printf("请输入内结点数目（n<100）:"); scanf("%d",&n); for(i=0;i<n;i++) { printf("请输入第%d个内部部结点的概率值：",i+1);scanf("%f",&P[i]); } for(i=0;i<=n;i++) { printf("请输入第%d个外部部结点的概率值：",i+1);scanf("%f",&Q[i]); }printf("\n结果显示是：\n"); for(i=0;i<=n;i++) { for(j=0;j<=n;j++) { C[i][j]=MAX; W[i][j]=MAX; } } for(i=0;i<=n-1;i++)//置初值 { W[i][i]=Q[i]; R[i][i]=0; C[i][i]=0; W[i][i+1]=Q[i]+Q[i+1]+P[i];//含有一个结点的最优树 C[i][i+1]=W[i][i+1];//由计算规则简化 R[i][i+1]=i+1;//选取根结点 } W[n][n]=Q[n];//继续赋初值 R[n][n]=0; C[n][n]=0; for(m=2;m<=n;m++)//找出m个结点的最优树 { for(i=0;i<=n-m;i++) { j=i+m; W[i][j]=W[i][j-1]+P[j-1]+Q[j]; k=i+1; min=W[i][j]+C[i][k-1]+C[k][j];//给min赋初值k1=k; k++; for(;k<=j;k++)//查找使C最小的K值，并计算C { if(min>(W[i][j]+C[i][k-1]+C[k][j]))//替换 { min=W[i][j]+C[i][k-1]+C[k][j]; k1=k; } }C[i][j]=min; R[i][j]=k1;//记录K }