蚂蚁问题的编程解决

  1 #include <stdio.h>
  2 #include <malloc.h>
  3 #include <stdlib.h>
  4 
  5 void main()
  6 {
  7     int t, i, flag;
  8     short *p1;
  9     int *p2;
 10     struct ant           //保存蚂蚁信息的结构体类型
 11     {
 12         struct ant *next;
 13         struct ant *before;
 14         short direction;     //蚂蚁位置 
 15         int position;        //蚂蚁方向
 16         int sign;            //蚂蚁编号
 17     };
 18     struct ant *psnew, *q, *head, *front, *after;
 19 
 20     typedef struct ant node;
 21 
 22     struct ant2
 23     {
 24         int time;
 25         int sign;
 26         struct ant2 *next;
 27     };
 28     struct ant2 *t2, *q2, *head2, *psnew2;
 29 
 30     typedef struct ant2 node2;
 31 
 32     struct ant3
 33     {
 34         int sign;
 35         struct ant3 *next;
 36     };
 37     struct ant3 *head3, *psnew3, *q3;
 38 
 39     typedef struct ant3 node3;
 40 
 41     printf ("please input the number of ants in stick\n");         /*输入位于杆上的蚂蚁个数,不能为0,数量不超过27*/     
 42     scanf ("%d", &t);                              
 43  
 44     p1=(short *)malloc (t*sizeof(short));
 45     p2=(int *)malloc (t*sizeof(int));
 46 
 47     for (i=0; i<t; i++)
 48     {
 49         printf ("please input the direction of %dnd ant\n", i+1);  /*输入第i+1个蚂蚁的初始方向,1表示向右,0表示向左*/
 50         scanf ("%d", p1+i);
 51 
 52         printf ("pleaase input the position of %dnd ant\n", i+1);  /*输入第i+1个蚂蚁的初始位置,杆长27cm,位置为蚂蚁所在处距杆左端的长度,只能为正整数,即位置只能为1cm,2cm,3cm---,26cm,27cm,位置需按照蚂蚁编号从小到大输入*/
 53         scanf ("%d", p2+i);
 54     }
 55 
 56     head=(node *)malloc (sizeof(node));
 57     q=head;
 58     head->next=NULL;
 59     head->before=NULL;
 60 
 61     for (i=0; i<t; i++)
 62     {
 63         psnew=(node *)malloc (sizeof(node));
 64         psnew->next=NULL;
 65     
 66         psnew->direction=p1[i];               //初始化蚂蚁队列和各蚂蚁刚开始的位置方向
 67         psnew->position=p2[i];
 68         psnew->sign=i+1;
 69 
 70         q->next=psnew;
 71         psnew->before=q;
 72         q=psnew;
 73     }
 74     
 75     head3=(node3 *)malloc (sizeof(node3));
 76     head3->next=NULL;
 77     q3=head3;
 78     
 79     head2=(node2 *)malloc (sizeof(node2));
 80     head2->next=NULL;
 81     q2=head2;
 82 
 83     t=0;
 84     while (head->next!=NULL)             /*判断线性链表是否为空链表,从而判断是否全部的蚂蚁都爬下了杆子,若是退出循环输出t,否则继续循环*/
 85     {
 86         t++;                             /*时间进一过度到下一个时间点*/                              
 87         q=head->next;
 88 
 89         while (q!=NULL)                   /*检测当前节点对应的蚂蚁的方向,根据方向调整蚂蚁的位置*/
 90         {
 91             if (q->direction)                     
 92                 q->position=q->position+1;  /*这种位置调整方式存在漏洞.若某时刻前一蚂蚁与后一蚂蚁位置相隔1,前一蚂蚁向右运动,后一蚂蚁向左运动,则按这种方式时间进一后前一蚂蚁将爬到后一蚂蚁前面一格,换言之两只蚂蚁位置交换了*/
 93             else                            /*换言之两只蚂蚁互相穿过了对方,这是不可能的,实际上时间进一后两只蚂蚁仍在原来的位置,两只蚂蚁在他们原来两个位置的中点相碰又回到了原来的位置,并且此时他们的方向应该和原来方向相反*/   
 94                 q->position=q->position-1;  /*因此需要对两只蚂蚁的位置方向进行修正,此外若时间进一所有蚂蚁按照各自的方向移动一格后,两只蚂蚁位置相同,即他们相对碰撞,则碰撞后蚂蚁运动方向和原来相反,因此也需要修正方向.*/
 95 
 96             q=q->next;
 97         }
 98 
 99             psnew=head->next;        /*psnew指向第一个节点*/    
100             if (psnew->next!=NULL)   /*判断第一个节点是否为尾节点,若不是说明有两只以上蚂蚁,则进行碰撞检测,修正蚂蚁运动方向,以及对发生相互穿越错误的一对蚂蚁的位置方向进行修正*/ 
101             {
102                 q=psnew;
103                 psnew=head;
104                 flag=1;
105 
106                 do                   
107                 {
108                     psnew=psnew->next;
109                     q=q->next;
110 
111                     if ((psnew->position)>(q->position))  /*检测发生相互穿越错误的一对蚂蚁并对其位置和方向进行修正*/
112                     {
113                         i=psnew->direction;
114                         psnew->direction=q->direction;
115                         q->direction=i;
116 
117                         i=psnew->position;
118                         psnew->position=q->position;
119                         q->position=i;
120 
121                         front=psnew->before;
122                         if (front->before!=NULL)
123                         {
124                             if(front->position==psnew->position)  /*进行碰撞检测,对碰撞后蚂蚁的方向进行修正*/
125                             {
126                                 i=front->direction;
127                                 front->direction=psnew->direction;
128                                 psnew->direction=i;
129 
130                                 if (q->next!=NULL)
131                                 {
132                                     after=q->next;
133                                     if(after->position==q->position)
134                                     {
135                                         i=after->direction;
136                                         after->direction=q->direction;
137                                         q->direction=i;
138                                         flag=0;
139                                     }
140                                 }
141                             }
142                         }
143                     }
144                     else
145                     {
146                             if (((psnew->position)==(q->position))&&flag) 
147                         {
148                             i=psnew->direction;
149                             psnew->direction=q->direction;
150                             q->direction=i;
151                         }
152                             else
153                                 flag=1;
154                     }
155                 }
156                 while (q->next!=NULL);
157             }
158 
159             psnew=head;
160             q=psnew->next;
161                 while (q!=NULL)
162                 {
163                     if ((q->position<1) || (q->position>=27))  /*蚂蚁的方向位置都修正完毕后对当前节点对应的蚂蚁的位置进行检测,判断蚂蚁是否爬下杆子*/
164                     {
165                         psnew3=(node3 *)malloc (sizeof(node3));
166                         psnew3->sign=q->sign;                 //保存越界的蚂蚁节点
167                         psnew3->next=NULL;
168 
169                         q3->next=psnew3;
170                         q3=psnew3;
171                         
172                         psnew2=(node2 *)malloc (sizeof(node2));
173                         psnew2->sign=q->sign;                     //建立另一个越界的蚂蚁节点，保存该蚂蚁离杆的时间
174                         psnew2->time=t;
175 
176                         if (head2->next==NULL)
177                         {
178                             psnew2->next=NULL;
179                             q2->next=psnew2;
180                         }
181                         else
182                         {
183                             t2=head2;
184                             q2=q2->next;
185                             while (1)
186                             {
187                                 if ((psnew2->sign)<(q2->sign))     //对越界的蚂蚁节点执行插入排序
188                                 {
189                                     psnew2->next=q2;
190                                     t2->next=psnew2;
191                                     q2=head2;
192                                     break;
193                                 }
194                                 else
195                                 {
196                                     if (q2->next==NULL)
197                                     {
198                                         q2->next=psnew2;
199                                         psnew2->next=NULL;
200                                         q2=head2;
201                                         break;
202                                     }
203                                     else
204                                     {
205                                         t2=t2->next;
206                                         q2=q2->next;
207                                     }
208                                 }
209                             }
210                         }
211 
212                         if (q->next!=NULL)         /*蚂蚁爬下杆子故需对节点进行删除,先判断删除的节点是否为尾节点,若不是尾节点,按照非尾节点释放该节点,释放后被释放节点的指针指向被释放节点后一节点*/
213                         {   
214                             psnew->next=q->next;
215                             after=q->next;
216                             after->before=q->before;
217                              free (q);
218                             q=psnew->next;
219                         }
220                         else
221                         {
222                             free (q);           /*若释放的节点是尾节点,直接删除尾节点,尾节点前一节点指针域置空指针,被释放节点的指针置空指针*/  
223                             psnew->next=NULL;
224                             q=psnew->next;
225                         }
226                     }
227                     else
228                     {
229                         psnew=q;           /*检测到当前节点对应的蚂蚁没有爬下杆子,故前驱节点的指针指向当前节点,当前节点的指针指向下一节点,为下一蚂蚁爬下杆子的判断与处理做准备*/       
230                         q=q->next;
231                     }
232                 }
233 
234             q=head;
235             while(q->next!=NULL)
236             {
237                 q=q->next;
238                 printf ("at the time%d,the%dnd ant is at the position%d,in the direction%d\n", t, q->sign, q->position, q->direction); /*输出当前时刻杆上所有蚂蚁的编号,位置,方向*/
239             }
240 
241             if (head3->next!=NULL)
242             {
243                 q3=head3->next;
244                 while (q3!=NULL)
245                 {
246                     printf ("The %dnd ant is off the stick at time%d\n", q3->sign, t);  //输出当前时间t离杆的蚂蚁编号
247                     q3=q3->next;
248                 }
249 
250                 q3=head3;
251                 while (q3->next!=NULL)
252                 {
253                     psnew3=q3->next;
254                     q3->next=psnew3->next;
255                     free (psnew3);
256                 }
257             }
258     }
259     printf ("the time of all ants need to be off the stick is %d\n", t); /*输出全部蚂蚁爬下杆子所对应时刻(蚂蚁均位于初始位置时视为t=0时刻),也就是蚂蚁全部爬出杆子所需时间*/
260     printf ("\n");
261 
262     q2=q2->next;
263         while (q2!=NULL)
264         {
265             printf ("The %dnd ant is off the stick at time%d\n", q2->sign, q2->time);  //输出各蚂蚁离杆时间
266             q2=q2->next;
267         }
268 }
269 
270 /*用线性链表实现解决蚂蚁问题,若干蚂蚁位于一长杆上,杆长27cm,蚂蚁初始方向可以任意,运动速度1cm/s,蚂蚁从初始位置出发,两蚂蚁若相碰不能穿过对方,只能相碰后各自掉头,求蚂蚁全部爬出杆子所需时间*/