武汉理工大学基础强化训练.doc

《武汉理工大学基础强化训练.doc》由会员分享，可在线阅读，更多相关《武汉理工大学基础强化训练.doc（16页珍藏版）》请在三一文库上搜索。

1、附件1：学 号： 课 程 设 计（基础强化训练）题 目花生问题（The Peanuts)学 院计算机科学与技术专 业软件工程班 级软件0804姓 名指导教师王舜燕2009年6月16日课程设计任务书学生姓名： 专业班级： 软件0804 指导教师： 王舜燕 工作单位：计算机科学与技术学院题 目: DNA 基因排序 初始条件： 输入： 输入的第一行包括三个整数，array_i, array_j 和time_limit，用空格隔开；表示花生田的大小为array_i * array_j（1= array_i, array_j = 20），多多采花生的限定时间为time_limit（0 = time_li

2、mit = 1000）个单位时间。接下来的M行，每行包括N 个非负整数，也用空格隔开；第i + 1 行的第j 个整数Pij（0 = Pij = 500）表示花生田里植株(i, j)下花生的数目，0 表示该植株下没有花生。输出： 输出包括一行，这一行只包含一个整数，即在限定时间内，多多在规定的时间内最多可以采到花生的个数。要求完成的主要任务: （包括课程设计工作量及其技术要求，以及说明书撰写等具体要求）1、完成算法分析2、给出对应的程序流程图3、给出能正确实现的程序源码5、给出试算截屏图6、课程设计工作的分析与总结7、给出不少于5篇参考文献。时间安排： 2009-7-13到2009-7-17指导

3、教师签名： 年 月 日系主任（或责任教师）签名： 年 月 日目录1 注册资料42 选题描述43 算法分析53.1 计算字符串的逆序数53.2 计数排序64 程序流程图85 程序源码96 试算截屏图117 分析与总结128 参考文献121 注册资料用户名：caoxulei密码：890630选题题号：19282 选题描述 英文描述：Mr. Robinson and his pet monkey Dodo love peanuts very much. One day while they were having a walk on a country road, Dodo found a sign

4、 by the road, pasted with a small piece of paper, saying Free Peanuts Here! You can imagine how happy Mr. Robinson and Dodo were.There was a peanut field on one side of the road. The peanuts were planted on the intersecting points of a grid as shown in Figure-1. At each point, there are either zero

5、or more peanuts. For example, in Figure-2, only four points have more than zero peanuts, and the numbers are 15, 13, 9 and 7 respectively. One could only walk from an intersection point to one of the four adjacent points, taking one unit of time. It also takes one unit of time to do one of the follo

6、wing: to walk from the road to the field, to walk from the field to the road, or pick peanuts on a point.According to Mr. Robinsons requirement, Dodo should go to the plant with the most peanuts first. After picking them, he should then go to the next plant with the most peanuts, and so on. Mr. Robi

7、nson was not so patient as to wait for Dodo to pick all the peanuts and he asked Dodo to return to the road in a certain period of time. For example, Dodo could pick 37 peanuts within 21 units of time in the situation given in Figure-2.Your task is, given the distribution of the peanuts and a certai

8、n period of time, tell how many peanuts Dodo could pick. You can assume that each point contains a different amount of peanuts, except 0, which may appear more than once.InputThe first line of input contains the test case number T (1 = T = 20). For each test case, the first line contains three integ

9、ers, M, N and K (1 = M, N = 50, 0 = K = 20000). Each of the following M lines contain N integers. None of the integers will exceed 3000. (M * N) describes the peanut field. The j-th integer X in the i-th line means there are X peanuts on the point (i, j). K means Dodo must return to the road in K un

10、its of time.OutputFor each test case, print one line containing the amount of peanuts Dodo can pick.Sample Input26 7 210 0 0 0 0 0 00 0 0 0 13 0 00 0 0 0 0 0 70 15 0 0 0 0 00 0 0 9 0 0 00 0 0 0 0 0 06 7 200 0 0 0 0 0 00 0 0 0 13 0 00 0 0 0 0 0 70 15 0 0 0 0 00 0 0 9 0 0 00 0 0 0 0 0 0Sample Output37

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

12、即第一行）的某棵花生植株；2) 从一棵植株跳到前后左右与之相邻的另一棵植株；3) 采摘一棵植株下的花生；4) 从最靠近路边（即第一行）的某棵花生植株跳回路边。例如在图2 所示的花生田里，只有位于(2, 5), (3, 7), (4, 2), (5, 4)的植株下长有花生，个数分别为13, 7, 15, 9。沿着图示的路线，多多在21 个单位时间内，最多可以采到37 个花生。输入： 第一行包括三个参数，第一第二个整数表示花生田的大小，第三个参数表示限制多多返回的最长时间。输出：输出就是多多在规定的时间内最多可以采到花生的数目。样例输入： 26 7 210 0 0 0 0 0 00 0 0 0 1

13、3 0 00 0 0 0 0 0 70 15 0 0 0 0 00 0 0 9 0 0 00 0 0 0 0 0 06 7 200 0 0 0 0 0 00 0 0 0 13 0 00 0 0 0 0 0 70 15 0 0 0 0 00 0 0 9 0 0 00 0 0 0 0 0 0样例输出：37283 算法分析3.1 判断采摘时间 我们可以将花生田模拟成一个矩阵，然后在矩阵中进行相应的操作。当结束一个采摘动作后，寻找花生田中下一个花生最多的位置。然后判断多多是否能从现在位置到达下一个花生个数最多的位置，完成采摘以及返回。如果时间允许的话就继续向下一个位置出发，如果时间不够则推出采摘。 i

