有关蚂蚁的笔试题目

前几天，我参加某公司的笔试，遇到如下题目

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

 当时急急忙忙写了一下，写得不是很完整，现在重新写下，和大家分享

import java.util.*;
public class MaYi
{
	public final static int FORWARD = 1;//向前走
	public final static int BACKWARD = -1;//向后走
	public int location;//位置
	public int direction;//方向
	
	public MaYi()
	{
		this.location =0;
		this.direction =FORWARD;
	}
	public MaYi(int location ,int direction)
	{
		this.location = location;
		this.direction = direction;
	}
	/**
          * 蚂蚁移动
	  */
	public  void walk()
	{
		location += direction;
	}
	/**
          * 蚂蚁掉转方向
	  */
	public void turn()
	{
		if(direction == FORWARD) direction = BACKWARD;
		else direction = FORWARD;
	}
	/**
          *两只蚂蚁是否碰头
          */
	public boolean isNear(MaYi m)
	{	if(m ==null) return false;
		int result = this.location - m.location;
		if(result ==1 || result== -1) return true;
		else return false;
	}
	/**
          *蚂蚁是否离开
          */
	public boolean isLeave()
	{
		if(location<1 || location >27) return true;
		else return false;
	}

	public static  void run(List<MaYi> list)
	{	//总的次数
		int count = 0;
		
		//循环，直到所有蚂蚁都离开
		while(!list.isEmpty())
		{
			MaYi first =null;
			MaYi second = null;
			for(int i = 0; i<list.size();i++)
			{
				first = list.get(i);

				//如果蚂蚁是最后一只，则它的前面没有任何蚂蚁
				//如果不是最后一只，则它的前面有蚂蚁
				//参考系为蚂蚁的前进方向
				if(first.direction == FORWARD)				{
					if(i+1 ==list.size()) second = null; 
					else second = list.get(i+1);
				}
				else if(first.direction == BACKWARD)
				{
					if( i== 0 ) second =null;
					else second = list.get(i-1);
				}
					
				//如果两支蚂蚁碰头，则调转方向
				if(first.isNear(second)) 
				{
					first.turn(); 
					second.turn();
				}

				//前进
				first.walk();

				//如果蚂蚁走到了尽头
				if(first.isLeave()) list.remove(first);
			}
			count++;//计算次数

		}
		System.out.println("  移动时间为："+count);
		System.out.println();
	}
	
	public static void main(String[] args)
	{
		int first ,second,third,fourth,fifth;
		List<MaYi> list = null;
		for(int a=0;a<2;a++)
			for(int b=0;b<2;b++)
				for(int c=0;c<2;c++)
					for(int d=0;d<2;d++)
						for(int e=0;e<2;e++)
						{
							if(a ==0) first =1;
							else first = -1;
							if(b ==0) second =1;
							else second = -1;
							if(c ==0) third =1;
							else third = -1;
							if(d ==0) fourth =1;
							else fourth = -1;
							if(e ==0) fifth =1;
							else fifth = -1;
							
							list= new LinkedList<MaYi>();
								list.add(new MaYi(3,first));
								list.add(new MaYi(7,second));
								list.add(new MaYi(11,third));
								list.add(new MaYi(17,fourth));
								list.add(new MaYi(23,fifth));
							System.out.printf("第1蚂蚁,位置3,方向%d\n",first);
							System.out.printf("第2蚂蚁,位置7,方向%d\n",second);
							System.out.printf("第3蚂蚁,位置11,方向%d\n",third);
							System.out.printf("第4蚂蚁,位置17,方向%d\n",fourth);
							System.out.printf("第5蚂蚁,位置23,方向%d\n",fifth);
							MaYi.run(list);
						}

			
		
	
	
	}
}

 

结果如下：

第1蚂蚁,位置3,方向1
第2蚂蚁,位置7,方向1
第3蚂蚁,位置11,方向1
第4蚂蚁,位置17,方向1
第5蚂蚁,位置23,方向1
移动时间为：25

