首页 > > 程序设计 > C/C++ >

蚂蚁问题的一个小扩展

2018-06-17 21:16:21来源：未知 阅读 ()

新老客户大回馈,云服务器低至5折

之前的博文谈到了蚂蚁问题，现在考虑其变形，要求输出从开始到所有蚂蚁离杆这段时间内的各时间段内的碰撞情况，有碰撞输出所有碰撞，没有则提示未发生碰撞，最后输出碰撞总次数，若整个过程没有发生任何碰撞则提示没有发生碰撞。

  代码如下(C语言):

#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>

void main()
{
    int t, i, flag;
    int number, sign;
    short *p1;
    int *p2;

    struct collision   //碰撞节点
    {
        int sign;   //参与碰撞的蚂蚁标号
        float t;    //碰撞时间
        float p;    //碰撞位置
        struct collision *next;
    };
    struct collision *head1, *psnew1, *q1, *t1;

    typedef struct collision node1;

    struct ant    //蚂蚁节点
    {
        struct ant *next;
        struct ant *before;
        short direction;   //当前时间点的蚂蚁方向
        int position;      //当前时间点的蚂蚁位置
        short direction1;  //上一时间点的蚂蚁方向
        int position1;     //上一时间点的蚂蚁位置
        int sign;          //蚂蚁标号
    };
    struct ant *psnew, *q, *head, *front, *after;

    typedef struct ant node;

    printf ("please input the number of ants in stick\n");         /*输入位于杆上的蚂蚁个数,不能为0,数量不超过27*/     
    scanf ("%d", &t);                              
 
    p1=(short *)malloc (t*sizeof(short));
    p2=(int *)malloc (t*sizeof(int));

    for (i=0; i<t; i++)
    {
        printf ("please input the direction of %dnd ant\n", i+1);  /*输入第i+1个蚂蚁的初始方向,1表示向右,0表示向左,不允许出现t=0时刻即一开始就有蚂蚁离开木杆的情况,即最左端蚂蚁方向向左,最右端蚂蚁方向向右*/
        scanf ("%d", p1+i);

        printf ("pleaase input the position of %dnd ant\n", i+1);  /*输入第i+1个蚂蚁的初始位置,杆长27cm,位置为蚂蚁所在处距杆左端的长度,只能为正整数,即位置只能为0cm,1cm,2cm,3cm---,26cm,27cm,位置需按照蚂蚁编号从小到大输入*/
        scanf ("%d", p2+i);
    }

    head=(node *)malloc (sizeof(node));
    q=head;                                //初始化存放各蚂蚁节点的链表
    head->next=NULL;
    head->before=NULL;

    for (i=0; i<t; i++)
    {
        psnew=(node *)malloc (sizeof(node));
        psnew->next=NULL;
    
        psnew->direction=p1[i];
        psnew->direction1=p1[i];              //创建存放各蚂蚁节点的链表
        psnew->position=p2[i];
        psnew->position1=p2[i];
        psnew->sign=i+1;

        q->next=psnew;
        psnew->before=q;
        q=psnew;
    }

    head1=(node1 *)malloc (sizeof(node1));
    q1=head1;                             //初始化碰撞链表
    head1->next=NULL;

    number=0;    //初始化碰撞计数变量
    sign=0;      //标志是否发生碰撞的变量的初始化
    t=0;         //时间初始化
    while (1)
    {
        t++;                             /*时间进一过度到下一个时间点*/                              
        q=head->next;

        while (q!=NULL)                   /*检测当前节点对应的蚂蚁的方向,根据方向调整蚂蚁的位置*/
        {
            if (q->direction)                     
                q->position=q->position+1;  /*这种位置调整方式存在漏洞.若某时刻前一蚂蚁与后一蚂蚁位置相隔1,前一蚂蚁向右运动,后一蚂蚁向左运动,则按这种方式时间进一后前一蚂蚁将爬到后一蚂蚁前面一格,换言之两只蚂蚁位置交换了*/
            else                            /*换言之两只蚂蚁互相穿过了对方,这是不可能的,实际上时间进一后两只蚂蚁仍在原来的位置,两只蚂蚁在他们原来两个位置的中点相碰又回到了原来的位置,并且此时他们的方向应该和原来方向相反*/   
                q->position=q->position-1;  /*因此需要对两只蚂蚁的位置方向进行修正,此外若时间进一所有蚂蚁按照各自的方向移动一格后,两只蚂蚁位置相同,即他们相对碰撞,则碰撞后蚂蚁运动方向和原来相反,因此也需要修正方向.*/

            q=q->next;
        }

            psnew=head->next;        /*psnew指向第一个节点*/    
            if (psnew->next!=NULL)   /*判断第一个节点是否为尾节点,若不是说明有两只以上蚂蚁,则进行碰撞检测,修正蚂蚁运动方向,以及对发生相互穿越错误的一对蚂蚁的位置方向进行修正*/ 
            {
                q=psnew;
                psnew=head;
                flag=1;

                do                   
                {
                    psnew=psnew->next;
                    q=q->next;

                    if ((psnew->position)>(q->position))  /*检测发生相互穿越错误的一对蚂蚁并对其位置和方向进行修正*/
                    {
                        i=psnew->direction;
                        psnew->direction=q->direction;
                        q->direction=i;

                        i=psnew->position;
                        psnew->position=q->position;
                        q->position=i;

                        front=psnew->before;
                        if (front->before!=NULL)
                        {
                            if(front->position==psnew->position)  /*进行碰撞检测,对碰撞后蚂蚁的方向进行修正*/
                            {
                                i=front->direction;
                                front->direction=psnew->direction;
                                psnew->direction=i;

                                if (q->next!=NULL)
                                {
                                    after=q->next;
                                    if(after->position==q->position)
                                    {
                                        i=after->direction;
                                        after->direction=q->direction;
                                        q->direction=i;
                                        flag=0;
                                    }
                                }
                            }
                        }
                    }
                    else
                    {
                            if (((psnew->position)==(q->position))&&flag) 
                        {
                            i=psnew->direction;
                            psnew->direction=q->direction;
                            q->direction=i;
                        }
                            else
                                flag=1;
                    }
                }
                while (q->next!=NULL);
            }

            psnew=head;
            q=psnew->next;
                while (q!=NULL)
                {
                    if ((q->position<1) || (q->position>=27))  /*蚂蚁的方向位置都修正完毕后对当前节点对应的蚂蚁的位置进行检测,判断蚂蚁是否爬下杆子*/
                    {
                        if (q->next!=NULL)         /*蚂蚁爬下杆子故需对节点进行删除,先判断删除的节点是否为尾节点,若不是尾节点,按照非尾节点释放该节点,释放后被释放节点的指针指向被释放节点后一节点*/
                        {   
                            psnew->next=q->next;
                            after=q->next;
                            after->before=q->before;
                             free (q);
                            q=psnew->next;
                        }
                        else
                        {
                            free (q);           /*若释放的节点是尾节点,直接删除尾节点,尾节点前一节点指针域置空指针,被释放节点的指针置空指针*/  
                            psnew->next=NULL;
                            q=psnew->next;
                        }
                    }
                    else
                    {
                        psnew=q;           /*检测到当前节点对应的蚂蚁没有爬下杆子,故前驱节点的指针指向当前节点,当前节点的指针指向下一节点,为下一蚂蚁爬下杆子的判断与处理做准备*/       
                        q=q->next;
                    }
                }

            if (head->next==NULL)    /*判断线性链表是否为空链表,从而判断是否全部的蚂蚁都爬下了杆子,若是退出循环输出t,否则继续循环*/
            {
                printf("time%d to time%d not including time%d\n", t-1, t, t-1);
                printf ("There is no collision happening from time%d to time%d not including time%d\n", t-1, t, t-1);
                printf ("\n");
                break;
            }
            else
            {
                q=head->next;
                if (q->next==NULL)
                {
                    printf ("time%d to time%d not including time%d\n", t-1, t, t-1);
                    if ((q->direction)!=(q->direction1))
                    {
                        sign=1;
                        number++;
                        if ((!(q->direction1))&&(q->direction))
                        {
                            printf("The %dnd collision happens at position%.1f at time%.1f between the%dnd ant and the%dnd ant\n", number, q->position-0.5, t-0.5, q->sign-1, q->sign);
                            printf ("\n");
                        }
                        else
                        {
                            printf("The %dnd collision happens at position%.1f at time%.1f between the%dnd ant and the%dnd ant\n", number, q->position+0.5, t-0.5, q->sign, q->sign+1);
                            printf ("\n");
                        }
                    }
                    else
                    {
                        printf ("There is no collision happening from time%d to time%d not including time%d\n", t-1, t, t-1);
                        printf ("\n");
                    }

                    q->direction1=q->direction;
                    q->position1=q->position;
                }
                else  //当前蚂蚁链表有两个以上蚂蚁节点，开始创建碰撞链表
                {
                    while (1)
                    {
                        psnew1=NULL;
                        if ((q->direction)!=(q->direction1))
                        {
                            if ((q->position)==(q->position1))
                            {
                                if((!(q->direction1))&&(q->direction))
                                {
                                    psnew1=(node1 *)malloc (sizeof(node1));
                                    psnew1->sign=q->sign;
                                    psnew1->t=(t-0.5);
                                    psnew1->p=(q->position-0.5);
                                }
                            }
                            else
                            {
                                if ((q->position1)>(q->position))
                                {
                                    psnew1=(node1 *)malloc (sizeof(node1));
                                    psnew1->sign=q->sign;
                                    psnew1->t=t;
                                    psnew1->p=q->position;
                                }
                            }
                        }
                        else
                        {
                            if ((q->position)==(q->position1))
                            {
                                psnew1=(node1 *)malloc (sizeof(node1));
                                psnew1->sign=q->sign;

                                if (q->direction1)
                                {
                                    psnew1->t=t;
                                    psnew1->p=q->position;
                                }
                                else
                                {
                                    psnew1->t=(t-0.5);
                                    psnew1->p=(q->position-0.5);
                                }
                            }
                        }

                        if (psnew1!=NULL)//生成了新的碰撞节点，按碰撞时间对碰撞节点执行插入排序，将碰撞节点插入到碰撞链表中
                        {
                            if (head1->next==NULL)
                            {
                                head1->next=psnew1;
                                psnew1->next=NULL;
                                q1=psnew1;
                            }
                            else
                            {
                                t1=head1->next;
                                if ((psnew1->t)<(t1->t))
                                {
                                    psnew1->next=head1->next;
                                    head1->next=psnew1;
                                }
                                else
                                {
                                    if ((psnew1->t)>(t1->t))
                                    {
                                        if (q1->next==NULL)
                                        {
                                            q1->next=psnew1;
                                            psnew1->next=NULL;
                                            q1=psnew1;
                                        }
                                        else
                                        {
                                            while (q1->next!=NULL)
                                            {
                                                q1=q1->next;
                                            }

                                            q1->next=psnew1;
                                            psnew1->next=NULL;
                                            q1=psnew1;
                                        }
                                    }
                                    else
                                    {
                                        if (psnew1->t==t)
                                        {
                                            q1->next=psnew1;
                                            psnew1->next=NULL;
                                            q1=psnew1;
                                        }
                                        else
                                        {
                                            if (q1->next==NULL)
                                            {
                                                if (q1->t==t)
                                                {
                                                    q1=head1->next;
                                                    t1=q1->next;

                                                    while ((q1->t)==(t1->t))
                                                    {
                                                        q1=q1->next;
                                                        t1=t1->next;
                                                    }

                                                    psnew1->next=q1->next;
                                                    q1->next=psnew1;
                                                    q1=psnew1;
                                                }
                                                else
                                                {
                                                    q1->next=psnew1;
                                                    psnew1->next=NULL;
                                                    q1=psnew1;
                                                }
                                            }
                                            else
                                            {
                                                psnew1->next=q1->next;
                                                q1->next=psnew1;
                                                q1=psnew1;
                                            }
                                        }
                                    }
                                }
                            }
                        }

                        if (q->next==NULL)
                            break;

                        q=q->next;
                    }
                    psnew1=NULL;
                    if ((q->direction)!=(q->direction1))     //处理蚂蚁链表中尾节点代表的蚂蚁的碰撞
                    {
                        if ((q->position)==(q->position1))
                        {
                             if((q->direction1)&&(!(q->direction)))
                             {
                                  psnew1=(node1 *)malloc (sizeof(node1));
                                  psnew1->sign=(q->sign+1);
                                  psnew1->t=(t-0.5);
                                  psnew1->p=(q->position+0.5);
                             }
                        }
                        else
                        {
                             if ((q->position1)<(q->position))
                             {
                                  psnew1=(node1 *)malloc (sizeof(node1));
                                  psnew1->sign=(q->sign+1);
                                  psnew1->t=t;
                                  psnew1->p=q->position;
                             }
                        }
                    }
                    else
                    {
                        if ((q->position)==(q->position1))
                        {
                             psnew1=(node1 *)malloc (sizeof(node1));
                             psnew1->sign=(q->sign+1);

                             if (q->direction1)
                             {
                                  psnew1->t=(t-0.5);
                                  psnew1->p=(q->position+0.5);
                             }
                             else
                             {
                                  psnew1->t=t;
                                  psnew1->p=q->position;
                             }
                        }
                    }

                    if (psnew1!=NULL) //新的碰撞节点生成，和以上操作类似，对碰撞节点执行插入排序
                    {
                         if (head1->next==NULL)
                         {
                              head1->next=psnew1;
                              psnew1->next=NULL;
                         }
                         else
                         {
                              t1=head1->next;
                              if ((psnew1->t)<(t1->t))
                              {
                                   psnew1->next=head1->next;
                                   head1->next=psnew1;
                              }
                              else
                              {
                                   if ((psnew1->t)>(t1->t))
                                   {
                                        if (q1->next==NULL)
                                        {
                                             q1->next=psnew1;
                                             psnew1->next=NULL;
                                        }
                                        else
                                        {
                                             while (q1->next!=NULL)
                                             {
                                                  q1=q1->next;
                                             }

                                             q1->next=psnew1;
                                             psnew1->next=NULL;
                                        }
                                   }
                                   else
                                   {
                                        if (psnew1->t==t)
                                        {
                                             q1->next=psnew1;
                                             psnew1->next=NULL;
                                        }
                                        else
                                        {
                                             if (q1->next==NULL)
                                             {
                                                  if (q1->t==t)
                                                  { 
                                                       q1=head1->next;
                                                       t1=q1->next;

                                                       while ((q1->t)==(t1->t))
                                                       {
                                                            q1=q1->next;
                                                            t1=t1->next;
                                                       }

                                                       psnew1->next=q1->next;
                                                       q1->next=psnew1;
                                                  }
                                                  else
                                                  {
                                                       q1->next=psnew1;
                                                       psnew1->next=NULL;
                                                  }
                                             }
                                             else
                                             {
                                                  psnew1->next=q1->next;
                                                  q1->next=psnew1;
                                             }
                                        }
                                   }
                              }
                         }
                    }

                    printf ("time%d to time%d not including time%d\n", t-1, t, t-1); //碰撞链表生成完毕输出(t-1 t] 时间段内的碰撞      
                    
                    if (head1->next!=NULL)//碰撞链表不空
                    {
                         sign=1;
                         q1=head1->next;

                             while (q1!=NULL)   //输出当前时间段内的所有碰撞
                             {
                                  number++;
                                  printf ("The %dnd collosion happens at position%.1f at time%.1f between the %dnd ant and the %dnd ant\n", number, q1->p, q1->t, q1->sign-1, q1->sign);
                                  q1=q1->next;
                             }
                             printf ("\n");

                             q1=head1;     //清空碰撞链表
                             while (q1->next!=NULL)
                             {
                                  t1=q1->next;
                                  q1->next=t1->next;
                                  free (t1);
                             }
                    }
                    else    //碰撞链表为空，当前时间段内没有碰撞
                    {
                        printf ("There is no collision happening from time%d to time%d not including time%d\n", t-1, t, t-1);
                        printf ("\n");
                    }

                    q=head->next;
                    while (q!=NULL)  //用当前时间点的位置方向更新上一时间点的位置方向
                    {
                          q->direction1=q->direction;
                          q->position1=q->position;
                          q=q->next;
                    }
                }
            }
    }
    if (sign==0)    //没有发生任何碰撞
        printf ("No collsion happens at the whole process\n");

    printf ("There are %d collisions in total\n", number);  //输出碰撞总数
}

