JAVA写的邮局选址问题程序源码

研究生课程算法设计与分析作业的答案，包括完整源码和测试数据，下载直接可以使用

import java.io.BufferedInputStream;
import java.io.FileInputStream;
import java.io.FileNotFoundException;

import java.io.FileWriter;
import java.io.IOException;
import java.util.Scanner;
public class postoffice {
	int number;//该数据文件中坐标点个数
	long  result;//最终结果
	long temp;//用来保存中间变量

	int bigx;//最西
	int bigy;//最北
	int smallx;//最东
	int smally;//最南
	
	
	int a[];//数组用来存储东西坐标值
	int b[];//数组用来存储南北坐标值
	/**
	 * 该方法完成输入输出并调用算法实现方法
	 */
	public void dojob（）{
		
		try {
			FileWriter fw = new FileWriter（“output.txt“）;
			
			for（int m=0;m<11;m++）{
			result =Long.MAX_VALUE;
			Scanner in;
			//从文件中读取数据初始化坐标数组（一共11组测试数据）
			if（m==10）
				in = new Scanner（new BufferedInputStream（new FileInputStream（“input_assign01_“+ m +“.dat“）））;
			else
				in = new Scanner（new BufferedInputStream（new FileInputStream（“input_assign01_0“+ m +“.dat“）））;
			
			number = in.nextInt（）;
			a=new int[number];
			b=new int[number];
			for（int i=0;i			{
				a[i]=in.nextInt（）;
				b[i]=in.nextInt（）;
			}
			//遍历数组得到东西南北坐标极值
			smallx =a[0]; bigx=a[0];
			smally =b[0]; bigy =b[0];
			for（int i=1;i			{	
				if（a[i]				else if（a[i]>bigx） bigx =a[i];
				if（b[i]				else if（b[i]>bigy） bigy =b[i];
				
			}
			//调用算法实现方法得到最佳点邮局与所有居民点距离之和
			result = findbest（a smallx bigx） + findbest（b smally bigy）;
			//将结果输出到文件中
			fw.write（result+““）;
			fw.write（“\r\n“）;
			fw.flush（）;
			//将结果输出到屏幕
			System.out.println（m + “:“ + result）;
			
			
			}
		} catch （FileNotFoundException e） {
			// TODO Auto-generated catch block
			e.printStackTrace（）;
		} catch （NumberFormatException e） {
			// TODO Auto-generated catch block
			e.printStackTrace（）;
		} catch （IOException e） {
			// TODO Auto-generated catch block
			e.printStackTrace（）;
		}
		
	}
/**
 * 该方法实现算法
 * @param a
 * @param small
 * @param big
 * @return
 */
	public long findbest（int a[]int smallint big）{

		long number1number2number3number4number5;
		if（big-small<4）//当区间内坐标很少时直接得到最佳坐标
			return least（asmallbig）;
		else{
			//计算区间五个端点的评价值
			number1 =length（asmall）;
			number2 =length（asmall + （big-small）/3*1）;
			number3 =length（asmall + （big-small）/3*2）;
			number4 =length（asmall + （big-small）/3*3）;
			number5 =length（abig）;
			//根据五个端点评价值的大小淘汰一些区间，得到一个较小的区间继续调用算法
			if（number1<=number2） return findbest（asmallsmall + （big-small）/3*1）;
			else if（number1>=number2&&number2<=number3） return findbest（a small small + （big-small）/3*2）;
			else if（number2>=number3&&number3<=number4） return findbest（asmall + （big-small）/3*1small + （big-small）/3*3）;
			else if（number3>=number4&&number4<=number5） return findbest（a small + （big-small）/3*2 big）;
		    else if（number4>=number5） return findbest（a small + （big-small）/3*3big）;
		    else {System.out.println（“数据异常！“）; return 0;}
			
		}
		
	}
	/*
	 * 该方法为辅助方法，用来计算某个坐标值与其他坐标值距离之和
	 */
	private long leng

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件         29  2011-03-29 21:21  input_assign01_00.dat

     文件         21  2011-03-06 14:58  input_assign01_01.dat

     文件         40  2011-03-06 14:58  input_assign01_02.dat

     文件        101  2011-03-06 14:58  input_assign01_03.dat

     文件        226  2011-03-06 14:58  input_assign01_04.dat

     文件        644  2011-03-06 14:58  input_assign01_05.dat

     文件       1282  2011-03-06 14:58  input_assign01_06.dat

     文件       5811  2011-03-06 14:58  input_assign01_07.dat

     文件      21798  2011-03-06 14:58  input_assign01_08.dat

     文件      93790  2011-03-06 14:58  input_assign01_09.dat

     文件     117779  2011-03-06 14:58  input_assign01_10.dat

     文件         72  2011-03-07 16:00  output.txt

     文件       3763  2011-03-07 16:17  postoffice.class

     文件       4179  2011-03-07 16:17  postoffice.java

----------- ---------  ---------- -----  ----

               249535                    14