百度面试题---5只蚂蚁走木棍问题的非递归解法(java实现)

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


之前给出了一个递归的解法，觉得还不够好，因为效率较低，所以用了一个非递归的方法来处理。同样算法步骤都在code的注释里有。

package com.leochan;

public class DirectAntWalker {

	public static int totalLength = 27;

	public static void main(String[] args) {

		directTest();

	}

	private static void directTest() {
		int count = 0;
		for (int d1 = -1; d1 <= 1; d1 += 2) {
			for (int d2 = -1; d2 <= 1; d2 += 2) {
				for (int d3 = -1; d3 <= 1; d3 += 2) {
					for (int d4 = -1; d4 <= 1; d4 += 2) {
						for (int d5 = -1; d5 <= 1; d5 += 2) {

							count++;

							// 构造蚂蚁数组
							int[] ants = { 3 * d1, 7 * d2, 11 * d3, 17 * d4,
									23 * d5 };

							// 设置index初始取值范围
							int idx1 = 0, idx2 = 4;
							int totalTime = 0;

							int i = 0;
							while (true) {

								// 如果有蚂蚁先达到边界，一定是发生在边界处
								// 如果第一只蚂蚁已经达到边界，就忽略这只蚂蚁
								if (ants[idx1] == 0
										|| ants[idx1] == totalLength) {
									idx1++;
								}
								// 如果最后一只蚂蚁已经达到边界，就忽略这只蚂蚁
								if (ants[idx2] == 0
										|| ants[idx2] == totalLength) {
									idx2--;
								}
								// 如果当前可访问的下界超过上界，就跳出循环
								if (idx1 > idx2)
									break;
								// 如果下届等于上界，则说明仅有一只蚂蚁还没有走出去。
								else if (idx1 == idx2) {
									if (ants[idx1] < 0) {
										totalTime -= ants[idx1];
									} else {
										totalTime += (totalLength - ants[idx1]);
									}
									break;
								}

								// 对于其他情况让 所有的蚂蚁走一步，如果出现了蚂蚁位置重合，就让重合的2只蚂蚁转向
							
								ants[idx1] = ants[idx1] + 1;
								for (i = idx1 + 1; i <= idx2; i++) {
									ants[i] = ants[i] + 1;
									if (ants[i] + ants[i - 1] == 0) {
										ants[i] *= -1;
										ants[i - 1] *= -1;
									}
								}
								
								// 消耗的时间递增1。
								totalTime++;
							}

							System.out.print("count=" + count + " d1=" + d1
									+ " d2=" + d2 + " d3=" + d3 + " d4=" + d4
									+ " d5=" + d5);
							System.out.println("  totalTime=" + totalTime);
						}
					}
				}
			}
		}
	}
}

欢迎各位来指正。

评论

23 楼 iaimstar 2009-12-11  

智力题。。智力题。

22 楼 moleApple 2009-12-11  

真是太厉害啦。。佩服哦。我算法不行啊。

21 楼 cowboycool 2009-08-21  

leochan007 写道

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


之前给出了一个递归的解法，觉得还不够好，因为效率较低，所以用了一个非递归的方法来处理。同样算法步骤都在code的注释里有。

package com.leochan;

public class DirectAntWalker {

	public static int totalLength = 27;

	public static void main(String[] args) {

		directTest();

	}

