百度笔试题 蚂蚁爬杆

最近在网上看到一个蚂蚁爬杆的笔试题，很多人写出来答案公布出来了，但是都不是很满意，下面是我自己写的，大家参考

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

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;


public class Mayi {
	public static final int MAX_LENGTH = 27;
	public static int[] list = {3,7,11,17,23};

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		
		int[][] direct = getDirect(5);

		List<Integer> result = new ArrayList<Integer>();
		for(int i=0;i<direct.length;i++){
			int[] start = new int[list.length];
			System.arraycopy(list, 0, start, 0, list.length);
			int time = move(start,direct[i],0);
			result.add(time);
		}
		System.out.println("max time:"+Collections.max(result));
		System.out.println("min time:"+Collections.min(result));
		
	}
	
	/**
	 * 递归生成方向数组
	 * @param n
	 * @return
	 */
	public static int[][] getDirect(int n){
		if(n==1){
			return new int[][]{{1},{-1}};
		}
		int[][] last = getDirect(n-1);
		int[][] result = new int[last.length*2][n];
		
		for(int k=0;k<last.length;k++){
			result[k][0]=1;
			for(int j=0;j<n-1;j++){
				result[k][j+1]=last[k][j];
			}
		}
		for(int k=0;k<last.length;k++){
			result[k+last.length][0]=-1;
			for(int j=0;j<n-1;j++){
				result[k+last.length][j+1]=last[k][j];
			}
		}
		return result;
	}
	/**
	 * 按照规定的起始方向走完需要的总时间
	 * @param list
	 * @param direct
	 * @param sum
	 * @return
	 */
	public static int move(int[] list,int[] direct,int sum){
		int tmp = -1;
		int distance = MAX_LENGTH;
		//查看是否可能会出现碰撞
		for(int i=0;i<direct.length-1;i++){
			if(direct[i]==1&&direct[i+1]==-1){
				if(list[i+1]-list[i]<=distance){
					distance = list[i+1]-list[i];
					tmp = i;
				}
			}
		}
		//如果有碰撞，递归进行下一步
		if(tmp!=-1){
			int time = distance/2;
			for(int i=0;i<list.length;i++){
				list[i] = list[i]+direct[i]*time;
			}
			direct[tmp]=-direct[tmp];
			direct[tmp+1]=-direct[tmp+1];
			return move(list,direct,sum)+time;
		}else{
			int time = 0;
			for(int i=0;i<list.length;i++){
				int des = list[i]*direct[i]<0?list[i]:MAX_LENGTH-list[i];
				if(list[i]>0&&list[i]<MAX_LENGTH&&time<des){
					time = des;
				}
			}
			return sum+time;
		}
	}

}

评论

2 楼 wjddnl 2011-04-17  

william_ai 写道

这道题用动量守恒定律来做是否会更好些，最小时间就是里木杆中心最近的蚂蚁离开木杆的最小时间，最大时间就是离木杆任何一段最远的蚂蚁离开木杆的时间。

public class Ant {  
    public static void main(String[] args) {  
    	double[] ants = {3,7,11,17,23}; 
    	double mid = 27 / 2.0;
    	double min = mid;
    	double minAnt = 0;
    	
    	for(Double i:ants){
    		double temp = Math.abs(i-mid);
    		if(temp < min){
    			min = temp;
    			minAnt = i;
    		}
    	}
    	
    	int maxAnt = (23 > 27 -3)?23:(27-3);
    	
    	System.out.println((int)minAnt);
    	System.out.println(maxAnt);
    }      
}  

哇哦~~~ 我还以为这个题要考的是递归呢。。。 没想到，还有动量守恒定律可以来解这道题。。。 这位哥们儿，真牛啊，学习了 

1 楼 william_ai 2011-04-17  

这道题用动量守恒定律来做是否会更好些，最小时间就是里木杆中心最近的蚂蚁离开木杆的最小时间，最大时间就是离木杆任何一段最远的蚂蚁离开木杆的时间。

public class Ant {  
    public static void main(String[] args) {  
    	double[] ants = {3,7,11,17,23}; 
    	double mid = 27 / 2.0;
    	double min = mid;
    	double minAnt = 0;
    	
    	for(Double i:ants){
    		double temp = Math.abs(i-mid);
    		if(temp < min){
    			min = temp;
    			minAnt = i;
    		}
    	}
    	
    	int maxAnt = (23 > 27 -3)?23:(27-3);
    	
    	System.out.println((int)minAnt);
    	System.out.println(maxAnt);
    }      
}