posts - 82, comments - 269, trackbacks - 0, articles - 1
  BlogJava :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

百度面试题目的答案[原创]

Posted on 2006-11-10 16:46 itspy 阅读(11366) 评论(52)  编辑  收藏 所属分类: 小巧实例JAVA技术

最近有同学找工作,经常在班级群里发一些大公司的面试,笔试题目.昨天收到这样一个题目,据说是百度的面试题目.

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

看了这个题目之后,突然很感兴趣,今天搞了半天把它做出来了,大概花了1个半小时.大公司的题目真是考人.反正都已经用算法实现了,我就不多说了,大家看代码吧.代码里面注释我也尽量全写了.一共有两个类,一个是Ant的模型,一个是控制类.原代码,大家可以在这取得:

http://www.blogjava.net/Files/itspy/baidu.rar



//////////////////////////////////////
/*百度面试题
 * 有一根27厘米的细木杆,在第3厘米、7厘米、11厘米、17厘米、23厘米这五个位置上各有一只蚂蚁。
 * 木杆很细,不能同时通过一只蚂蚁。开始 时,蚂蚁的头朝左还是朝右是任意的,它们只会朝前走或调头,
 * 但不会后退。当任意两只蚂蚁碰头时,两只蚂蚁会同时调头朝反方向走。假设蚂蚁们每秒钟可以走一厘米的距离。
 * 编写程序,求所有蚂蚁都离开木杆 的最小时间和最大时间。
 *
 *
 * 分析:题目中的蚂蚁只可能相遇在整数点,不可以相遇在其它点,比如3.5cm处之类的,也就是可以让每只蚂蚁走 1秒,然后
 * 查看是否有相遇的即可.
 *
 * 这样我的程序实现思路就是,初始化5只蚂蚁,让每只蚂蚁走1秒,然后看是否有相遇的,如果有则做相应处理.当每只蚂蚁都
 * 走出木杆时,我就记录当前时间.这样就可以得到当前状态情况下,需要多久可以走出木杆,然后遍历所有状态则可以得到所胡
 * 可能.
 */

package baidu;

public class Ant {
 /*
  * step 表示蚂蚁每一个单位时间所走的长度
  */
 private final static int step = 1;

 /*
  * position表示蚂蚁所处的初始位置
  */
 private int position;

 /*
  * direction表示蚂蚁的前进方向,如果为1表示向27厘米的方向走, 如果为-1,则表示往0的方向走。
  */
 private int direction = 1;

 /*
  * 此函数运行一次,表示蚂蚁前进一个单位时间,如果已经走下木杆则会抛出异常
  */
 public void walk() {
  if (isOut()) {
   throw new RuntimeException("the ant is out");
  }
  position = position + this.direction * step;
 };


 /**
  * 检查蚂蚁是否已经走出木杆,如果走出返回true
  *
  */

 public boolean isOut() {
  return position <= 0 || position >= 27;
 }

 /**
  * 检查此蚂蚁是否已经遇到另外一只蚂蚁
  * @param ant
  * @return 如果遇到返回true
  */
 public boolean isEncounter(Ant ant) {
  return ant.position == this.position;
 }

 /**
  * 改变蚂蚁的前进方向
  */
 public void changeDistation() {
  direction = -1 * direction;
 }


 /**
  * 构造函数,设置蚂蚁的初始前进方向,和初始位置
  * @param position
  * @param direction
  */
 public Ant(int position, int direction) {
  this.position = position;
  if (direction != 1) {
   this.direction = -1;//方向设置初始位置,比如为0时,也将其设置为1.这样可以方便后面的处理
  } else {
   this.direction = 1;
  }
 }

}

 

/////////////////////////////////////////////////////////


package baidu;

public class Controller {

 public static void main(String[] args) {

  int time = 0;
  for (int i = 0; i < 32; i++) {
   Ant[] antArray = getAntList(getPoistions(), getDirections(i));
   while (!isAllOut(antArray)) {
    for (Ant ant : antArray) {
     if (!ant.isOut()) {
      ant.walk();
     }
    }
    time++;
    // 查看是否有已经相遇的Ant,如果有则更改其前进方向
    dealEncounter(antArray);
   }
   System.out.println(time);

   // 将时间归0,这样可以重新设置条件,再次得到全部走完所需要的时间.
   time = 0;
  }

 }

 /**
  * 这个函数的算法很乱,但暂时能解决问题
  *
  * @param list
  */
 public static void dealEncounter(Ant[] antArray) {

  int num_ant = antArray.length;
  for (int j = 0; j < num_ant; j++) {
   for (int k = j + 1; k < num_ant; k++) {
    if (antArray[j].isEncounter(antArray[k])) {
     antArray[j].changeDistation();
     antArray[k].changeDistation();
    }
   }
  }

 }

 /**
  * 因为有5只Ant,所以组合之后有32种组合.刚好用5位二进制来表示,如果为0则表示Ant往0的方向走 如果为1,则表示往27的方向走
  *
  * 注:在通过Ant的构造函数设置初始值时,通过过滤把0修改成了-1.
  */
 public static int[] getDirections(int seed) {
  int result[] = new int[5];
  result[0] = seed % 2;
  result[1] = seed / 2 % 2;
  result[2] = seed / 4 % 2;
  result[3] = seed / 8 % 2;
  result[4] = seed / 16 % 2;

  System.out.println("directions is " + result[0] + "|" + result[1] + "|"
    + result[2] + "|" + result[3] + "|" + result[4]);

  return result;

 }

 /**
  * 批量设置Ant的初始位置,这样设置不是十分必要,可以直接在代码中设置
  *
  * @return
  */
 public static int[] getPoistions() {
  return new int[] { 3, 7, 11, 17, 23 };
 }

