算法题：蚂蚁走木杆.
有一根27厘米的细木杆，在第3厘米、7厘米、11厘米、17厘米、23厘米这五个位置上各有一只蚂蚁。 木杆很细，不能同时通过一只蚂蚁。开始 时，蚂蚁的头朝左还是朝右是任意的，它们只会朝前走或调头， 但不会后退。当任意两只蚂蚁碰头时，两只蚂蚁会同时调头朝反方向走。假设蚂蚁们每秒钟可以走一厘米的距离。 编写程序，求所有蚂蚁都离开木杆 的最小时间和最大时间。http://www.blogjava.net/itspy/archive/2006/11/10/80435.html
下面贴上我的测试程序
namespace ANTS
{
//#define N 5#define LENGTH 27 enum STATUS
{
Left=0, Right=1, STOP=2,
}; struct ANT { double Position; STATUS status; }; int goOut(ANT ant) { if(ant.Position>=0 && ant.Position<=LENGTH) return 0; if(( ant.Position>=LENGTH && ant.status==Left)|| ( ant.Position<=0 && ant.status==Right)) { printf("Error:位置%g和状态%s不符合\n",ant.Position,ant.status==Left?"L":"R" ); exit(0); } return 1; } int (__cdecl compare )(const void *e1, const void *e2 ) { ANT *elem1=(ANT *)e1; ANT *elem2=(ANT *)e2; if(elem1->Position <elem2->Position) return -1; if(elem1->Position >elem2->Position) return 1; return 0; } int Move(ANT *ant,int N,double *timeUsed) { //how many go out? int i,j,k; int num=0; for (i=0;i<N;i++) { if (goOut(ant[i]) ) { ant[i].status=STOP; num++; } } Trace("%d个已经出去的",num); if(num>=N) { Trace("END---------------"); return 1; } // qsort(ant,N,sizeof(ANT),compare); for(i=0;i<N-1;i++) { if(fabs(ant[i].Position-ant[i+1].Position)<1e-5 && ant[i].status==Right && ant[i+1].status==Left ) { ant[i].status=Left; ant[i+1].status=Right; } } Trace("排序后状态"); for(i=0;i<N;i++) Trace(" %g%s ",ant[i].Position,ant[i].status==Left?"L":"R"); // i=0;// while (ant[i].status==STOP)// {// CHECK(i<N);// i++;// }// // j=N-1;// while (ant[j].status==STOP)// {// CHECK(j>=0);// j--;// }// // CHECK(j-i+1>0); //find 最小 碰撞 int p=-1; double len=1e10; for (i=0;i<N-1;i++) { if(ant[i].status==Right && ant[i+1].status==Left && ant[i+1].Position>=0 && ant[i+1].Position<=LENGTH && ant[i].Position>=0 && ant[i].Position<=LENGTH && ant[i+1].Position-ant[i].Position>1e-5 &&ant[i+1].Position-ant[i].Position<len ) { p=i; len=ant[i+1].Position-ant[i].Position; } } if(p>=0)//移动一次直到碰撞 { double lastP1=ant[p].Position; double lastP2=ant[p+1].Position; double t=len/2; ant[p].Position += t; ant[p+1].Position -= t; ant[p].status=Left; ant[p+1].status=Right; for (i=0;i<N;i++) { if(i==p || i==p+1) continue; if(ant[i].status!=STOP) ant[i].Position+=(ant[i].status==Right?1:-1) * t; } *timeUsed += t; Trace("找到最小碰撞的位置%g vs %g,碰撞后时间 %g(dt=%g)",lastP1,lastP2,*timeUsed ,t); return 0; } else//所有的都移动 { double tMax=0; for (i=0;i<N;i++) { if(ant[i].status!=STOP ) { if(ant[i].status==Left && ant[i].Position >tMax) tMax=ant[i].Position; else if(ant[i].status==Right && LENGTH - ant[i].Position >tMax) tMax=LENGTH- ant[i].Position; } } *timeUsed+=tMax; Trace("没有碰撞,全部出去时间为%g(dt=%g)",*timeUsed,tMax); return 1; } } void Test() { ANT ant[5]; int Position[5]={3,7,11,17,23}; int status=0; int i; double timeUsed=0; for(status=0;status<=1/*0x1f*/ ;status++) { printf("初始状态：\n"); for(i=0;i<5;i++) { ant[i].Position=Position[i]; ant[i].status=(status & (1<<i))?Right:Left; printf("%g%s ",ant[i].Position,ant[i].status==Left?"L":"R"); } printf("\n"); i=0; timeUsed=0; while(!Move(ant,5,&timeUsed) && i++<10); Trace("END----------"); printf("使用时间%g\n",timeUsed); } }
}