信息学奥林匹克竞赛指导心得
信息学奥林匹克竞赛指导心得
青少年信息学奥林匹克联赛(NOIP)普及的重点是根据中学生的特点,培养学生学习计算机的兴趣,使得他们对信息技术的一些核心内容有更多的了解,提高他们创造性地运用程序设计知识解决实际问题的能力。通过三年的实践,我认识到,信息学奥林匹克联赛应该让更多的学生参预其中,学生生源雄厚,竞赛理念深入人心,我们的学生生源力量才会层出不穷,我们的联赛才会永葆鲜活的生命力。虽然最终获奖的只能是少数的学生,但不能让比赛从始至终都是少数人的竞争,那就失去了举办青少年信息学奥林匹克联赛的初衷。
我从2001年开始从事信息学奥林匹克竞赛的指导工作,第一年完全是在一种糊里糊涂的状态下在高一选了8名学生就参赛了,结果只有4名入围复赛,后来又全部出局了,尽管这次可以说是惨败,但学生们对竞赛有了一定的认识,出局的一些学生主动要求明年再上一次信息学联赛的考场。因为初试形式为笔试,侧重考察学生的计算机基础知识和编程的基本能力,并对知识面的广度进行测试。提高组的初赛试题难度不算太大,经过系统而全面的辅导,因成绩都相对不错,我们学校每年几乎全部同学都能够进入复赛。但由于重点高中学生学习的情况的特殊性,学生对非高考科目一般不会下太多功夫也没有时间在这方面有更多的时间给予指导,一般而言都是文件下来就开始从高一高二选一些学生,初赛报完名开始集训两个月,从完全空白到强行给学生灌输大量的程序和数据结构知识,虽能闯进复赛,但复赛的试题的难度就不够适应,或者有畏惧心理,虽然我们也做了相应的准备,但每次成绩都不理想,无法通过复赛试题的考察,最终也只能拿到市级的鼓励证书,而与内蒙级国家级差之甚远。对此,我虽心有不甘,但是通过实际的比赛,也让他们体会了竞赛的意义及学习的乐趣。我还是希望有一天我的学生也能有所突破。
经过近三年不断的努力,通过进一步的教学辅导工作,我对青少年信息学奥林匹克联赛(NOIP)也有了更加深刻的认识。对于初赛的组织要相对轻松一些。除了数据结构部分要进行进一步的辅导和练习外,基础知识部分可以结合高中学生信息技术会考内容同时进行,不需要花费太多的精力。只要感兴趣的同学报名参加初赛都会有一个可能认同的成绩。这同时也能极大的鼓舞学生的求学信心。
但到了复赛,就进入了比较专业的范畴了。进入到这一层面的同学就需要和指导教师一起来研讨关于竞赛的诸多问题了,例如程序算法,程序的调试,比赛时的策略,比赛的心态等等环节。中学生信息学奥林匹克竞赛是中学生奥林匹克竞赛的一个重要组成部分,和其他科目的奥林匹克竞赛相比它在竞赛方式上和评分标准上有着很大不同。竞赛复赛实施的方式完全是上机编程序,实践性很强,评分的唯一标准是依据测试数据,不给过程分。
分区联赛(NOIP)的辅导一般分为三个阶段。第一阶段是编程语言的学习。通常我们都是用PASCAL语言来做示例(以前也用过QBASIC),这个阶段主要是把编程语言中的语法结构交待清楚。基础的语言语法熟练了以后,再逐步深入地学习。这部分内容也可以要求学生们通过自学(比如自己看书上机编程、看现成的程序、讨论交流等)来完成,这样的学习方法不但可以牢固掌握和深刻理会知识点,还提高了自学能力。第二阶段是基础算法的学习和应用。如求最小公倍数/最大公约数,高精度(加减乘除/输入输出/组合数),查找排序,素数判定/方程的解/因式分解,进制转换及应用,N皇后问题(回溯法)等;学算法时,先让学生自己想,尝试去做;然后看标准算法和标准程序,实践。再对比一下优劣,取长补短。基本的算法必须是牢记的。这也今后竞赛编程的基础。第三阶段是关于数据结构的知识。包括简单数据结构:栈、队列、链表等;复杂一点的数据结构:树和图,基本概念(二叉树的计数)和基本算法(最短路径等);简单的深度搜索和广度搜索;更多的算法:动态规划等;初等组合:这是信息学解题的思维方式;图论:主要是基础概念方面的,用于理解算法;数学问题:这类题目考的是数学思维,或是数学建模创造力。一定要加强实战模拟练习,提高熟练程序和解题经验。
然后就进入竞赛的实战阶段。通常竞赛中编写一个程序可以分为这样几个环节:分析题目,设计算法,数据结构,编码,调试和测试。算法和设计测试数据的能力是竞赛考察的重点。算法和测试两大方面的学习和训练是我们应该注重的。
一、关于算法: 一个算法应该具有以下五个基本特征:1、有穷性,一个算法必须保证执行有限步之后结束;2、确切性,算法的每一步骤必须有确切的定义; 3、输入 ,一个算法有零个或多个输入,以刻画运算对象的初始情况。4、
输出 ,一个算法有一个或多个输出,以反映对输入数据加工后的结果。没有输出的算法是毫无意义的。5、可行性,算法原则上能够精确地运行,而且人们用笔和纸做有限次运算后即可完成。
常见算法和算法设计思想:
递推-当直接计算比较麻烦的时候可以尝试用递推方法。
递归― 把问题简化的重要思想。
贪心― 看起来简单,但是要证明贪心法可用也不是很容易的事情。
分治― 当尝试直接递归的做遇到困难的时候,可以考虑加入一些附加操作,形成分治法。其实很多题目都可以使用它。包括很多计算几何题目。
枚举 ― 简单的思想。
构造法― 如果手算问题的过程中受到很大启发,那么可以考虑使用构造法。 模拟法― 思路简单,有时也很有效。
修正与调整 ― 一种很重要的思想,在网络流,欧拉回路等问题的算法中都有体现。
数学方法- 例如列方程组,不等式组等,可以使问题清晰化。
二、关于程序代码的书写
养成良好的编程习惯,可以帮助我们提高编程正确率。首先程序书写要规范。我们书写程序时要使用缩进格式,不同层次的语句向后缩进若干格,这样可以保证程序尽量少出语法错误。命名变量名时应尽量有一定意义,增加程序的可读性,调试程序时也方便。但是不要把变量名起得太长,这样会影响编程速度,可以使用一些简短的汉语拼音或英文缩写,只要自己好记就可以了。
其次编程时要使用自顶向下分析的方法和模块化的方法。可以将一些独立的功能例如输入、输出功能模块化,这样在调试的时候可以逐模块地检查排错,将一个大规模问题分解成几个小规模问题。信息学奥林匹克竞赛中出的题目往往都不大,所以也不必分成太多的模块。模块化的依据主要在于程序的内在逻辑。
最后使用全局变量时要特别小心。信息学奥林匹克竞赛中的程序规模一般比较小,全局变量的使用会很频繁,有时全局变量可以简化编程复杂度,但是全局变量的使用也会带来危险,特别是在过程或函数中改变全局变量的值可能会带来不可预期的后果。例如,在深度优先搜索中可以设一个全局的“栈”来存储搜索
中的状态,但是在递归过程中,进入递归时数据“进栈”,回溯时数据“出栈”。在这个过程中要对全局变量“栈”和“栈的指针”进行操作,在这个过程中非常容易出错,出错后很难检查和调试。所以一定要给学生讲清楚全局变量和局部变量的区别,全局变量在过程或函数中被修改时对程序的影响,养成学生正确使用全局变量的习惯。
三、 测试是信息学奥林匹克竞赛的关键
竞赛评测时给的标准测试数据都是相当苛刻的,如果程序提交前没有经过充分的测试,很有可能不能通过标准测试数据。学生在参加竞赛时经常会遇到这样的情况:竞赛完了以后感觉非常好,觉得题目不难,而且几道题自己都做完了,都通过了样例数据,但是等成绩出来以后却和期望中的相差甚远。使用标准测试数据测试自己的程序后才发现,不是某些特殊情况没有考虑到,就是犯了小错误。其实出现错误是很正常的,无论多么擅长编程的人都不可能完全避免出错。那么怎样及时纠正这些由“粗心”引起的错误呢?在竞赛中我们编写完一个题目后,可以自己设计多组测试数据来测试程序,从而找到程序中隐藏的错误。测试是编程时的最后关卡,测试进行得越充分,程序的正确率就越高,所以“测试”这一环节是竞赛中获得最理想成绩的关键。
还有一点也是不容忽视的,那就和学生融洽的师生关系也是竞赛的一个重要因素。几乎每个辅导教师都会有这样的同感,对于我们辅导的学生有着一种由衷的爱意及欣赏的态度。为了这一份共同的事业可以克服个人的许多困难,并不只为了我们的学生一定要拿奖,为我们脸面增光。教师的亲和力也足以让学生产生信任感,并能够激发他们自觉自愿学习的勇气和信心。因为我们都知道,这是我们共同愿意为之付出汗水和泪水的事业。
虽然我的学生没有取得令人羡慕的奖项,但我仍会无怨无悔我的工作。收获的不仅仅是只有奖牌,还有一种理念,一种精神。
(作者单位:内蒙古杭锦后旗奋斗中学信息技术教研组 张敏)