有一根27厘米的细木杆，在第3厘米、7厘米、11厘米、17厘米、23厘米这五个位置上各有一只蚂蚁。
木杆很细，不能同时通过两蚂蚁。开始时，蚂蚁的头朝左还是朝右是任意的，它们只会朝前走或调
头，但不会后退。当任意两只蚂蚁碰头时，两只蚂蚁会同时调头朝反方向走。假设蚂蚁们每秒钟可以
走一厘米的距离。编写程序，求所有蚂蚁都离开木杆的最小时间和最大时间。
1
// baiduant.cpp : Defines the entry point for the console application.
2//
3
4#include "stdafx.h"
5#include <math.h>
6#include <stdio.h>
7#include <stdlib.h>
8#define N 5
9
10
/**//*
11
* check all other ant's positions, if has a same position as ant[i],
12* return 1, else 0.
13
*/
14int meet(int* ant, int i)
15
{
16 int x = 0;
17 while( x < N)
18
{
19 if(x != i && ant[x] == ant[i] && ant[x] != 0 && ant[x] != 27) return 1;
20 x ++;
21
}
22 return 0;
23}
24
25/**//*
26* to check all the ant's positions, if all ants are out of stick,
27* return 1, else 0.
28*/
29int game_over(int* ant)
30{
31 int i = 0;
32 for(i = 0; i < N; i ++)
33 if(ant[i] != 0 && ant[i] != 27)
34 return 0;// no, continue.
35
36 return 1; // game over.
37}
38
39int ant_time(int* ant, int* dir, int* bak)
40{
41 int elapsed = 0; // time elapsed.
42 while(1)
43 {
44 int i = 0;
45 // back up current ants.
46 for(i = 0; i < N; i ++) bak[i] = ant[i];
47
48 for(i = 0; i < N; i ++)
49 {
50 if(ant[i] == 0 || ant[i] == 27) continue;
51 if(meet(bak, i)) dir[i] ^= 1; // reverse dir[i], 1->0, 0->1.
52 if(dir[i] == 1) ant[i] ++; // move right.
53 else ant[i] --; // move left.
54 }
55
56 elapsed ++; // time elapsed ++.
57 if(game_over(ant)) return elapsed;
58 }
59}
60
61int main(int argc, char* argv[])
62{
63 int i = 0;
64 int xxx[64];
65 for(i = 0; i < 64; i ++)
66 {
67 int ant[N] = {3, 7, 11, 17, 23}; // initial ant positions.
68 int dir[N] = {0, 0, 0, 0, 0}; // random direction, 1: right, 0: left.
69 int bak[N] = {3, 7, 11, 17, 23}; // back up current ant positions.
70
71 int j = 0;
72 for(j = 0; j < N; j ++) dir[j] = (i & (1 << j)) > 0 ? 1 : 0;
73
74 xxx[i] = ant_time(ant, dir, bak);
75 }
76
77 for(i = 0; i < 64; i ++)
78 {
79 xxx[0] = xxx[i] > xxx[0] ? xxx[i] : xxx[0];
80 xxx[1] = xxx[i] < xxx[1] ? xxx[i] : xxx[1];
81 }
82 printf("max: %d\nmin: %d\n", xxx[0], xxx[1]);
83 getchar();
84 return 0;
85}