第1蚂蚁,位置3,方向1
第2蚂蚁,位置7,方向1
第3蚂蚁,位置11,方向1
第4蚂蚁,位置17,方向1
第5蚂蚁,位置23,方向-1
移动时间为：24

第1蚂蚁,位置3,方向1
第2蚂蚁,位置7,方向1
第3蚂蚁,位置11,方向1
第4蚂蚁,位置17,方向-1
第5蚂蚁,位置23,方向1
移动时间为：24

第1蚂蚁,位置3,方向1
第2蚂蚁,位置7,方向1
第3蚂蚁,位置11,方向1
第4蚂蚁,位置17,方向-1
第5蚂蚁,位置23,方向-1
移动时间为：24

第1蚂蚁,位置3,方向1
第2蚂蚁,位置7,方向1
第3蚂蚁,位置11,方向-1
第4蚂蚁,位置17,方向1
第5蚂蚁,位置23,方向1
移动时间为：24

第1蚂蚁,位置3,方向1
第2蚂蚁,位置7,方向1
第3蚂蚁,位置11,方向-1
第4蚂蚁,位置17,方向1
第5蚂蚁,位置23,方向-1
移动时间为：24

第1蚂蚁,位置3,方向1
第2蚂蚁,位置7,方向1
第3蚂蚁,位置11,方向-1
第4蚂蚁,位置17,方向-1
第5蚂蚁,位置23,方向1
移动时间为：22

第1蚂蚁,位置3,方向1
第2蚂蚁,位置7,方向1
第3蚂蚁,位置11,方向-1
第4蚂蚁,位置17,方向-1
第5蚂蚁,位置23,方向-1
移动时间为：24

第1蚂蚁,位置3,方向1
第2蚂蚁,位置7,方向-1
第3蚂蚁,位置11,方向1
第4蚂蚁,位置17,方向1
第5蚂蚁,位置23,方向1
移动时间为：24

第1蚂蚁,位置3,方向1
第2蚂蚁,位置7,方向-1
第3蚂蚁,位置11,方向1
第4蚂蚁,位置17,方向1
第5蚂蚁,位置23,方向-1
移动时间为：24

第1蚂蚁,位置3,方向1
第2蚂蚁,位置7,方向-1
第3蚂蚁,位置11,方向1
第4蚂蚁,位置17,方向-1
第5蚂蚁,位置23,方向1
移动时间为：22

第1蚂蚁,位置3,方向1
第2蚂蚁,位置7,方向-1
第3蚂蚁,位置11,方向1
第4蚂蚁,位置17,方向-1
第5蚂蚁,位置23,方向-1
移动时间为：24

第1蚂蚁,位置3,方向1
第2蚂蚁,位置7,方向-1
第3蚂蚁,位置11,方向-1
第4蚂蚁,位置17,方向1
第5蚂蚁,位置23,方向1
移动时间为：22

第1蚂蚁,位置3,方向1
第2蚂蚁,位置7,方向-1
第3蚂蚁,位置11,方向-1
第4蚂蚁,位置17,方向1
第5蚂蚁,位置23,方向-1
移动时间为：24

第1蚂蚁,位置3,方向1
第2蚂蚁,位置7,方向-1
第3蚂蚁,位置11,方向-1
第4蚂蚁,位置17,方向-1
第5蚂蚁,位置23,方向1
移动时间为：20

第1蚂蚁,位置3,方向1
第2蚂蚁,位置7,方向-1
第3蚂蚁,位置11,方向-1
第4蚂蚁,位置17,方向-1
第5蚂蚁,位置23,方向-1
移动时间为：24

第1蚂蚁,位置3,方向-1
第2蚂蚁,位置7,方向1
第3蚂蚁,位置11,方向1
第4蚂蚁,位置17,方向1
第5蚂蚁,位置23,方向1
移动时间为：22

