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


似乎是某公司面试题～～偶用穷举法实现了一下～～但是这个肯定考的不是穷举法，应该有优化的多的算法～有兴趣且有时间的朋友可以做着玩玩～～

PS：没时间的话如果有好的算法也可以说出来分享一下～HOHO～

发一下偶的巨土的穷举法实现～～
package com.gufengdebianyuan;
import java.util.*;
import java.lang.*;

/*
* 该类的主要作用是模拟蚂蚁的各种属性
*/
public class Mayi {

//构造函数
public Mayi(String para,int coordinate){
this.coordinate = coordinate;

sum = 0;

state = true;

if(para.equals("0")){
direction = -1;
}
else
{
direction = 1;
}
}

//方向
public int direction;

//走动量
public int sum;

//当前坐标
public int coordinate;

//状态（是已落杆还是行进中）
public boolean state;

//判断蚂蚁是否已经落杆
public void judge()
{
if(coordinate<=0||coordinate>=27)
{
state = false;
}
}

//模拟蚂蚁走路的步骤
public void go()
{
if(state){
coordinate = coordinate + direction;
sum++;
}
judge();
}

}

/**
* 该类的主要作用是穷举所有可能发生的蚂蚁的初始化状态
*/
public class Step {

//存放所有的初始化状态
public ArrayList list;

//构造函数，初始化链表
public Step()
{
list = new ArrayList();
}

//把每种初始化状态加到链表中
public void addStep(int a,int b,int c,int d,int e){

String tal = String.valueOf(a)+String.valueOf(b)+String.valueOf(c)+
String.valueOf(d)+String.valueOf(e);

list.add(tal);

}

//返回链表的大小
public int size(){
return list.size();
}

//返回指定位置的初始化状态
public Object get(int i){
return list.get(i);
}
}

/**
* 主类，模拟蚂蚁的运动过程，并记录数据进行分析
*/
public class Test {

//存放所有可能出现的初始情况
Step steplist;
int a,b ,c ,d ,e;


public Test(){
a = 0;
b = 0;
c = 0;
d = 0;
e = 0;

steplist = new Step();
}

//把所有的初始情况增加到steplist中
public void add(){

for(int a=0;a<2;a++)
{
for(int b=0;b<2;b++)
{
for(int c=0;c<2;c++)
{
for(int d=0;d<2;d++)
{
for(int e=0;e<2;e++)
{
steplist.addStep(a,b,c,d,e);
}
}
}
}
}

}

//看两只蚂蚁是否碰头，若碰头则进行转向处理
public static void balance(Mayi mayia,Mayi mayib){
if(mayia.coordinate==mayib.coordinate)
{
mayia.direction = (-1)*mayia.direction;
mayib.direction = (-1)*mayib.direction;
}
}

public static void main(String []args)
{
Test test = new Test();
test.add();

//用向量存放每种情况的最后一只蚂蚁爬下杆子时的步数
Vector total = new Vector();


Mayi mayi1,mayi2,mayi3,mayi4,mayi5;

//循环每一种初始化状态
for(int i=0;i<test.steplist.size();i++)
{
//取当前的五个蚂蚁的初始化状态
String tempTest = (String)test.steplist.get(i);

mayi1 = new Mayi(tempTest.substring(0,1),3);

mayi2 = new Mayi(tempTest.substring(1,2),7);

mayi3 = new Mayi(tempTest.substring(2,3),11);

mayi4 = new Mayi(tempTest.substring(3,4),17);

mayi5 = new Mayi(tempTest.substring(4,5),23);


while(mayi1.state||mayi2.state||mayi3.state||mayi4.state||mayi5.state)
//判断是否所有的蚂蚁都已下杆，若不是则继续循环
{

//蚂蚁开始行走
mayi1.go();
mayi2.go();
mayi3.go();
mayi4.go();
mayi5.go();

//判断蚂蚁是否有碰头
Test.balance(mayi1,mayi2);
Test.balance(mayi2,mayi3);
Test.balance(mayi3,mayi4);
Test.balance(mayi4,mayi5);

}

int []temp = new int[]{mayi1.sum,mayi2.sum,mayi3.sum,mayi4.sum,mayi5.sum};

//为当前次每个蚂蚁行走的步数排序
Arrays.sort(temp);

total.add(String.valueOf(temp[4]));
}

//为每次的最大步数组成的链表排序
Collections.sort(total);

System.out.println("蚂蚁爬出杆子的最短时间为："+total.elementAt(0)+"秒；");

System.out.println("蚂蚁爬出杆子的最长时间为："+total.lastElement()+"秒。");

}

}

[此贴子已经被作者于2006-11-19 20:27:17编辑过]

呵呵,在CSDN上看到的吧

哈哈，不是，是在一个别的论坛上看到的，但是据说是在CSDN上转的～

去CSDN上看了一下。。。。发现如果用鬼魂算法来解是如此的简单。。。。。还是数学思想不行啊～55555555，谁让偶上大学的时候直接把数学扔了呢～～