算法实验报告实验21输油管道问题.docx

算法分析与设计

实验报告

实验名称： 输油管道问题
实验日期： 2011/03/１３
学生姓名：
学生学号：

一、实验目的
某石油公司计划建造一条由东向西的主输油管道。该管道要穿过一个有n口油井的油田。从每口油井都要有一条输油管道沿最短路经(或南或北)与主管道相连。如果给定n口油井的位置,即它们的x坐标（东西向）和y坐标（南北向）,应如何确定主管道的最优位置,即使各油井到主管道之间的输油管道长度总和最小的位置?证明可在线性时间内确定主管道的最优位置。
　　给定n口油井的位置,编程计算各油井到主管道之间的输油管道最小长度总和。
二、实验环境
Windows7 + Visual Studio 2010
三、实验内容
1. 设计思路
因为输油管道是东西走向，每口油井到管道的最短路径都是垂直于管道的。所以，该问题实际是求得所有油井的Ｙ坐标的中位数。利用线性时间选择算法找到坐标中位数。再求出最小长度总和。
2. 相关模块
#include<iostream>
#include<fstream>
#include<string>
#include<cstdlib>
#include<cmath>
using namespace std;

void write(char* filename,int length);
int RandomizedSelect(int *a,int p,int r,int k);
int RandomizedPartition(int *a,int p,int r);
int Partition(int *a,int p,int r);
void swap(int&,int&);
int Random(int p,int r);
int lengthOfPipeline(int *a,int size,int length);

int main()
{
int size=0;
char* inFileName = "H:\\C++\\Algorithms\\in.txt";
char* outFileName = "H:\\C++\\Algorithms\\out.txt";
ifstream input(inFileName,ios::in);

//从文件读取数据
input >> size;
int *a = new int[size];
int readcount=1,i=0;
while(readcount<=(size*2))
{
int temp = 0;
input >> temp;
if(readcount%2==0)
a[i++]=temp;
readcount++;
}
input.close();

//获取数据中位数y，即为通道Y坐标
int length = RandomizedSelect(a,0,size-1,(size+1)/2);

//将总的管道长度写入out.txt文件中
write(outFileName,lengthOfPipeline(a,size,length));
system("pause");
return 0;
}

//将最后结果写入文件中
void write(char* filename,int length)
{
ofstream output;
output.open(filename,ofstream::out);
output<<length;
output.close();
}

//随机获取p到r中的数
int Random(int p,int r)
{
return p + rand()%(r - p + 1);
}

//划分
int Partition(int *a,int p,int r)
{
int i = p, j = r + 1;
int x = a[p];

//将<x的元素交换到左边区域
//将>x的元素交换到左边区域
while(true)
{
while(a[++i]<x&&i<r);
while(a[--j]>x);
if(i>=j)break;
swap(a[i],a[j]);
}
a[p]=a[j];
a[j]=x;
return j;
}

//产生随机划分优化算法
int RandomizedPartition(int *a,int p,int r)
{
int i= Random(p,r);
swap(a[i],a[p]);
return Partition(a,p,r);
}

//利用随机划分来找到中位数
int RandomizedSelect(int *a,int p,int r,int k)
{
if(p>=r)return a[p];
int i = RandomizedPartition(a,p,r),
j = i-p+1;
if (k == j) return a[i];
if(k<j) return RandomizedSelect(a,p,i-1,k);
else return RandomizedSelect(a,i+1,r,k-j);
}

//交换两个数据
void swap(int &n,int &m)
{
int temp = n;
n = m;
m = temp;
}

//计算输油管道最小长度总和
int lengthOfPipeline(int *a,int size,int length)
{
int distance = 0;
for(int i=0; i<size; ++i)
distance += abs(a[i] - length);
return distance;
}

四、实验结果分析及结论

算法RandomizedSelect 可以在O（n）平均时间内找出n个坐标中的中位数。