算法题:蚂蚁走木杆.

有一根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==|| 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);
        }

    }

}

Powered by Jekyll and Theme by solid

本站总访问量