Home 文章 Java基础 关于蚂蚁问题（Ants）

主菜单


feedsky
抓虾
google reader
my yahoo
关于蚂蚁问题（Ants） E-mail
User Rating: / 0
PoorBest 
作者是 dreamingnest   
2008-05-10 21:22:59
之前看有的朋友谈百度的一道面试试题－蚂蚁问题（有一根27厘米的细木杆，在第3厘米、7厘米、11厘米、17厘米、23厘米这五个位置上各有一只蚂蚁。木杆很细，不能同时通过一只蚂蚁。开始时，蚂蚁的头朝左还是朝右是任意的，它们只会朝前走或调头，但不会后退。当任意两只蚂蚁碰头时，两只蚂蚁会同时调头朝反方向走。假设蚂蚁们每秒钟可以走一厘米的距离。编写程序，求所有蚂蚁都离开木杆的最小时间和最大时间）。关于这道题目，网上给出了很多的解释，但从整体来看，基本都是用到了等价置换（等量代换）的思想。要求最小时间，即为“最不容易”先到达两端的蚂蚁以最短的时间到达，所以我们只需找到所有蚂蚁中间的一只（共奇数只蚂蚁）或两只（共偶数只蚂蚁）到达一端的最短时间。比较麻烦的是求最长时间，有人会觉得当有很多只蚂蚁时，中间的蚂蚁们相互碰撞的次数多些会增加时间，感觉上比较复杂，可如果我们用等量代换的思想来解释就比较容易。假设中间的任意两只相邻蚂蚁即将发生碰撞，如：A －>        <－B，当A，B发生碰撞后，便有<－A    B－>。A，B反向相当于<－B   A －> ，即二者继续向着原来的方向前进，对于任意相邻的发生碰撞的蚂蚁都适用，所以只需求最两端的两只蚂蚁距离两端的最远距离。由以上分析可知，如果出这样的问题，我们可以不用通过程序便能说出结果：5个点，中间蚂蚁的位置为11，即0－11－27，显然最小为11，最两端蚂蚁，0－3－27，最大为24，0－23－27，最大为23，所以最大为24。对于这个题，给出如下Java代码（随便写了几句，不符合面向对象思想）。
public class Ant {
    public static void main(String[] args){
        int length=27,points=5,min=0,max=0,temp_min=0,temp_max=0;
        int[] pos={3,7,11,17,23};
        for(int i: pos){
            temp_min=i>length-i?length-i:i;
            temp_max=i<length-i?length-i:i;
            if(temp_min>min)
                min=temp_min;
            if(temp_max>max)
                max=temp_max;
        }
        System.out.println("最短时间:"+min+"  最长时间:"+max);
    }
}
最近更新 ( 2008-05-10 21:22:59 )
 
Java家,