《实验一 输油管道问题》由会员分享，可在线阅读，更多相关《实验一 输油管道问题（4页珍藏版）》请在金锄头文库上搜索。
1、实验一 输油管道问题05计算机 13 班 叶迪平 X05620321实验目的：熟练掌握分治法的相关概念和其递归表达式。实验要求：能用分治法解决现实生活中一些简单的问题。内容：某石油公司计划建造一条由东向西的主输油管道。该管道要穿过一个有n 口油井的油田。从每口油井都要有一条输油管道沿最短路经(或南或北)与主管道 相连。如果给定n 口油井的位置，即它们的x坐标(东西向)和y坐标(南北向)， 应如何确定主管道的最优位置,即使各油井到主管道之间的输油管道长度总和最 小的位置?证明可在线性时间内确定主管道的最优位置给定n 口油井的位置，编程计算各油井到主管道之间的输油管道最小长度总和。 由文件inpu
2、t.txt提供输入数据。文件的第1行是油井数n, lWnWIOOOO。 接下来n行是油井的位置，每行2个整数x和y, -lOOOOWx, yW 10000。 程序运行结束时,将计算结果输出到文件 output.txt 中。文件的第 1 行中的 数是油井到主管道之间的输油管道最小长度总和问题分析：由题意易得本题x对结果无影响，不必考虑。假设铺油管道y坐标为 t,则结果为所有lyi-tI的和，所以问题就在于求t,而中位数这点就是最小代价点。 问题转化为求中位数,算法采用平均情况下的线性时间选择算法。原代码：#include#include #include int partition(int a,
3、int p,int r) 快速排序的划分函数int i，j，x，temp;i=p;j=r+1;x=ap;while (1)while (a+ix);if (i=j)break;temp=ai;ai=aj;aj=temp;ap=aj;aj=x;return j;int randpartition(int a,int p,int r) 随机划分函数int i;i=p+rand()%(r-p+l); 生产随机数int temp; temp=ai; ai=ap; ap=temp;return partition(a,p,r); 调用划分函数int Median (int a,int p,int r,i
4、nt k)查找中位数函数f (p=r)递归结束，找到中位数return ap;int i,j;i=randpartition(a,p,r); 戈 U分 j=i-p+l;f (k=j)递归结束，找到中位数 return ai;if (kj)return Median (a,p,i-1,k);递归调用，在前面部分查找中位数elsereturn Median (a,i+1,r,k-j);递归调用，在后面部分查找中位数void main()int i,n,mid,min=0,arrx20,arry20;FILE *fp,*fp1,*fp2; printf(input n,(x,y)n); scanf(
5、%d,&n); for(i=0;in;i+)scanf(%d,&arrxi); scanf(%d,&arryi);fp=fopen(input.txt,w); fprintf(fp,%dn,n);for(i=0;in;i+)fprintf(fp,%d %dn,arrxi,arryi);fp1=fopen(input.txt,r);fprintf(fp1,%dn,n);for(i=0;in;i+)fprintf(fp1,%d %dn,arrxi,arryi);mid= Median (arry,0,n-1,(n+1)/2); for(i=0;in;i+)min+=fabs(arryi-mid);fp2=fopen(output.txt,w);fprintf(fp2,%dn,min); printf(%dn,min);实验心得： 用分治法处理输油管道问题，降低了算法复杂度，通过这个问题是我更深入的了解了快速排 序算法在实际问题中的应用，c语言中文件这个陌生的知识点也在本实验中复习并进行了运 用，觉得很有收获。