 /**
  * 取得设置好初始值的5只Ant
  *
  * @param positions
  * @param directions
  * @return
  */
 public static Ant[] getAntList(int[] positions, int[] directions) {
  Ant ant3 = new Ant(positions[0], directions[0]);
  Ant ant7 = new Ant(positions[1], directions[1]);
  Ant ant11 = new Ant(positions[2], directions[2]);
  Ant ant17 = new Ant(positions[3], directions[3]);
  Ant ant23 = new Ant(positions[4], directions[4]);

  return new Ant[] { ant3, ant7, ant11, ant17, ant23 };
 }

 /**
  * 判断是否所有的Ant都已经走出了木杆,也就是设置退出条件
  *
  * @param antArray
  * @return
  */
 public static boolean isAllOut(Ant[] antArray) {
  for (Ant ant : antArray) {
   if (ant.isOut() == false) {
    return false;
   }
  }
  return true;
 }
}

 


评论

# re: 百度面试题目的答案[原创]  回复  更多评论   

2006-11-11 00:27 by 差沙
dealEncounter这里。
不相邻的蚂蚁是不会相遇的。

# re: 百度面试题目的答案[原创]  回复  更多评论   

2006-11-11 11:44 by itspy
是的,这个dealEncounter有很大改进的空间.不过你刚才说的这个我之前没有考虑到.

我之前只是考虑到了:有一些蚂蚁已经走出了木杆,就不用去处理了.不过实现起来有些不太方便.就没有去处理了.

所以在注释中,我也说明了这个dealEncounter肯定可以进行.


谢谢你的评论

# re: 百度面试题目的答案[原创]  回复  更多评论   

2006-11-11 15:29 by itspy
改进后的dealEncounter为,谢谢差沙的回复


/**
* 这个函数的算法很乱,但暂时能解决问题
*
* @param list
*/
public static void dealEncounter(Ant[] antArray) {

int num_ant = antArray.length;
for (int j = 0; j < num_ant-1; j++) {
if (antArray[j].isEncounter(antArray[j + 1])) {
antArray[j].changeDistation();
antArray[j + 1].changeDistation();

}
}

}

# re: 百度面试题目的答案[原创]  回复  更多评论   

2006-11-12 11:13 by 路过
/*百度面试题
* 有一根27厘米的细木杆,在第3厘米、7厘米、11厘米、17厘米、23厘米这五个位置上各有一只蚂蚁。
* 木杆很细,不能同时通过一只蚂蚁。开始 时,蚂蚁的头朝左还是朝右是任意的,它们只会朝前走或调头,
* 但不会后退。当任意两只蚂蚁碰头时,两只蚂蚁会同时调头朝反方向走。假设蚂蚁们每秒钟可以走一厘米的距离。
* 编写程序,求所有蚂蚁都离开木杆 的最小时间和最大时间。
*
*/
public class TestMain {
/**
* @param args
*/
public static void main(String[] args) {
AntSubjectCalculate calculate=new AntSubjectCalculate(27,1000);
Ant ant1=new Ant(calculate,1,true,3,null);
ant1.setName("a");
Ant ant2=new Ant(calculate,1,true,7,ant1);
ant2.setName("b");
Ant ant3=new Ant(calculate,1,false,11,ant2);
ant3.setName("c");
Ant ant4=new Ant(calculate,1,false,17,ant3);
ant4.setName("d");
Ant ant5=new Ant(calculate,1,false,23,ant4);
ant5.setName("e");
calculate.notifyAllObjects();//开始运行
System.out.println("总共用时:"+calculate.sumTime());
}

}

# re: 百度面试题目的答案[原创]  回复  更多评论   

