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

题目：有一根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;}}}

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); } } 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); } }


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