蚂蚁爬杆问题的java实现

/** 
 * Filename:    com.yangphere.demo.AntWalker.java 
 * Description:  题目描述： 有一根27厘米的细木杆， 在第3厘米、7厘米、11厘米、17厘米、23厘米这五个位置上各有一只蚂蚁。 木杆很细，不能同时通过一只蚂蚁。
 * 开始时，蚂蚁的头朝左还是朝右是任意的，它们只会朝前走或调头，但不会后退。 当任意两只蚂蚁碰头时，两只蚂蚁会同时调头朝反方向走。
 * 假设蚂蚁们每秒钟可以走一厘米的距离。 编写程序，求所有蚂蚁都离开木杆的最小时间和最大时间。
 * Copyright:   Copyright (c)2009 
 * Company:     yangphere 
 * @author:     yangphere 
 * @version:    1.0 
 * Create at:   2009-6-28
 * 
 * Modification History: 
 * Date			Author		Version		Description 
 * ------------------------------------------------------------------ 
 * 2009-6-28	yangphere	1.0			1.0 Version 
 */
package com.yangphere.demo;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Set;

/**
 * 配合逻辑分析给出一种简单的实现方式
 * 其中有个很重要的原则是：当任意两只蚂蚁碰头时，两只蚂蚁会同时调头朝反方向走，其实和假设两只蚂蚁之间可以无障碍穿过时是一样的（忽略蚂蚁自身的长度）。
 * 
 * @author yangphere
 * 
 */
public class AntWalker {

	/**
	 * 细木杆长度
	 */
	private static final int TOTAL_LENGTH = 27;

	/**
	 * 蚂蚁的位置
	 */
	private static final List<Integer> ANT_PER_POSITION = new ArrayList<Integer>();

	/**
	 * 初始化蚂蚁位置
	 */
	static {
		ANT_PER_POSITION.add(3);
		ANT_PER_POSITION.add(7);
		ANT_PER_POSITION.add(11);
		ANT_PER_POSITION.add(17);
		ANT_PER_POSITION.add(23);
	}

	/**
	 * 
	 * @author yangphere 2009-6-28
	 * @param args
	 */
	public static void main(String[] args) {
		if (!check()) {
			System.out.println("参数错误！");
		} else {
			System.out.println("最短时间是：" + getMinTime() + "秒");
			System.out.println("最长时间是：" + getMaxTime() + "秒");
		}
	}

	/**
	 * 获得最长时间 根据那个原则，无需关心蚂蚁碰撞的问题，最长时间就是所有蚂蚁中距细杆一端最长的那只蚂蚁的爬完时间
	 * 
	 * @author yangphere 2009-6-29
	 * @return
	 */
	private static int getMaxTime() {
		// 对蚂蚁位置排序
		Collections.sort(ANT_PER_POSITION);
		// 获得最靠两端的蚂蚁
		int oneSide = ANT_PER_POSITION.get(0);
		int anotherSide = ANT_PER_POSITION.get(ANT_PER_POSITION.size() - 1);

		// 获得一只蚂蚁距两端最长的距离
		int oneMax = (oneSide > (TOTAL_LENGTH - oneSide)) ? oneSide
				: TOTAL_LENGTH - oneSide;
		int antherMax = (anotherSide > (TOTAL_LENGTH - anotherSide)) ? anotherSide
				: TOTAL_LENGTH - anotherSide;

		return oneMax > antherMax ? oneMax : antherMax;
	}

	/**
	 * 获得最短时间 根据那个原则，最短时间就是距细杆中间最近的那只蚂蚁爬完细杆最短的那端所花的时间
	 * 
	 * @author yangphere 2009-6-29
	 * @return
	 */
	private static int getMinTime() {

		// 蚂蚁距一端的距离
		int oneSide = getNearCenterAnt();

		// 蚂蚁距另一段的距离
		int anotherSide = TOTAL_LENGTH - oneSide;

		return oneSide < anotherSide ? oneSide : anotherSide;
	}

	/**
	 * 获得最接近细杆中间的蚂蚁
	 * 
	 * @author yangphere 2009-6-29
	 * @return
	 */
	private static int getNearCenterAnt() {
		// 中间位置
		double center = TOTAL_LENGTH / 2.0;
		// 离中间最近的蚂蚁的位置
		int antNearCenter = 0;

		Map<Integer, Double> map = new HashMap<Integer, Double>();

		double antNearPosition = center - ANT_PER_POSITION.get(0);
		for (Integer ant : ANT_PER_POSITION) {
			antNearPosition = antNearPosition < Math.abs(center - ant) ? antNearPosition
					: Math.abs(center - ant);

			map.put(ant, Math.abs(center - ant));
		}

		Set<Integer> set = map.keySet();
		for (Iterator iterator = set.iterator(); iterator.hasNext();) {
			Integer key = (Integer) iterator.next();
			if (antNearPosition == map.get(key)) {
				antNearCenter = key;
				break;
			}
		}

		return antNearCenter;
	}

	/**
	 * 检查参数的正确性
	 * 
	 * @author yangphere 2009-6-29
	 * @return
	 */
	private static boolean check() {
		if (TOTAL_LENGTH <= 0) {
			return false;
		} else if (ANT_PER_POSITION.size() <= 0) {
			return false;
		}

		// 站在杆外
		for (Integer ant : ANT_PER_POSITION) {

			if (ant <= 0) {
				return false;
			} else if (ant > TOTAL_LENGTH) {
				return false;
			}
		}

		return true;
	}

}