2006-11-12 11:14 by 路过
public class Ant implements Subject,Runnable {
private long position;//位置
private String name;//名字
private int rate;//速度
private int useTime;//走完全程用时
private boolean isStop;//停止,说明是否已经走出木杆,是则true,否则false
private boolean forWord;//蚂蚁的前进方向false为负,true为正
//private int distance;//每次的间隔的路程
private List observers =new ArrayList();
private Ant frontAnt;//前一个蚂蚁
public void run() {
try{
notifyObservers();
}catch(Exception e){
e.printStackTrace();
}
}
/*public int getDistance(){
return this.distance;
}
public void setDistance(int increment){
this.useTime+=increment;
this.distance=this.rate*increment;
}*/
public void seIsStop(boolean isStop){
this.isStop=isStop;
}
public boolean isStop(){
return this.isStop;
}

public void setUseTime(int useTime){
this.useTime=useTime;
}
public int getUseTime(){
return this.useTime;
}
public void setFrontAnt(Ant frontAnt){
this.frontAnt=frontAnt;
}
public Ant getFrontAnt(){
return this.frontAnt;
}
public Ant(EveryCalculate concreteCalculate,int rate,boolean forWord,long position,Ant frontAnt){
this.rate=rate;
this.position=position;
this.forWord=forWord;
this.isStop=false;
setFrontAnt(frontAnt);
concreteCalculate.add(this);
attach((Observer)concreteCalculate);
}
public void attach(Observer observer) {
observers.add(observer);
}

public void detach(Observer observer) {
observers.remove(observer);
}

public void notifyObservers()throws Exception{
for(Iterator it=observers.iterator();it.hasNext();){
Observer observer=(Observer)it.next();
observer.update(this);
}
}

public boolean isForWord() {
return forWord;
}
public void setForWord(boolean forWord) {
this.forWord = forWord;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public long getPosition() {
return position;
}
//改变蚂蚁的前进方向,当和前一个蚂蚁相遇时就两只蚂蚁都调头
public void setPosition(long position) {
this.position = position;
}
public int getRate() {
return rate;
}
public void setRate(int rate) {
this.rate = rate;
}
public void inverse(){
this.forWord=!this.forWord;
}
}

# re: 百度面试题目的答案[原创]  回复  更多评论   

2006-11-12 11:14 by 路过
public interface Observer {
public void update(Subject object)throws Exception;
}

# re: 百度面试题目的答案[原创]  回复  更多评论   

2006-11-12 11:15 by 路过
/*
* 抽像层,提供了要加入计算的对象集合,继承的子类要实现他们自已的运算规则
*/
public abstract class EveryCalculate {
protected List calculates=new ArrayList();//每个要计算的对象
public abstract void calculate(Object object)throws Exception;//每种算法
public void add(Object object){
calculates.add(object);
}
public void remove(Object object){
calculates.remove(object);
}
public Iterator iterator(){
return calculates.iterator();
}
public int size(){
return calculates.size();
}
public abstract void notifyAllObjects ();
}

# re: 百度面试题目的答案[原创]  回复  更多评论   

2006-11-12 11:15 by 路过
public interface Subject {
public void attach(Observer observer);
public void detach(Observer observer);
public void notifyObservers()throws Exception;
}

# re: 百度面试题目的答案[原创]  回复  更多评论   

2006-11-12 11:16 by 路过
/*
* 实现运算规则
*/
public class AntSubjectCalculate extends EveryCalculate implements Observer {
private final int length;
private final long incrementTime;//表示蚂蚁前进一个单位时间,间隔时间以毫秒计算
private int useTime;
public AntSubjectCalculate(int length,long incrementTime){
this.length=length;
this.incrementTime=incrementTime;
}
public void calculate(Object object)throws Exception{
Ant ant=(Ant)object;//在算法中确定他的前后节点
int second=(int)this.getSecond(this.incrementTime);//每秒
ant.setUseTime(ant.getUseTime()+second);
if(ant.isForWord())
ant.setPosition(ant.getRate()* second+ant.getPosition());
else
ant.setPosition(ant.getPosition()-ant.getRate()*second);
Ant frontAnt = ant.getFrontAnt();
//当两个蚂蚁走到同一点时就转向
if(frontAnt!=null && frontAnt.getPosition()>= ant.getPosition()){
System.out.println("蚂蚁:"+ant.getName()+"和"+frontAnt.getName()+"转向了!");
ant.inverse();
frontAnt.inverse();
}
if(ant.getPosition() >= this.getLength() || ant.getPosition() <= 0){
ant.seIsStop(true);//停止这个蚂蚁的行动!
if(ant.getUseTime()>this.useTime){
this.useTime = ant.getUseTime();//保存最后一只蚂蚁的时间
}
System.out.println("蚂蚁:"+ant.getName()+"已出木杆,用时:" + ant.getUseTime());
}
System.out.println("蚂蚁:"+ant.getName()+"位置"+ant.getPosition());
}
//这个方法也可移出去,作为一个外层的控制触了器来用,主要模拟蚂蚁开始行走的情况
public void notifyAllObjects (){
while(this.size()>0){
for(Iterator it=this.iterator();it.hasNext();){
Ant ant=(Ant)it.next();
ant.run();
if(ant.isStop()){
it.remove();
}
}
}
}
public void update(Subject object)throws Exception{
calculate(object);
}
public int getLength(){
return this.length;
}
public long sumTime(){
return useTime;
}
public long getIncrementTime(){
return this.incrementTime;
}
//算成秒
public long getSecond(long time){
return time/1000;
}
}

# re: 百度面试题目的答案[原创]  回复  更多评论   

2006-11-12 11:21 by 路过
我是用观察者模式实现的。实现之前,没有看原创的实现,只按自已的想法写了这段代码!不是为了比较谁好谁坏,只不过想了表一下自已的一些见解,因为代码是相通的,只是实现手法不一相而已。欢迎相互交流,我的邮箱是yoohoo.lai@163.com

# re: 百度面试题目的答案[原创]  回复  更多评论   

2006-11-12 11:24 by 路过
外面代码入口在public class TestMain 之中,由于没加更多注释.可能看起来有点费力

# re: 百度面试题目的答案[原创]  回复  更多评论   

2006-11-12 15:49 by itspy
@路过
之前我也想过用观察者模式来实现,但是在最后写出了Ant的模式之后,发现不用这个模式也很容易实现,也就没有用这个模式了.

谢谢讨论

# re: 百度面试题目的答案[原创]  回复  更多评论   

2006-11-12 18:56 by 路过
其实代码的实现,是有多种方法的,但如果百度的题目改一下可能要用N只蚂蚁,用不同的速度离开时,这时侯,就可能要改算法,而我实现这个的目的就在于,如果提出了这个要求我只要,另写一个实现算法就能实现另外的题目public class *Calculate extends EveryCalculate implements Observer
而不用更改其它代码!这也是我为什么会考虑用观察者实现的原因了!

# re: 百度面试题目的答案[原创]  回复  更多评论   

2006-11-12 19:08 by 路过
不相邻的蚂蚁,我的做法是直接在Ant类中用链表结构定义的。其实细仔想起来这个这一层应该跟业务对象隔离开来!蚂蚁的排列规则,应该在写一个接口和实现类去定义,这样当改变排列顺序的时侯也只要多写一个实现类而已!

# re: 百度面试题目的答案[原创]  回复  更多评论   

2006-11-12 21:11 by itspy
你说的很对,其实之前我也考虑过这个问题,百度刚好把Ant放置在了几个特别的位置.这时几个Ant只可能在整数点相遇.比如要是有一个Ant在5处,有一个在8处.这时我们实现时,可能就不能一厘米一厘米的走了.


不错,你的实现确实比我要好多了.

# re: 百度面试题目的答案[原创]  回复  更多评论   

2006-11-13 16:30 by xinheqishi
楼上的兄弟们,你们是不是把问题复杂化了??

如果五个蚂蚁最初的状态已经确定,那么全部离开木杆的时间已经确定。所以问题的关键是如何决定蚂蚁最初的状态。

1.把木杆根据中点分为左半部分和右半部分。
2.作为一只蚂蚁,要想最快地离开木杆,首先是判断自己属于木杆的哪部分。如果是左,则向左走;如果是右,就向右走。这样就可最快地离开木杆。
3.如果是想最慢地离开木杆,只需改成相反规则就可:如果是左,则向右走;如果是右,就向左走。这个有点意思,可能有人怀疑,真的是这样吗?

问题就是这么简单,呵呵。


# re: 百度面试题目的答案[原创]  回复  更多评论   

2006-11-13 17:16 by itspy
@xinheqishi

楼上说的第3点,在这个场景中是对的,但不知道如何去证明他的通用性.如第3点不成立的话,则只好使用遍历去找出所有的时间了.

通过遍历查找,有32种可能的方向组合,但有16种"并列"为最慢.
当然,最快的只有一种,就是你说的那种


哪个能想办法证明一下这一点吗?
3.如果是想最慢地离开木杆,只需改成相反规则就可:如果是左,则向右走;如果是右,就向左走。这个有点意思,可能有人怀疑,真的是这样吗?

# re: 百度面试题目的答案[原创]  回复  更多评论   

2006-11-13 19:31 by joycsharp
通过算各个蚂蚁运动的路程可以算出每个蚂蚁的运动时间

主要控制部分:
int[] pos ={ 3, 7, 11, 17, 23 }; //位置
ArrayList antlist = new ArrayList(); //存放运行中蚂蚁
Random ran = new Random();
foreach (int p in pos)
{
int speed = ran.Next(11) % 2 == 0 ? 1 : -1; //随机方向,1 or -1
Console.WriteLine(p.ToString() + ":" + speed.ToString());
antlist.Add(new Ant(p,speed));
}
while (antlist.Count > 0)
{
ArrayList delete = new ArrayList(); //以出杆的蚂蚁
foreach (Ant a in antlist)
{
a.movenext();
if (a.isout) //出杆
{
delete.Add(a);
}
}
foreach(Ant a in delete) //在antlist删除已出杆的蚂蚁
{
antlist.Remove(a);
}
delete.Clear();
for (int i = 0; i < antlist.Count; i++) //判断此时是否有相遇的,如有,各自掉头
{
for (int j = i; j < antlist.Count; j++)
{
Ant a = (Ant)antlist[i];
Ant b = (Ant)antlist[j];
if (a.pos == b.pos)
{
if (a.speed + b.speed == 0)
{
a.speed = -a.speed;
b.speed = -b.speed;
}
}
}
}
}


//ant类



public class Ant
{
public int pos; //初始位置
public int speed; //速度
public bool isout = false;
int totaldistance = 0; //运动总距离
public Ant(int pos,int speed)
{
this.pos = pos;
this.speed = speed;
}
public void movenext()
{
if (pos <= 0 || pos >= 27) //判断是否出杆
{
isout = true;
Console.WriteLine("out:" + this.totaldistance.ToString());
}
else
{
totaldistance += Math.Abs(speed);
pos += speed;
}
}
}


大致算了下,好象没错误。c#编写

# re: 百度面试题目的答案[原创]  回复  更多评论   

2006-11-13 19:39 by joycsharp
觉得此题比较有迷惑性,蚂蚁碰头后各自掉头,实际整个过程中蚂蚁都在运动,如果能算出蚂蚁走的总路程,那么蚂蚁的运动时间也就能得出。觉得这样算法会简单许多

# re: 百度面试题目的答案[原创]  回复  更多评论   

2006-11-14 08:55 by 路过
楼上说的观点和我的初衷的出发点是不一样的,如果就是了解决这个问题其实方法可以很简单,这个题目不就为了算出五只蚂蚁离开一个杆子吗?其实只要抓住一点就行,就是比较最后一只离开杆子的蚂蚁走的总的路程就可以了。路程最短的也就最快,路程最大的就最慢!应用数学上一些算法就能解决。这根本用不着一个一个按间隔时间遍历,耗这个性能在里面。
之所以用模式的东西去解决问题,其实是把这道题模拟了一下蚂蚁的行走的场景。注重的是他的扩展性,而不是算法本身!

# re: 百度面试题目的答案[原创]  回复  更多评论   

2006-11-14 09:04 by 路过
所以从算法的角度来讲这个是把简单的东西复杂化,这是没必要的!从软件的开闭原则来讲,这些也不算什么!

# re: 百度面试题目的答案[原创]  回复  更多评论   

2006-11-14 09:33 by xinheqishi
哪个能想办法证明一下这一点吗?
3.如果是想最慢地离开木杆,只需改成相反规则就可:如果是左,则向右走;如果是右,就向左走。这个有点意思,可能有人怀疑,真的是这样吗?

×××××××××××××××××××××××××××××××××××××××××
楼主你好,我是凭着对数学的一种直觉得出这个结论的。并没有经过严格的证明,忽悠了一下楼主,呵呵。见笑见笑!

当时我是这么想的,把左边的所有蚂蚁作为一个整体,右边的作为一个整体,哪么这个情形就跟木杆上只有两只蚂蚁的情形就一样了。这是从纯数学的角度去思考。

我觉得从解决问题的角度,应该是这种思路,直奔主题。简单的问题就尽量用简单的方法解决。

Java编程方面,我只是一个初学者,我还得谢谢楼主,让我又多学了点。

# re: 百度面试题目的答案[原创]  回复  更多评论   

2006-11-14 09:37 by xinheqishi
之所以用模式的东西去解决问题,其实是把这道题模拟了一下蚂蚁的行走的场景。注重的是他的扩展性,而不是算法本身!

×××××××××××××××××××××××××××××××××××××××××
从学东西的角度,我是认可这个观点的。

# re: 百度面试题目的答案[原创]  回复  更多评论   

2006-11-14 10:17 by xinheqishi
模拟了一下蚂蚁的行走的场景。

关于这点,我当时还有这么一个想法:设计两个类,一个是蚂蚁,一个是木杆。
木杆用来记录状态,如某点上的值为0表示该点上没有蚂蚁,为1表示有一个蚂蚁,为2表示有两个蚂蚁(即碰撞)。蚂蚁从A走到B,A上的值减1,B上的值加1。木杆上只要发生有X点值为2的情况,马上就让X点的两个蚂蚁调头。

问下大家这个思路是否可行?

# re: 百度面试题目的答案[原创]  回复  更多评论   

2006-11-14 10:20 by joycsharp
整理成模式应该不是件难事把,既然是面视的题目,就要简单快速的解决问题,这才是重要

# re: 百度面试题目的答案[原创]  回复  更多评论   

2006-11-14 10:57 by xinheqishi
楼上的兄弟,实话说,Java方面我只是个新手,设计模式也还没怎么接触,不过挺有兴趣的。还请兄弟多指教。你的代码我看了,感觉我的思路跟你的观察者模式是类似的。木杆就相当于是个观察者了吧?

# re: 百度面试题目的答案[原创]  回复  更多评论   

2006-11-17 10:35 by thinker[匿名]
楼上说的第3点,在这个场景中是对的,但不知道如何去证明他的通用性.如第3点不成立的话,则只好使用遍历去找出所有的时间了.

通过遍历查找,有32种可能的方向组合,但有16种"并列"为最慢.
当然,最快的只有一种,就是你说的那种

============
最快的摆放

1.把木杆根据中点分为左半部分和右半部分。
2.作为一只蚂蚁,要想最快地离开木杆,首先是判断自己属于木杆的哪部分。如果是左,则向左走;如果是右,就向右走。这样就可最快地离开木杆。

最慢的摆放
1, 除非在中点,每只蚂蚁离开木杆都有一个近端距离, 远端距离
2, 只要保证5只蚂蚁中 远端距离最长的蚂蚁面向远端, 其他的蚂蚁随便摆放即可。 所以在"32种可能的方向组合,有16种并列为最慢".

程序懒得写了 最多10行解决问题

# re: 百度面试题目的答案[原创]  回复  更多评论   

2006-11-17 14:32 by itspy
回复楼上:
我想这个题目让人来做,肯定比电脑快.所以楼上才能这么游刃有余的这样分析,找出答案 .

1)你如何让程序找出:5只蚂蚁中哪个的远端距离最长?
2)远端距离如何定义?要知道每只蚂蚁的方向的改变最终可能都会影响到其它的蚂蚁的爬行距离.远端距离可能并不好算.

