分类：
2010-09-05 16:33:18
题目描述：
有一根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
public Ant( int p, Direction dir, ArrayList
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
public Ant( int p, Direction dir, ArrayList
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
/*
* 蚂蚁队列为空即全部爬出
*/
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
ArrayList
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
/*
* 蚂蚁队列为空即全部爬出
*/
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
ArrayList
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();
}
}
我感觉这个题目不应该这么做，因为在面试的时候没有人（就是有也很少）会有这么长时间来做这个的。最后我想了想，感觉这个题目很有趣：下面是我的思路
我感觉没这么复杂，直接算也可以。最短就是，从杆的中间分开，在左边的朝左走，在右边的朝右走（蚂蚁离那边近就朝那边走），这样就得到最小时间了为11s（max（max（3，7，11），max（27-17，27-23））=11）
而最长时间是基于蚂蚁的速度相同来做的： 最长的就是24 （max（27-3，23）），因为所有蚂蚁的速度相同，因此蚂蚁相撞就看成，两个换了一下位置，（例如3，和7撞了，我们就当3原来在7的位置，7原来在3的位置，这样以来就可以理解为撞了也可以继续前进，这样可以得到答案了，最长时间就是两头的向离自己最远的一段走，即3位置的往27那边走，23位置的往0位置走，那个时间长就是答案）
实现起来很简单，就是一个max函数
int max（int num1，int num2） { return (num1>num2 ? num1 : num2); }
