有一根长27厘米的小木棍儿，在木棍儿的3厘米，7厘米，11厘米，17厘米，23厘米的地方各有一只蚂蚁。这5只蚂蚁的走向是不知道的，假设小木棍儿很细只能通过一只蚂蚁。蚂蚁只能往前走或者掉头，不能后退（也就是不能倒着走）！当任意两只蚂蚁碰头的时候会同时掉头朝反方向走。假设蚂蚁一秒钟能走一厘米，求蚂蚁全部离开木棍儿的最小和最大时间。用程序设计出来，可以只写思路！
[code="java"]
public class Test {
static int[] state = new int[5]; // -1:left; 1:right
static int ss = 0; // 结果
static int[] pos = { 3, 7, 11, 17, 23 };
static int start = 0;
static int end = 27;
static void go() {
while (true) {
ss++;
for (int i = 0; i < pos.length; i++) {
if (pos[i] > 0 && pos[i] < 27) {
pos[i] += state[i];
if (i < pos.length - 1 && state[i] == 1
&& state[i + 1] == -1) {
// 碰头情况
if (pos[i] + 1 > pos[i + 1]) {
state[i] = -1;
state[i + 1] = 1;
}
}
if (i > 0 && state[i] == -1 && state[i - 1] == 1) {
// 碰头情况
if (pos[i] - 1 < pos[i - 1]) {
state[i] = 1;
state[i - 1] = -1;
}
}
}
}
if (proof()) {
print();
break;
}
}
}
private static void print() {
System.out.println(ss);
}
private static boolean proof() {
boolean isOk = true;
for (int i = 0; i < state.length; i++) {
if (pos[i] > 0 && pos[i] < 27) {
isOk = false;
}
}
return isOk;
}
static void init() {
ss = 0;
pos[0] = 3;
pos[1] = 7;
pos[2] = 11;
pos[3] = 17;
pos[4] = 23;
}
public static void main(String[] args) {
state[0] = -1;
state[1] = -1;
state[2] = -1;
state[3] = 1;
state[4] = 1;
// 共32种情况
for (int i = 0; i < 32; i++) {
String s = Long.toBinaryString(i);
int n = 5 - s.length();
for (int j = 0; j < n; j++) {
s = "0" + s;
}
for (int j = 0; j < s.length(); j++) {
char a = s.charAt(j);
if (a == '1')
state[j] = 1;
else
state[j] = -1;
}
init();
go();
}
}
}
[/code]
答案很简单，不管方向怎么走，结果都是24秒……
硬要写个程序的话...
a = [3,7,11,17,23]
b = 27 - a
max(a.max, b.max)
每个蚂蚁对象维护自己的几个属性：
time 在木头上走的时间
pos 在木头上的坐标
orientation 方向(-1 or 1)
recursion:
1.所有蚂蚁走一步，矢量pos加1，time加1
2.检查是否有蚂蚁在同一坐标上，如果有，将它们掉头
3.检查是否有蚂蚁的坐标在[0,27]以外的外围，如果有，记下它的time值，然后这个蚂蚁出局
4.反复1-3步，直到所有蚂蚁出局。它们time的最大值就是一个解(一共有32个情况，32种解).
其实你只要考虑最中间和最外面的那2个蚂蚁就可以了，因为最中间那个也就是11cm的那个蚂蚁用时是最少的，为11s，而用时最大的就是那个3cm的蚂蚁，用时24s，只要把这2个判断好就可以了，其他的可以忽视。
蚂蚁碰头同时掉头朝反方向走，可以理解成只要把2只蚂蚁位子置换一下就可以了，这样就可以理解为什么最大是24s了，因为3cm的蚂蚁离另一头是最远的。