这两个问题我不大会解决,更不用说10行代码了,这个请楼帮忙说清楚些,或者是其它有人明白的,讲讲也行.

# re: 百度面试题目的答案[原创]  回复  更多评论   

2006-11-20 10:57 by thinker[匿名]
以题目为例
"有一根27厘米的细木杆,在第3厘米、7厘米、11厘米、17厘米、23厘米这五个位置上各有一只蚂蚁"

3cm 的 (近端3,远端24)
7 (7,20)
11 (11,16)
17 (10,17)
23 (4,23)

所以只要保证3 厘米的蚂蚁面向24的一端 其他的蚂蚁随便摆

把碰撞简化成AB相遇延a,b原方向继续前进,即可求出最大时间 就是最大的远端距离/速度。

词解法可以用于任意位置 任意速度, 但必须保证每个蚂蚁速度相同

# re: 百度面试题目的答案[原创]  回复  更多评论   

2006-11-20 11:13 by itspy
楼上的解法十分简单明白,不过我还是有些不解^_^。


于是想找个反例,但找了半天,也没找到。


# re: 百度面试题目的答案[原创]  回复  更多评论   

2006-11-20 14:58 by thinker[匿名]
没有反例的啦, 哪怕有10000只蚂蚁在上面, 只要保证最远端的蚂蚁面向远端, 最长的时间就是最远端/速度。

