浅析模拟算法

1.描述

     有些问题难以找到公式或规律来解决，可以按照步骤，模拟人的解决行为，一步一步往下走就能找到答案。

2.实例分析

   （1）（北大考研机试）一根长度为1米的木棒上有若干只蚂蚁在爬动。它们的速度为每秒一厘米或静止不动，方向只有两种，向左或者向右。如果两只蚂蚁碰头，则它们立即交换速度并继续爬动。三只蚂蚁碰头，则两边的蚂蚁交换速度，中间的蚂蚁仍然静止。如果它们爬到了木棒的边缘（0或100厘米处）则会从木棒上坠落下去。在某一时刻蚂蚁的位置各不相同且均在整数厘米处（即1，2，3，…99厘米），有且只有一只蚂蚁A速度为0，其他蚂蚁均在向左或向右爬动。给出该时刻木棒上的所有蚂蚁位置和初始速度，找出蚂蚁A从此时刻到坠落所需要的时间。

 

输入

第一行包含一个整数表示蚂蚁的个数N（2<=N<=99），之后共有N行，每一行描述一只蚂蚁的初始状态。每个初始状态由两个整数组成，中间用空格隔开，第一个数字表示初始位置厘米数P（1<=P<=99），第二个数字表示初始方向,-1表示向左，1表示向右，0表示静止。
输出

蚂蚁A从开始到坠落的时间。若不会坠落，输出“Cannot fall!”

样例输入

4

10 1

90 0

95 -1

98 -1

样例输出

98

 

分析：输入蚂蚁信息后，模拟时间从1开始增加，时间每增加1，改变在木棒上各个蚂蚁的位置，然后判断是否有蚂蚁坠落、是否有三只蚂蚁碰头（因为只有一只蚂蚁的速度是0，所以最多只可能发生一处三只蚂蚁碰头的情况，关键是找到速度为0的蚂蚁）、判断是否有两只蚂蚁碰头。直到蚂蚁A坠落则结束。注意：a、每次碰撞后从第一只蚂蚁检测碰撞 b、碰撞可能发生在整数点的位置也可能发生在非整数点的位置

实现：a.定义蚂蚁的结构体：包含蚂蚁的速度，蚂蚁的位置

         b.定义一个数组，数组元素是一只蚂蚁。初始化蚂蚁信息

          c.循环，每次时间加1，改变蚂蚁位置，然后判断。。。直到蚂蚁A坠落

 

 

/**
  * 蚂蚁坠落
  *
  **/

#include<stdio.h>
#define MAX_ANT_NUMBER 101 //最大蚂蚁数量

//蚂蚁结构体定义如下
typedef struct
{
	int speed;//蚂蚁的速度，有正负之分（+1或者是-1）
	int site;//蚂蚁的位置
}Ant;

Ant antArray[MAX_ANT_NUMBER];
int front,rear,index,k; //分别指向蚂蚁数组的第一只、A、最后一只蚂蚁、速度为0的蚂蚁
int time=0;

//初始化蚂蚁的信息
void init()
{
	int i;
	front=0;
	printf("please enter ant's number:\n");
	scanf("%d",&rear);
	printf("please enter ant's site speed:\n");
	for(i=0;i<rear;i++){
		scanf("%d%d",&antArray[i].site,&antArray[i].speed);
		if(antArray[i].speed==0)
			k=index=i;
	}
  	rear--;  
}

