如何设计测试数据-曹文.doc

如何设计测试数据 ——江苏省常州高级中学 曹文 （文章来源：《NOI专刊》总第13期） 有些同学参加一次信息学比赛之后，自我感觉非常不错，但是测评结果成绩却并不理想。造成这种情况的原因有多方面，但是我认为其中不可忽视的一大原因就是在写完程序之后，他们并不知道如何保证程序的正确性。在这里，我就这个问题提出一点自己的看法。 先从考试的时间分配问题讲起。很多同学觉得考试时间很充分，NOIP有三个小时，写完4个程序绰绰有余。显然这个想法是错误的。考试有三个小时，可这三个小时不是全都用来写程序的。一个合理的规划方案应该是： 1.半个小时读题，想算法； 2.一个半小时写程序； 3.一个小时制作测试数据测试程序。 当然，参加不同的比赛，题目质量不同，身体状态不同，心理压力也不同，这个规划方案不可能按部就班。但我认为它是有一定的指导意义的。下面让我们一起来仔细地分析一下整个方案。 读题和想算法，是比赛的重中之重，想必所有的同学都已经铭记于心，不必再多说了。而写程序的话，也许一个半小时仓促了一点，但是这其实只是一个编程熟练程度的问题。如果我们勤加练习，对算法和各种常用过程（快速排序、堆排序等）了如指掌，这个目标并不难达到。事实上，我校一位在NOIP2007中取得满分的同学读题加写程序一共只用了1小时15分钟。 最后一步，也是本文的中心，就是制作测试数据了。整个规划方案中安排了一个小时用来测试题目，也许有些同学会觉得没有必要。但是我认为，每一道题都应该设计测试数据，有些把握不大的题应该设计多种测试数据以保证测试的全面。因此，在这一个小时里，为4个程序设计数据，平均15分钟就要设计一个，这还不包括如果你发现了程序中的问题，再修改程序用的时间。这么一算，一个小时就有点吃紧了，似乎还不怎么够，不过其实还是够的，因为做数据比做题要简单得多。 测试数据分很多种。一般而言可以把它们分成小数据、大数据和极限数据三种。 一、小数据 样例无疑是所有OIer的最爱。大家学编程的时候就知道写完程序第一件事就是过样例，样例就是一个典型的小数据。小数据有三大优点： 1.易于调试。很多同学对pascal的调试模式有很大的依赖性，静态查错的能力很弱。严格地说这不能算是一个坏习惯，因为调试模式确实给我们带来了高效率，帮助我们在极短的时间找到程序的问题所在。但是调试的弊端就是不能处理大数据量的数据。因此，对于静态查错能力弱而调试能力相对较强的同学而言，小数据很重要，绝大部分的错误都是靠小数据的跟踪调试找到的。 2.易于设计。这一点不用多说。由于数据量小，我们往往可以手工设计质量更高的数据，同时对于数据本身也有直观的了解。与此同时，很多的题都会有所谓的“变态数据”，这和极限数据有着一些不同，它虽然数据量不大，但是剑走偏锋，比如某矩阵题给你一个全都是1的矩阵之类的。这种狡猾的数据在评测的时候往往并不罕见，由于这样那样的原因，我们就栽了跟头。为了使得自己的程序更加强壮，我们需要预先测试自己的程序是否能够通过这样的数据。这种变态数据只能够由我们手工设计，因此一般都是小数据。 3.覆盖面广。对于很多题目而言，测试数据理论上存在无穷多组；但是如果有n5并且所有数都小于10的限制，那么数据的个数就变得有限了，不妨设是1000组。我们可以通过写一个程序，直接把这1000组小数据全部都制作出来，然后逐个儿测试。虽然这些数据的数据量小，但是由于它们把小数据的所有可能的情况都包括在其中了，因此你的程序的大部分问题都能够在这1000组数据中有所体现。同时，因为是小数据，程序可以在很短的时间内运行出解，例如是0.05秒，这样，1000组数据，也不过只要50秒，完全可以接受。但是要注意，生成所有数据的同时，我们还要写一个效率差，确保正确的程序来验证结果的正确性。因此这种想法至少需要2个程序。（具体操作流程参考“大数据”部分）。 二、大数据 大数据是属于那种数据量比小数据大，同时可以使用较弱的替代算法得到结果的数据。一般的操作流程是这样的：先写一个随机化的制作大数据的程序；然后写一个针对题目的效率较差但是正确性能够保证的使用替代算法的程序；最后使用一个批处理文件，进行多次对比测试，即生成一个数据，然后再比较两个程序的结果。一定要注意这三个程序的文件输入输出和批处理的实现，这些地方很容易出错。 大数据的使用方法和前面讲过的小数据的穷举方法差不多，但是相比之下有些许不同： 1.数据量不同。数据量变大之后，对程序是一个新的挑战，一些更加难以发现的问题可能会显露出来。 2.可以随机化。与小数据不同，由于大数据的数据个数过多，不能够穷举完成，因此推荐使用随机化。而随机化显然比穷举要容易编写得多，因此大数据的实现更加方便。而随机化的缺点是，变态数据未必能够随机到。 而与极限数据相比，大数据的优点是可以使用替代算法。极限数