	private static void directTest() {
		int count = 0;
		for (int d1 = -1; d1 <= 1; d1 += 2) {
			for (int d2 = -1; d2 <= 1; d2 += 2) {
				for (int d3 = -1; d3 <= 1; d3 += 2) {
					for (int d4 = -1; d4 <= 1; d4 += 2) {
						for (int d5 = -1; d5 <= 1; d5 += 2) {

							count++;

							// 构造蚂蚁数组
							int[] ants = { 3 * d1, 7 * d2, 11 * d3, 17 * d4,
									23 * d5 };

							// 设置index初始取值范围
							int idx1 = 0, idx2 = 4;
							int totalTime = 0;

							int i = 0;
							while (true) {

								// 如果有蚂蚁先达到边界，一定是发生在边界处
								// 如果第一只蚂蚁已经达到边界，就忽略这只蚂蚁
								if (ants[idx1] == 0
										|| ants[idx1] == totalLength) {
									idx1++;
								}
								// 如果最后一只蚂蚁已经达到边界，就忽略这只蚂蚁
								if (ants[idx2] == 0
										|| ants[idx2] == totalLength) {
									idx2--;
								}
								// 如果当前可访问的下界超过上界，就跳出循环
								if (idx1 > idx2)
									break;
								// 如果下届等于上界，则说明仅有一只蚂蚁还没有走出去。
								else if (idx1 == idx2) {
									if (ants[idx1] < 0) {
										totalTime -= ants[idx1];
									} else {
										totalTime += (totalLength - ants[idx1]);
									}
									break;
								}

								// 对于其他情况让 所有的蚂蚁走一步，如果出现了蚂蚁位置重合，就让重合的2只蚂蚁转向
							
								ants[idx1] = ants[idx1] + 1;
								for (i = idx1 + 1; i <= idx2; i++) {
									ants[i] = ants[i] + 1;
									if (ants[i] + ants[i - 1] == 0) {
										ants[i] *= -1;
										ants[i - 1] *= -1;
									}
								}
								
								// 消耗的时间递增1。
								totalTime++;
							}

							System.out.print("count=" + count + " d1=" + d1
									+ " d2=" + d2 + " d3=" + d3 + " d4=" + d4
									+ " d5=" + d5);
							System.out.println("  totalTime=" + totalTime);
						}
					}
				}
			}
		}
	}
}

欢迎各位来指正。

太庞大了看不懂：（

20 楼 ppig 2009-08-20  

sjbrising 写道

chirking 写道

“当任意两只蚂蚁碰头时，两只蚂蚁会同时调头朝反方向走。“
其实你可以当作它们擦肩而过。
所以，最长时间应该是 最左短端的蚂蚁一直往右走 和 最右短端的蚂蚁一直往左走 两个时间的最大值。（不考虑别的蚂蚁，一直走就对了）
最小时间应该是 左边的3个蚂蚁往左走，右边的2个蚂蚁往右走 花的时间。
你可以试试。

确实很厉害，一语中的！！

楼主用的是穷举模拟过程吧，然后找出最大和最小
为什么不用公式呢？只是最小时间需要稍微要考虑一下蚂蚁之间的间隔。

19 楼 lianxianghui 2009-08-20  

jltest 写道

lianxianghui 写道

我觉得这个帖子中关于这个问题的程序最简洁
http://www.iteye.com/topic/417157

那个算出来答案不靠谱啊

运行结果是 24 和 11 ，你的23是错的。

18 楼 330217445 2009-07-29  

打印出所有方式所花费的时间，时间晚了代码没整理，欢迎批评及质疑！

 package com;

public class TestAntWalk {
	int lenth;

	int antNum;

	int speed;

	int[] antPos ;

	// 蚂蚁数组，第一维：方向 ；第二维：位置；
	int[][] ants;

	public TestAntWalk(int lenth, int[] antPos, int speed) {
		this.lenth = lenth;
		this.antPos = antPos;
		this.antNum = antPos.length;
		this.speed = speed;
		ants = new int[antNum][2];
	}

