信息学竞赛辅导中“挤”的艺术_信息学联赛辅导_高中频道-查字典高考网
 
请输入您要查询的关键词

信息学竞赛辅导中“挤”的艺术

发布时间: 2009-11-12   来源:查字典高考网

在信息学竞赛辅导中,培养学生抓住题目本质、把题目做完全(得满分)的能力是非常重要的。在高层次的竞赛中,大部分已经达到一定层次的学生的水平实际上非常接近。比如在广东省信息学奥赛总决赛中,对于每天的四个题目,高层次的学生(这类学生全省有30人左右)一般都能做其中三题。请注意,我这里用的是能做二字,一些题目很多学生能做,但却不能得到该题的满分,这里就是涉及到能否把能做的题目做完全的问题。而一旦谁能把能做的这几题做完全,有两题或两题以上都得到满分(或高分),谁就将脱颖而出,进入省前五名是顺理成章的事。

例如有这样一题竞赛题:求N个字母的字符串组合:

如:用A、B、C三个字母组成长度为3的字符串,但每个字母都不允许重复使用,并且每个字母都不能摆在自己序号的位置上,则符合条件的只有两个字符串:BCA、CAB。对于键盘输入的n(n=17),则意味着给出了A1、A2、、An个不同的字母,用它们组成长度为N的字符串,但每个字母不允许重复使用,并且每个字母都不能摆在自己序号的位置上。问有多少个符合条件的字符串S。

几乎所有学生一拿到就立刻用递归算法下手,对于输入的n,把满足条件的n个字符的字符串全部找出来,最后输出总数,不用多少时间就得到程序,一运行,结果也对,于是绝大部分学生都认为大功告成了。熟不知测试数据中有n=17的情况,而限时竟然只有短短的5秒!绝大部分同学都因大数据超时而只得到该题的很少的几分。显然,对于这样一题人人会做的题目,最终却只有少数几人能做得完全,能得满分。事实上,此题有一公式,对于n=17的情况也不用1秒就能得出结果,找到这一公式才能把这题做得完全,虽然使用的仍是递归算法,但速度却要快出无数倍,因为对于输入的n,直接计算字符串的总数而无需得到每一个字符串,耗时自然大大减少了。给出公式如下:

0  (x=1)

f(x)= x*f(x-1)+1 (x2,x mod 2=0)

x*f(x-1)-1 (x2,x mod 2=1)

程序自然不必多说了。

所以,一个题目会做却并不等于你能把这题做全,能把这题的分得全,这就是真高手与半高手的区别。那么,怎样才能在平常的训练中培养学生的这种把题目做全的能力呢?下面笔者想以第四届全国青少年信息学(计算机)奥林匹克分区联赛复赛高中组第二题为例,谈谈笔者在奥赛训练中采用的挤的训练方法。

题目如下:

设有N个正整数(N=20),将它们联成一排,组成一个最大的多位整数。

例如:N=3时,3个整数13、312、343联成的最大整数为:34331213;

又如:N=4时,4个整数7,13,4,246联成的最大整数为:7424613;

输入: N

N个数

输出:联成的多位数。

测试数据如下:

序号

输入

输出

分值

1

3

121 21 3

321121

5

2

4

13 24 75 42

75422413

10

查看全部
推荐文章
猜你喜欢
附近的人在看
推荐阅读
拓展阅读
大家都在看