《如何开展信息学奥林匹克.ppt》由会员分享，可在线阅读，更多相关《如何开展信息学奥林匹克.ppt（29页珍藏版）》请在三一文库上搜索。
1、如何开展信息学奥林匹克,朱全民,认识信息学奥林匹克,NOIP ( National Olympiad in Informatics in Province ) -面向普及,全员参与 NOI ( National Olympiad in Informatics ) -提高,每省4人 CTSC ( Country Team Selecting Contest ) -国家集训队选手,全国20人 IOI ( International Olympiad in Informatics ) -每个国家4人,信息学奥林匹克考什么?,NOIP 联赛大纲,分初赛和复赛。 NOI 没有大纲,着重考察选手运用计算机
2、解决问题的能力和创新能力。 CTSC 高难题,着重考察选手创新能力和应变能力。 IOI 每年都有新变化,着重考察选手创新能力和应变能力。,雅礼94年以来信息学奥赛取得成绩,涌现出一批批优秀学生,博弈机器人,搞好竞赛的基本条件,领导支持 -保障作用 教师的激情 -充分条件 生源 -必要条件,如何开展,精心选材，打好基础 -兴趣是最好老师 -强有力的数学基础是学好信息学的保障 -优秀的品质和好的学习习惯是必需的,如何开展,培养素质，提高能力 -兴趣培养(兴趣是最好的老师) -学习习惯和能力培养(培养知识) -情感的培养(培养综合素质) -个性培养(创新精神的养成),开展步骤,实施方案，造就人才 分
3、层次教学 分层的目的, 分层的方法, 分层的弊端 个别指导 个别指导的关键在于怎样发现选手的问题，怎样针对性的采取办法进行解决。 点面结合 点面结合是纵向和横向交叉训练的一种手段。采用的办法可以用讨论式、答疑式、互帮式多种手段同时进行。,如何提高自身素质,勤奋学习，勇于钻研 虚心向别人请教 经常参加一些学习活动，开阔视野 在教学中不断改进教学方法 教学相长,有一个上n节楼梯，他可以一次跨1级，也可以一次跨2级，也可以1次跨3级，问，他能有多少种到上楼的方法？,示例,分析：我们将上楼梯的方法用数字1，2，3表示，那么 如果只有1节楼梯，显然只有1种上楼的方法，方法为1。 如果只有2节楼梯，显然只
4、有2种上楼的方法，方法为11，2。 如果只有3节楼梯，显然只有4种上楼的方法，方法为111，12，21，3。 超过节楼梯时可以归结为最后只有，节楼梯的情况,多于3节楼梯呢?,假设有n节楼梯, 设 f(n)表示上节楼梯的方法数，显然有,算法,Function f(n:integer):longint; Begin if n=1 then f:=1; if n=2 then f:=2; if n=3 then f:=4; if n3 then f:=f(n-1)+f(n-2)+f(n-3); End;,是否我们可以满足了呢？,看下面的算法： Function f(n:integer):longin
5、t; var a,b,c,d: longint; Begin a:=1;b:=2;c:=4; for i:=4 to n do begin d:=a+b+c; a:=b;b:=c;c:=d; end; f:=d; End;,对比！,算法采用递归的形式，由于递归要反复压栈和弹栈，使得操作要多很多，并且受到空间限制，时间复杂度为O(3n) 算法采用递推的形式，只是利用公式从前往后逐步递推,采用变量之间相互传递结果，时间复杂度为(n) 实践证明，采用算法比算法快很多，而算法最多做到2就巨慢了,算法2可做得巨大。,总结,上题看起来非常简单，但在分析问题时，可以启发学生思维由浅入深地进行思考 从算法和算
6、法的对比，可以培养学生不断求精的一种思维习惯 从该问题，可以总结出一种递推思维的过程，由此及彼，举一反三,示例,求!=1*2*N,最末尾有多少个0,最后一位非零数字是多少? 例如N=12,则12!=479001600,最末尾有2个0,最后一位非零数字为6 分析： 显然很容易想到每次都乘以一个数，去掉末尾的，求出！后，最后只要对10求余即可!,N很大呢?,当N达到20以上就需要采用多精度值进行处理 如果每次只存储最后一个非零数字,然后进行运算会出现问题.例如,假设最后的非零数字为625,接下来来乘以1624,那么 5*1624=8120,最后非零数字为2, 625*1624=1015000,最后
7、非零数字为5, 由此可知,最后非零数字取得不仅仅跟最后一位有关,而跟最后几位有关!,到底跟多少位非零数字有关呢?,仔细分析, 如果最后是5,那么可以得出1个0,而使得跟前一个非零数字发生进位, 如果最后是25=52,那么可以得出2个0,使得前2位的非零数字发生进位, 如果最后是125=53,那么可以得出3个0,使得前3位的非零数字发生进位, 如果末尾为5n,那么可以得出n个0,使得前n位的非零数字发生进位.,算法,读入n 计算n以内有多少个5,其中25算2个5,125算3个5,得出有多少个0 计算n以内5K的K的最大数值,如N=1000,则K=4, N=20000,K=6,. 枚举N!的每位数
8、,保留结果的后K位. 计算最后1位即为答案.,算法框架,read(n); m:=n; while m0 do 求有多少个0; m:=m div 5 ; zero:=zero + m; m:=n;k:=0; while m=5 do 求最多保留多少位 inc(k); m:=m div 5 s:=1; for i:=1 to n do 枚举每一位乘数 s:=s*i; s:=s mod k s := s mod 10; s为答案,总结,从该题分析可以看出,运用简单的思维逻辑,将使得程序非常复杂,而更深入的思考,需要以一定的数学知识为基础。 该题告诉学生,要不段创新,只有创新,才是解决问题最根本的源动
9、力。 思维角度的转化往往是解决问题的关键，授课的过程一定要培养学生创新的思维习惯。,示例,有个人到个水龙头去打水，每人打水的时间不同，问 （1）如何安排这n个人打水的顺序，才能使得他们花费的总时间最少？ （2）如何安排这n个人去打水，才能在最短的时间内都能打到水？ 分析： 两问含义不一样，第1问表示求最早完成任务的时间，第2表示求最少平均等待时间。,举例,有2个水龙头，5个人去打水。他们的打水时间分别为 5，6，7，8，9 最早完成的安排如下，完成打水时间为5+6+7=18 水龙头1：7 6 5 水龙头2：9 8 打水最少的安排如下，等待时间为5+12+21+6+14=58 水龙头1：5 7
10、9 水龙头2：6 8,分析,显然第1问可以转化为n根短木棍，需要拼节成m根短木棍使得他们的长度之差最小。 那么能否采用先将长的拼接然后再拼接短的呢？看看这样做会出现什么情况：照上例， 水龙头1：8 7 5 水龙头2：9 6 那么最少打水时间为8+7+5=20，显然不是最优！ 仔细分析，该题的实质类似背包问题，因此可用搜索来求解。,分析,第2问是否也需要用搜索求解呢？ 分析可知，该题类似磁带的存储问题，我们知道，磁带使用信息比较频繁而且很短的肯定要刻录在最前面，这里也是一个道理，越靠前面的人计算的次数越多，这样，让那些打水时间最短的人先打到水，因此总的等待时间比较少。事实证明如此。 因此我们只需要排序以后，按从小到大的顺序将n个打水之人分配到每个水龙头打水即可。,总结,从本题可以看出，该问题采用了联想和类比。 要把握问题的内涵，不要想当然。 注意逐层分析的方法，就象拨竹笋，一层层拨开，最后看到问题的本质。 类比和联想是竞赛的常用思维方式，在授课过程中，一定要精选问题，让学生学会类比思维。,思考！,教师留给学生最根本的东西是什么？ 知识？ 留给学生的是能力、思维、创造性。 改变学生学习方式最根本的是什么？ 读写算方式？ 最根本的改变是学生思维方式的改变。,