《计算机奥林匹克竞赛讲座》由会员分享，可在线阅读，更多相关《计算机奥林匹克竞赛讲座（46页珍藏版）》请在金锄头文库上搜索。
1、2013-5-31,吴再陵,1,初中信息学奥林匹克竞赛,方法与内容,2013-5-31,吴再陵,2,一、组织方法 二、教师本身所具有的品质 三、教学进度与时间安排 四、教学方法 五、奥赛教学体会 六、初赛 七、复赛,与同行们共商讨,2013-5-31,吴再陵,3,组织方法三级制,市级中级水平以上的培训学校负责初级、中级及高级年级按年级组织课外活动小组，循序渐进，完成教学任务 视学生水平和能力、师资力量、学校支持程度灵活组织课外活动小组,2013-5-31,吴再陵,4,人员选拔是关键 ： 初一新生 ： 通过考试选拔数学，新知识探究 分层次组班,2013-5-31,吴再陵,5,教师具备的素质,1.
2、 对事业的责任心、对工作的态度2. 对学生的爱心3. 自身学习能力、悟性4. 教学能力5. 组织能力,2013-5-31,吴再陵,6,时间与进度,总体目标设计：（1）初一：基本知识与简单算法 初二（上）竞赛：初见成效 （2）初二：数据结构与算法 初三（上）竞赛：取得成果 充分利用寒暑假时间，保证有一定的培训时间具体安排,2013-5-31,吴再陵,7,课程进度安排,1. 中级本：数组、过程 2. 中级本：集合、记录、文件 3. 数据结构：线性表、栈、队列+简单算法 4. 数据结构： 指针变量+线性链表+树、图基本知识+常用算法 5. 数据结构+算法深入应用,2013-5-31,吴再陵,8,培训
3、方法,1. 讲授法2. 上机实践3. 小组讨论4. 专题讲座5. 模拟练习6. 实战练习其他综合性学习,2013-5-31,吴再陵,9,奥赛教学体会,1. 把握每一章的教学重点，解决难点，循序渐进、脚踏实地开展基础知识教育2. 培养学生良好的学习习惯，认真对待每一次上机实习和练习，真诚对待每一个学生。3. 培养学生创新意识、思维方法，关注一题多解。4. 多用问题分析法、问题讨论的教学方法,2013-5-31,吴再陵,10,5. 适时、适当进行专题讲座与专题练习，加强与巩固所学习知识 6. 分层次教学：起点不同、目标不同，根据实际情况因材施教。 7. 教师间相互学习、相互协作，设计本校总体目标培
4、训计划，以求得到校领导、班主任和其他老师的支持，建立友好的协作关系。,2013-5-31,吴再陵,11,教学重难点及解决方法：,1. 循环结构：循环应用2. 数组：元素与整体，应用（排序，选举）3. 过程与函数：参数、变量、过程与函数调用4. 递归程序设计及执行过程5. 指针变量6. 链表及应用：头指针7. 栈与队列的应用：栈与递归、栈与回溯 队列与宽搜,2013-5-31,吴再陵,12,8. 哈夫曼树的生成算法及应用 9. 图的遍历及应用 10. 最短路径及应用 11. 查找与排序：快排、堆排序，哈希函数及应用 12. 回溯算法及应用 13. 搜索算法：时间与空间问题 14. 数学、递推及应
5、用 15. 动态规划：转移方程的建立,2013-5-31,吴再陵,13,初赛复习（根据大纲）,1. 基本知识2. 基本算法3. 基本概念4. 组合数学、数学推理5. 阅读程序6. 完善程序,2013-5-31,吴再陵,14,阅读程序的技巧,阅读程序的结构：先主程序后子程序阅读程序需要输出的结果或内容用列表的方法，将程序中主要变量值的变化过程写出来，找出变化规律，以快速求得程序的运行结果。在阅读主程序时，需要注意主程序完成哪些操作任务，其最后输出什么，它在调用过程或函数时，参数值是什么。阅读子程序时，主要掌握过程或函数完成什么样的功能，其传递参数是什么样的参数（值参、变参）值参、变参、局部变量、
6、全程变量作用域、变化情况,2013-5-31,吴再陵,15,1. pmgram Gxp3 （利用数学知识得到结果）Var d1,d2,X,Min:real;beginmin:=10000;X:=3;while X15 do begin d1:=sqrt(9+(X-3)*(X-3);d2:=sqrt(36+(15-X)*(15-X);if (d1+d2)Min then Min:=d1+d2;X:=x+0.001;end;writeln(Min:1O:2);end.,输出: 15.00,2013-5-31,吴再陵,16,2. program exam_3； var a:array_19 of s
7、tring； st,x：string；I，j，n，m：integer； begin repeat writeln(please input a string(length10)：)； readln(st); n：=length(st)； until (n10) and odd (n)； m:=trunc(n+1)2)； for I:=l to n do for j：=l to n do ai, j：= ；,2013-5-31,吴再陵,17,for I:=1 to m do 取半 4 for j:=i to n+l-I do begin x:=copy(st，J，1)；ai，J：=x; an+1
8、-i,n+l-j：=x；end； for j:=n downto l do begin for i：=1 to n do write(ai,J：2)；writeln; end： end. 输入数据： please input a string (length10) ： RUTYFPE,2013-5-31,吴再陵,18,I=4，J=4TO 4,用列表方法，找出规律，正确写出运行结果：输出结果：,I=1，J=1TO 7,I=2, J=2TO 6,I=3，J=3TO 5,2013-5-31,吴再陵,19,3. program exam_4； ( 9 分) var a: array1.10 of in
9、teger ； s, n, m： longint ; flag：set of byte； procedure try(dep：integer)； val i: integer； begin for i:=1 to n do if not（i in flag ） then begin flag：=flag +i； adep：=i； if dep=m then inc(s) else try (dep+1)；,2013-5-31,吴再陵,20,flag：=flag-i； end； end； begin writeln (please input M and N：)； readln(m,n)； fl
10、ag：= ；s=0； try(1)； writeln(s)； end. 输入数据： please input M and N：4 5 输出结果：,2013-5-31,吴再陵,21,Dep=1 , for I:=1 to 5 do flag:=1 , adep=1 Dep=2 , for I:=2 to 5 do flag=1,2, adep=2 Dep=3, for I:=3 to 5 do flag=1,2,3, adep=3Dep=4, for I:=4 to 5 do flag=1,2,3,4 , adep=4此时满足 dep=m , 则 s:=s+1 , 回溯从集合中去掉当前I，用其后
11、数据填入集合中根据问题可以知道：四重循环：2*3*4*5=120,2013-5-31,吴再陵,22,4、program exp2;( 2002 初中) var n,jr,jw,jb:integer; ch1:char; ch:array1.20d char; begin readln(n); for i:=1 to n do read(chi): jr:=1; jw=n; jb:=n; while (jr=jw) do,2013-5-31,吴再陵,23,Begin If (chjw=R) then begin ch1:=Chjr; Chjr:=chjw; chjw:=ch1: jr:=jr+1
12、; end else if chjw=W then jw:=jw-1 Else begin ch1:=chjw; chjw:=chjb; chjb:=ch1; jw:=jw-1; jb:=jb-1; endend;,2013-5-31,吴再陵,24,for i:=1 to n do write(chi); writeln;end.输入:10RBRBWWRBBR输出: RRRRWWBBBB,2013-5-31,吴再陵,25,完善程序题解题方法 步骤：1. 仔细阅读文字解释，理解题意和提供的解题思路2. 根据问题的求解要求，了解输入、输出内容和问题处理方法3. 先阅读主程序，了解输出变量和输出要求
13、以及主程序中需要调用的过程或函数是哪些。4. 阅读过程或函数，了解其完成的功能5. 填空方法：一般从主程序最后输出要求，反推主程序中的变量填写或表达式、语句等的书写,2013-5-31,吴再陵,26,6. 根据主程序参数与子程序参数传递关系，填写子程序 的变量，根据子程序需要完成的功能，完成子程序填空。 7. 填写完毕，再将程序整个阅读、执行一遍，看能否完成问题提出的要求。,2013-5-31,吴再陵,27,1. 在A，B两个城市之间设有N个路站(如下图中的S1，且N100)，城市与路站之间、路站和路站之间各有若干条路段(各路段数20，且每条路段上的距离均为一个整数)。,2013-5-31,吴再陵,28,A，B的一条通路是指：从A出发，可经过任一路段到达S1，再从S1出发经过任一路段，最后到达B。通路上路段距离之和称为通路距离(最大距离1000)。当所有的路段距离给出之后，求出所有不同距离的通路个数(相同距离仅记一次)。例如：下图所示是当N=1时的情况：,2013-5-31,
