百度面试题---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);
						}
					}
				}
			}
		}
	}
}

欢迎各位来指正。

“编写程序”那句，绝对是一些人牵强附会加上去的。本来是智力题 ……

是嘛？？不知道啊。。 我做了3种方法 后来发现问题就很简单了 呵呵 anyway 还是有点收获的 编程可以不需要考虑太多 它怎么阐述就怎么做。  计算机本来就会把人变傻：）

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

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

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

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

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

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

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

正解

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

首先是一个方向的枚举

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

}