这道题最大的迷惑项 是相撞, 如果转换成只是相遇,擦肩而过就好理解了,并且这种转化不影响结果。

假设A B相向而行,A距远端的距离为a, B为b, A B各自走了距离c以后相遇,碰撞,反向, A要走(b-c)距离, B要走(a-c), 总共A走了b, B走了a距离。所以max(a,b)就是最远距离,相撞还是擦肩而过只是影响到是A走了a还是走了b, 对整体答案没有影响。

应该可以有更缜密的数学推理,我的数学很差,就不献丑了。

# re: 百度面试题目的答案[原创]  回复  更多评论   

2006-11-20 15:34 by itspy
这道题最大的迷惑项 是相撞, 如果转换成只是相遇,擦肩而过就好理解了。


可能大部分看过这个帖子的人都被这个迷惑。反正我是被迷惑了。

# re: 百度面试题目的答案[原创]  回复  更多评论   

2006-12-06 14:55 by hyry
呵呵,这个题目有意思,看上去复杂,其实简单。我的理解是如果蚂蚁转身不需要时间,而且所有的蚂蚁都长得一样,而且我眼神也不好的话,那么两只蚂蚁是碰撞还是擦肩而过,看上去都一样,反正我看到的先是两个黑点靠近,然后这两个黑点碰到一起,然后又分开。

