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

看到很多人发布了他们的解法, 我觉得都过于复杂并不甚清晰, 以下是我的思路和实现.

1. 思路与建模

*将木杆看成0至27的坐标, 5只蚂蚁分别在3, 7, 11, 17, 23的位置

*创建enum Directory{ Left, Right}

*创建Ant类, 蚂蚁可以爬行(walk), 掉头(shift),  并且如果爬出能把自己从蚂蚁队列中移出去.

*创建Controller类, 给定蚂蚁的初始方向, Controller类可以计算出在这种初始方向下蚂蚁全部爬出需要的时间.

*创建Simulator类, 它给出蚂蚁初始方向的所有组合, 并使用Controller执行得到所有时间, 选择最大值和最小值.

蚂蚁的初始方向不是向左就是向右, 可以用二进制表示. 5只蚂蚁, 2^5=32个组合.

所以, 用0-31的二进制刚好可以表示蚂蚁的初始方向. 使用: Integer.toBinaryString(i), 不够五位的话左填充0至五位, 即可得到的如01010这样的二进制串, 比如0表示向左, 1表示向右, 即可得到蚂蚁的初始方向.

 

2. 实现

在Model包内:

 view plaincopy to clipboardprint?
package cn.dfeng.model;  
 
public enum Direction {  
 
    Left, Right  
} 
package cn.dfeng.model;

public enum Direction {

 Left, Right
}

view plaincopy to clipboardprint?
package cn.dfeng.model;  
 
import java.util.ArrayList;  
 
public class Ant {  
 
    public static final int LENGTH = 27;   
    private int position;  
    Direction direction;  
 
    /* 
     * 在木杆上的蚂蚁队列 
     */ 
    ArrayList<Ant> list;  
      
    public Ant( int p, Direction dir, ArrayList<Ant> list ){  
        this.position = p;  
        this.direction = dir;  
        this.list = list;  
    }  
 
    /** 
     * 蚂蚁行走 
     */ 
    public void walk(){  
          
        if( direction == Direction.Right ){  
            position++;  
        }else{  
            position--;  
        }  
          
        //如果大于最大长度获小于0即视为爬出木杆  
        if( position >= LENGTH || position <= 0 ){  
            list.remove( this );  
        }  
    }  
      
    /** 
     * 蚂蚁调头, 行走一秒后查看自己是不是需要调头 
     */ 
    public void shift(){  
        int index = list.indexOf( this );  
        if( index == 0 && list.size() > 1 ){  
            if( this.position == list.get(1).position ){  
                doShift();  
            }  
        }else if( index == list.size()-1 && index > 0 ){  
            if( this.position == list.get(index-1).position ){  
                doShift();  
            }  
        }else if( index > 0 && index < list.size()-2){  
            if( this.position == list.get(index+1).position || this.position == list.get(index-1).position){  
                doShift();  
            }  
        }  
    }  
      
    private void doShift(){  
        this.direction = (this.direction == Direction.Left) ? Direction.Right : Direction.Left;  
    }  
} 
package cn.dfeng.model;

import java.util.ArrayList;

public class Ant {

 public static final int LENGTH = 27;
 private int position;
 Direction direction;

 /*
  * 在木杆上的蚂蚁队列
  */
 ArrayList<Ant> list;
 
 public Ant( int p, Direction dir, ArrayList<Ant> list ){
  this.position = p;
  this.direction = dir;
  this.list = list;
 }

 /**
  * 蚂蚁行走
  */
 public void walk(){
  
  if( direction == Direction.Right ){
   position++;
  }else{
   position--;
  }
  
  //如果大于最大长度获小于0即视为爬出木杆
  if( position >= LENGTH || position <= 0 ){
   list.remove( this );
  }
 }
 
 /**
  * 蚂蚁调头, 行走一秒后查看自己是不是需要调头
  */
 public void shift(){
  int index = list.indexOf( this );
  if( index == 0 && list.size() > 1 ){
   if( this.position == list.get(1).position ){
    doShift();
   }
  }else if( index == list.size()-1 && index > 0 ){
   if( this.position == list.get(index-1).position ){
    doShift();
   }
  }else if( index > 0 && index < list.size()-2){
   if( this.position == list.get(index+1).position || this.position == list.get(index-1).position){
    doShift();
   }
  }
 }
 
 private void doShift(){
  this.direction = (this.direction == Direction.Left) ? Direction.Right : Direction.Left;
 }
}
 

在Controller包内

view plaincopy to clipboardprint?
package cn.dfeng.control;  
 
import java.util.ArrayList;  
 
import cn.dfeng.model.Ant;  
import cn.dfeng.model.Direction;  
 
public class Controller {  
 
