《输油管问题》.docVIP

北京科技大学 计算机与通信工程学院 实 验 报 告 实验名称： 输油管问题 学生姓名： 朱帅 专 业： 计算机科学与技术 班 级： 计1203 学 号： 指导教师： 罗熊 实验成绩： 实验地点： 机电楼303 实验时间： 2015年4月15日 实验目的与实验要求 ? 某石油公司计划建造一条由东向西的主输油管道。该管道要穿过一个 有n口油井的油田。从每口油井都要有一条输油管道沿最短路径（或 南或北）与主管道相连。如果给定n口油井的位置，即它们的x坐标 （东西向）和y坐标（南北向），应如何确定主管道的最优位置，即 使各油井到主管道之间的输油管道长度总和最小的位置？证明可在线 性时间内确定主管道的最优位置。给定n口油井的位置，编程计算各 油井到主管道之间的输油管道最小长度总和。 二、实验设备（环境）及要求 J avaSDK、eclipse 三、实验内容与步骤 1、实验1 （1）实验内容 1、根据题意找出数学模型 2、编写程序实现内容 3、检查结果，讨论分析 （2）主要步骤 1、数学模型的建立 此实验的核心不在于x坐标，而是y坐标。当输油管的位置在所有井口位置之上或之下时（y坐标），总的长度为所有油井到输油管距离之和 。而当井口位置在输油管两边分配均匀时（y坐标），所得长度为最小长度之和。 2、 编程实现 代码：package shuyouguan; import java.util.Scanner; public class Shuyouguan { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); /* 输入井口个数 */ System.out.println(请输入井口个数:); int a = scanner.nextInt(); /* 输入井口位置 */ double xzuobiao[]; xzuobiao=new double[a]; System.out.println(请输入各井口x坐标:); for (int i = 0; i a; i++) { xzuobiao[i] = scanner.nextDouble(); } double[] jingkou; jingkou = new double[a]; System.out.println(请输入各井口y坐标:); for (int i = 0; i a; i++) { jingkou[i] = scanner.nextDouble(); } scanner.close(); /* 井口位置排序 */ for (int s = 1; s a; s++) { for (int i = a - 1; i = s; i--) { if (jingkou[i] = jingkou[i - 1]) { double z; z = jingkou[i - 1]; jingkou[i - 1] = jingkou[i]; jingkou[i] = z; } } } /* 找中间位置的井口 */ if (a % 2 == 0) { double sum = 0; for (int i = 1; i = (a / 2); i++) { sum = sum + (jingkou[(a / 2) + i - 1] - jingkou[(a / 2) - i]); } System.out.println(输油管位置为:y坐标为 + jingkou[(a / 2) - 1] + 与y坐标为 + jingkou[a / 2] + 的井口之间); System.out.println(最小长度总和为: + sum); } else { double sum = 0; for (int i = 1; i = (((a + 1) / 2) - 1); i++) { sum = sum + (jingkou[((a + 1) / 2) + i - 1] - jingkou[((a +