# re: 百度面试题目的答案[原创]  回复  更多评论   

2006-12-06 16:30 by xinheqishi
哈,回来看看,看见楼上,^_^,高!

# re: 百度面试题目的答案[原创]  回复  更多评论   

2007-01-18 20:19 by ahuan
好多聪明人,thinker果然是个思考者.

# re: 百度面试题目的答案[原创]  回复  更多评论   

2007-02-12 15:51 by Signture.updata(土豆)
高! thinker 是个高人啊,能够看到本质问题。

# re: 百度面试题目的答案[原创]  回复  更多评论   

2007-03-30 09:41 by 大河
高!!!

这才叫解决问题呢。。。
编码编了变天,都看不懂,屁用!!!

# re: 百度面试题目的答案[原创]  回复  更多评论   

2007-06-27 12:33 by suntao19830709@gmail.com
/**
* Copyright 1994-2006. EMC Corporation. All Rights Reserved.
*/
package ant;

/**
*
* @version ${version}, Jun 27, 2007 11:23:46 AM
* @author Tao Sun (Sun_Tao@emc.com)
* @since JDK1.5
*/
public class Ant
{
public int direction = 1;
public int distance = 0;
public int maxDistance = 1;

public Ant(int distance, int direction, int maxDistance)
{
this.direction = direction;
this.distance = distance;
this.maxDistance = maxDistance;
}

public int getDistance()
{
return distance;
}

public void move()
{
if(!isOut())
{
distance += direction;
}
}

private void changeDirection()
{
direction = direction == 1? -1 : 1;
}

public void check(int distance1, int distance2, int distance3, int distance4)
{
if(distance == distance1||distance == distance2||distance == distance3||distance == distance4)
{
changeDirection();
}
}

public boolean isOut()
{
return distance == 0 || distance == maxDistance;
}
}


/**
* Copyright 1994-2006. EMC Corporation. All Rights Reserved.
*/
package ant;

/**
* @version ${version}, Jun 27, 2007 11:37:34 AM
* @author Tao Sun (Sun_Tao@emc.com)
* @since JDK1.5
*/
public class Run
{
public static void main(String[] args)
{
for(int i = 0; i<32; i++)
{
String str = Integer.toBinaryString(i);
str = formatString(str);
Ant ant1 = new Ant(3, getDirection(str, 0), 27);
Ant ant2 = new Ant(7, getDirection(str, 1), 27);
Ant ant3 = new Ant(11, getDirection(str, 2), 27);
Ant ant4 = new Ant(17, getDirection(str, 3), 27);
Ant ant5 = new Ant(23, getDirection(str, 4), 27);
run(ant1, ant2, ant3, ant4, ant5);
}
}

private static void run(Ant ant1, Ant ant2,Ant ant3, Ant ant4, Ant ant5)
{
int i = 0;
while (!(ant1.isOut()&&ant2.isOut()&&ant3.isOut()&&ant4.isOut()&&ant5.isOut()))
{
ant1.move();
ant2.move();
ant3.move();
ant4.move();
ant5.move();
checkAnt(ant1, ant2,ant3, ant4,ant5);
i++;
}
System.out.println(i);
}

private static void checkAnt(Ant ant1, Ant ant2,Ant ant3, Ant ant4, Ant ant5)
{
int distance1 = ant1.getDistance();
int distance2 = ant2.getDistance();
int distance3 = ant3.getDistance();
int distance4 = ant4.getDistance();
int distance5 = ant5.getDistance();
ant1.check(distance2, distance3, distance4, distance5);
ant2.check(distance1, distance3, distance4, distance5);
ant3.check(distance1, distance2, distance4, distance5);
ant4.check(distance1, distance2, distance3, distance5);
ant5.check(distance1, distance2, distance3, distance4);
}


private static int getDirection(String str, int i)
{
if(str.charAt(i)=='0')
{
return -1;
}
else
{
return 1;
}
}

private static String formatString(String str)
{
int length = str.length();
for(int i = 0; i< 5 - length ; i++)
{
str = "0" + str;
}
return str;
}
}

# re: 百度面试题目的答案[原创]  回复  更多评论   

2007-06-27 12:40 by suntao19830709@gmail.com
俺上面的代码没写注释,但相信有一定编程经验的很容易看懂.关键的一个地方就是5个蚂蚁的方向就是2的5次方种可能,故用0-31的2进制数的对应位是1还是0来表示方向.

# re: 百度面试题目的答案[原创]  回复  更多评论   

2007-06-27 13:07 by suntao19830709@gmail.com
其实编程归编程,其实还有个更深刻的原理.就是楼上各位已经分析过的.
1:微观上看a蚂蚁和b蚂蚁相遇后是调头了.即a现在是沿着b本应该走的路走了,b沿着a本应该走的路继续走.
2:宏观上如果把a蚂蚁和b蚂蚁看成是完全一样的蚂蚁,那么相当于两个蚂蚁都没有调头.
3:如果一时想不明白,可以想最简单的情形,就只有两只蚂蚁从棍子两端相向而行,在中间遇到后调头,是不是跟没调头一样呢???
4:这就是有名的鬼魂理论,跟物理上的动量守恒很类似.

# re: 百度面试题目的答案[原创]  回复  更多评论   

