案例教学法在信息学奥赛培训中的应用.doc

案例教学法在信息学奥赛培训中的应用【摘要】本文针对信息学奥赛培训的特点，提出信息学奥赛培训的教学适于采用案例教学法，并举例分析了“案例教学法”在信息学奥赛培训中如何应用及应该注意的事项。【关键词】案例 案例教学法 引导 信息学奥赛如果说信息科学与计算机技术为我们开辟了一片新的天地，程序设计是这片天地的灵魂家园，那么，程序设计竞赛则是点缀这个花园，使她充满灵气的塔宇。中学信息学奥赛一个非常重要的组成部分就是程序设计竞赛，是极富智慧和挑战性的。参加竞赛的学生一方面能从中得到智力开发的训练，享受到竞赛带来的快乐；另一方面又接受着重重考验：时间的考验，学业成绩的考验，乃至三番五次失败的考验。因此，在不影响学生的文化学习和参加其他竞赛的前提下，在非常有限的时间内，作为信息学奥赛的培训教师，如何使学生高效地掌握信息学奥赛的相关知识，高效地培养他们的编程能力、维持良好的编程状态就显得举足轻重了。我把这项工作当作课题来研究，并从中摸索可行的路子，以最大程度提高培训的绩效。笔者认为，案例教学法对于信息学奥赛培训是比较有效的一种教学方法。这是因为，案例教学法应用实际案例来训练学生，既开拓学生思路、视野，促使学生开动脑筋，又适应学校集中教育的特点。它不仅符合人类的认知过程，更符合学生的学习要求，便于学生理解和接受。本文将以信息学奥赛试题中的“迷宫”问题和“合并果子”问题的讲解为例，说明如何在信息学奥赛培训中合理应用“案例教学法”以取得更好的教学效果。一、教学案例选择案例教学是教师根据教学内容、学生实际及教学目的、要求，设计(引入)一个具体的案例，通过展示案例、分析案例和讲解案例展开对知识点的讲解，从而达到让学生掌握知识和培养学生分析问题解决问题能力的一种教学方法。它的特点是直观，易懂，特别能培养学生分析问题和解决问题的能力。信息学奥赛要考核的一个非常重要的能力就是程序设计的能力。而程序设计的核心是算法设计。算法设计涉及许多先修的基础知识，包括数据结构、高级语言程序设计、图论、组合数学、计算几何等。当然还包括除数学与信息学之外的其他学科知识，因为没有这些知识，往往连题目都看不懂，因此，参加信息学奥赛的选手应该具备全面科学素养。然而，即使是一些基础知识，由于学生之前接触较少，日常应用不多，学生往往不容易理解。选择合适的案例，在案例的分析和模拟操练中进行知识的讲解，能收到事半功倍的效果。比如：对于数据结构的讲解部分。很多学生都知道这样一个事实：“算法+数据结构=程序设计”。但什么是数据结构？学生总是糊里糊涂，他们最大的困惑是所谓的“数据结构”不知道该如何用。在初赛中，往往有很多类似这样的题目：（NOIP2006普及组一.13）某个车站呈狭长形，宽度只能容下一台车，并且只有一个出入口。已知某时刻该车站状态为空，从这一时刻开始的出入记录为：“进，出，进，进，进，出，出，进，进，进，出,出”。假设车辆入站的 顺序为 1，2，3，则车辆出站的顺序为（ ）。A. 1, 2, 3, 4, 5 B. 1, 2, 4, 5, 7C. 1, 4, 3, 7, 6 D. 1, 4, 3, 7, 2（NOIP2006普及组一.19.） 设栈S的初始状态为空，元素a, b, c, d, e 依次入栈，以下出栈序列不可能出现的有（ ）。A. a, b, c, e, d B. b, c, a, e, dC. a, e, c, b, d D. d, c, e, b, a这些案例的学习和讲解，很容易让他们知道，“栈”这种数据结构是先进后出的，当然，也会由此讲到“队列”（先进先出）。这样，在初赛的时候考核此类问题，他们都可以稳拿到分。然而，在复赛的时候，队列和栈这些数据结构究竟如何用，他们往往就糊涂了。为了帮助他们理解“数据结构”究竟是什么，我从历年NOIP试题库等培训资料中找到一些运用各种数据结构来解题的典型例题作为教学的案例，如对“队列”的讲解，我用“迷宫”作为案例；对“栈”的讲解，我用NOIP2005提高组的第四题“等价表达式”作为案例；对“堆”的讲解，则用了NOIP2004提高组的第二题“合并果子”作为案例等等。通过这些案例，成功地揭开了“数据结构”的神秘面纱，学生们终于明白：数据结构的根本目的是优化算法，而并非一个专门的工具，它在具体实现中仍然使用普通的数据类型，只是对数据的存取使用了某种技巧，从而更方便且更快速地解决问题，降低时间复杂度；而对于数据结构的各类名称，实际上是先有想法（算法），然后才给它一个通俗易懂的名称而已。可以这么说，案例选择，是案例式教学中很关键的一步，是为整个案例式授课作铺垫。在授课前，教师要仔细斟酌授课内容，根据教学计划、课时分配、教学要求和目的，以及教学的重点和难点，设计或选择有代表性的案例，准备好教学素材。当然，案例的选择应该遵循一定的标准。第一，案例要具体、典型，并且可以检测结果（即要准备好测试数据）。第二，要选择难易适中的案例。案例的选择要考虑学生的知识背景，过于复杂的案例，将导致学生学习兴趣的下降。难易适中的案例有利于案例学习的深入进行，提高学生的学习积极性和主动性。不妨可以考虑，用简单的案例引入，再逐步深入的方法，逐层递进地为学生搭好学习的脚手架，一步一步地向上攀登。第三，选择的案例和将要讲解的知识在本质上要有相通性。案例要和教学内容相呼应，关联性要极高，这样的案例才能最大程度上有助于知识的讲解。第四，案例要能覆盖多个知识点，这有利于提高综合运用知识的能力，并达到整合知识的目的。信息学奥赛一个非常重要的技能就是阅读题目，选手们往往栽在题目的“不知所云”上，而并非不懂如何建模、如何解题。在培训中，也常常遇到这样的情况，面对一大堆的描述文字，学生们就显得紧张而不知所措，甚至连静下心来阅读题目都做不到，而往往经过老师的点滴解释后，就恍然大悟了。因此，所选择的案例应该和信息学奥赛题目的问题描述形式一致，即用讲故事或情景创设的形式来描述问题以训练学生的读题能力。二、课堂组织实施1、案例引入阶段案例的引入要在“巧”字上下工夫。对老师已经选定的教学案例，在引入阶段，教师应该根据所选的案例背景，提炼出一个较为精简的问题，作为引导学生开始新的思考的切入点。让学生有一个适当的过度，否则，学生可能会因为一下子要解决那么多的问题而丧失学习和探讨的兴趣。比如对用于讲解“队列”的“迷宫”一例（题目见附录一），笔者在案例的引入阶段，是以5*6矩阵中的具体局势为例开始的。具体做法是：事先布局好起点和终点以及可行和不可行的局势各一个，在黑板上画出来，并让学生思考，找出最短路程。很快，学生会发现，对于最短路程，可能会有不同的路径。然而，答案只关心最短路程而不关心具体路径。因此，如果仍然使用一般的搜索算法（把各条可能的路径都走一遍再从中找最短路程的方法），势必大大浪费了时间，并极有可能会在大规模数据的前提下导致程序运行超时。那该怎么办？就这样，引发了学生新的思考，即在问题的实质弄明白以后，思考的重心转移到如何优化算法之上来了这就水到渠成地把学生引向新的知识的学习：数据结构“队列”。再如，对于案例“合并果子”（NOIP2004提高组第二题，题目见附录二）的引入部分，笔者将其简化成“容器填充”问题，以确保问题的实质不变，但描述明确，这样，就容易起到引导的作用。简化结果如下：有一个容器一开始是空的，现在要对它做如下几个操作：1）插入n个数；2）删除当前最小的数。操作可以不限顺序进行，即可以先插入若干个数，又删除若干个数或者两个操作交替各若干次，要求高效完成（比如1s内完成200000次操作）。这样，要解决的问题实际上就是：1）插入n个数；2）查找最小的数；3）删除最小的数；同时每次操作后都要动态地维护它，以便下次操作可以用同样的方法实现。2、案例讨论与分析阶段案例讨论环节类似于头脑风暴，旨在分析问题，即提出解决问题的途径和方法。对程序设计而言，就是算法设计的部分。对于同一个案例，不同的学生会提出不同的分析结果和实现方法。教师要引导学生过滤掉案例中次要的细节，发现案例中的主要结构、案例与所授知识之间的内在联系。这个环节落实情况的好坏关键在于学生和教师是否共同努力，把案例中的内容与相应的若干条理论知识联系起来。要达到这样的要求，教师关键要做好启发引导工作，想方设法创造自由宽松的讨论氛围，在宏观上把握和指导好案例讨论，让学生成为案例讨论的真正主角， 同时又不至于出现大的方向性的偏差。教师尽力创设民主和谐的教学气氛，对学生的大胆回答要及时加以鼓励，即使学生的回答有点偏离正确答案，也不要急于评判，可以用设疑的方法帮助他们自我更正，使学生在没有压力的良好心态下进行创造性的探索。这个环节能够充分调动学生的自主性，让学生在不断尝试中得到新知。体现出了学生是学习的主体，学生把同学、教师都作为学习的帮助者，目的是为了更好地自我学习。在信息学奥赛培训中，当案例引入阶段完成后，可以抛出整个案例的所有问题，即呈现问题的庐山真面目。由于有案例引入阶段的铺垫，面对描述复杂的问题，同学们都比较容易理解问题的本质即完成建模。但是，众所周知，信息学奥赛中一个非常重要的就是时间复杂度的问题，选手们的算法对了或者是测试样例通过了，但往往只能拿到一两个测试点，要拿满分并不容易，其最主要的原因是数据规模较大的时候，程序运行超时。因此，算法优劣始终是信息学奥赛中水平差异最主要的原因。因此，在案例讨论与分析这个阶段，主要是围绕着算法的时间复杂度这个关键点进行。对于“迷宫”问题，把引入阶段的具体数值抽象成变量后，即在问题的实质没有变化时，应如何优化算法就成了大家讨论的热点。经过热烈的讨论，同学们发现，由于每走一步，距离都会增加1，而且可走的方向可以是多个，因此，不妨可以考虑对于所到的每一个格子，都把它下一个可以走的所有格子的各种信息记录下来（包括坐标，走过与否的标志，离起点的距离等），之后就可以不再考虑当前的格子了，如此下去，直到走到终点为止（以坐标判断）或者是无路可走的时候为止。在这样的分析下，同学们不难发现，只需用数组存起从起点格子开始考察的每一个可走的格子信息，并用一个变量指向下次将考察格子（作为头指针），用另一变量指向当前数组的尾部（作为尾指针），就可以实现考察完的格子“删除”（头指针指向当前的下一个），由此下去，问题就可以得到解决了。这样，学生们就会发现，这样的数组实际上就是一个队列（单链表）。当然，经历了这样的讨论，他们自己已经找到了“队列究竟有什么用”的答案；更为可喜的是，学生还发现如果用数组来表示由于不同方向引起的坐标差值，则可以减少代码冗余，并且即使是增加几个方向，比如将题目适当变形，改为走迷宫的方向可以走斜线时（此时有8个方向）也可依葫芦画瓢如法炮制。再如，同学们很快就发现，对于“合并果子”的问题，本质上就是“填充容器”，所不同的是，删除的时候最小值要记下来，因为每次插入的数是当前删除的所有数的累计值。所以，首先要解决的是如何解决“填充容器”的问题。学生们在课堂上想到如下几种解决的方案：想法一：不考虑顺序1）插入：每次都插入到最后，这样很容易实现；时间复杂度o(n)2）查找：只能顺序查找。从头到尾的遍历查找的时间复杂度直接跟n成正比，次数一多必然超时；3）删除：删除后平移也是很费时间。想法二：先让它有序（快速排序，时间复杂度为o(knlog2n)，k为系数）1）由此带来的便利是：由于一直维持有序，所以最小的询问时间为o(1)，即第一个就是，因此查找最小的和删除它就相当于将表中的开始位置指向下一个即可，非常容易。2）插入非常麻烦，即使可以使用二分查找o(log2n)找到该去的地方，但要放进去还是要挪位置，移动也需要o(n)，n次则会达到o(n2)。想法三：想法二的问题主要是插入花时间，因此，在此基础上，很容易想到，使用链表，链表的插入可以很容易，只需要把指针修改一下即可，但是有序的链表不能进行二分查找，也就是说，要找到插入的位置一样要从头来，这样就仍然把插入的效率降下来了，仍然为o(n)级别。只要有一个操作的时间复杂度为o(n)，整个算法的时间复杂度就可能达到o(n2)级。当然，他们很难想到别的方案，此时，老师就可以引出本次课学习的内容。笔者是这样处理的：再次分析想法二，耗时的主要原因是要维持有序这样的工作比较麻烦。那可不可以使用折中的办法，让插入的时候不是非常有序，但又不要杂乱无章，也就是说有序程度不需要太高，但又不能完全没有顺序。打个比方，有八支队伍进行淘汰赛（在正规的大型比赛中，16强后都是进行淘汰赛的，假设没有平局的，输的那方就出局，胜者晋级），最后8号赢了，获得冠军，但是比赛结束后检查出来服用了兴奋剂。这样，比赛就显得不公平了，假设规定如发生此类情况要换一个新的8号重赛。那需不需要全部重赛？为什么？谁会感到不公平？我在黑板上用图描述出来后，学生很快发现，有一半的人是不需要重赛的，只有有原8号参与的那一半人才要重赛。对于奥班的学生，当讲解到这个时候，就有一部分学生若有所思了，似乎想到了什么；进而，我结合容器填放问题，用刚才淘汰赛的情况模拟一下：如果这8个人就是8个数，那么，就可以把两个两个比较后小的数成为赢家上去，这样一路上去，最小的就是最顶端那个数。此时，要查询最小的数就轻而易举了，而插入维护也比较容易实现，只需要把刚插入的数先放到最后，然后和与之有关的相比，一层一层由下往上(时间复杂度为o(log2n) )，就可以得到维护了。删除（即去掉最顶端那个）也将很容易实现：只需把最后一个挪到第一个覆盖掉原来的即可，相当于插入了一个新的数到最顶端，就和插入一样维护，所不同的就是由上往下比较，时间复杂度也一样是为o(log2n)。这样，整个算法的时间复杂度就降为o(n*log2n)级别了。这时，一棵完全二叉树就出现在同学们的面前，同学们会发现，这棵二叉树具有如下的性质：除了最后一层，其余是满的，而且最后一层的所有节点都是往左靠的；并且每个节点都比其子孙节点小。这样，“堆”这个特殊的数据结构就出现了。教师此时可以引导学生一起总结“堆”这个数据结构的重要特征：“堆”满足以下两个性质：1）完全二叉树；2）每个节点都比其子孙节点小。当然，上面性质2）中每个节点都比其子孙节点大也是可以的。通过讨论分析，学生们很清楚：不论是哪种数据结构，都要时时刻刻维护它，一直保持其应有的性质。比如，“堆”在进行任何一次操作（如插入或者删除）后都首先要维护好它，以保证时时刻刻它都是“堆”。3、案例评述在评述案例时，教师对案例讨论与分析阶段学生的讨论结果进行适当提炼，尤其是案例的关键之处和新知识，加以讲解和引申，便于加强学生对重要知识点的巩固和新知识点的学习，便于学生对学习内容有一个整体认识，清楚学习的重点；对学生方案中易疏漏的部分加以强调，避免错误重现。在“迷宫”的教学中，经过分析，在案例评述阶段，教师应该把“队列”这个概念明确地抛出，并指明“队列”在具体的程序实现过程中是如何体现的以及“队列”在“迷宫”问题的求解中起到了优化算法的关键作用。据此，可以很容易得出在程序实现的具体过程中使用的主要数据结构：t:array 0.110,0.110 of 0.1;/图中的格子能不能走，为1能走，为0不能走。初识全为0，为了把边界封住，不至于下标越界溢出，因此设大一点的数组，相当于让外围全用“*”封起来了。因此，数组下标要从0开始。ans:array0.110,0.110 of integer;/该格到起始位置的最短距离，初始为0意为现在还没有找到通路x,y:array 1.10010of integer;/即队列中格子的坐标，x表示行坐标,y表示列坐标a,b:integer;/ a,b分别表示未处理过的点的起止位置dx1.4=0,0,1,-1;/方向，dx与dy对应地配合起来，可以表示多个方向dy1.4=1,-1,0,0;同理，在“合并果子”的题中，通过分析，在评述这个阶段，教师需要提炼出关键的知识并加以强调，可以总结如下：堆是一种数据结构，它满足2个性质：1）完全二叉树；2）每个节点都小于（或都大于）其子孙节点。堆能高效地进行插入操作，并能高效地查询最值并删除最值，其时间复杂度为o(n*log2n)。同时，在具体的程序编写中，堆可以用数组a来存储，为了体现其层间节点的父子关系，根是a1，对每一个节点ai，其左儿子是ai*2，其右儿子是ai*2+1，而堆操作则可以通过如下步骤实现：1）插入：先把新插入的节点放在最后再进行位置的调整，保证每一层父亲节点都小于其儿子节点，如果当前的不满足，只需和它的父亲节点交换一下，一直维护到顶层，则最多交换log2n（即二叉树的层数）次。2）删除：step1:把最后一个节点移到根（第一个），就算删除了，但在“合并果子”的题中，需要把每次最小的值记下来，并加到将要插入的数中;step2:维护保证每个节点都比其子孙节点小，当把最后的节点移到根后，看当前的根是否最小，如不是则需要从上到下，不断和下面层中较小的儿子节点交换。这样，最坏的情况就是交换log2n次，即走到叶子节点处。所以，要解决这个问题，并把算法的时间复杂度降为o(n*log2n)，之所以能得到优化，得归功于数据结构，在这里正是“堆”起到了关键作用！通过评述，学生能够清楚自己算法设计的问题所在，也能够进一步掌握算法的时间复杂度对竞赛的重要意义。评述结束后，教师就可以把时间留给学生，让学生体会经过算法优化后的程序设计过程。往往，学生会情不自禁地赞叹优化后的算法。三、课后巩固练习阶段在课堂上借助案例的学习后，学生掌握了一定的技巧，但往往还只是停留在模仿的层面上，因此，需要经过一段时间的课后巩固练习才能将知识内化。尤其是每次集中培训的时间只有2个半小时左右，学生编程的时间是不够的，因此每次课后针对当堂课所教授的内容，适当给他们一些课后练习任务或主题，将有助于他们巩固知识和提高技能。比如对于背包问题，我在以NOIP01年装箱问题为案例进行教学后，我还以NOIP05年提高组第2题的采药问题、NOIP04年提高组合唱队形、NOIP06年提高组金明的预算方案和NOIP05年提高组第4题的过河问题作为课后练习题，以巩固对背包问题算法的理解和应用。四、案例教学中应注意的问题1、案例的设计（选择）紧扣教学内容，针对性要强案例的设计必须紧紧围绕教学任务和目标，针对要传授的知识点来进行。有些案例虽然好看吸引人，却与所讲内容不符或是只重复少数几个知识点，是不易选用的。比如要讲“队列”，如果使用需要打印出各种可能从起点到达终点的路径的“新迷宫”问题（此时需要使用搜索算法）作为案例，则不可能起到很好的教学效果。2、案例能层层推进，有分明的层次，难度要适中案例要由简到繁、由易到难，从简单容易的操作(问题)入手，层层推进，最后引导学生掌握复杂的操作。老师在使用案例的时候，需要对诸多材料进行整合、排序等各种处理，以体现案例自身的逻辑性和递进性。总之，层次性强，难度适中的案例可以提高课堂教学效果，促进学生学习的主动性、积极性和创造性，也有利于培养学生分析问题解决问题的能力。3、案例要贴近竞赛实际，应用性要强结合NOIP的实际选择案例进行分析，能使得学生深刻感到所学的知识对其参赛帮助很大，能激发其学习兴趣，还能减缓学生对竞赛的惧怕心理，因此教学效果也好。4、突破“模仿”，灵活应用案例不能成为学习的最终目标。模仿案例是学生进行实际操作的第一步，其作用的真正意义在于通过案例模仿，使学生更容易理解相关知识的含义和作用，更有利于掌握一些操作技巧，而并不是以解决案例本身的问题为最终目标。我们应该注意的是，采用案例教学时，学生往往容易走进这个误区。所以，在教学过程中教师要注意教学艺术，在案例讲解过程中能将知识点加以引伸，并在案例问题得到解决的同时，能有效地进行总结提升，能有效地评价学生的学习成果，促进学生在理解和掌握知识的基础上，灵活应用知识。由于信息学奥赛更注重的是对知识的应用（建模），因此，必要的时候，尽可能少地直接给出最后答案，而是引导学生去思考和讨论；甚至在时间允许的时候，可以让学生依据讨论的结果先把程序写下来；在遇到问题和障碍时，再给出部分提示，以免学生一味地进行模仿、照搬。5、适当进行阶段性教学总结在案例教学的过程中，阶段教学总结，是具有重要意义的。对学生而言，主要从学生的掌握程度、理解程度和是否能独立地完成任务以及实际编程能力等指标来进行总结评价；对教师而言，主要从案例的选取、课堂实施案例的教学效果以及教学艺术等方面进行总结评价。适当的阶段总结会促使学生在短时间内有较快的进步，同时也会促使教师在教学上获得更多的心得体会，以获得最大的教学绩效。6、重视师生互动良好的师生互动氛围，可以最大程度地打开学生的思路，促使案例教学的讨论分析阶段收到很好的效果，提高他们学习的积极性和主动参与性。结语实践证明，案例教学法是理论联系实际，激发学生创造思维，提高学生解决问题能力的有效途径，是一种行之有效的教学方法。在信息学奥赛培训的教学工作中应用案例教学法，容易使教学过程充满挑战性、趣味性，学生也容易从案例中的实际问题的解决过程的体验中，学会分析问题，解决问题尤其是优化算法的能力，对促进学生的编程能力具有重大的帮助意义。同时，案例教学法能够进一步增强学生的学习和提高编程能力的积极主动性，培养学生解决实际问题的能力和评鉴能力。在信息学奥赛培训中，案例教学法是有效地、可行的。【鸣谢】感谢华南师大附中高三（1）班的罗穗骞同学，他以丰富的做题和大赛经验认真、热情地帮助我对低年级学生进行信息学奥赛培训，收到了良好效果；而这也为我完成这篇论文奠定了基础。非常感谢他！【参考文献】1李振汕 蒋萍，“案例教学法”在Photoshop教学中的应用，教育与教学研究，20092郑金州，案例教学指南M上海：华东师范大学出版社，20003季贤，基于任务驱动的案例教学法探讨，教育时空，2008附录一：迷宫问题（特殊的最短路径问题）【问题描述】