百度面试题，很不错哦

Question

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

Answer 1

kaoloveting(甲克虫):
"我最怕这种iq题目，哎--"---哎--, 看到这种东西就头疼....

Answer 2

烦！kaoloveting(甲克虫):
"我最怕这种iq题目，哎--"---哎--, 看到这种东西就头疼....

Answer 3

mzcyc() ( ) 信誉：100    Blog  2006-11-8 13:11:49  得分: 0  
 
 
   
把蚂蚁看成是鬼魂，可以各自穿过对方的身体，那这道题目就很好得出答案了。
最小时间是11秒，最大时间是24秒。  
 
================================这个想法不错

Answer 4

能看一下 JAVA_WEB(不停地往上爬) 的程序吗

Answer 5

最小11,最大就....32种走法,用程序模拟算比较简单,如果找算法规律.....就.....正解！每个蚂蚁对象维护自己的几个属性：
time 在木头上走的时间
pos  在木头上的坐标
orientation 方向(-1 or 1)recursion:
1 所有蚂蚁走一步，矢量pos加1，time加1
2 检查是否有蚂蚁在同一坐标上，如果有，将它们掉头
3 检查是否有蚂蚁的坐标在[0,27]以外的外围，如果有，记下它的time值，然后这个蚂蚁出局
4 repeat 1-3，直到所有蚂蚁出局。它们time的最大值就是一个解(一共有32个情况，32种解)。

Answer 6

我怎么算完了最小11,最大25,源程序如下:
class FunnyAnt {
class Ant {
public final static int LEFT = 0;
public final static int RIGHT = 1;
int x;
int direction;
public Ant(int x, int direction) {
this.x = x;
this.direction = direction;
}
public void setDirection(int direction) {
this.direction = direction;
}
public void move() {
if (direction == LEFT) {
x -= 1;
} else {
x += 1;
}
}
public void switchDirection() {
direction = (direction + 1) % 2;
}
public int getX() {
return x;
}
public String getDirection() {
return (direction == LEFT) ? "Left" : "Right";
}
}
public static void main(String[] args) {
Vector v = new Vector();
Vector timerV = new Vector();
FunnyAnt fa = new FunnyAnt();
int[] positions = {3, 7, 11, 17, 23};
Ant ant = null;
// list all conditions
for (byte i = 0; i < 32; i++) {
// System.out.println("I :" + i);
int tempI = i;
for (int j = 0; j < 5; j++) {
byte temp = (byte) (tempI & 0x01);
// System.out.println("Position Got :" + temp);
ant = fa.new Ant(positions[j], temp);
v.addElement(ant);
tempI = (byte) (tempI >> 1);
}
int timer = 0;
while (v.size() > 0) {
ant = null;
// move ants if out delete
for (int k = 0; k < v.size(); k++) {
ant = (FunnyAnt.Ant) v.elementAt(k);
ant.move();
int x = ant.getX();
if (x <= 1 || x >= 27) {
v.removeElementAt(k);
}
}
timer++;
// check whether there is collide
ant = null;
for (int l = 0, lastX = -1; l < v.size(); l++) {
ant = (FunnyAnt.Ant) v.elementAt(l);
if (lastX == ant.getX()) {
((FunnyAnt.Ant) (v.elementAt(l))).switchDirection();
((FunnyAnt.Ant) (v.elementAt(l - 1))).switchDirection();
}
lastX = ant.getX();
}
}
timerV.addElement(new Integer(timer));
v.removeAllElements();
}
int min = ((Integer) (timerV.elementAt(0))).intValue(), max = ((Integer) (timerV.elementAt(0))).intValue();
Integer value = null;
for (int i = 0; i < timerV.size(); i++) {
value = (Integer) timerV.elementAt(i);
int x = value.intValue();
if (x < min) {
min = x;
}
if (x > max) {
max = x;
}
}
System.out.println("Max :" + max + " Min :" + min);
}
}

Answer 7

