6.模拟及高精度计算.pptVIP

第六讲;现实中的有些问题难以找到公式或规律来解决。只能按照一定步骤不停地做下去，最后才能得到答案。这样的问题，用计算机来解决十分合适，只要能让计算机模拟人在解决问题时的行为即可。这一类的问题可以称之为“模拟题”。;摘花生 /practice/2950; 有经验的多多一眼就能看出，每棵花生植株下的花生有多少。为了训练多多的算术，鲁宾逊先生说：“你先找出花生最多的植株，去采摘它的花生；然后再找出剩下的植株里花生最多的，去采摘它的花生；依此类推，不过你一定要在我限定的时间内回到路边。” 我们假定多多在每个单位时间内，可以做下列四件事情中的一件： (1) 从路边跳到最靠近路边（即第一行）的某棵花生植株； (2) 从一棵植株跳到前后左右与之相邻的另一棵植株； (3) 采摘一棵植株下的花生； (4) 从最靠近路边（即第一行）的某棵花生植株跳回路边。 现在给定一块花生田的大小和花生的分布，请问在限定时间内，多多最多可以采到多少个花生？注意可能只有部分植株下面长有花生，假设这些植株下的花生个数各不相同。; 例如在图2所示的花生田里，只有位于(2, 5), (3, 7), (4, 2), (5, 4)的植株下长有花生，个数分别为13, 7, 15, 9。沿着图示的路线，多多在21个单位时间内，最多可以采到37个花生。 ; 输入格式 输入的第一行包括一个整数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表示该植株下没有花生。 输出要求 输出包括T行，每一行只包含一个整数，即在限定时间内，多多最多可以采到花生的个数。 ;; 找规律得到一个以花生矩阵作为自变量的公式来解决这个问题，是不现实的。 结果只能是做了才知道。即走进花生地．每次要采下一株花生之前，先计算一下剩下的时间够不够走到那株花生，采摘，并从那株花生走回到路上。如果时问够．则走过去采摘；如果时间不够，则采摘活动到此结束。 设二维数组aField存放花生地的信息。然而，用aField[0][0]还是aField[1][1]对应花生地的左上角是值得思考一下的。因为从地里到路上还需要1个单位时间，题目中的坐标又都是从1开始。所以若aField[1][1]对应花生地的左上角，则从aField[i][j]点回到路上所需时间就是i，这样更为方便和自然，不易出错。;参考程序; while(nTotalTimeK) { //如果还有时间 int nMax=0, nMaxi, nMaxj; //最大的花生数目， //及其所处的位置 for(int i=1; i=M; i++) //下面这个循环寻找下一个 //最大花生数目及其位置 for(int j=1; j=N; j++) if(nMaxaFieId[i][j]) { nMax=aFieId[i][j]; nMaxi=i; nMaxj=j; } if(nMax = = 0) //地里已经没有花生了 break; if(nCuri = = 0) nCurj=nMaxj; //如果当前位置是在路上，那么 //应走到横坐标nMaxj处，再进人花生地; // 下一行看剩余时间是否足够走到(nMaxi，nMaxj)处，