有一根27厘米的细木杆，在第3厘米、7厘米、11厘米、17厘米、23厘米这五个位置上各有一只蚂蚁。木杆很细，不能同时通过一只蚂蚁。
开始时，蚂蚁的头朝左还是朝右是任意的，它们只会朝前走或调头，但不会后退。当任意两只蚂蚁碰头时，两只蚂蚁会同时调头朝反方向走。
假设各位置的蚂蚁们（从3厘米依次到23厘米）每秒钟分别可以走2厘米、1厘米、3厘米、2厘米、1厘米的距离。编写程序，求所有蚂蚁都离开木杆的最小时间和最大时间。
开始时，蚂蚁的头朝左还是朝右是任意的，它们只会朝前走或调头，但不会后退。当任意两只蚂蚁碰头时，两只蚂蚁会同时调头朝反方向走。
假设各位置的蚂蚁们（从3厘米依次到23厘米）每秒钟分别可以走2厘米、1厘米、3厘米、2厘米、1厘米的距离。编写程序，求所有蚂蚁都离开木杆的最小时间和最大时间。
#4所说的书应该是《编程之美》中的题4.7,其中的参数都一样,但是书中的所有蚂蚁每秒只能移动一厘米.也正因为这样lz所说的题无法用书中方法解答,而且lz的题中可能出现在前的蚂蚁被在后的蚂蚁赶上的情况,但题目中没明确说明该如何处理,那就假设速度快的蚂蚁被速度慢的挡住好了.(当然,也可能有更复杂的情况,这就要需要题目说得更清楚了) 最小时间:考虑到这样一个事实,对于每只蚂蚁,若它从左边离开木杆,则初始位置在它左边的蚂蚁必定也从左边离开木杆(右边的情况对称),故最短时间的初始情况只可能是左边的蚂蚁向左,右边的蚂蚁向右.这样只需计算6种情况.
最大时间:我一时无法给出完备且高效的方法.(一开始想的是左边的蚂蚁向右,右边的蚂蚁向左,但是不知道对不对)
#include <stdio.h>
#include <math.h>
struct Ant
{
int iPos;
float iSpeed;
};int main()
{
int pos[] = {3,7,11,17,23};
int speed[] = {2,1,3,2,1};
Ant ant[5];
for (int i=0; i<5; i++)
{
ant[i].iPos = pos[i];
ant[i].iSpeed = speed[i];
}
int len = 27;
float min = ant[0].iPos/ant[0].iSpeed, max = 0.0; // 以中点为分界向两边走,两只蚂蚁都不碰头
for (int i=0; i<5; i++)
{
if (ant[i].iPos < len/2)
{
float time = ant[i].iPos/ant[i].iSpeed;
if (time > min)
{
min = time;
}
} if (ant[i].iPos > len/2)
{
float time = (len-ant[i].iPos)/ant[i].iSpeed;
if (time > min)
{
min = time;
}
}
}
printf("min: %.2f\n", min); // 最长时间:找一只蚂蚁，使它到较远端的距离最大,速度最慢 max = ant[4].iPos/ant[4].iSpeed;
printf("max: %.2f\n", max); return 0;
}
没找到技巧const int PRECISION = 1000;
const int MAXPLACE = 27*PRECISION;const int ONEPLACE = 3*PRECISION;
const int TWOPLACE = 7*PRECISION;
const int THRPLACE = 11*PRECISION;
const int FOURPLACE = 17*PRECISION;
const int FIVEPLACE = 23*PRECISION;class AntRun
{
public:
AntRun(int, int, int);
void run(int);
void converse();
void SetTime(int);
bool GetIsEnd();
void SetSpeed(int);//初始化蚂蚁开始的朝向 bool operator == (const AntRun& R)
{
//只要两者距离小于3就认为已经相遇
if ( 0>(m_iSpeed*R.m_iSpeed) )
{
return ((abs(m_iStation - R.m_iStation) < 3));
}
else
{
return (m_iStation == R.m_iStation);
}
}
private:
int m_iStation;
int m_iEndTime;
int m_iSpeed;
bool m_isEnd;
int m_iNum;
};AntRun::AntRun(int iStation ,int iSpeed, int iNum)
{
m_iStation = iStation;
m_iSpeed = iSpeed;
m_iNum = iNum;
m_isEnd = false;
}void AntRun::run(int iTime)
{
if ( (m_iStation>0) && (m_iStation<MAXPLACE) && !m_isEnd )
{
m_iStation += m_iSpeed;
} if (((m_iStation<=0) || (m_iStation>=MAXPLACE)) && !m_isEnd)
{
SetTime(iTime);
m_isEnd = true; cout << m_iNum << " time:" << (float)m_iEndTime/PRECISION << "; " ;
}
}void AntRun::converse()
{
m_iSpeed = -m_iSpeed;
}void AntRun::SetTime(int iTime)
{
m_iEndTime = iTime;
}bool AntRun::GetIsEnd()
{
return m_isEnd;
}void AntRun::SetSpeed(int a)
{
if (0 != a)
{
m_iSpeed = -m_iSpeed;
}
}
void main()
{
for (int i=0; i<32; i++)
{
AntRun AntOne(ONEPLACE, 2, 1);
AntRun AntTwo(TWOPLACE, 1, 2);
AntRun AntThr(THRPLACE, 3, 3);
AntRun AntFour(FOURPLACE, 2, 4);
AntRun AntFive(FIVEPLACE, 1, 5); //按位与设定朝向
AntOne.SetSpeed(i&1);
AntTwo.SetSpeed(i&2);
AntThr.SetSpeed(i&4);
AntFour.SetSpeed(i&8);
AntFive.SetSpeed(i&16); int iTime = 0;
while (1)
{
AntOne.run(iTime);
AntTwo.run(iTime);
AntThr.run(iTime);
AntFour.run(iTime);
AntFive.run(iTime); if (AntOne == AntTwo)
{
AntOne.converse();
AntTwo.converse();
}
else if (AntTwo == AntThr)
{
AntTwo.converse();
AntThr.converse();
}
else if (AntThr == AntFour)
{
AntThr.converse();
AntFour.converse();
}
else if (AntFour == AntFive)
{
AntFour.converse();
AntFive.converse();
} if ( AntOne.GetIsEnd()
&& AntTwo.GetIsEnd()
&& AntThr.GetIsEnd()
&& AntFour.GetIsEnd()
&& AntFive.GetIsEnd() )
{
break;
}
iTime++;
}
cout << endl;
}
system("color 0e");
}
using namespace std;#define ANT_COUNT 5 // 蚂蚁数量
#define ROAD_LENGTH 27 // 杆长度
#define WAY_AHEAD true // 前进
#define WAY_BACK false // 后退
#define GAME_OVER -100 // 出杆class CAnt
{
public:
// 构造函数
CAnt();
// 初始化蚂蚁信息
void Init(int iPos, int iSpeed, bool bWay);public:
int m_iPos; // 位置
int m_iSpeed; // 速度
bool m_bWay; // 方向 true:前进 false:反向
int m_iCurPos; // 蚂蚁当前位置
// bool m_bFinish; // 是否走完
static int m_iAntCount; // 当前蚂蚁数量
static int m_iTime; // 共用总时间};int CAnt::m_iAntCount = ANT_COUNT;
int CAnt::m_iTime = 0;// 构造函数
CAnt::CAnt()
{
m_iPos = 0;
m_iSpeed = 0;
m_bWay = 0;
m_iCurPos = 0;
//m_bFinish = false;
}void CAnt::Init(int iPos, int iSpeed, bool bWay)
{
m_iPos = iPos;
m_iCurPos = iPos;
m_iSpeed = iSpeed;
m_bWay = bWay;
}void Go(CAnt *pAnt)
{
for (int i=0; i<ANT_COUNT; i++)
{
if (pAnt[i].m_iCurPos == GAME_OVER) continue; if (pAnt[i].m_bWay == WAY_AHEAD)
{
pAnt[i].m_iCurPos += pAnt[i].m_iSpeed;
}
else
{
pAnt[i].m_iCurPos -= pAnt[i].m_iSpeed;
}
} // 相遇
for (int i=0; i<ANT_COUNT-1; i++)
{
if (pAnt[i].m_iCurPos == GAME_OVER) continue; for (int j=i+1; j<ANT_COUNT; j++)
{
if (pAnt[j].m_iCurPos == GAME_OVER) continue;
if (pAnt[i].m_iCurPos == pAnt[j].m_iCurPos)
{
pAnt[i].m_bWay = !pAnt[i].m_bWay;
pAnt[j].m_bWay = !pAnt[j].m_bWay;
printf("注意: %d 和 %d相遇,反向\n\n", i, j);
}
else
{
if (pAnt[i].m_iCurPos > ROAD_LENGTH || pAnt[i].m_iCurPos <= 0)
{
pAnt[i].m_iCurPos = GAME_OVER; // 完成
CAnt::m_iAntCount--;
}
}
}
} if (pAnt[CAnt::m_iAntCount-1].m_iCurPos > ROAD_LENGTH ||
pAnt[CAnt::m_iAntCount-1].m_iCurPos <= 0 &&
CAnt::m_iAntCount>0)
{
pAnt[CAnt::m_iAntCount-1].m_iCurPos = GAME_OVER; // 完成
CAnt::m_iAntCount--;
} if (CAnt::m_iAntCount <= 0)
{
printf("剩余: %d\n", CAnt::m_iAntCount);
printf("完成! \n\n");
return;
}
else
{
printf("第 %d 秒", ++CAnt::m_iTime);
printf(" 剩余: %d\n\n", CAnt::m_iAntCount);
}
Go(pAnt);
}
int main()
{
CAnt *pAnt = new CAnt[ANT_COUNT](); // 初始化5只蚂蚁
int iPos[] = {3,7,11,17,23};
int iSpeed[] = {2,1,3,2,1};
for (int i=0; i<ANT_COUNT; i++)
{
pAnt[i].Init(iPos[i], iSpeed[i], WAY_AHEAD);
} Go(pAnt); delete [] pAnt;
return 0;
}