def set_ants_dist(ants) :    
    ants[0]['dist'] = 3
    ants[1]['dist'] = 7
    ants[2]['dist'] = 11
    ants[3]['dist'] = 17
    ants[4]['dist'] = 23
    def all_out(ants) :
    count = len(ants)
    sec = 0
    out = True
    while True :
        sec = sec + 1
        out = True
        for i in range(0, count) :
            old =  ants[i]['dist']
            if ants[i]['dist'] == 0 or ants[i]['dist'] == 27 :
                pass
            else :
                if ants[i]['dir'] == 1 :
                    ants[i]['dist'] = ants[i]['dist'] - 1
                else :
                    ants[i]['dist'] = ants[i]['dist'] + 1
                if ants[i]['dist'] == 0 or ants[i]['dist'] == 27 :
                    pass
                else :
                    out = False              
        if out == True :
            return sec
        # meet?
        for j in range(0, count-1) :
            if ants[j]['dist'] == ants[j+1]['dist'] :
                ants[j]['dir'] = -1 * ants[j]['dir']
                ants[j+1]['dir'] = -1 * ants[j+1]['dir']
        
def ants_walk() :
    secLst = []
    ants = []
    for count in range(0, 5) :
        tmp = {}
        tmp['dir'] = 1
        ants.append(tmp)
        
    for i in range(0, 2) :
        ants[0]['dir'] = -1 * ants[0]['dir']
        for j in range(0, 2) :
            ants[1]['dir'] = -1 * ants[1]['dir']
            for k in range(0, 2) :
                ants[2]['dir'] = -1 * ants[2]['dir']
                for l in range(0, 2) :
                    ants[3]['dir'] = -1 * ants[3]['dir']
                    for m in range(0, 2) :
                        ants[4]['dir'] = -1 * ants[4]['dir']
                        set_ants_dist(ants)
                        secLst.append(all_out(ants))
    return secLstif __name__ == '__main__' :
    result = ants_walk()
    print result
    print "min : ", min(result), ", ", "max : ", max(result)

Answer 8

把蚂蚁看作鬼混是正解，为什么可以看作鬼混，假设有两只蚂蚁A，B对着走，他们碰头时反向，其实这时可以把A看作B，B看作A，即他们仍朝各自的方向行走，而互不受影响。

Answer 9

那最大时间就是max(27-3,23-1);了吗

Answer 10

to  
-----------------------------------------------------------------------------------
zuguanqun(小群) ( ) 信誉：100    Blog  2006-11-08 14:56:00  得分: 0  
 
 
   能看一下 JAVA_WEB(不停地往上爬) 的程序吗
-----------------------------------------------------------------------------------
import java.util.HashSet;
import java.util.Set;public class Test { static int[] state = new int[5];// -1:left; 1:right
static int ss = 0;
static Set set = new HashSet();
static int[] pos = new int[5];
static {
pos[0] = 3;
pos[1] = 7;
pos[2] = 11;
pos[3] = 17;
pos[4] = 23;
} static int start = 0; static int end = 27; static void go() {
while (true) {
ss++;
for (int i = 0; i < pos.length; i++) {
if (pos[i] > 0 && pos[i] < 27) {
pos[i] += state[i];
// if (pos[i] <= start || pos[i] >= end) {
// state[i] = 0;
// }
if (i < pos.length - 1 && state[i] == 1
&& state[i + 1] == -1) {
// 碰头情况
if (pos[i] + 1 > pos[i + 1]) {
state[i] = -1;
state[i + 1] = 1;
}
}
if (i > 0 && state[i] == -1 && state[i - 1] == 1) {
// 碰头情况
if (pos[i] - 1 < pos[i - 1]) {
state[i] = 1;
state[i - 1] = -1;
}
}
}
}
if (yanzheng()) {
print();
break;
}
}
} private static void print() {
System.out.println(ss);
set.add(ss);
} private static boolean yanzheng() {
boolean isOk = true;
for (int i = 0; i < state.length; i++) {
// if (state[i] != 0)
// isOk = false;
if (pos[i] > 0 && pos[i] < 27) {
isOk = false;
}
}
return isOk;
} static void init() {
ss = 0;
pos[0] = 3;
pos[1] = 7;
pos[2] = 11;
pos[3] = 17;
pos[4] = 23;
} public static void main(String[] args) { state[0] = -1;
state[1] = -1;
state[2] = -1;
state[3] = 1;
state[4] = 1;
// 10种初始化状态
for(int i = 0; i < 32; i ++) {
String s = Long.toBinaryString(i);
int n = 5 - s.length();
for(int j = 0; j < n; j ++) {
s = "0" + s;
}
for(int j = 0; j < s.length(); j ++) {
char a = s.charAt(j);
if(a == '1')
state[j] = 1;
else
state[j] = -1;
}
init();
go();
}
System.out.println("daskf:" + set.size());
}
}
请多多指教。

Answer 11

