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