百度面试题---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 楼 stone2oo6 2009-06-28  

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

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

2 楼 leochan007 2009-06-27  

night_stalker 写道

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

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

1 楼 night_stalker 2009-06-27  

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