模拟与高精度计算

《模拟与高精度计算》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第六讲模拟与高精度计算ACM算法与程序设计数学科学学院：汪小平wxiaoping325@163.com现实中的有些问题难以找到公式或规律来解决。只能按照一定步骤不停地做下去，最后才能得到答案。这样的问题，用计算机来解决十分合适，只要能让计算机模拟人在解决问题时的行为即可。这一类的问题可以称之为“模拟题”。摘花生http://poj.grids.cn/practice/2950问题描述鲁宾逊先生有一只宠物猴，名叫多多。这天，他们两个正沿着乡间小路散步，突然发现路边的告示牌上贴着一张小小的纸条：“欢迎免费品尝我种

2、的花生！——熊字”。鲁宾逊先生和多多都很开心，因为花生正是他们的最爱。在告示牌背后，路边真的有一块花生田，花生植株整齐地排列成矩形网格（如图1）。有经验的多多一眼就能看出，每棵花生植株下的花生有多少。为了训练多多的算术，鲁宾逊先生说：“你先找出花生最多的植株，去采摘它的花生；然后再找出剩下的植株里花生最多的，去采摘它的花生；依此类推，不过你一定要在我限定的时间内回到路边。”我们假定多多在每个单位时间内，可以做下列四件事情中的一件：(1)从路边跳到最靠近路边（即第一行）的某棵花生植株；(2)从一棵植株跳到前后左

3、右与之相邻的另一棵植株；(3)采摘一棵植株下的花生；(4)从最靠近路边（即第一行）的某棵花生植株跳回路边。现在给定一块花生田的大小和花生的分布，请问在限定时间内，多多最多可以采到多少个花生？注意可能只有部分植株下面长有花生，假设这些植株下的花生个数各不相同。例如在图2所示的花生田里，只有位于(2,5),(3,7),(4,2),(5,4)的植株下长有花生，个数分别为13,7,15,9。沿着图示的路线，多多在21个单位时间内，最多可以采到37个花生。输入格式输入的第一行包括一个整数T，表示数据组数。每组输入的第一

4、行包括三个整数，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表示该植株下没有花生。输出要求输出包括T行，每一行只包含一个整数，即在限定时间内，多多最多可以采到花生的个数。样例输入1672100000000000130000000070150000000090000000000样

5、例输出37找规律得到一个以花生矩阵作为自变量的公式来解决这个问题，是不现实的。结果只能是做了才知道。即走进花生地．每次要采下一株花生之前，先计算一下剩下的时间够不够走到那株花生，采摘，并从那株花生走回到路上。如果时问够．则走过去采摘；如果时间不够，则采摘活动到此结束。设二维数组aField存放花生地的信息。然而，用aField[0][0]还是aField[1][1]对应花生地的左上角是值得思考一下的。因为从地里到路上还需要1个单位时间，题目中的坐标又都是从1开始。所以若aField[1][1]对应花生地的左上

6、角，则从aField[i][j]点回到路上所需时间就是i，这样更为方便和自然，不易出错。解题思路参考程序#include#include#include#includeintT,M,N,K;#defineMAX_NUM55intaField[MAX_NUM][MAX_NUM];intmain(){scanf(“%d”,&T);for(intt=0;t

7、的数组元素是aField[1][1]，路的纵坐标是0for(intm=1;m<=M;m++)for(intn=1;n<=N;n++)scanf(“%d”，&afield[m][n]);intnTotalPeanuts=0;//摘到的花生总数intnTotalTime=0;//已经花去的时问intnCuri=0，nCurj;//当前位置坐标，//nCuri代表纵坐标，开始是在路上，所以初值为0while(nTotalTime

8、//及其所处的位置for(inti=1;i<=M;i++)//下面这个循环寻找下一个//最大花生数目及其位置for(intj=1;j<=N;j++)if(nMax