/*用线性链表实现解决蚂蚁问题,若干蚂蚁位于一长杆上,杆长27cm,蚂蚁初始方向可以任意,运动速度1cm/s,蚂蚁从初始位置出发,两蚂蚁若相碰不能穿过对方,只能相碰后各自掉头,求蚂蚁全部爬出杆子所需时间*/

若初始时刻杆上共有三只蚂蚁，第一第二第三只蚂蚁初始方向位置分别为：1(右),2  1(右),3  0(左),4,则程序运行结果如下:

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有

上一篇：南理工2016考研复试上机题男女程序员排队

下一篇：扩展中国剩余定理详解

相关文章

IDC资讯： 主机资讯 注册资讯 托管资讯 vps资讯 网站建设

网站运营： 建站经验 策划盈利 搜索优化 网站推广 免费资源

网站联盟： 联盟新闻 联盟介绍 联盟点评 网赚技巧

行业资讯： 搜索引擎 网络游戏 电子商务 广告传媒

网络编程： Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它

服务器技术： Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护

软件技巧： 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷

网页制作： FrontPages Dreamweaver Javascript css photoshop fireworks Flash

程序设计： Java技术 C/C++ VB delphi

网络知识： 网络协议 网络安全 网络管理 组网方案 Cisco技术

操作系统： Win2000 WinXP Win2003 Mac OS Linux FreeBSD

热门词条
最新资讯
热门关注
热门标签