第1蚂蚁,位置3,方向-1
第2蚂蚁,位置7,方向1
第3蚂蚁,位置11,方向1
第4蚂蚁,位置17,方向1
第5蚂蚁,位置23,方向-1
移动时间为：22

第1蚂蚁,位置3,方向-1
第2蚂蚁,位置7,方向1
第3蚂蚁,位置11,方向1
第4蚂蚁,位置17,方向-1
第5蚂蚁,位置23,方向1
移动时间为：22

第1蚂蚁,位置3,方向-1
第2蚂蚁,位置7,方向1
第3蚂蚁,位置11,方向1
第4蚂蚁,位置17,方向-1
第5蚂蚁,位置23,方向-1
移动时间为：24

第1蚂蚁,位置3,方向-1
第2蚂蚁,位置7,方向1
第3蚂蚁,位置11,方向-1
第4蚂蚁,位置17,方向1
第5蚂蚁,位置23,方向1
移动时间为：20

第1蚂蚁,位置3,方向-1
第2蚂蚁,位置7,方向1
第3蚂蚁,位置11,方向-1
第4蚂蚁,位置17,方向1
第5蚂蚁,位置23,方向-1
移动时间为：24

第1蚂蚁,位置3,方向-1
第2蚂蚁,位置7,方向1
第3蚂蚁,位置11,方向-1
第4蚂蚁,位置17,方向-1
第5蚂蚁,位置23,方向1
移动时间为：18

第1蚂蚁,位置3,方向-1
第2蚂蚁,位置7,方向1
第3蚂蚁,位置11,方向-1
第4蚂蚁,位置17,方向-1
第5蚂蚁,位置23,方向-1
移动时间为：24

第1蚂蚁,位置3,方向-1
第2蚂蚁,位置7,方向-1
第3蚂蚁,位置11,方向1
第4蚂蚁,位置17,方向1
第5蚂蚁,位置23,方向1
移动时间为：18

第1蚂蚁,位置3,方向-1
第2蚂蚁,位置7,方向-1
第3蚂蚁,位置11,方向1
第4蚂蚁,位置17,方向1
第5蚂蚁,位置23,方向-1
移动时间为：24

第1蚂蚁,位置3,方向-1
第2蚂蚁,位置7,方向-1
第3蚂蚁,位置11,方向1
第4蚂蚁,位置17,方向-1
第5蚂蚁,位置23,方向1
移动时间为：18

第1蚂蚁,位置3,方向-1
第2蚂蚁,位置7,方向-1
第3蚂蚁,位置11,方向1
第4蚂蚁,位置17,方向-1
第5蚂蚁,位置23,方向-1
移动时间为：24

第1蚂蚁,位置3,方向-1
第2蚂蚁,位置7,方向-1
第3蚂蚁,位置11,方向-1
第4蚂蚁,位置17,方向1
第5蚂蚁,位置23,方向1
移动时间为：12

第1蚂蚁,位置3,方向-1
第2蚂蚁,位置7,方向-1
第3蚂蚁,位置11,方向-1
第4蚂蚁,位置17,方向1
第5蚂蚁,位置23,方向-1
移动时间为：24

第1蚂蚁,位置3,方向-1
第2蚂蚁,位置7,方向-1
第3蚂蚁,位置11,方向-1
第4蚂蚁,位置17,方向-1
第5蚂蚁,位置23,方向1
移动时间为：18

第1蚂蚁,位置3,方向-1
第2蚂蚁,位置7,方向-1
第3蚂蚁,位置11,方向-1
第4蚂蚁,位置17,方向-1
第5蚂蚁,位置23,方向-1
移动时间为：24

 

评论

1 楼 playfish 2009-10-28  

5重for循环。。。比较囧一点。。。

我觉得可以用01表示方向，5重for循环就可以简单改成2进制的表示法，00000到11111，就是for(<32)，一个for循环就够了

00000 = 0
00001 = 2^0
00010 = 2^1
00011 = 2^1+2^0