算法实验报告--实验2-1输油管道问题(共6页).docx

精选优质文档-倾情为你奉上算法分析与设计实验报告实验名称： 输油管道问题 实验日期： 2011/03/ 学生姓名： 学生学号： 一、实验目的某石油公司计划建造一条由东向西的主输油管道。该管道要穿过一个有n口油井的油田。从每口油井都要有一条输油管道沿最短路经(或南或北)与主管道相连。如果给定n口油井的位置,即它们的x坐标（东西向）和y坐标（南北向）,应如何确定主管道的最优位置,即使各油井到主管道之间的输油管道长度总和最小的位置?证明可在线性时间内确定主管道的最优位置。给定n口油井的位置,编程计算各油井到主管道之间的输油管道最小长度总和。二、实验环境 Windows7 + Visual Studio 2010三、实验内容1. 设计思路因为输油管道是东西走向，每口油井到管道的最短路径都是垂直于管道的。所以，该问题实际是求得所有油井的坐标的中位数。利用线性时间选择算法找到坐标中位数。再求出