2007-06-27 13:34 by suntao19830709@gmail.com
数学归纳证明来了...
1:假设如果不碰头,有一个蚂蚁a0的需要走的距离为S0.时间为t0,所有蚂蚁速度为v,则s0=v*t0.同理,还有一个蚂蚁a1,需要走的距离为S1,时间为t1, s1= v*t1.
2:当a0遇到a1的时候,假设走了t秒,a1剩的距离为s0-v*t.因此a1剩的距离为v*t0-v*t,剩下的时间为t0-t,恰好为a0本来走到头需要的时间.因此此时a1总共需要走出的时间为t0.而a0需要走出的时间总共为t1.
3:一般来说,当蚂蚁aN遇到a(N+1)的时候,aN原本需要的总共的时间tN被赋给了a(N+1),而t(N+1)被赋给了aN.
4:因此n只蚂蚁如果遇到不调头走出需要的时间分别为t1,t2,....tN,那么每一次有蚂蚁碰头的时候,他们需要的时间仍然为t1,t2,....tN,只是具体哪只蚂蚁需要多少时间可能互相有交换.
5:因此最大最小时间就是最后一只能走出去的蚂蚁的最大最小时间.

# re: 百度面试题目的答案[原创]  回复  更多评论   

2007-07-10 07:24 by zhanghk
有个问题,如果所有蚂蚁的初始状态都确定了,所有走出去应该只有一个时间,何来最小时间和最大时间?

# re: 百度面试题目的答案[原创]  回复  更多评论   

2007-08-24 17:15 by 林林
这道题求最长时间只能用编程来解决。
Thinker所说的理解看似很对,但有漏洞,我这里只简单的举个反例吧。
还是长度27厘米的树杆,只有三只蚂蚁,3厘米有一只,7厘米有一只,25厘米有一只。3厘米向右,7厘米向左,25厘米向左,最后所花时间为27厘米/速度。
而如果7厘米和25厘米得蚂蚁都向右,那么所花时间为24厘米/速度。
如果按Thinker所说把3厘米的向右,其他随便摆,怎么找出这两个谁大啊,所以还是要遍历的

# re: 百度面试题目的答案[原创][未登录]  回复  更多评论   

2007-10-12 14:26 by Allen
@林林
Thinker的理解没有错,是你搞错了一个地方。Thinker说的是最远端的蚂蚁朝向远端,因此在你的例子里面,应该是25厘米的蚂蚁朝左,而其他的蚂蚁随便摆,这样才是最大时间。

# re: 百度面试题目的答案[原创][未登录]  回复  更多评论   

2007-10-12 14:29 by Allen
有个问题,如果所有蚂蚁的初始状态都确定了,所有走出去应该只有一个时间,何来最小时间和最大时间?
==============================================

题目中说了:蚂蚁的头向左向右是随机的,所以初始状态不是确定的,这样就有最小时间和最大时间。

# re: 百度面试题目的答案[原创]  回复  更多评论   

2007-10-21 15:02 by lovegiven
toooooooooooooooooooooooooold
就是一个穿过的问题,不用写程序,微软也考过

# re: 百度面试题目的答案[原创]  回复  更多评论   

2007-10-24 12:40 by cnc224
贪心,相遇当成路过

# re: 百度面试题目的答案[原创]  回复  更多评论   

2007-10-25 20:49 by ysuncn
#include<iostream>
using namespace std;
class ant
{
public:
bool orient; //0-left;1-right;
short pos; //1-27;
bool onbar; //0-off;1-on;
void meet()
{
orient=orient>0?0:1;
}
void move()
{
if(orient==0) pos--;
else pos++;
if(pos==0||pos==28)onbar=0;
}
};
int main()
{
ant a1,a2,a3,a4,a5;
cout<<"orient(0-left;1-right)"<<endl;
for(int i1=0;i1<=1;i1++)
for(int i2=0;i2<=1;i2++)
for(int i3=0;i3<=1;i3++)
for(int i4=0;i4<=1;i4++)
for(int i5=0;i5<=1;i5++)
{
a1.orient=i1;a2.orient=i2;a3.orient=i3;a4.orient=i4;a5.orient=i5;
a1.pos=3;a2.pos=7;a3.pos=11;a4.pos=17;a5.pos=23;
a1.onbar=1;a2.onbar=1;a3.onbar=1;a4.onbar=1;a5.onbar=1;

cout<<"orient:"<<a1.orient<<a2.orient<<a3.orient<<a4.orient<<a5.orient<<" ";
short time=0;
while(a1.onbar||a2.onbar||a3.onbar||a4.onbar||a5.onbar)
{
if(a1.onbar) a1.move();
if(a2.onbar) a2.move();
if(a3.onbar) a3.move();
if(a4.onbar) a4.move();
if(a5.onbar) a5.move();
if(a1.pos+1==a2.pos&&a1.onbar&&a2.onbar){a1.meet();a2.meet();}
if(a2.pos+1==a3.pos&&a2.onbar&&a3.onbar){a2.meet();a3.meet();}
if(a3.pos+1==a4.pos&&a3.onbar&&a4.onbar){a3.meet();a4.meet();}
if(a4.pos+1==a5.pos&&a4.onbar&&a5.onbar){a4.meet();a5.meet();}
time++;
}
cout<<"cost time:"<<time<<"s"<<endl;
}
}


orient(0-left;1-right)
orient:00000 cost time:23s
orient:00001 cost time:17s
orient:00010 cost time:23s
orient:00011 cost time:11s
orient:00100 cost time:23s
orient:00101 cost time:17s
orient:00110 cost time:23s
orient:00111 cost time:17s
orient:01000 cost time:23s
orient:01001 cost time:21s
orient:01010 cost time:23s
orient:01011 cost time:21s
orient:01100 cost time:23s
orient:01101 cost time:21s
orient:01110 cost time:23s
orient:01111 cost time:21s
orient:10000 cost time:25s
orient:10001 cost time:25s
orient:10010 cost time:25s
orient:10011 cost time:25s
orient:10100 cost time:25s
orient:10101 cost time:25s
orient:10110 cost time:25s
orient:10111 cost time:25s
orient:11000 cost time:25s
orient:11001 cost time:25s
orient:11010 cost time:25s
orient:11011 cost time:25s
orient:11100 cost time:25s
orient:11101 cost time:25s
orient:11110 cost time:25s
orient:11111 cost time:25s

