学步园

致歉：之前贴的代码有bug。

题目描述：

   有一根27厘米的细木杆，在第3厘米、7厘米、11厘米、17厘米、23厘米这五个位置上各有一只蚂蚁。木杆很细，不能同时通过一只蚂蚁。开始时，蚂蚁的头朝左还是朝右是任意的，它们只会朝前走或调头，但不会后退。当任意两只蚂蚁碰头时，两只蚂蚁会同时调头朝反方向走。假设蚂蚁们每秒钟可以走一厘米的距离。编写程序，求所有蚂蚁都离开木杆的最小时间和最大时间。

当然，这道题目可以不用编程做，注意到“两只蚂蚁会同时调头朝反方向走”，也就是一秒钟两只蚂蚁完成调头和反方向爬行两个动作，可以理解为蚂蚁穿越了对方毫无影响地原方向前进（或者将两只蚂蚁互换来看待），那么

最大时间就取决于两头的蚂蚁的方向：

如果23厘米处的蚂蚁向原点爬行离开木杆，需用时23秒；如果3厘米处的蚂蚁向27厘米处爬行离开木杆，需用27-3=24秒，所以最大用时为24秒。

最小时间就取决于中间蚂蚁朝两头跑所用时间：

如果处于小于等于11厘米处的蚂蚁向原点爬行离开木杆，需用时11秒；如果大于11厘米处的蚂蚁向27厘米处爬行离开木杆，需用27-17=10秒，所以都爬出最小用时为11秒。

但如果面试官要求编写程序，那就老实编程吧，以下是一个Java编写的程序，以及编程思路。

思路与建模

• 将木杆看成0至27的坐标, 5只蚂蚁分别在3, 7, 11, 17, 23的位置
• 创建enum Direction{ Left, Right}
• 创建Ant类, 蚂蚁可以爬行(walk), 掉头(shift),  以及记录是否已经爬出的标记.
• 创建Controller类, 给定蚂蚁的初始方向, Controller类可以计算出在这种初始方向下蚂蚁全部爬出需要的时间.
• 创建Simulator类, 它给出蚂蚁初始方向的所有组合, 并使用Controller执行得到所有时间, 选择最大值和最小值.

蚂蚁的初始方向不是向左就是向右，可以用二进制表示。5只蚂蚁, 2^5=32个组合，所以用0-31之间的整数的二进制刚好可以表示蚂蚁的初始方向。比如24的二进制为11000，分别与二进制数00001, 00010, 00100, 01000, 10000相与，结果不为零的蚂蚁方向向右，可得第四、五只蚂蚁方向向右。

实现

在Model包内，包含Ant类

package cn.dfeng.model;
/**
 * 蚂蚁
 * @author dfeng
 *
 */
public class Ant {
	private int position; //蚂蚁的位置
	Direction direction;  //爬行方向
	private boolean out = false; //是否已经爬出

	public Ant(int p, Direction dir){
		this.position = p;
		this.direction = dir;
	}

	/**
	 * 蚂蚁行走
	 */
	public void walk(){
		if(direction == Direction.Right){
			position++;
		}else{
			position--;
		}
	}
	
	/**
	 * 蚂蚁调头
	 */
	public void shift(){
		this.direction = (this.direction == Direction.Left) ? Direction.Right : Direction.Left;
	}
	
	public int getPosition() {
		return this.position;
	}
	
	public Direction getDirection() {
		return this.direction;
	}
	
	public boolean isOut() {
		return out;
	}

	public void setOut(boolean out) {
		this.out = out;
	}
}

在Controller包内

package cn.dfeng.control;

import java.util.ArrayList;
import java.util.Arrays;

import cn.dfeng.model.Ant;
import cn.dfeng.model.Direction;

/**
 * 控制器
 * @author dfeng
 *
 */
public class Controller {

	public static final int MAX_LENGTH = 27; 
	
	/*
	 * 蚂蚁初始位置
	 */
	private static final int[] POSITIONS = {3, 7, 11, 17, 23};
	
	private int online_number = 5; //还在木杆上的蚂蚁数，初始为5
	
    private long timer = 0; //计时器
    
    ArrayList<Ant> ants;
    
