[转]5只蚂蚁的问题

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

模拟每秒钟5只蚂蚁的情况。在生成Ant对象时确定蚂蚁的运行方向和名字。代码如下：

public class Ant {
    //蚂蚁的位置
    private int position;
    //爬行方向
    private boolean front_flg;
    //是否到达终点
    private boolean isOver = false;
    //蚂蚁的名字
    private String antName;
    public boolean isOver() {
        if((position == 0)||(position == 27)){
            isOver = true;
        } else {
            isOver = false;
        }
        return isOver;
    }
    public void setOver(boolean isOver) {
        this.isOver = isOver;
    }
    public String getAntName() {
        return antName;
    }
    public void setAntName(String antName) {
        this.antName = antName;
    }
    public boolean isFront_flg() {
        return front_flg;
    }
    public void setFront_flg(boolean front_flg) {
        this.front_flg = front_flg;
    }
    public void setPosition(int position) {
        this.position = position;
    }
    //构造方法
    public Ant (int position,boolean flg,String antName){
        this.position = position;
        this.front_flg = flg;
        this.antName = antName;
    }
    public void crawl(boolean front_flg){
        //根据爬行方向判断position的加减
        if(!(isOver())){
            if (front_flg){
                position = position + 1;
            } else {
                position = position - 1;
            }
        }
        System.out.println(antName + " has arrived position : " + position);
    }
    public int getPosition() {
        return position;
    }
    
    /**
     * @param args
     */
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Ant ant3 = new Ant (3,true,"ant3");
        Ant ant7 = new Ant (7,true,"ant7");
        Ant ant11 = new Ant (11,true,"ant11");
        Ant ant17 = new Ant (17,false,"ant17");
        Ant ant23 = new Ant (23,false,"ant23");
        //记录爬行时间
        int useTime = 1;
        while(!(ant3.isOver()
                &&ant7.isOver()
                &&ant11.isOver()
                &&ant17.isOver()
                &&ant23.isOver())){
            
            //如果两只蚂蚁相遇则调转爬行方向
            if (ant3.getPosition()==ant7.getPosition()){
                boolean temp;
                temp = ant3.isFront_flg();
                ant3.setFront_flg(ant7.isFront_flg());
                ant7.setFront_flg(temp);
            }
            if (ant3.getPosition()==ant11.getPosition()){
                boolean temp;
                temp = ant3.isFront_flg();
                ant3.setFront_flg(ant11.isFront_flg());
                ant11.setFront_flg(temp);
            }
            if (ant3.getPosition()==ant17.getPosition()){
                boolean temp;
                temp = ant3.isFront_flg();
                ant3.setFront_flg(ant17.isFront_flg());
                ant17.setFront_flg(temp);
            }
            if (ant3.getPosition()==ant23.getPosition()){
                boolean temp;
                temp = ant3.isFront_flg();
                ant3.setFront_flg(ant23.isFront_flg());
                ant23.setFront_flg(temp);
            }
            
            if (ant7.getPosition()==ant11.getPosition()){
                boolean temp;
                temp = ant7.isFront_flg();
                ant7.setFront_flg(ant11.isFront_flg());
                ant11.setFront_flg(temp);
            }
            if (ant7.getPosition()==ant17.getPosition()){
                boolean temp;
                temp = ant7.isFront_flg();
                ant7.setFront_flg(ant17.isFront_flg());
                ant17.setFront_flg(temp);
            }
            if (ant7.getPosition()==ant23.getPosition()){
                boolean temp;
                temp = ant7.isFront_flg();
                ant7.setFront_flg(ant23.isFront_flg());
                ant23.setFront_flg(temp);
            }
            
            if (ant11.getPosition()==ant17.getPosition()){
                boolean temp;
                temp = ant11.isFront_flg();
                ant11.setFront_flg(ant17.isFront_flg());
                ant17.setFront_flg(temp);
            }
            if (ant11.getPosition()==ant23.getPosition()){
                boolean temp;
                temp = ant11.isFront_flg();
                ant11.setFront_flg(ant23.isFront_flg());
                ant23.setFront_flg(temp);
            }
            
            if (ant17.getPosition()==ant23.getPosition()){
                boolean temp;
                temp = ant17.isFront_flg();
                ant17.setFront_flg(ant23.isFront_flg());
                ant23.setFront_flg(temp);
            }
            //蚂蚁爬行
            ant3.crawl(ant3.isFront_flg());            
            ant7.crawl(ant7.isFront_flg());            
            ant11.crawl(ant11.isFront_flg());            
            ant17.crawl(ant17.isFront_flg());            
            ant23.crawl(ant23.isFront_flg());            
            System.out.println("Use time is :" + useTime++);
            System.out.println("================================");
        }
    }
}

评论

3 楼 windows1987 2010-01-05  

今天我在一本叫做《编程之美-微软技术面试心得》这本书上看到了这道题的解法，建议楼主看一下，相当的简单，相当的有启发，呵呵！

2 楼 gainfirst 2009-06-25  

我的思路是定义了一个木头类和蚂蚁类，蚂蚁碰头掉转方向的依据是当前蚂蚁所在木头上的位置蚂蚁的数量是否是等于2，如果是掉头，就是这一点不一样，其他差不多。

1 楼 gainfirst 2009-06-25  

   很有意思，我自己也写了个，写完后看了下你的实现思路算是差不多，不一样的地方就是我的蚂蚁在有限的长度内的位置和方向可以随便改动。我的疑问是如果把这个问题进行扩展，如何定义一种好的数据结构能都将木头的长度，蚂蚁的位置和数量表达的情况。里面有个问题就是如果是这种好的结构是存在，那么在初始化蚂蚁的位置和方向的时候，如何去检验这个是正确的。比如：
      A在3，B在4，A向右爬，B向左爬，此时这个位置错误的 这种情况还好说
      A在3，B在4，C在5，A-R,B-R,C-R 正确，但是这个里面如果C-L,那么这个是错误的

    当然还有很多复杂的情况可以假设，如果蚂蚁的数量很多，情况就会很复杂，我就在想这里面有没有很好的初始化校验的方法，一直在想，却不得其解。本来是写着玩的，但是脑一闲下来的时候就会忍不住就想，哎