呵呵
开始我想的不大一样!我以为碰头时会有两种情况呢:
第一就是现在大家讨论的两只蚂蚁都掉头的情况;
第二就是只有一方掉头的情况.前者确如 gql_w() : "  把蚂蚁看作鬼混是正解，为什么可以看作鬼混，假设有两只蚂蚁A，B对着走，他们碰头时反向，其实这时可以把A看作B，B看作A，即他们仍朝各自的方向行走，而互不受影响。"所说.
不知道后者的情况如何?

Answer 12

to malligator(大螟):没有第二种情况，你想下，如果有这种情况的话，说明两只蚂蚁在一个位置上（一个蚂蚁站在令一个头上？）

Answer 13

我刚学java  到底什么是面向对象   为什么总是用面向过程的方法来用java     

Answer 14

to gql_w() :
怎能如此说呢？那碰头也算踩头了？？我只想说那么考虑的话程序不好写了

Answer 15

因为蚂蚁的速度都是相同的，所以蚂蚁碰头之后返回就相当于穿透向前走了，这样就很容易得出最大时间了。
Easy!!!

Answer 16

动量定理
mv+mv=mv+mv
这里mv的五只蚂蚁的速度和质量都是相同的
动能定理
5mv^2/2=5mv^2/2
5只蚂蚁其实只要看成一只会分身的蚂蚁就好了
一只长20米的蚂蚁头部在3厘米尾部在23厘米
分身的话是最快的从11米分成两段；
不分身的话就最慢的从23米那头爬直到3厘米也出去

Answer 17

抛开楼上的说的这道题的局限性,各位帮我看看我的程序哪里出错了,我是真找不出来了
我的道理很简单,就是不知道哪里出错了.看时间长了,越看越对
// 每种情况下,装载蚂蚁的容器
Vector v = new Vector();
// 记录每次所用时间的容器
Vector timerV = new Vector(); FunnyAnt fa = new FunnyAnt();
int[] positions = {3, 7, 11, 17, 23};
Ant ant = null;
// 一共有32种情况,每次都是一种情况
for (byte i = 0; i < 32; i++) { int tempI = i;
for (int j = 0; j < 5; j++) {
byte temp = (byte) (tempI & 0x01);
ant = fa.new Ant(positions[j], temp);
// System.out.println("Direction :" + ant.getDirection());
v.addElement(ant);
tempI = (byte) (tempI >> 1);
}
// 计数器,记录时间
int timer = 0;
while (v.size() > 0) {
// 计数
timer++; // 让每只蚂蚁爬一步
ant = null;
for (int k = 0; k < v.size(); k++) {
ant = (Ant) v.elementAt(k);
ant.move();
}
// 看哪些蚂蚁爬出了[1,27],删除它们
ant = null;
Vector tempV = new Vector();
for (int k = 0; k < v.size(); k++) {
ant = (Ant) v.elementAt(k);
int x = ant.getX();
if (x <= 1 || x >= 27) {
} else {
tempV.addElement(ant);
}
}
v = tempV; // 检查剩下的蚂蚁是否有已经重叠的,如果有的话,让他们调头
ant = null;
for (int l = 0, lastX = -1; l < v.size(); l++) {
ant = (FunnyAnt.Ant) v.elementAt(l);
// System.out.println("Before :" + ant.direction);
if (lastX == ant.getX()) {
((Ant) (v.elementAt(l))).switchDirection();
((Ant) (v.elementAt(l - 1))).switchDirection();
}
lastX = ant.getX();
}
}
timerV.addElement(new Integer(timer));
}

Answer 18

Ant 类
class Ant {
public final static int LEFT = 0;
public final static int RIGHT = 1;
int x;
int direction;
public Ant(int x, int direction) {
this.x = x;
this.direction = direction;
}
public void setDirection(int direction) {
this.direction = direction;
}
public void move() {
if (direction == LEFT) {
x -= 1;
} else {
x += 1;
}
}
public void switchDirection() {
direction = (direction + 1) % 2;
}
public int getX() {
return x;
}
public String getDirection() {
return (direction == LEFT) ? "Left" : "Right";
}
}

Answer 19

gql_w() : "  把蚂蚁看作鬼混是正解，为什么可以看作鬼混，假设有两只蚂蚁A，B对着走，他们碰头时反向，其实这时可以把A看作B，B看作A，即他们仍朝各自的方向行走，而互不受影响。"所说.一针见血提出本质

Answer 20

烦！kaoloveting(甲克虫):
"我最怕这种iq题目，哎--"---哎--, 看到这种东西就头疼....

Answer 21

