计算机奥林匹克竞赛讲座.ppt

2013-5-31,吴再陵,1,初中信息学奥林匹克竞赛,方法与内容,2013-5-31,吴再陵,2,一、组织方法 二、教师本身所具有的品质 三、教学进度与时间安排 四、教学方法 五、奥赛教学体会 六、初赛 七、复赛,与同行们共商讨,2013-5-31,吴再陵,3,组织方法三级制,市级中级水平以上的培训学校负责初级、中级及高级年级按年级组织课外活动小组，循序渐进，完成教学任务 视学生水平和能力、师资力量、学校支持程度灵活组织课外活动小组,2013-5-31,吴再陵,4,人员选拔是关键：初一新生：通过考试选拔数学，新知识探究 分层次组班,2013-5-31,吴再陵,5,教师具备的素质,1.对事业的责任心、对工作的态度2.对学生的爱心3.自身学习能力、悟性4.教学能力5.组织能力,2013-5-31,吴再陵,6,时间与进度,总体目标设计：（1）初一：基本知识与简单算法 初二（上）竞赛：初见成效（2）初二：数据结构与算法 初三（上）竞赛：取得成果 充分利用寒暑假时间，保证有一定的培训时间具体安排,2013-5-31,吴再陵,7,课程进度安排,1.中级本：数组、过程 2.中级本：集合、记录、文件 3.数据结构：线性表、栈、队列+简单算法 4.数据结构：指针变量+线性链表+树、图基本知识+常用算法 5.数据结构+算法深入应用,2013-5-31,吴再陵,8,培训方法,1.讲授法2.上机实践3.小组讨论4.专题讲座5.模拟练习6.实战练习其他综合性学习,2013-5-31,吴再陵,9,奥赛教学体会,1.把握每一章的教学重点，解决难点，循序渐进、脚踏实地开展基础知识教育2.培养学生良好的学习习惯，认真对待每一次上机实习和练习，真诚对待每一个学生。3.培养学生创新意识、思维方法，关注一题多解。4.多用问题分析法、问题讨论的教学方法,2013-5-31,吴再陵,10,5.适时、适当进行专题讲座与专题练习，加强与巩固所学习知识 6.分层次教学：起点不同、目标不同，根据实际情况因材施教。7.教师间相互学习、相互协作，设计本校总体目标培训计划，以求得到校领导、班主任和其他老师的支持，建立友好的协作关系。,2013-5-31,吴再陵,11,教学重难点及解决方法：,1.循环结构：循环应用2.数组：元素与整体，应用（排序，选举）3.过程与函数：参数、变量、过程与函数调用4.递归程序设计及执行过程5.指针变量6.链表及应用：头指针7.栈与队列的应用：栈与递归、栈与回溯 队列与宽搜,2013-5-31,吴再陵,12,8.哈夫曼树的生成算法及应用 9.图的遍历及应用 10.最短路径及应用 11.查找与排序：快排、堆排序，哈希函数及应用 12.回溯算法及应用 13.搜索算法：时间与空间问题 14.数学、递推及应用 15.动态规划：转移方程的建立,2013-5-31,吴再陵,13,初赛复习（根据大纲）,1.基本知识2.基本算法3.基本概念4.组合数学、数学推理5.阅读程序6.完善程序,2013-5-31,吴再陵,14,阅读程序的技巧,阅读程序的结构：先主程序后子程序阅读程序需要输出的结果或内容用列表的方法，将程序中主要变量值的变化过程写出来，找出变化规律，以快速求得程序的运行结果。在阅读主程序时，需要注意主程序完成哪些操作任务，其最后输出什么，它在调用过程或函数时，参数值是什么。阅读子程序时，主要掌握过程或函数完成什么样的功能，其传递参数是什么样的参数（值参、变参）值参、变参、局部变量、全程变量作用域、变化情况,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 string；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-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 integer；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)；flag：=；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，用其后数据填入集合中根据问题可以知道：四重循环：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;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.先阅读主程序，了解输出变量和输出要求以及主程序中需要调用的过程或函数是哪些。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,吴再陵,29,从A到B的通路条数为6，但因其中通路5+5=4+6，所以满足条件的不同距离的通路条数为5。算法说明：本题采用穷举算法。数据结构：N：记录A，B间路站的个数数组DI，0记录第I-1到第I路站间路段的个数DI，1，DI，2，记录每个路段距离数组G记录可取到的距离,2013-5-31,吴再陵,30,程序清单：PROGRAM CHU7_6；VAR I，J，N，S：INTEGER；B：ARRAY0.100OF INTEGER；D：ARRAY0.100，0.20 OF INTEGER；G：ARRAY0.1000 OF 0.1；,2013-5-31,吴再陵,31,BEGINREADLN(N)；FOR I:=1 TO N+1 DOBEGINREADLN(DI，0)；FOR J:=1 TO DI，0DO READLN(DI，J)；END；D0，0:=1；FOR I:=1 TO N+1 DO BI:=1；B0:=0；FOR I:=0 TO 1000 DO GI:=0；WHILEDO,2013-5-31,吴再陵,32,BEGINS:=0；FOR I:=1 TO N+1 DOS:=GS:=1；J:=N+1；WHILE DO J:=J-1；BJ:=BJ+1；FOR I:=J+1 TO N+1 DO BI:=1；END；S:=0；FOR I:=1 TO 1000 DO；WRITELN(S)；READLN；END.,B0=0;S+DI,BI;BJ=DJ,0;S:=S+GI;,2013-5-31,吴再陵,33,2.求子串位置。从键盘输入两个字符串x1,x2，要求查找出x2在x1字符串中的位置（起始位置）。算法说明：（1）用两个变量分别表示输入的字符串，并求出两个字符串的长度。（2）利用I,j变量作为扫描两个字符串的指针（3）扫描两个字符串，当其相等时，将指针指向下一个字符，当j的值大于 len2,则输出x2在x1中的位置（4）若子串位置不匹配，则使I的指针回溯，j指针重新指向子串的第一个字符。,2013-5-31,吴再陵,34,program exp4_1;var x1,x2:string;i,j,len1,len2,ps:integer;function pos1(r1,r2:string;L1,L2:integer):integer;var i,j:integer;begin i:=1;j:=1;while(i=L1)and(j=L2)do,2013-5-31,吴再陵,35,if r1i=r2j then begin；end else begin；end;if jL2 then else;end;begin readln(x1);readln(x2);writeln(x1);,writeln(x2);len1:=;len2:=;ps:=pos1(x1,x2,len1,len2);writeln(ps:5);end.,2013-5-31,吴再陵,36,(3)I:=I+1;(4)J:=J+1;(5)I:=I-J+2;(6)J:=1;(7)POS1:=I-(J-1);(8)POS1:=0;,2013-5-31,吴再陵,37,3.有k个人在银行排队等待存取钱，假如营业员接待每个人的时间为Ti，请编写一个程序，找出这k个人排队的一种顺序，使得k个人的平均等待时间最短。程序如下：program exp_6;var i,j,k,p,s:longint;a:array 1.200,1.2 of longint;begin readln(k);for i:=1 to k do begin read(ai,1);ai,2:=i;end;,2013-5-31,吴再陵,38,for i:=1 to k-1 do for j:=i+1 to k do if _(1)_ then begin ai,1:=ai,1+aj,1;aj,1:=_(2)_;ai,1:=_(3)_;p:=ai,2;ai,2:=_(4)_;aj,2:=_(5)_;end;,2013-5-31,吴再陵,39,for i:=1 to k do if ik then write(ai,2,)else writeln(ai,2);p:=0;s:=a1,1;for i:=2 to k do begin p:=_(6)_;s:=_ _(7)_;end;writeln(p/k:0:2);end.,2013-5-31,吴再陵,40,银行取钱，等待时间最短（贪心算法）（1）aI,1aj,1（2）aj,1:=aI,1-aj,1;（3）aI,1:=aI,1-aj,1;（4）aI,2:=aj,2;（5）aj,2:=p;（6）p:=p+s（7）s:=s+aI,1;,2013-5-31,吴再陵,41,4.设有一棵二叉树，如图所示，其中圈中的数字表示各个旅游景点旅游的人数，圈边上数字表示结点编号，现在需要建立一个旅馆，使所有旅游人所走的路程之和为最小，同时约定结点之间的距离为1，如图所示，若旅馆建在：1处，则距离和=4+12+2*20+2*40=1362处，则距离和=4*2+13+20+40=81.输出最小距离和。程序如下：,2013-5-31,吴再陵,42,program exp_7;var w:array 1.100 of longint;g:array 1.100,1.100 of longint;n,i,j,k,l,r,min,s:longint;begin readln(n);for i:=1 to n do for j:=1 to n do gI,j:=1000000;,2013-5-31,吴再陵,43,for i:=1 to n do begin g I,I:=0;readln(wi,L,r);if L 0 then begin gI,l:=1;gl,i:=1 end;,2013-5-31,吴再陵,44,if r 0 then begin gI,r:=1;gr,I:=1 end end;for k:=1 to n do for i:=1 to n do if i k then for j:=1 to n do,2013-5-31,吴再陵,45,if(i j)and(k j)and _(1)_ then gI,j:=_(2)_;min:=maxlongint;for i:=1 to n do begin s:=0;for j:=1 to n do s:=_(3)_;if s min then min:=_(4)_;end;writeln(_(5)_);end.,（1）gI,k+gk,j gI,j（2）gI,j:=gI,k+gk.j（3）s:=s+gI,j*wj;（4）min:=s;（5）writeln(min),2013-5-31,吴再陵,46,谢 谢,