    /* 
     * 蚂蚁初始位置 
     */ 
    private int[] positions = { 3, 7, 11, 17, 23 };  
      
    /* 
     *蚂蚁初始方向 
     */ 
    private Direction[] dir;  
      
    private long timer = 0;  
      
    /** 
     * 指定蚂蚁初始方向, 创建控制器 
     * @param dir 
     */ 
    public Controller( Direction[] dir ){  
        this.dir = dir;  
    }  
      
    public long start(){  
        ArrayList<Ant> list = this.init();  
          
        /* 
         * 蚂蚁队列为空即全部爬出 
         */ 
        while( list.size() != 0 ){  
            //爬行  
            for( int i = 0; i < list.size(); i++ ){  
                Ant ant = list.get(i);  
                ant.walk();  
            }  
            //掉头  
            for( int i = 0; i < list.size(); i++ ){  
                Ant ant = list.get(i);  
                ant.shift();  
            }  
              
            timer++;  
        }  
        return timer;  
    }  
      
    /* 
     * 创建初始蚂蚁队列 
     */ 
    private ArrayList<Ant> init(){  
        ArrayList<Ant> list = new ArrayList<Ant>();  
        for( int i = 0; i < positions.length; i++ ){  
            Ant ant = new Ant( positions[i], dir[i], list );  
            list.add( ant );  
        }  
        return list;  
    }  
} 
package cn.dfeng.control;

import java.util.ArrayList;

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

public class Controller {

 /*
  * 蚂蚁初始位置
  */
 private int[] positions = { 3, 7, 11, 17, 23 };
 
 /*
  *蚂蚁初始方向
  */
 private Direction[] dir;
 
    private long timer = 0;
   
    /**
     * 指定蚂蚁初始方向, 创建控制器
     * @param dir
     */
    public Controller( Direction[] dir ){
     this.dir = dir;
    }
   
    public long start(){
     ArrayList<Ant> list = this.init();
     
     /*
      * 蚂蚁队列为空即全部爬出
      */
     while( list.size() != 0 ){
      //爬行
      for( int i = 0; i < list.size(); i++ ){
       Ant ant = list.get(i);
       ant.walk();
      }
      //掉头
      for( int i = 0; i < list.size(); i++ ){
       Ant ant = list.get(i);
       ant.shift();
      }
      
      timer++;
     }
     return timer;
    }
   
    /*
     * 创建初始蚂蚁队列
     */
    private ArrayList<Ant> init(){
     ArrayList<Ant> list = new ArrayList<Ant>();
     for( int i = 0; i < positions.length; i++ ){
      Ant ant = new Ant( positions[i], dir[i], list );
      list.add( ant );
     }
     return list;
    }
}
 

在Root包内

view plaincopy to clipboardprint?
package cn.dfeng;  
 
import cn.dfeng.control.Controller;  
import cn.dfeng.model.Direction;  
 
public class Simulator {  
 
    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 i) {  
        Direction[] dirs = new Direction[5];  
        String binString = Integer.toBinaryString(i);  
        StringBuilder sb = new StringBuilder();  
        int lack = 5 - binString.length();  
          
        for( int c = 0; c < lack; c++ ){  
            sb.append('0');  
        }  
        sb.append( binString );  
        binString = sb.toString();  
        int p = 0;  
        while( p < binString.length() ) {  
              
            if (binString.charAt(p) == '0') {  
                dirs[p] = Direction.Left;  
            } else {  
                dirs[p] = Direction.Right;  
            }  
            p++;  
        }  
          
        System.out.print( "Round: " + binString );  
 
        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();  
    }  
} 
package cn.dfeng;

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

public class Simulator {

 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 i) {
  Direction[] dirs = new Direction[5];
  String binString = Integer.toBinaryString(i);
  StringBuilder sb = new StringBuilder();
  int lack = 5 - binString.length();
  
  for( int c = 0; c < lack; c++ ){
   sb.append('0');
  }
  sb.append( binString );
  binString = sb.toString();
  int p = 0;
  while( p < binString.length() ) {
   
   if (binString.charAt(p) == '0') {
    dirs[p] = Direction.Left;
   } else {
    dirs[p] = Direction.Right;
   }
   p++;
  }
  
  System.out.print( "Round: " + binString );

  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();
 }
}
 

3. 评析

蚂蚁的初始方向不是向左就是向右, 可以用二进制表示. 5只蚂蚁, 2^5=32个组合.

所以, 用0-31的二进制刚好可以表示蚂蚁的初始方向. 使用: Integer.toBinaryString(i), 不够五位的话左填充0至五位, 即可得到的如01010这样的二进制串, 比如0表示向左, 1表示向右, 即可得到蚂蚁的初始方向.

有了初始方向和初始位置, 就可以使用Controller模拟并比较了.