算了一把time spent...24
time spent...24
time spent...24
time spent...24
time spent...24
time spent...24
time spent...24
time spent...24
time spent...24
time spent...24
time spent...24
time spent...24
time spent...24
time spent...24
time spent...24
time spent...24
time spent...20
time spent...23
time spent...20
time spent...23
time spent...20
time spent...23
time spent...20
time spent...23
time spent...16
time spent...23
time spent...17
time spent...23
time spent...11
time spent...23
time spent...17
time spent...23

Answer 22

.... 这题是某ACM Online Judge中的一道弱智题.... 楼上竟然有人给出那么强的程序....shunan的答案是正解...

Answer 23

借鉴楼上几位的设计想法,具现化了一把 java代码package net.ant.move;class Ant{
private int currentpos;
private int usedtime;

//'0'往前 '1'往后
private char derection;

public static int TOTAL_LENGTH = 27;
public int getCurrentpos() {
return currentpos;
}
public void setCurrentpos(int currentpos) {
this.currentpos = currentpos;
}
public int getDerection() {
return derection;
}
public void setDerection(char derection) {
this.derection = derection;
}
public int getUsedtime() {
return usedtime;
}
public void setUsedtime(int usedtime) {
this.usedtime = usedtime;
}

public Ant(int currentpos,char derection){
this.currentpos = currentpos;
this.derection = derection;
}

public void collide(){
this.currentpos = TOTAL_LENGTH - currentpos;
this.derection = derection=='0'? '1':'0';
}

public boolean isCollide(Ant ant2){
if((this.currentpos+ant2.currentpos==TOTAL_LENGTH)&&this.derection!=ant2.derection)
return true;
else
return false;
}
}package net.ant.move;class TestAntMove{
Ant[] ant = new Ant[5];
public static void main(String args[]){
TestAntMove tam = new TestAntMove();
tam.launch();
}

public  void launch() {
for (int i = 0; i < 32; i++) {
String s = Long.toBinaryString(i);

int n = 5 - s.length();
for (int j = 0; j < n; j++) {
s = "0" + s;
}
// System.out.println("s:=" + s);

ant[0] = s.charAt(0)=='0'? new Ant(3,s.charAt(0)):new Ant(Ant.TOTAL_LENGTH-3,s.charAt(0));

ant[1] = s.charAt(1)=='0'? new Ant(7,s.charAt(1)):new Ant(Ant.TOTAL_LENGTH-7,s.charAt(1));

ant[2] = s.charAt(2)=='0'? new Ant(11,s.charAt(2)):new Ant(Ant.TOTAL_LENGTH-11,s.charAt(2)); ant[3] = s.charAt(3)=='0'? new Ant(17,s.charAt(3)):new Ant(Ant.TOTAL_LENGTH-17,s.charAt(3));
 
ant[4] = s.charAt(4)=='0'? new Ant(23,s.charAt(4)):new Ant(Ant.TOTAL_LENGTH-23,s.charAt(4));

begin();
}
}

public void begin(){
while(true){
for(int i=0;i<4;i++)
//撞头
if(ant[i].isCollide(ant[i+1])){
ant[i].collide();
ant[i+1].collide();
// System.out.println("colliding...");
}
paseAndtimeIncrease();

if(allFinished()){
// System.out.println("all finished...");
System.out.println("time spent..."+getMaxTime());
break;
}
}
} private int getMaxTime() {
int tmp = ant[0].getUsedtime();
for(int i=0;i<5;i++){
if(tmp<ant[i].getUsedtime())
tmp = ant[i].getUsedtime();
}
return tmp;
} private boolean allFinished() {
return 
(ant[0].getCurrentpos()==Ant.TOTAL_LENGTH&&
ant[1].getCurrentpos()==Ant.TOTAL_LENGTH&&
ant[2].getCurrentpos()==Ant.TOTAL_LENGTH&&
ant[3].getCurrentpos()==Ant.TOTAL_LENGTH&&
ant[4].getCurrentpos()==Ant.TOTAL_LENGTH);
} private void paseAndtimeIncrease() {
for(int i=0;i<5;i++){
if(ant[i].getCurrentpos()<Ant.TOTAL_LENGTH){
ant[i].setUsedtime(ant[i].getUsedtime()+1);
ant[i].setCurrentpos(ant[i].getCurrentpos()+1);
}
// System.out.println("ant["+i+"]: "+ant[i].getCurrentpos()+"......"+ant[i].getUsedtime()+"....."+ant[i].getDerection());
}

}
}