14、f(time_count+Max_i+abs(curt_i-Max_i)+abs(curt_j-Max_j)+1)=time_limit) time_count=time_count+abs(curt_i-Max_i)+abs(curt_j-Max_j)+1; curt_i=Max_i; curt_j=Max_j; peanuts_count=peanuts_count+Max_peanuts; ArrayMax_iMax_j=0; 3.2 寻找花生个数最多的位置 由于花生田的矩阵不会很大，因此在本设计中采取了遍历矩阵的算法。遍历矩阵中所有的元素，找到当前花生个数最大的然后记录下他的行列下标，

15、以及花生个数。直到遍历整个矩阵结束。Max_peanuts=0;for(int ari=1;ari=array_i;ari+)for(int arj=1;arjMax_peanuts)Max_peanuts=Arrayariarj;Max_i=ari;Max_j=arj;3.3 矩阵初始化技巧 用二维数组存放花生地的信息是很自然的想法。然而，用 Array00还是Array11对应花生地的左上角，是值得思考一下的。因为从地里到路上还需要1 个单位时间，题目中的坐标又都是从1 开始，所以若aField11对应花生地的左上角，则从aFieldij点，回到路上所需时间就是i，这样更为方便和自然，不易

16、出错。并不是C/C+的数组下标从0 开始，我们使用数组的时候，就要从下标为0 的元素开始用。应该根据实际情况选取适合实际情况，并且处理起来不容易出错的下标进行初始化。4 程序流程图5 程序源码#include #include #define MAX_SIZE 51/矩阵最大行列值using namespace std;int main( ) int curt_i,curt_j;/矩阵中当前的位置int time_limit,array_i,array_j,num; /时间限制，以及花生矩阵的大小 int Array MAX_SIZEMAX_SIZE;/声明矩阵int peanuts_coun

17、t=0;/采摘到的花生cinnum;for(int i=0;iarray_i;cinarray_j;cintime_limit;peanuts_count=0;for(int ari=1;ari=array_i;ari+)for(int arj=1;arjArrayariarj;curt_i=0;curt_j=0;int num_peanuts=0;int Max_i=0;int Max_j=0;int Max_peanuts=0;int time_count=0;while (time_counttime_limit)Max_peanuts=0;/将最多的花生重置清零 /* 遍历矩阵挑选出其

18、中花生个数最多的，记录其行列下标以及花生个数*/for(int ari=1;ari=array_i;ari+)for(int arj=1;arjMax_peanuts)Max_peanuts=Arrayariarj;Max_i=ari;Max_j=arj; if (Max_peanuts=0) break; if (curt_i=0) curt_j=Max_j; /* 判断是否来得及时间从当前花生株到下一个花生株并且返回大路*/ if(time_count+Max_i+abs(curt_i-Max_i)+abs(curt_j-Max_j)+1)=time_limit) time_count=t

19、ime_count+abs(curt_i-Max_i)+abs(curt_j-Max_j)+1; curt_i=Max_i; curt_j=Max_j; peanuts_count=peanuts_count+Max_peanuts; ArrayMax_iMax_j=0; else break; coutpeanuts_countendl;return 0;6 试算截屏图7 分析与总结 本设计对于题目进行了模拟，将花生田模拟成了一个矩阵，然后在矩阵中进行操作。由于矩阵中的下标能够很好表示移动的时间，只要将行列下标想减取绝对值然后加上采摘的单位时间1，就能很好的满足题目的要求。由于编写代码的时候

20、细节注意不够未将Max_peanuts=0在循环体开头初始化为0，导致程序运行结果始终不正确，最后通过仔细分析才找到问题所在之处。由于题目给出了矩阵行列大小介于150之间，而最初定义的#define MAX_SIZE 为50即#define MAX_SIZE 50，由于下标0的元素均为使用导致了实际只用了Array4949大小的矩阵。因此在提交给服务器的时候始终提示Runtime Error，而自己又无法检测到程序出错的环节，最后参阅了指导书发现问题的所在只要宏定义为#define MAX_SIZE 51就能通过测试。所以以后宏定义大小的时候可以适当的增大一些空间，通过牺牲适当的空间换来安全性

21、和可靠性。8 参考文献1 Stanley B.Lippman .C+ PrimerM. 北京：人民邮电出版社，2008.2 谭浩强. C程序设计M. 北京：清华大学出版社，2005.3 严蔚敏，吴伟民. 数据结构M. 北京:清华大学出版社，1996.4 Stephen Prata. C+ Primer PlusM.北京：人民邮电出版社，2008.5 李文新、郭炜、余华山 .程序设计导引及在线实践M.北京 清华大学出版社 本科生课程设计成绩评定表班级：软件0804姓名：学号：0120810680426序号评分项目满分实得分1学习态度认真、遵守纪律102设计分析合理性103设计方案正确性、可行性、创造性204设计结果正确性405设计报告的规范性106设计验收10总得分/等级评语：注：最终成绩以五级分制记。优（90-100分）、良（80-89分）、中（70-79分）、及格（60-69分）、60分以下为不及格指导教师签名：2010 年月日