# re: 百度面试题目的答案[原创]  回复  更多评论   

2007-10-25 21:00 by ysuncn
@ysuncn小马虎一下,呵呵bar 0-27

#include<iostream>
using namespace std;
class ant
{
public:
bool orient; //0-left;1-right;
short pos; //0-27;
bool onbar; //0-off;1-on;
void meet()
{
orient=orient>0?0:1;
}
void move()
{
if(orient==0) pos--;
else pos++;
if(pos==0||pos==27)onbar=0;
}
};
int main()
{
ant a1,a2,a3,a4,a5;
cout<<"orient(0-left;1-right)"<<endl;
for(int i1=0;i1<=1;i1++)
for(int i2=0;i2<=1;i2++)
for(int i3=0;i3<=1;i3++)
for(int i4=0;i4<=1;i4++)
for(int i5=0;i5<=1;i5++)
{
a1.orient=i1;a2.orient=i2;a3.orient=i3;a4.orient=i4;a5.orient=i5;
a1.pos=3;a2.pos=7;a3.pos=11;a4.pos=17;a5.pos=23;
a1.onbar=1;a2.onbar=1;a3.onbar=1;a4.onbar=1;a5.onbar=1;

cout<<"orient:"<<a1.orient<<a2.orient<<a3.orient<<a4.orient<<a5.orient<<" ";
short time=0;
while(a1.onbar||a2.onbar||a3.onbar||a4.onbar||a5.onbar)
{
if(a1.onbar) a1.move();
if(a2.onbar) a2.move();
if(a3.onbar) a3.move();
if(a4.onbar) a4.move();
if(a5.onbar) a5.move();
if(a1.pos+1==a2.pos&&a1.onbar&&a2.onbar){a1.meet();a2.meet();}
if(a2.pos+1==a3.pos&&a2.onbar&&a3.onbar){a2.meet();a3.meet();}
if(a3.pos+1==a4.pos&&a3.onbar&&a4.onbar){a3.meet();a4.meet();}
if(a4.pos+1==a5.pos&&a4.onbar&&a5.onbar){a4.meet();a5.meet();}
time++;
}
cout<<"cost time:"<<time<<"s"<<endl;
}
}

orient(0-left;1-right)
orient:00000 cost time:23s
orient:00001 cost time:17s
orient:00010 cost time:23s
orient:00011 cost time:11s
orient:00100 cost time:23s
orient:00101 cost time:17s
orient:00110 cost time:23s
orient:00111 cost time:16s
orient:01000 cost time:23s
orient:01001 cost time:20s
orient:01010 cost time:23s
orient:01011 cost time:20s
orient:01100 cost time:23s
orient:01101 cost time:20s
orient:01110 cost time:23s
orient:01111 cost time:20s
orient:10000 cost time:24s
orient:10001 cost time:24s
orient:10010 cost time:24s
orient:10011 cost time:24s
orient:10100 cost time:24s
orient:10101 cost time:24s
orient:10110 cost time:24s
orient:10111 cost time:24s
orient:11000 cost time:24s
orient:11001 cost time:24s
orient:11010 cost time:24s
orient:11011 cost time:24s
orient:11100 cost time:24s
orient:11101 cost time:24s
orient:11110 cost time:24s
orient:11111 cost time:24s


# re: 百度面试题目的答案[原创][未登录]  回复  更多评论   

2007-10-31 15:18 by javaa
又学到东西了^_^

# re: 百度面试题目的答案[原创]  回复  更多评论   

2007-11-14 09:21 by 王者之剑
thinker是高手,一分钟内可以解决的问题,有人写这么长程序
(看不懂的,你们完了,哈哈,开玩笑的)

# re: 百度面试题目的答案[原创]  回复  更多评论   

2008-04-01 10:54 by xiepan

#include <iostream>
#include <vector>
#include <cmath>
#include <bitset>

using namespace std;

typedef struct tagANT
{
int pos;
bool bleft;
}ANT;

vector<ANT> vAnts(5);

void InitAntsState(int seed)
{
bitset<5> bit(seed);

for(int i=0; i<(int)vAnts.size(); i++)
{
if(!bit.test(i))
vAnts[i].bleft = true;
else
vAnts[i].bleft = false;
}

vAnts[0].pos = 3;
vAnts[1].pos = 7;
vAnts[2].pos = 11;
vAnts[3].pos = 17;
vAnts[4].pos = 23;
}

int main()
{
for(int seed = 0; seed <= 31; seed ++)
{
InitAntsState(seed);

int nTimeTicked = 0;
while (true)
{
int nAntsExitNum = 0;
for(int i=0; i<(int)vAnts.size(); i++)
{
if(vAnts[i].pos >=0 && vAnts[i].pos <= 27)
nAntsExitNum ++;

if( ((i+1) < (int)vAnts.size()) && (vAnts[i].bleft != vAnts[i+1].bleft)
&& (abs(vAnts[i].pos - vAnts[i+1].pos) == 1))
{
vAnts[i].bleft = !vAnts[i].bleft;
vAnts[i+1].bleft = !vAnts[i+1].bleft;
}

if(vAnts[i].bleft)
{
vAnts[i].pos --;
}
else
{
vAnts[i].pos ++;
}
}

if(nAntsExitNum == 0)
break;

nTimeTicked++;
}

bitset<5> bits(seed);
for(int i=0; i<5; i++)
{
if(!bits.test(i))
{
cout << "L, ";
}
else
{
cout << "R, ";
}
}

cout << " <time " << nTimeTicked << " sec>" << endl;
}


cin.get();
}

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


网站导航: