5只蚂蚁走木棍

1、5只蚂蚁走木棍问题优美的 Java非递归解法题目描述：有一根27厘米的细木杆，在第 3厘米、7厘米、11厘米、17厘米、23厘米这五个位 置上各有一只蚂蚁。木杆很细，不能同时通过一只蚂蚁。开始时，蚂蚁的头朝左还是朝右是 任意的，它们只会朝前走或调头，但不会后退。当任意两只蚂蚁碰头时，两只蚂蚁会同时调 头朝反方向走。假设蚂蚁们每秒钟可以走一厘米的距离。编写程序，求所有蚂蚁都离开木杆的最小时间和最大时间。看到很多人发布了他们的解法，我觉得都过于复杂并不甚清晰，以下是我的思路和实现.1 .思路与建模* 将木杆看成0至27的坐标，5只蚂蚁分别在 3, 7,11,17, 23的位置* 创建 enum D

2、irectory Left, Right* 创建Ant类，蚂蚁可以爬行（walk）,掉头（shift）,并且如果爬出能把自己从蚂蚁队列中移出 去,* 创建Controller类，给定蚂蚁的初始方向，Controller类可以计算出在这种初始方向下蚂蚁全 部爬出需要的时间.* 创建Simulator类，它给出蚂蚁初始方向的所有组合，并使用Controller执行得到所有时间选择最大值和最小值.2 .实现在Model包内：view plaincopy to clipboardprint? package ;public enum Direction Left, Rightpackage ;publ

3、ic enum Direction Left, Right)view plaincopy to clipboardprint?package ;import ;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.

4、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 &am

5、p;& 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)list.get(index+1).position | this.positionif(

6、 this.positionlist.get(index-1).position) doShift();)private void doShift()this.direction = (this.direction = Direction.Left) ? Direction.Right : Direction.Left; ) ) package ;import ;public class Ant public static final int LENGTH = 27;private int position;Direction direction;/* 在木杆上的蚂蚁队列*/ArrayList

7、<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.remov

8、e( 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()

9、;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

10、 clipboardprint?package ;import ;import ;import ;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<

11、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()Arr

12、ayList<Ant> list = new ArrayList<Ant>();for( int i = 0; i < positions.length; i+ )Ant ant = new Ant( positionsi, diri, list ); list.add( ant );) return list;)package ;import ;import ;import ;public class Controller /* 蚂蚁初始位置* /private int positions = 3, 7, 11, 17, 23 );/* 蚂蚁初始方向* /pri

13、vate 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();

14、)/掉头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( positionsi, diri, list ); list

15、.add( ant );) return list;)在Root包内view plaincopy to clipboardprint?package cn.dfeng;import ;import ;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.getDirection

16、s(i);long time = con.start();if( time > longest ) longest = time;)if( time < shortest ) shortest = time;)"Time: " + time );)/*创建蚂蚁初始位置*/private Direction getDirections(int i) Direction dirs = new Direction5;String binString = Integer.toBinaryString(i);StringBuilder sb = new StringBui

17、lder();int lack = 5 - binString.length();for( int c = 0; c < lack; c+ )sb.append('O');)sb.append( binString );binString = sb.toString();int p = 0;while( p < binString.length() ) if (binString.charAt(p) = '0') dirsp = Direction.Left; else dirsp = Direction.Right;p+；"Round:

18、" + binString );return dirs;/*打印结果*/public void getResult() "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 ;import ;public class Simulator private lo

19、ng 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;)"Time: " + time );)/*创建蚂蚁初始位置*/private Direction getDirections(int i) Direction dirs = new Direction5;String binString = Integer.toBinaryString(i);StringBuilder sb = new StringBuilder();int lack = 5 - binString.length();for( int c = 0; c < lack;