	public void antWalk() {
		int walkWayNum = 1 << antNum;
		// 遍历蚂蚁前进方向数组
		for (int i = 0; i < walkWayNum; i++) {
			int[] seq = new int[antNum];
			// 生成方向排序序列
			for (int j = 0; j < antNum; j++) {
				seq[j] = (i >> (antNum - 1 - j)) % 2;
			}
			// 蚂蚁数组填充
			for (int j = 0; j < antNum; j++) {
				ants[j][0] = seq[j];
				ants[j][1] = antPos[j];
			}
			// 完成蚂蚁数量
			int overNum = 0;
			int time = 0;
			while (overNum < antNum) {
				// 碰头换方向
				for (int j = 0; j < antNum - 1; j++) {
					if (ants[j][1] == ants[j + 1][1]
							&& ants[j][0] != ants[j + 1][0]) {
						ants[j][1] = ants[j][1] + ants[j + 1][1];
						ants[j + 1][1] = ants[j][1] - ants[j + 1][1];
						ants[j][1] = ants[j][1] - ants[j + 1][1];
					}
				}

				// 蚂蚁前进
				for (int j = 0; j < antNum; j++) {
					if ((ants[j][1] == 0 || ants[j][1] == lenth)
							&& ants[j][0] != -1) {
						overNum++;
						ants[j][0] = -1;
					} else {
						if (ants[j][0] == 1) {
							ants[j][1] = ants[j][1] + speed;
						} else if (ants[j][0] == 0) {
							ants[j][1] = ants[j][1] - speed;
						}
					}

				}
				time++;
			}
			time--;
			System.out.println("....." + i + "..:" + time);
		}

	}

	public static void main(String[] args) {
		TestAntWalk antWalk = new TestAntWalk(27, new int[] { 3, 7, 11, 17, 23 }, 1);
		antWalk.antWalk();
	}
}

17 楼 jltest 2009-07-29  

lianxianghui 写道

我觉得这个帖子中关于这个问题的程序最简洁
http://www.iteye.com/topic/417157

那个算出来答案不靠谱啊

16 楼 jltest 2009-07-29  

min:23
max:51

我算出来的

15 楼 sjbrising 2009-07-29  

chirking 写道

“当任意两只蚂蚁碰头时，两只蚂蚁会同时调头朝反方向走。“
其实你可以当作它们擦肩而过。
所以，最长时间应该是 最左短端的蚂蚁一直往右走 和 最右短端的蚂蚁一直往左走 两个时间的最大值。（不考虑别的蚂蚁，一直走就对了）
最小时间应该是 左边的3个蚂蚁往左走，右边的2个蚂蚁往右走 花的时间。
你可以试试。

确实很厉害，一语中的！！

14 楼 akfucc 2009-07-25  

这题其实有一种很方便的解法, 记得有人叫它灵魂算法
两只蚂蚁相遇并掉头,完全可以看成是两头蚂蚁穿过对方

最小时间
离中心最近的蚂蚁 向 离自己近的一棍头跑, 就是最短时间

最长时间
离棍头最短的蚂蚁, 向 离自己远的一头跑, 就是最长时间了

应该就是如此了

13 楼 lianxianghui 2009-07-17  

我觉得这个帖子中关于这个问题的程序最简洁
http://www.iteye.com/topic/417157

12 楼 windforce9811 2009-07-17  

我怎么觉得最长时间是23

11 楼 leochan007 2009-07-14  

挪威的幽灵 写道

太简单了，最短距离11  最长27
你的算法是错误的
其实你思考下，求最短时 11 和17的两边往外走 最久11秒
最长就更简单了 同时往一边走

i am wrong????  no   .no..... you r wrong...

please see it carefully again.

shorest  11     and longest 24...

10 楼 挪威的幽灵 2009-07-14  

太简单了，最短距离11  最长27
你的算法是错误的
其实你思考下，求最短时 11 和17的两边往外走 最久11秒
最长就更简单了 同时往一边走

9 楼 gordianyuan 2009-07-13  

尝试写了一下, 可以接受任意个参数, 自定义边界

首先是一个方向的枚举

public enum Direction {
	LEFT, RIGHT;
}

接着是Ant对象

public class Ant {

	private Direction direction = Direction.LEFT;
	private int location;

	public Ant(int location, Direction direction) {
		this.location = location;
		this.direction = direction;
	}

	public void move() {
		if (Direction.LEFT.equals(direction)) {
			location--;
		} else {
			location++;
		}
	}

	public void turnAround() {
		if (Direction.LEFT.equals(direction)) {
			direction = Direction.RIGHT;
		} else {
			direction = Direction.LEFT;
		}
	}

	public int getLocation() {
		return location;
	}

}