    /**
     * 指定蚂蚁初始方向, 创建控制器
     * @param directions 蚂蚁初始方向
     */
    public Controller(Direction[] directions){
    	ants = new ArrayList<Ant>();
    	/*
         * 创建初始蚂蚁队列
         */
    	for( int i = 0; i < POSITIONS.length; i++ ){
    		Ant ant = new Ant(POSITIONS[i], directions[i]);
    		ants.add(ant);
    	}
    }
    
    public long start(){
    	/*
    	 * 在木杆上的蚂蚁数为0即全部爬出
    	 */
    	while(online_number > 0){
    		shiftAnts();
    		moveAnts();
    		timer++;
    		analyzeAntStatus();
    	}
    	return timer;
    }
    
    //移动还在杆上的蚂蚁
    private void moveAnts() {
    	for (Ant ant : ants) {
    		if (!ant.isOut())
    			ant.walk();
    	}
    }
    
    //分析蚂蚁的状态
    private void analyzeAntStatus() {
    	for (Ant ant : ants) {
    		if (ant.isOut()) {
    			continue;
    		}
    		if ((ant.getPosition() == MAX_LENGTH) ||
    				(ant.getPosition() == 0)) {
    			ant.setOut(true);
    			online_number--;
    			System.out.println("Ant " + ants.indexOf(ant) + " is out at " + timer);
    		}
    	}
    }
    
    //移动前检查杆上的蚂蚁是否需要调头
    //使用了检查一串字符串中是否有重复字符的算法，空间换时间
    private void shiftAnts(){
    	short[] flags = new short[28];
    	Arrays.fill(flags, (short)-1);
    	
    	for (int i = 0; i < ants.size(); i++) {
    		Ant ant = ants.get(i);
    		if (ant.isOut()) {
    			continue;
    		}
    		short result = flags[ant.getPosition()];
			if(result == -1) {
				flags[ant.getPosition()] = (short)i; //如果还没有蚂蚁在这个位置，就记下这只蚂蚁的序号。
			} else { //如果已经有了，两只蚂蚁调头
				ant.shift();
				ants.get(result).shift();
				System.out.println("Ant " + i + " and ant " + result + " shift at " + timer);
			}
    	}
    }
}

在Root包内

package cn.dfeng;

import cn.dfeng.control.Controller;
import cn.dfeng.model.Direction;

public class Simulator {

	private static final int[] DIRECTIONS = {0x01, 0x02, 0x06, 0x08, 0x10}; //它们的二进制分别是00001, 00010, 00100, 01000, 10000，你知道为什么使用它们了吧
	
	private long longest = 0;
	private long shortest = Long.MAX_VALUE;
	
	/**
	 * 开始模拟
	 */
	public void simulate() {
		for (int i = 0; i < 32; i++) {
			Controller con = new Controller(this.getDirections(i));
			long time = con.start();
			if( time > longest ){
				longest = time;
			}
			if( time < shortest ){
				shortest = time;
			}
			System.out.println( " Time: " + time );
		}
	}

	/*
	 * 创建蚂蚁初始位置
	 */
	private Direction[] getDirections(int seed) {
		Direction[] dirs = new Direction[5];
		for(int i = 0; i < DIRECTIONS.length; i++) {
			if((DIRECTIONS[i] & seed) == 0) {
				dirs[i] = Direction.Left;
			} else {
				dirs[i] = Direction.Right;
			}
		}
		
		System.out.println( "Round: " + Integer.toBinaryString(seed));

		return dirs;
	}

	/**
	 * 打印结果
	 */
	public void getResult() {
		System.out.printf("Longest time %d.\nShortest Time: %d", longest,
				shortest);
	}

	public static void main( String[] args ){
		Simulator sim = new Simulator();
		
		sim.simulate();
		
		sim.getResult();
	}
}

评析

蚂蚁的初始方向不是向左就是向右，可以用二进制表示。5只蚂蚁, 2^5=32个组合，所以用0-31之间的整数的二进制刚好可以表示蚂蚁的初始方向。比如24的二进制为11000，分别与二进制数00001, 00010, 00100, 01000, 10000相与，结果不为零的蚂蚁方向向右，可得第四、五只蚂蚁方向向右。有了初始方向和初始位置, 就可以使用Controller模拟并比较了.

用最好的算法判断蚂蚁是否应该调头也是一个需要思考的地方，它与判断一个字符串中是否有重复字符的面试题颇为相似，可以使用空间换时间的思路快速解决。