算法实验报告实验输油管道问题.docx
- 文档编号:2152943
- 上传时间:2023-05-02
- 格式:DOCX
- 页数:5
- 大小:71.97KB
算法实验报告实验输油管道问题.docx
《算法实验报告实验输油管道问题.docx》由会员分享,可在线阅读,更多相关《算法实验报告实验输油管道问题.docx(5页珍藏版)》请在冰点文库上搜索。
算法实验报告
算法分析与设计
实验报告
实验名称:
输油管道问题
实验日期:
2011/03/13
学生姓名:
学生学号:
一、实验目的
某石油公司计划建造一条由东向西的主输油管道。
该管道要穿过一个有n口油井的油田。
从每口油井都要有一条输油管道沿最短路经(或南或北)与主管道相连。
如果给定n口油井的位置,即它们的x坐标(东西向)和y坐标(南北向),应如何确定主管道的最优位置,即使各油井到主管道之间的输油管道长度总和最小的位置?
证明可在线性时间内确定主管道的最优位置。
给定n口油井的位置,编程计算各油井到主管道之间的输油管道最小长度总和。
二、实验环境
Windows7+VisualStudio2010
三、实验内容
1.设计思路
因为输油管道是东西走向,每口油井到管道的最短路径都是垂直于管道的。
所以,该问题实际是求得所有油井的Y坐标的中位数。
利用线性时间选择算法找到坐标中位数。
再求出最小长度总和。
2.相关模块
#include
#include
#include
#include
#include
usingnamespacestd;
voidwrite(char*filename,intlength);
intRandomizedSelect(int*a,intp,intr,intk);
intRandomizedPartition(int*a,intp,intr);
intPartition(int*a,intp,intr);
voidswap(int&,int&);
intRandom(intp,intr);
intlengthOfPipeline(int*a,intsize,intlength);
intmain()
{
intsize=0;
char*inFileName="H:
\\C++\\Algorithms\\in.txt";
char*outFileName="H:
\\C++\\Algorithms\\out.txt";
ifstreaminput(inFileName,ios:
:
in);
//从文件读取数据
input>>size;
int*a=newint[size];
intreadcount=1,i=0;
while(readcount<=(size*2))
{
inttemp=0;
input>>temp;
if(readcount%2==0)
a[i++]=temp;
readcount++;
}
input.close();
//获取数据中位数y,即为通道Y坐标
intlength=RandomizedSelect(a,0,size-1,(size+1)/2);
//将总的管道长度写入out.txt文件中
write(outFileName,lengthOfPipeline(a,size,length));
system("pause");
return0;
}
//将最后结果写入文件中
voidwrite(char*filename,intlength)
{
ofstreamoutput;
output.open(filename,ofstream:
:
out);
output< output.close(); } //随机获取p到r中的数 intRandom(intp,intr) { returnp+rand()%(r-p+1); } //划分 intPartition(int*a,intp,intr) { inti=p,j=r+1; intx=a[p]; //将 //将>x的元素交换到左边区域 while(true) { while(a[++i] while(a[--j]>x); if(i>=j)break; swap(a[i],a[j]); } a[p]=a[j]; a[j]=x; returnj; } //产生随机划分优化算法 intRandomizedPartition(int*a,intp,intr) { inti=Random(p,r); swap(a[i],a[p]); returnPartition(a,p,r); } //利用随机划分来找到中位数 intRandomizedSelect(int*a,intp,intr,intk) { if(p>=r)returna[p]; inti=RandomizedPartition(a,p,r), j=i-p+1; if(k==j)returna[i]; if(k elsereturnRandomizedSelect(a,i+1,r,k-j); } //交换两个数据 voidswap(int&n,int&m) { inttemp=n; n=m; m=temp; } //计算输油管道最小长度总和 intlengthOfPipeline(int*a,intsize,intlength) { intdistance=0; for(inti=0;i distance+=abs(a[i]-length); returndistance; } 四、实验结果分析及结论 算法RandomizedSelect可以在O(n)平均时间内找出n个坐标中的中位数。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 算法 实验 报告 输油管道 问题