全信息学奥林匹克竞赛中得高分的关键环节-测试

[全]信息学奥林匹克竞赛中得高分的关键环节-测试中学生信息学奥林匹克竞赛是中学生奥林匹克竞赛的一个重要组成部分，和其他科目的奥林匹克竞赛相比它在竞赛方式上和评分标准上有着很大不同。竞赛实施的方式完全是上机编程序，实践性很强，评分的唯一标准是看通过测试数据的多少。通常竞赛中编写一个程序可以分为这样几个环节：分析题目—设计算法和数据结构—编码—调试—测试，设计测试数据的能力是竞赛考察的重点之一。但是很多学习信息学奥林匹克竞赛的学生和一些教师常常只重视算法的学习，忽视了“测试”这个环节。有的同学在竞赛中为了赶时间多做完一道题目，没有对已经做过的题目进行充分的测试，认为设计测试数据是浪费时间，所以经常会出现会做的题目不得分或者得不了满分的情况。那么怎么才能提高程序的正确率，在竞赛中取得高分呢？一、良好的习惯可以帮助提高编程正确率众所周知，要想提高学生编程的正确率必须要培养学生有一个良好的编程习惯。这些良好的习惯包括：A、规范地书写程序。我们书写程序时要使用缩进格式，不同层次的语句向后缩进若干格，这样可以保证程序尽量少出语法错误。另外，命名变量名时应尽量有一定意义，增加程序的可读性，调试程序时也方便。但是不要把变量名起得太长，这样会影响编程速度，可以使用一些简短的汉语拼音或英文缩写，只要自己好记就可以了。B、编程时要使用自顶向下分析的方法和模块化的方法。可以将一些独立的功能例如输入、输出功能模块化，这样在调试的时候可以逐模块地检查排错，将一个大规模问题分解成几个小规模问题。但是也不能盲目地将程序分割成太多模块，信息学奥林匹克竞赛中出的题目往往都不大，所以不必分成太多的模块，分得太多反而会成为累赘。模块化的依据主要在于程序的内在逻辑。C、使用全局变量时要特别小心。信息学奥林匹克竞赛中的程序规模一般比较小，全局变量的使用会很频繁，有时全局变量可以简化编程复杂度，但是全局变量的使用也会带来危险，特别是在过程或函数中改变全局变量的值可能会带来不可预期的后果。例如，在深度优先搜索中可以设一个全局的“栈”来存储搜索中的状态，但是在递归过程中，进入递归时数据“进栈”，回溯时数据“出栈”。在这个过程中要对全局变量“栈”和“栈的指针”进行操作，在这个过程中非常容易出错，出错后很难检查和调试。所以在教学中一定要给学生讲清楚全局变量和局部变量的区别，全局变量在过程或函数中被修改时对程序的影响，养成学生正确使用全局变量的习惯。二、测试是信息学奥林匹克竞赛中得高分的关键养成良好的习惯能避免编程中的很多错误，但是这还不足以能保证竞赛中编写的程序能通过所有的测试数据，这是因为竞赛评测时给的标准测试数据都是相当苛刻的，如果程序提交前没有经过充分的测试，很有可能不能通过标准测试数据。学生在参加竞赛时经常会遇到这样的情况：竞赛完了以后感觉非常好，觉得题目不难，而且几道题自己都做完了，都通过了样例数据，但是等成绩出来以后却和期望中的相差甚远。使用标准测试数据测试自己的程序后才发现，不是某些特殊情况没有考虑到，就是犯了小错误，例如变量误用，或者数组声明地太小。很多学生不止一次犯过类似这样的错误，常常因为这样的错误而懊悔不已，原本应该能够拿到的分数却没有拿到。大多数人把这种错误归咎于粗心，其实出现错误是很正常的，无论多么擅长编程的人都不可能完全避免出错。那么能不能及时纠正这些由“粗心”引起的错误呢？在竞赛中我们编写完一个题目后自己应该设计多组测试数据来测试自己的程序从而找到程序中隐藏的错误，测试是编程时的“把门将军”，他可以将错误拒之门外，测试进行得越充分，程序的正确率就越高，所以“测试”这一环节是竞赛中得高分的关键。三、学习和掌握系统的测试技术和方法题目给的样例数据都非常简单，不能只用它来测试程序。我们需要设计出精巧的测试数据，使用的数量既不多，不浪费竞赛中宝贵的时间，又能够找出程序中隐含的错误。要想尽量少使用数据，又能找出程序中尽可能多的错误，设计测试数据时就不能“跟着感觉走”，只有系统学习“软件工程”中的测试技术，并且不断在实践中总结经验，才能找出好的测试数据的设计方法。但是竞赛中编写的程序又区别于“软件工程”中的“软件”，例如竞赛中的程序一般规模不大、有严格的输入输出规定、程序模块逻辑复杂度比较大，所以也不能原样照搬软件工程中的测试技术。下面介绍一些经常使用的设计测试数据的原则和方法。1、设计测试数据的目的我们的目标是希望能够设计出这样的测试数据，它们能够系统地揭示不同类型的错误并且耗费最少的时间和工作量。2、设计测试数据的原则测试是一个为了发现错误而执行程序的过程。有很多人认为，一个成功的测试是指没有找到错误的测试。但是事实和这种观点正好相反，即使非常熟练编程员，也不能完全避免错误和疏漏的发生，一个好的测试应该能够揭示尚未发现的隐含错误。设计测试数据时也要抱着努力“破坏”程序的态度，不能自觉或不自觉地按照自己的思路设计程序恰好能接受的测试数据。Pareto原则。Pareto原则是指程序错误中的80%很可能来源于程序模块中的20%。这就提示我们，要想减少工作量，就要将程序按照模块分离，找出有疑点的模块进行充分测试，将主要精力集中在这些最有可能引起程序错误的模块。这些模块通常是程序中逻辑最复杂的和功能最关键的模块。测试应从独立模块开始，逐步转向整个程序。开始测试时把焦点放在单个模块上，先确保单个模块的在各种输入情况下的正确性，然后再考虑模块之间的联系和影响，最后在整个程序中查找错误。3、设计测试数据方法设计测试数据时我们通常使用两种方法：黑盒测试和白盒测试。在信息学奥林匹克竞赛中评测时主要使用黑盒测试，这是由竞赛的评测标准和易操作性的需要所决定的。但是我们在竞赛中要检查自己的程序是否存在错误，仅仅使用黑盒测试是不够的，白盒测试可以起到有效的补充作用。（1）黑盒测试黑盒测试是指不考虑程序的控制结构和实现细节，只考虑各种情况的输入是否能得出正确输出结果的一种测试方法。黑盒测试的优点在于设计方法简单、查找错误的效率高，而且使用这种方法设计测试数据时我们可以不考虑自己编写的程序只考虑问题本身，使用这样的测试数据可以更全面客观的测试自己的程序，主观影响小。下面介绍两种黑盒测试方法。A、等价划分。等价划分是一种黑盒测试方法，它将程序的输入域划分为等价类，每一类中的不同测试数据的测试效果相同。我们知道，即使一个小程序，想要穷举所有的输入数据也是不可能的，使用这种方法，可以将输入数据分为不同等价类，每一等价类只取一个测试数据。因为等价类的数目很小，这样我们就可以大大减少测试数据的个数，加快测试速度。另外，按照划分等价类的方法，可以让我们全面地设计各类测试数据，不容易遗漏。我们以USACOGate1.2.1《断开的项链》（BrokenNecklace）一题为例介绍等价划分的方法。【例】断开的项链有一条n（3<n<350）个珠子穿成的项链，珠子有红（red）、蓝（blue）、白（white）三种颜色，分别使用字母r,b,w来代表。如图所示：项链可以从某一个位置断开，然后从断开的位置沿着两个方向收集珠子。相同颜色的珠子能被收集到一块，白色的珠子能和蓝色的收集成一堆也能和红色的收集成一堆。问题：给定一个项链，问从哪里断开收集的珠子总个数最多。输入样例：（第一行是一个数字，表示项链中的珠子数；第二行是每个珠子颜色）29wwwbbrwrbrbrrbrbrwrwwrbwrwrrb输出样例：（输出结果是最多收集的珠子个数）11这个程序的算法并不复杂，因为数据规模不大，我们可以使用枚举断开位置的方法计算从每一个位置断开可以收集到的珠子数。我们通过分析可知输入数据可以分为如下几个等价类，相应的每个等价类可以设计一个代表测试数据：●项链中全是白色珠子(如6wwwwww)●项链中只有一种颜色（非白色）的珠子(如6rrrrrr)●项链中只有两种颜色珠子，其中一种是白色(如6wwwbbb)●项链中只有红、蓝两种颜色的珠子(如6rrrbbb)●项链中有三种颜色的珠子，红色和蓝色中间没有白色珠子(如6rwrbwb)●项链中有三种颜色的珠子，红色和蓝色中间有白色珠子(如6rwrbbw)B、边界值分析。边界值分析（BoundaryValueAnalysis,BVA）是一种注重分析选择测试数据来检查边界值的黑盒测试方法，它是等价划分的一种补充。边界值分析指出，输入域的边界比中间更容易发生错误。因此我们应该：a、如果输入条件指定为以x和y为下上界的范围，测试数据应当包括x、y、略大于x的值和略小于y的值；b、如果输入条件指定为一组值，测试数据应当执行其中的最大值和最小值，还应当测试略大于最小值、略小于最大值的值。黑盒测试有它的优点，但我们不能将所有精力仅用于这一种测试方法，这是因为黑盒测试自身有缺点。●不可能用黑盒测试穷举所有的输入数据。有一些隐含的错误，特别是条件、循环的特殊情况很难被发现，有限的测试数据很可能没有执行到某一段隐含错误的代码。●程序的逻辑有时是违反直觉的，这意味着我们关于控制流和数据流的一些无意识的假设可能导致编程错误，只有路径测试才能发现这些错误。因此，我们还需要使用白盒测试作为黑盒测试的补充。（2）白盒测试。白盒测试是在查看源程序过程中进行测试的一种方法，它使用过程设计的控制结构导出测试案例。也就是说，我们要针对程序的内部控制结构和存储结构来设计测试数据。我们在使用白盒测试的方法设计测试数据时需要：●保证一个模块中的所有独立路径至少被使用一次；●对所有逻辑值均需测试真、假；●在上、下边界之间即可操作范围内运行所有循环●检查内部数据结构以确保其有效性。上面介绍的几个对于测试数据的要求看起来非常难实现，其实我们在信息学奥林匹克竞赛中编写的程序规模都是非常小的，完成主要功能的模块只有一、两个。因此，我们可以把精力集中在主要功能模块上，设计少量的测试数据就可以覆盖该模块中的所有独立路径，测试的时候还可以使用“流程图”来帮助我们检查是否有遗漏的路径。进行白盒测试的时候还要特别注意：●分支语句中的条件（逻辑表达式）可能是单个条件也可能是复合条件（由and、or连接多个条件组成），应该对它们取true或false时的各种组合进行充分测试，不能仅仅查看整个逻辑表达式的值。●可以用数据流的方式跟踪察看起关键作用的数据结构的值，例如搜索中使用的栈或队列、图中使用的邻接表或邻接矩阵等。●测试循环时要注意while…do循环和repeat…until循环的区别、循环的退出条件、循环的边界。●测试递归过程或函数时要注意程序中修改的全局变量，还要注意退出递归的条件。4、两种测试方法的综合运用一般我们可以先不考虑自己编的程序，使用黑盒测试的方法将输入域划分多个等价类，充分分析边界值，针对这些等价类和边界值设计多个测试数据，然后用这些数据测试、调试和修改程序。需要注意的是，每当用一组测试数据找到程序错误后，对程序作的修改特别是比较大的修改可能会引入新的错误，修改程序后还要使用所有的测试数据重新测试。在信息学奥林匹克竞赛中特别是NOI中经常会出现大规模的测试数据，这主要是用来考察选手对于算法的优化能力。这些大规模的测试数据通常不容易设计，简单规律的大规模数据不能覆盖所有等价类，