//蚂蚁移动
int move()
{
	int i,temp;
	int f=0;
	while(1){
		//A蚂蚁坠落
		if(antArray[index].site==0||antArray[index].site==100)
			break;
		//判断两端是否有蚂蚁坠落
		if(antArray[front].site==0){
			front++;
		}
		if(antArray[rear].site==100){
			rear--;
		} 
		//处理碰头，发生碰头交换速度。注意，没发生一次碰头，便从第一只蚂蚁开始检测是否发生碰头
		for(i=front;i<=rear-1;i++){
     		//判断是否三只蚂蚁碰头,有的话交换速度
     		if(k-1>=front && k+1<=rear && antArray[k-1].speed==1 && antArray[k+1].speed==-1 && 
				antArray[k-1].site+1==antArray[k].site && antArray[k+1].site-1==antArray[k].site){
                temp=antArray[k-1].speed;
                antArray[k-1].speed=antArray[k+1].speed;
		        antArray[k+1].speed=temp;
				i=front-1;
				f=1;
				continue;
			}
			//判断是否有两只蚂蚁碰头（其中一只速度为0），有的话交换速度
			if(antArray[k-1].speed==1 && (antArray[k-1].site==antArray[k].site)){
               temp=antArray[k].speed;
               antArray[k].speed=antArray[k-1].speed;
			   antArray[k-1].speed=temp;
			   k=k-1;
			   i=front-1;
			   f=1;
			   continue;
			}
			if(antArray[k+1].speed==-1 && (antArray[k+1].site==antArray[k].site)){
               temp=antArray[k].speed;
               antArray[k].speed=antArray[k+1].speed;
			   antArray[k+1].speed=temp;
			   k=k+1;
			   i=front-1;
			   f=1;
			   continue;
			}

			//判断是否有两只蚂蚁速度都不为0的蚂蚁碰头，分两种碰头情况
			//不是在整数点位置碰头
			if(antArray[i].speed==1 && antArray[i+1].speed==-1 && antArray[i].site-1==antArray[i+1].site){
               temp=antArray[i].speed;
               antArray[i].speed=antArray[i+1].speed;
			   antArray[i+1].speed=temp;
			   antArray[i].site--;
			   antArray[i+1].site++;
			   i=front-1;
			   f=1;
			   continue;
			}
			//在整数点位置碰头
    		if(antArray[i].speed==1 && antArray[i+1].speed==-1 && antArray[i].site==antArray[i+1].site){
               temp=antArray[i].speed;
               antArray[i].speed=antArray[i+1].speed;
			   antArray[i+1].speed=temp;
			   i=front-1;
			   f=1;
			   continue;
			}
		}
		for(i=front;i<=rear;i++)
			//蚂蚁走一步
            antArray[i].site+=antArray[i].speed;			
        time++;
		if(time>100 && f==0)
			return 0;
	}
	return 1;
}
void main()
{
	init();
	if(move())
    	printf("蚂蚁A坠落的时间是：%d\n",time);
	else
    	printf("Can't fall\n");

}

 

（2）打印蛇形矩阵（也称螺旋上三角）

分析与代码实现：http://touch-2011.iteye.com/blog/1044775

  

（3）鲁宾逊先生有一只宠物猴，名叫多多。这天，他们两个正沿着乡间小路散步，突然发现路边的告示牌上贴着一张小小的纸条：“欢迎免费品尝我种的花生！——熊字”。
鲁宾逊先生和多多都很开心，因为花生正是他们的最爱。在告示牌背后，路边真的有一块花生田，花生植株整齐地排列成矩形网格（如图1）。有经验的多多一眼就能看出，每棵花生植株下的花生有多少。为了训练多多的算术，鲁宾逊先生说：“你先找出花生最多的植株，去采摘它的花生；然后再找出剩下的植株里花生最多的，去采摘它的花生；依此类推，不过你一定要在我限定的时间内回到路边。”
 


我们假定多多在每个单位时间内，可以做下列四件事情中的一件：
1) 从路边跳到最靠近路边（即第一行）的某棵花生植株；
2) 从一棵植株跳到前后左右与之相邻的另一棵植株；
3) 采摘一棵植株下的花生；
4) 从最靠近路边（即第一行）的某棵花生植株跳回路边。
现在给定一块花生田的大小和花生的分布，请问在限定时间内，多多最多可以采到多少个花生？注意可能只有部分植株下面长有花生，假设这些植株下的花生个数各不相同。
例如在图2所示的花生田里，只有位于(2, 5), (3, 7), (4, 2), (5, 4)的植株下长有花生，个数分别为13, 7, 15, 9。沿着图示的路线，多多在21个单位时间内，最多可以采到37个花生。

Input

输入的第一行包括一个整数T，表示数据组数
每组输入的第一行包括三个整数，M, N和K，用空格隔开；表示花生田的大小为M * N（1 <= M, N <= 50），多多采花生的限定时间为K（0 <= K <= 1000）个单位时间。接下来的M行，每行包括N个非负整数，也用空格隔开；第i + 1行的第j个整数Pij（0 <= Pij <= 500）表示花生田里植株(i, j)下花生的数目，0表示该植株下没有花生。

Output

输出包括T行，每一行只包含一个整数，即在限定时间内，多多最多可以采到花生的个数。

 

分析：注意到题目要求“找出剩下的植株里花生最多的，去采摘它的花生”。所以先走进花生地，每次要采下一株花生之前，先计算一下是否有足够的时间走到那株花生、采摘、回到路上，如果时间不够，则采摘活动结束。

实现：定义一个二维数组存放花生地，找出最多花生的那株的位置，然后根据多多的当前位置判断是否能摘这株花生，如果不能则结束。

 

(4)题目：

 

分析：