《模拟与高精度计算教学提纲》由会员分享，可在线阅读，更多相关《模拟与高精度计算教学提纲（65页珍藏版）》请在金锄头文库上搜索。
1、第六讲,模拟与高精度计算,ACM算法与程序设计,数学科学学院：汪小平 ,现实中的有些问题难以找到公式或规律来解决。只能按照一定步骤不停地做下去，最后才能得到答案。这样的问题，用计算机来解决十分合适，只要能让计算机模拟人在解决问题时的行为即可。这一类的问题可以称之为“模拟题”。,摘花生 ,问题描述 鲁宾逊先生有一只宠物猴，名叫多多。这天，他们两个正沿着乡间小路散步，突然发现路边的告示牌上贴着一张小小的纸条：“欢迎免费品尝我种的花生！熊字”。 鲁宾逊先生和多多都很开心，因为花生正是他们的最爱。在告示牌背后，路边真的有一块花生田，花生植株整齐地排列成矩形网格（如图1）。,有经验的多多一眼就能看出，每
2、棵花生植株下的花生有多少。为了训练多多的算术，鲁宾逊先生说：“你先找出花生最多的植株，去采摘它的花生；然后再找出剩下的植株里花生最多的，去采摘它的花生；依此类推，不过你一定要在我限定的时间内回到路边。” 我们假定多多在每个单位时间内，可以做下列四件事情中的一件： (1) 从路边跳到最靠近路边（即第一行）的某棵花生植株； (2) 从一棵植株跳到前后左右与之相邻的另一棵植株； (3) 采摘一棵植株下的花生； (4) 从最靠近路边（即第一行）的某棵花生植株跳回路边。 现在给定一块花生田的大小和花生的分布，请问在限定时间内，多多最多可以采到多少个花生？注意可能只有部分植株下面长有花生，假设这些植株下的
3、花生个数各不相同。,输入格式 输入的第一行包括一个整数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行，每一行只包含一个整数，即在限定时间内，多多最多可以采到花生的个数。,样例输入 6 7 21 0 0 0 0 0 0 0 0 0 0 0 13
4、0 0 0 0 0 0 0 0 7 0 15 0 0 0 0 0 0 0 0 9 0 0 0 0 0 0 0 0 0 0 样例输出 37,找规律得到一个以花生矩阵作为自变量的公式来解决这个问题，是不现实的。 结果只能是做了才知道。即走进花生地每次要采下一株花生之前，先计算一下剩下的时间够不够走到那株花生，采摘，并从那株花生走回到路上。如果时问够则走过去采摘；如果时间不够，则采摘活动到此结束。 设二维数组aField存放花生地的信息。然而，用aField00还是aField11对应花生地的左上角是值得思考一下的。因为从地里到路上还需要1个单位时间，题目中的坐标又都是从1开始。所以若aField1
5、1对应花生地的左上角，则从aFieldij点回到路上所需时间就是i，这样更为方便和自然，不易出错。,解题思路,参考程序,#include #include #include #include int T, M, N, K; #define MAX_NUM 55 int aFieldMAX_NUM MAX_NUM; main() scanf(“%d, /当前位置坐标， /nCuri代表纵坐标，开始是在路上，所以初值为0,while(nTotalTimeK) /如果还有时间 int nMax=0, nMaxi, nMaxj; /最大的花生数目， /及其所处的位置 for(int i=1; i=M;
6、 i+) /下面这个循环寻找下一个 /最大花生数目及其位置 for(int j=1; j=N; j+) if(nMaxaFieIdij) nMax=aFieIdij; nMaxi=i; nMaxj=j; if(nMax = = 0) /地里已经没有花生了 break; if(nCuri = = 0) nCurj=nMaxj; /如果当前位置是在路上，那么 /应走到横坐标nMaxj处，再进人花生地,/ 下一行看剩余时间是否足够走到(nMaxi，nMaxj)处， /摘取花生，并回到路上 if(nTotaITime+nMaxi+1+abs(nMaxi-nCuri) +abs(nMaxj-nCurj)
7、 =K) / 下一行加上走到新位置，以及摘花生的时问 nTotalTime+=1+abs(nMaxi-nCuri)+abs(nMaxj-nCurj); nCuri=nMaxi; nCurj=nMaxj; /走到新的位置 nTotaiPeanuts+=aFieldnMaxinMaxj; aFieldnMaxinMaxj=0; /摘走花生 else break； printf(“%dn”, nTotalPeanuts); ,常见问题,这个题目应该仔细阅读。往往没有看到每次只能拿剩下花生株中最大的，而是希望找到一种在规定时间内能够拿最多花生的组合，把题目变成了另外一道题。 没有读到没有两株花生株的花
8、生数目相同”的条件，因此把题目复杂化了。 这个题目是假设猴子在取花生的过程中不会回到大路上，而有些同学思考是否可能在中间回到大路上，因为题目没说在大路上移动要花时间，所以有可能中途出来再进去摘的花生更多。 本题的解法虽然直观但是有一个弊端就是每次在寻找下一个最大花生植株时，都要遍历整个矩阵，效率不高。用什么办法才能高效率地找到下一个最大花生植株?,显示器,1、链接地址 2、问题描述 你的一个朋友买了一台电脑。他以前只用过计算器，因为电脑的显示器上显示的数字的样子和计算器是不一样，所以当他使用电脑的时候会比较郁闷。为了帮助他，你决定写一个程序把在电脑上的数字显示得像计算器上一样。,输入数据 输入
9、包括若干行，每行表示一个要显示的数。每行有两个整数s 和n (1 = s = 10, 0 =n= 99999999)，这里n 是要显示的数，s 是要显示的数的尺寸。如果某行输入包括两个0，表示输入结束。这行不需要处理。 输出要求 显示的方式是：用s 个-表示一个水平线段，用s 个|表示一个垂直线段。这种情况下，每一个数字需要占用s+2 列和2s+3 行。另外，在两个数字之间要输出一个空白的列。在输出完每一个数之后，输出一个空白的行。注意：输出中空白的地方都要用空格来填充。,输入样例 2 12345 3 67890 0 0,输出样例,一个计算器上的数字显示单元，可以看作由以下编号从1 到7 的7
10、 个笔画组成：,3、解题思路,那么，我们可以说，数字8 覆盖了所有的笔画，数字7 覆盖笔画1、3 和6，而数字1覆盖笔画3、6。注意，每个笔画都是由s 个-或s 个|组成。 输出时，先输出第1 行，即整数n 中所有数字里的笔画1，然后输出第2 行到第s+1 行，即所有数字的笔画2 和笔画3，接下来是第s+2 行，即所有数字的笔画4，再接下来是第s+3行到2s+2 行，就是所有数字的笔画 5 和笔画6，最后的第2s+3 行，是所有数字的笔画7。如果某个数字d 没有覆盖某个笔画m (m = 17)，那么，输出数字d 的笔画m 的时候，就应该都输出空格；如果覆盖了笔画m，则输出s 个-或s 个|，这
11、取决于笔画m 是横的还是竖的。,解题思路,由上思路，解决这道题目的关键，就在于如何记录每个数字都覆盖了哪些笔画。实际上，如果我们记录的是每个笔画都被哪些数字覆盖，则程序实现起来更为容易。一个笔画被哪些数字所覆盖，可以用一个数组来记录，比如记录笔画1 覆盖情况的数组如下： char n111 = - - -; 其中，n1i(i = 09) 代表笔画1 是否被数字i 覆盖。如果是，则n1i 为-，如果否，则n1i为空格。上面的数组的值体现了笔画1 被数字0, 2, 3, 5, 6, 7, 8, 9 覆盖。 对于竖向的笔画2，由字符 | 组成，则记录其覆盖情况的数组如下： char n211 = |
12、 | |; 该数组的值体现了笔画2 被数字0, 4, 5, 6, 8, 9 覆盖。,解题思路,4、参考程序,#include #include char n111=- - -;/笔画1 被数字0,2,3,5,6,7,8,9 覆盖 char n211=| | |;/笔画2 被数字0,4,5,6,8,9 覆盖 char n311=| |;/笔画3 被数字0,1,2,3,4,7,8,9 覆盖 char n411= - -;/笔画4 被数字2,3,4,5,6,8,9 覆盖 char n511=| | | | ;/笔画5 被数字0,2,6,8覆盖 char n611=| |;/笔画6 被数字0,1,3,
13、4,5,6,7,8,9 覆盖 char n711=- - - -;/笔画7 被数字0,2,3,5,6,8,9 覆盖 int main(void) int s; char szNumber20; int nDigit , nLength, i , j , k;,while(1) scanf( %d%s, ,4、参考程序,for (i = 0 ; i s ; i+) /输出所有数字的笔画2 和笔画3 for (j = 0 ; j nLength ; j+) nDigit = szNumberj - 0; printf(%c, n2nDigit); for (k = 0 ; k s ; k+) pr
14、intf( ); /笔画2 和笔画3 之间的空格 printf(%c , n3nDigit);/有一个空格 printf(n); for (i = 0 ; i nLength ; i+) /输出所有数字的笔画4 printf( ); nDigit = szNumberi - 0; for (j = 0 ; j s ; j+) printf(%c, n4nDigit); printf( );/两个空格 printf(n);,4、参考程序,4、参考程序,for (i = 0 ; i s ; i+) /输出所有数字的笔画5 和笔画6 for (j = 0 ; j nLength ; j+) nDig
15、it = szNumberj - 0; printf(%c, n5nDigit); for (k = 0 ; k s ; k+) printf( ); /笔画5 和笔画6 之间的空格 printf(%c , n6nDigit);/有一个空格 printf(n); for (i = 0 ; i nLength ; i+) /输出所有数字的笔画7 printf( ); nDigit = szNumberi - 0; for (j = 0 ; j s ; j+) printf(%c, n7nDigit); printf( );/两个空格 printf(n); printf(n); return 0; ,5、实现技巧,一个笔画被哪些数字所覆盖，最直接的想法是用整型数组来记录，比如： int n110 =
