百度面试题---5只蚂蚁走木棍问题的分析优化解法(java实现)

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

前面发了2篇文章给了递归和非递归的算法，但是那基本是模拟了蚂蚁运动的过程，真实的复现了实验的场景，在此基础上，我又对蚂蚁运动过程进行了简单的分析，发现其运动的问题可以转化成新的更简略的问题
  为此，给出了一个简化算法，实现步骤如下，算法思想也在注释里说明，请大家指正.

package com.leochan;

public class AnalysisAntWalker {

	public static int totalLength = 27;

	public static void main(String[] args) {

		analysisTest();

	}

	/*
	 * 处理的思想是
	 * 我们不妨假设，所有的蚂蚁即便是走到了边界也不停下，继续向前走，此外，我们将蚂蚁编号a,b,c,d,e
	 * 那么对于5只蚂蚁，无论方向如何，只要经历的时间相同，那么它们走过的路程也一定相同
	 * 所以对于过程中，出现蚂蚁相遇的情况，可以等价看成不变向，让原先的蚂蚁继续向前走，直到它们都达到边界。
	 * 所以最终的结果是，2种情况下求出的时间相同，只是达成这个时间的蚂蚁编号不同
	 * 因此，所有的蚂蚁所需的时间只取决于它初始位置和方向，把原始的问题转化为一个新的等价问题，
	 * 求解得到各种情况下所需的时间，从而得知最大时间和最小时间。
	 */
	private static void analysisTest() {
		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 dd1 = d1 * 3, dd2 = d2 * 7, dd3 = d3 * 11, dd4 = d4 * 17, dd5 = d5 * 23;

							int time = 0;

							// d1
							if (d1 < 0)
								time = -dd1;
							else
								time = totalLength - dd1;

							// d2
							if (d2 < 0)
								time = time > (-dd2) ? time : (-dd2);
							else
								time = time > (totalLength - dd2) ? time
										: (totalLength - dd2);

							// d3
							if (d3 < 0)
								time = time > (-dd3) ? time : (-dd3);
							else
								time = time > (totalLength - dd3) ? time
										: (totalLength - dd3);

							// d4
							if (d4 < 0)
								time = time > (-dd4) ? time : (-dd4);
							else
								time = time > (totalLength - dd4) ? time
										: (totalLength - dd4);

							// d5
							if (d5 < 0)
								time = time > (-dd5) ? time : (-dd5);
							else
								time = time > (totalLength - dd5) ? time
										: (totalLength - dd5);

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

评论

2 楼 leochan007 2009-07-02  

stone2oo6 写道

这个处理思想高明

呵呵 这样子处理就不需要非要像前2种解法那样必须要求蚂蚁处于相邻偶数距离的位置了～

1 楼 stone2oo6 2009-07-01  

这个处理思想高明