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

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

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

please see it carefully again.

shorest  11     and longest 24...

我怎么觉得最长时间是23

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

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

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

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

应该就是如此了

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

min:23
max:51

我算出来的

那个算出来答案不靠谱啊

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

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

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