最后是主代码

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

public class Main {

	public static void main(String[] args) {

		int leftEdge = 0;
		int rightEdge = 27;
		List<List<Ant>> antsList = createAntsList(3, 7, 11, 17, 23);

		List<Integer> times = new ArrayList<Integer>();

		for (List<Ant> ants : antsList) {

			int time = 0;

			while (ants.size() > 0) {
				for (Ant ant : ants) {
					ant.move();
				}

				List<Ant> removed = new ArrayList<Ant>();
				for (Ant ant : ants) {
					int location = ant.getLocation();
					if (location <= leftEdge || location >= rightEdge) {
						removed.add(ant);
					}
				}
				ants.removeAll(removed);

				for (int i = 0; i < ants.size() - 1; i++) {
					Ant leftAnt = ants.get(i);
					Ant rightAnt = ants.get(i + 1);
					if (leftAnt.getLocation() >= rightAnt.getLocation()) {
						leftAnt.turnAround();
						rightAnt.turnAround();
					}
				}

				time++;
			}

			times.add(time);

		}

		System.out.println("Max: " + Collections.max(times));
		System.out.println("Min: " + Collections.min(times));

	}

	private static List<List<Ant>> createAntsList(int... locations) {
		int length = locations.length;
		int times = (int) Math.pow(2, length);
		List<List<Ant>> antsList = new ArrayList<List<Ant>>();
		for (int i = 0; i < times; i++) {
			String seq = toBinaryString(i, length);
			List<Ant> ants = new ArrayList<Ant>();
			for (int j = 0; j < length; j++) {
				int location = locations[j];
				Direction direction = seq.charAt(j) == '0' ? Direction.LEFT
							: Direction.RIGHT;
				ants.add(new Ant(location, direction));
			}
			antsList.add(ants);
		}
		return antsList;
	}

	private static String toBinaryString(int integer, int length) {
		String result = Integer.toBinaryString(integer);
		while (result.length() < length) {
			result = "0" + result;
		}
		return result;
	}

}

8 楼 icyfarer 2009-07-13  

chirking 写道

“当任意两只蚂蚁碰头时，两只蚂蚁会同时调头朝反方向走。“
其实你可以当作它们擦肩而过。
所以，最长时间应该是 最左短端的蚂蚁一直往右走 和 最右短端的蚂蚁一直往左走 两个时间的最大值。（不考虑别的蚂蚁，一直走就对了）
最小时间应该是 左边的3个蚂蚁往左走，右边的2个蚂蚁往右走 花的时间。
你可以试试。

正解

7 楼 leochan007 2009-07-11  

superwind 写道

蚂蚁分别向距离自己最近的一端走，得到的就是最短时间
分别向最远的一端走去，得到的就是最长时间

可以这么说把。。。详情见我第三种解法。。。

6 楼 superwind 2009-07-11  

蚂蚁分别向距离自己最近的一端走，得到的就是最短时间
分别向最远的一端走去，得到的就是最长时间

5 楼 chirking 2009-07-10  

“当任意两只蚂蚁碰头时，两只蚂蚁会同时调头朝反方向走。“
其实你可以当作它们擦肩而过。
所以，最长时间应该是 最左短端的蚂蚁一直往右走 和 最右短端的蚂蚁一直往左走 两个时间的最大值。（不考虑别的蚂蚁，一直走就对了）
最小时间应该是 左边的3个蚂蚁往左走，右边的2个蚂蚁往右走 花的时间。
你可以试试。

4 楼 leochan007 2009-06-28  

stone2oo6 写道

题目隐含了一个条件的就是任何时候2只蚂蚁之间的距离都是偶数倍。

那若初始化时存在2只蚂蚁的不是相聚偶数倍或者是存在这样的情况：某个时间2只蚂蚁的距离不是偶数，楼主的代码就不能适应了 

这个我当然知道  具体问题具体分析 才会有上述方法 如果题目有变 自然算法也要调整

不过用我的第三种分析优化方法就可以了 随便什么位置