随笔 - 312, 文章 - 14, 评论 - 1393, 引用 - 0
数据加载中……

百度面试题的java实现

本文为原创,如需转载,请注明作者和出处,谢谢!

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

java实现代码

public class test_ant
{
    
private int[] ants = new int[5];
    
// 1:左 2:右
    private int enumDirection[][] = new int[32][5];
    
private void initDirection()
    {
        
for (int i = 16, column = 0; i > 0; i = i / 2, column++)
        {
            
int n = 1;
            
for (int j = 0; j < 32; j++)
            {
                
if((j / i) % 2 == 0)
                    enumDirection[j][column] 
= 1;
                
else
                    enumDirection[j][column] 
= 2;
            }
        }
    }
    
private boolean checkAnts()
    {
        
for (int i = 0; i < 5; i++)
        {
            
if (ants[i] > 0 && ants[i] < 28)
                
return true;
        }
        
return false;
    }
    
private void changeDirection(int row, int col)
    {
        
if (enumDirection[row][col] == 1)
            enumDirection[row][col] 
= 2;
        
else
            enumDirection[row][col] 
= 1;
    }
    
public void antClimb()
    {
        initDirection();
        
for (int n = 0; n < 32; n++)
        {
            
int seconds = 0;
            ants[
0= 3;
            ants[
1= 7;
            ants[
2= 11;
            ants[
3= 17;
            ants[
4= 23;
            
while (checkAnts())
            {
                seconds
++;
                
for (int i = 0; i < ants.length; i++)
                {
                    
if (i < ants.length - 1)
                    {
                        
// 蚂蚁相遇
                        if ((ants[i] == ants[i + 1])
                                        
&& ((enumDirection[n][i] + enumDirection[n][i + 1]) == 3))
                        {
                            changeDirection(n, i);
                            changeDirection(n, i 
+ 1);
                        }
                    }
                    
if (enumDirection[n][i] == 1)
                        ants[i]
--;
                    
else
                        ants[i]
++;
                }
            }
            
for (int j = 0; j < 5; j++)
                System.out.print(enumDirection[n][j]);
            System.out.println(
"");
            System.out.println(seconds);
        }
    }
    
public static void main(String[] args)
    {
        
new test_ant().antClimb();
    }
}


其中ants数组保存了5只蚂蚁当前在竿上的位置
enumDirection枚举了所有的32种初始化方向,1代表向左,2代表向右

最短11秒, 最大25秒

运行结果

11111
23
11112
17
11112
23
11122
11
11112
23
11122
17
11122
23
11222
17
11112
23
11122
21
11122
23
11222
21
11122
23
11222
21
11222
23
12222
21
11112
25
11122
25
11122
25
11222
25
11122
25
11222
25
11222
25
12222
25
11122
25
11222
25
11222
25
12222
25
11222
25
12222
25
12222
25
22222
25






Android开发完全讲义(第2版)(本书版权已输出到台湾)

http://product.dangdang.com/product.aspx?product_id=22741502



Android高薪之路:Android程序员面试宝典 http://book.360buy.com/10970314.html


新浪微博:http://t.sina.com.cn/androidguy   昵称:李宁_Lining

posted on 2008-05-10 09:23 银河使者 阅读(6639) 评论(10)  编辑  收藏 所属分类: javaalgorithm 原创

评论

# re: 百度面试题的java实现  回复  更多评论   

刚刚看到你对这道题目的解释,新写了一篇文章,觉得最大是24秒,而且感觉没有这么复杂,可以看一下,相互学习吧,加油~
2008-05-10 11:37 | dreamingnest

# re: 百度面试题的java实现  回复  更多评论   

dreamingnest的思路很好,跳出了"不能同时通过两个蚂蚁"的心理暗示.
2008-05-10 12:42 | jacky-q

# re: 百度面试题的java实现[未登录]  回复  更多评论   

其实文中蚂蚁相撞两蚂蚁调头
可以这样看问题,如果相撞后,杆可以过两只蚂蚁
蚂蚁不调头,即擦肩而过,继续沿原来方向前进(与调头是一样的,只是换了一只蚂蚁而已)
这样问题就简化了,呵呵。
即所有蚂蚁中离杆其中一端最远的那只蚂蚁,即为最长时间。
即27-3=24
呵呵,最短时间同理可以推出。。。略
2008-05-12 14:07 | Blues

# re: 百度面试题的java实现  回复  更多评论   

北大的OJ上有这道题
2008-05-22 16:26 | stonebow

# re: 百度面试题的java实现  回复  更多评论   

很明显最小时间为3秒!!!!因为有一只蚂蚁在第三CM处,如它一开始就向第0CM处跑,那不就三秒钟就离开了杆了吗?而题目是:求所有蚂蚁都离开木杆的最小时间!!!!!!!
2008-07-09 10:48 | jackie

# re: 百度面试题的java实现  回复  更多评论   

有兴趣可以探讨下!!我QQ
330620600
2008-07-09 10:51 | jackie

# re: 百度面试题的java实现  回复  更多评论   

这道题的若干trick:
1. 两只蚂蚁相撞后折返,和两只蚂蚁相撞后互相穿过效果是一样的;
2. 左右方向的遍历用bit位更方便:1表示左,0表示右;
3. 其实因为只需要求出最常最短时间,甚至都不用遍历所有的方向,参见minMax1()。
public class Ant {

int len = 27;
int[] pos = {3,7,11,17,23};

public static void main(String[] args) {
new Ant().minMax2();
}
public void minMax() {
int maxs = (1 << 5) - 1;
int min = Integer.MAX_VALUE;
int max = Integer.MIN_VALUE;
int step = 0;
for(int i = 2; i <= maxs; i++) {
step = 0;
for(int j = 0; j < 5; j++) {
if((i & (1 << j)) != 0) {
step = Math.max(step,pos[j]);
} else {
step = Math.max(step,28 - pos[j]);
}
}
max = Math.max(max,step);
min = Math.min(min,step);
}
System.out.println(min);
System.out.println(max);
}

public void minMax2() {
int min = Integer.MIN_VALUE;
int max = Integer.MIN_VALUE;

for(int i = 0; i < 5; i++) {
min = Math.max(Math.min(pos[i],28 - pos[i]),min);
max = Math.max(Math.max(pos[i],28 - pos[i]),max);
}
System.out.println(min);
System.out.println(max);
}
}
2008-09-22 01:38 | geagle

# re: 百度面试题的java实现[未登录]  回复  更多评论   

其实想想之后就是一个数学定律:

最大时间:找到离出口最近的蚂蚁,然后所有的蚂蚁同一个方向朝反向出去
最小时间:找到最靠近中心的蚂蚁,然后两边的蚂蚁朝两个方向分别出去
2009-02-10 14:35 | zero

# re: 百度面试题的java实现  回复  更多评论   

最长24秒,因为作者写的检查条件是 && ants[i] < 28,多写了一厘米造成。
思路挺不错,我的思路是用多线程来解决,这个比我的思路简单一些。看来高人不少啊!

蚂蚁不调头,即擦肩而过,继续沿原来方向前进(与调头是一样的,只是换了一只蚂蚁而已) ,这个思路也不错,鼓励一下!
2009-12-19 17:23 | 匿名

# re: 百度面试题的java实现[未登录]  回复  更多评论   

根据Blues的思路实现
根本就是一道数学题嘛
用不到遍历,纯数学
贴代码:
java code:

public class Test{
public static int MAX_LENGTH;
public static void main(String args[]){
MAX_LENGTH = 27;
int[] poses = {3,7,11,17,23};
System.out.println("max:" + max(poses));
System.out.println("min:" + min(poses));
}

public static int max(int[] poses){
if(poses == null || poses.length == 0){
System.out.println("oh no,dear, you cann't do that");
return -1;
}

int result1 = poses[0] > MAX_LENGTH - poses[0] ? poses[0] : MAX_LENGTH - poses[0];
int result2 = poses[poses.length - 1] > MAX_LENGTH - poses[poses.length - 1] ? poses[poses.length - 1] : MAX_LENGTH - poses[poses.length - 1];
return result1 > result2 ? result1 : result2;
}
public static int min(int[] poses){
if(poses == null || poses.length == 0){
System.out.println("oh no,dear, you cann't do that");
return -1;
}
int result1 = poses[poses.length / 2] < MAX_LENGTH - poses[poses.length / 2] ? poses[poses.length / 2] : MAX_LENGTH - poses[poses.length / 2];
if(poses.length % 2 == 0){
int result2 = poses[poses.length / 2 + 1] < MAX_LENGTH - poses[poses.length / 2 + 1] ? poses[poses.length / 2 + 1] : MAX_LENGTH - poses[poses.length / 2 + 1];
return result1 > result2 ? result1 : result2;
}else{
return result1;
}
}
}
2010-07-15 11:47 | wavesun

只有注册用户登录后才能发表评论。


网站导航: