当前位置:首页 > 奥林匹克 > 信息学奥林匹克 > 信息学奥赛大数据测参快速制作方法(图文)

信息学奥赛大数据测参快速制作方法(图文)

发表日期:2019-10-15 14:08:08文章编辑:信息管理员浏览次数: 标签:    

 

在信息学奥林匹克竞赛过程中,自己制作测试参数,不仅可以检验程序的正确性,还对解题思路有一定的启示作用。有些程序测试参数制作难度不大,例如求表达式的结果,测试输入参数就是一个数字表达式。输出结果则是表达式的值,我们轻易就能算出结果。大规模的测试数据就不太好做。本文特别讨论一下,规模较大的测试参数的快速制作方法。

大数据测试参数要用来测试程序在空间和时间上的效率,所以测试参数的规模要接近数目的上限,不仅要检验程序的正确性,还由于数据量很大,给制作测参带来两个困难,一是数字多,输入费时费力。而是计算困难,无法手工运算获得正确结果。那么如何来解决这样的问题呢?下面我们举例说明集中测试参数的制作方法。

  例一、数字三角形

数字三角形是一个常做的训练题,因为它有可以适应多种方法解题,但主要用来训练新手学习动态规划,这里用它来做一个100行的数据。

100行的数字三角形,且11个,22个,...nn个。如果我们用随机函数来产生一个100行的数字三角形,难度不大,可是正确结果是什么,没发预料,也不便计算。

如果我们通过程序按格式要求产生5000个均为50的数,那这个测考的输出结果,毫无疑问的结果是50*100

接下来,我们将任意行任意列的一个50改为98,无疑输出正确结果为50*99+98=5048

但上述测量,用贪心法也能获得正确的结果,于是我们在98的上一行,且不在同一路径上的列上改一个5065(大于50但小于98)。如图1所示,如果程序的输出结果仍为5048,则已能证明动态规划程序的正确性。

为了进一步证明程序的正确性,我们还可以在98的路线上修改两个相邻的数,且一大一小,使程序能选择其中大的那个数,至此,我们就完全可以放心了。

上述方式,由100行改成200行,方法也不变,工作量不增加。且输入数据制作好的入、输出结果也会立马得出。

  例二 走迷宫

走迷宫是宽度优先搜索的重要练习题,在0-1矩阵是搜索一条从左上角到右下角的最短路径。当数据稍大时,路径的复杂程度可想而知。如果随机产生数据几乎是不可能的,因为要手工清理出最短路径也是一个高难度动作,费时费力。

所以,我们的办法是,我们用程序生成一个100x1000-1矩阵,其边界和内部除一条阶梯道路外,其余均外为0,如图2所示。

此图的输出最短路径长度为n+m-1

如果我们在这条通道上增加多个死胡同,相信大家能够理解,这些死胡同对程序正确输出结果没有影响,但可检验程序对死胡同处理的正确性。

如果我们将最短通道的任何一个1改为0。则输出结果为“No Answer!”,再增加一个弯道,形成道路,则新的结果为:n+m+弯道长度-2

为了进一步检测时间和空间效率,可继续增加死胡同数量和可导通路径。虽然这个数据制作会与数据规模大小有一定关系,但仍然能保持快速制作,且修改完成,结果一起出来。

222.png

                                                                                 图3 邻接图                                                                   4 增加路径

例三 最短路径问题

在图论中有两种经典的计算最短路径问题的方法,这不是本文讨论的关键,本文讨论的是如何快速得到一组又一组的数据,同时我们要借助特殊方式来处理。我们不妨将图简化为图3的方格图,共100个结点。这个图看起来简单,可是其邻接矩阵却有10000个数据,我们又假定相邻任意两点的距离场为80,则邻接矩阵就可以由程序实现,而任意两点之间的最短路径也就容易计算出来,即两节点(行差+列差)x80

大家看到这,知道下一步要修改了。

首先,我们将其中两个相邻结点之间的距离减小一个为50,即路径上包含这一路径的两结点之间的最短路径同时减小30,第二个测量又完成了所谓路径包含,是指以起点与终点,在图3中组成的矩形包含刚才减小的那条路径,故也可以用程序来修改参数。

其次,我们在任意两个不相邻的结点ij之间增加一条边,如图4中的斜线所示。假设它的长度为原来的最短长度-50(不能大于80),即邻接矩阵里的G[i,j]0变成S[i,j]-50,仍然会有邻接矩阵的相应变化,即包含上述路径的矩形对角线之间的最短路径减小50

接下来,我们将在已改的基础上,将一条边的权改为0,即去掉非加上去的一条边,此时,仅仅对去掉边的两个端点产生影响外,对其他两点之间的距离没有影响。

最后,我们将一列横线或一行竖线,除留上边或左边一条通道外,其余全部去除,则同在左边和右边的结点之间的最短路径不变,但左右两边结点的最短距离,如图5所示,由三部分组成,即由左边A点到A点的最短路径+AB长度+B点到右边各点的最短路径。

综上所述,我们在做大规模数据时,先用相同或相近,或有规律的数据,用程序编写成一个数据模板,但最终运算结果也非常清楚。

然后,修改一些关键的数据,使修改后的数据既不失一般性,又具有特殊性。每一次更改产生一组新的数据,且输出结果简单易算。

333.png

  图5  去掉一列道路

修改数据时,要考虑用其他算法可能导致的错误,防止用别的不正确算法也能得出正确结论这样的情况。还有一些边界条件等相关问题。

如没特殊注明,文章均为亮宁电子原创,转载请注明出处
相关新闻

枚举循环优化习题(图文)

一、 减少循环的层数1、市场上三种鸡的价格是:母鸡5文钱一只,公鸡3文钱一致,仔鸡1文钱3只。某人想用100文钱买100只鸡,请列出所有可行的方案。2、四位数abcd是11的倍数,其中...

日期:2019-10-15

信息学奥赛大数据测参快速制作方法(图文)

在信息学奥林匹克竞赛过程中,自己制作测试参数,不仅可以检验程序的正确性,还对解题思路有一定的启示作用。有些程序测试参数制作难度不大,例如求表达式的结果,测试输入参数就是...

日期:2019-10-15

信息学奥林匹克数论基础题

1、已知3个不同的质数之和是最小合数的完全平方,求这3个质数的和。2、筐里有96个苹果,如果不一次全拿出,也不一个一个地拿,要求每次拿出同样多,拿完时不多不少,有多少种不同的拿...

日期:2019-09-25