计算机奥林匹克竞赛讲座

初中信息学奥林匹克竞赛——方法与内容2013-5-311吴再陵第一页，共四十七页。

一、组织方法二、教师本身所具有的品质三、教学进度与时间安排四、教学方法五、奥赛教学体会六、初赛七、复赛与同行们共商讨2013-5-312吴再陵第二页，共四十七页。组织方法——三级制市级——中级水平以上的培训学校——负责初级、中级及高级年级——按年级组织课外活动小组，循序渐进，完成教学任务视学生水平和能力、师资力量、学校支持程度灵活组织课外活动小组2013-5-313吴再陵第三页，共四十七页。

人员选拔是关键：初一新生：通过考试选拔——数学，新知识探究分层次组班

2013-5-314吴再陵第四页，共四十七页。教师具备的素质1.对事业的责任心、对工作的态度2.对学生的爱心3.自身学习能力、悟性4.教学能力5.组织能力2013-5-315吴再陵第五页，共四十七页。时间与进度总体目标设计：（1）初一：基本知识与简单算法初二（上）竞赛：初见成效（2）初二：数据结构与算法初三（上）竞赛：取得成果充分利用寒暑假时间，保证有一定的培训时间具体安排2013-5-316吴再陵第六页，共四十七页。课程进度安排

1.中级本：数组、过程2.中级本：集合、记录、文件3.数据结构：线性表、栈、队列+简单算法4.数据结构：指针变量+线性链表+树、图基本知识+常用算法5.数据结构+算法深入应用2013-5-317吴再陵第七页，共四十七页。培训方法1.讲授法2.上机实践3.小组讨论4.专题讲座5.模拟练习6.实战练习其他综合性学习2013-5-318吴再陵第八页，共四十七页。奥赛教学体会1.把握每一章的教学重点，解决难点，循序渐进、脚踏实地开展基础知识教育2.培养学生良好的学习习惯，认真对待每一次上机实习和练习，真诚对待每一个学生。3.培养学生创新意识、思维方法，关注一题多解。4.多用问题分析法、问题讨论的教学方法2013-5-319吴再陵第九页，共四十七页。

5.适时、适当进行专题讲座与专题练习，加强与巩固所学习知识6.分层次教学：起点不同、目标不同，根据实际情况因材施教。7.教师间相互学习、相互协作，设计本校总体目标培训计划，以求得到校领导、班主任和其他老师的支持，建立友好的协作关系。2013-5-3110吴再陵第十页，共四十七页。教学重难点及解决方法：1.循环结构：循环应用2.数组：元素与整体，应用（排序，选举）3.过程与函数：参数、变量、过程与函数调用4.递归程序设计及执行过程5.指针变量6.链表及应用：头指针7.栈与队列的应用：栈与递归、栈与回溯队列与宽搜2013-5-3111吴再陵第十一页，共四十七页。

8.哈夫曼树的生成算法及应用9.图的遍历及应用10.最短路径及应用11.查找与排序：快排、堆排序，哈希函数及应用12.回溯算法及应用13.搜索算法：时间与空间问题14.数学、递推及应用15.动态规划：转移方程的建立2013-5-3112吴再陵第十二页，共四十七页。初赛复习（根据大纲）1.基本知识2.基本算法3.基本概念4.组合数学、数学推理5.阅读程序6.完善程序2013-5-3113吴再陵第十三页，共四十七页。阅读程序的技巧阅读程序的结构：先主程序后子程序阅读程序需要输出的结果或内容用列表的方法，将程序中主要变量值的变化过程写出来，找出变化规律，以快速求得程序的运行结果。在阅读主程序时，需要注意主程序完成哪些操作任务，其最后输出什么，它在调用过程或函数时，参数值是什么。阅读子程序时，主要掌握过程或函数完成什么样的功能，其传递参数是什么样的参数（值参、变参）值参、变参、局部变量、全程变量作用域、变化情况2013-5-3114吴再陵第十四页，共四十七页。1.pmgramGxp3（利用数学知识得到结果）Vard1,d2,X,Min:real;beginmin:=10000;X:=3;whileX<15dobegind1:=sqrt(9+(X-3)*(X-3));d2:=sqrt(36+(15-X)*(15-X));if(d1+d2)<MinthenMin:=d1+d2;X:=x+0.001;end;writeln(Min:1O:2);end.输出:15.002013-5-3115吴再陵第十五页，共四十七页。2.programexam_3；vara:array_[1…9]ofstring；st,x：string；I，j，n，m：integer；beginrepeatwriteln('pleaseinputastring(length<10)：’)；readln(st);n：=length(st)；until(n<10)andodd(n)；m:=trunc((n+1)／2)；forI:=ltondoforj：=ltondoa[i,j]：=’‘；2013-5-3116吴再陵第十六页，共四十七页。forI:=1tomdo{取半4}forj:=iton+l-Idobeginx:=copy(st，J，1)；a[i，J]：=x;a[n+1-i,n+l-j]：=x；end；forj:=ndowntoldobeginfori：=1tondowrite(a[i,J]：2)；writeln;end：end.输入数据：pleaseinputastring(length<10)：RUTYFPE2013-5-3117吴再陵第十七页，共四十七页。12345671RUTYFPE2UTYFP3TYF4Y5FYT6PFYTU7EPFYTURI=4，J=4TO4用列表方法，找出规律，正确写出运行结果：输出结果：I=1，J=1TO7I=2,J=2TO6I=3，J=3TO52013-5-3118吴再陵第十八页，共四十七页。3.programexam_4；(9分)vara:array[1..10]ofinteger；s,n,m：longint;flag：setofbyte；proceduretry(dep：integer)；vali:integer；beginfori:=1tondoifnot（iinflag）thenbeginflag：=flag+[i]；a[dep]：=i；ifdep=mtheninc(s)elsetry(dep+1)；

2013-5-3119吴再陵第十九页，共四十七页。flag：=flag-[i]；end；end；begin

writeln('pleaseinputMandN：’)；readln(m,n)；flag：=[]；s=0；try(1)；writeln(s)；end.输入数据：pleaseinputMandN：45输出结果：——2013-5-3120吴再陵第二十页，共四十七页。Dep=1,forI:=1to5doflag:=[1],a[dep]=1Dep=2,forI:=2to5doflag=[1,2],a[dep]=2Dep=3,forI:=3to5doflag=[1,2,3],a[dep]=3Dep=4,forI:=4to5doflag=[1,2,3,4],a[dep]=4此时满足dep=m,则s:=s+1,回溯从集合中去掉当前[I]，用其后数据填入集合中根据问题可以知道：四重循环：2*3*4*5=1202013-5-3121吴再陵第二十一页，共四十七页。4、programexp2;(2002初中)varn,jr,jw,jb:integer;ch1:char;ch:array[1..20]dchar;beginreadln(n);fori:=1tondoread(ch[i]):jr:=1;jw=n;jb:=n;while(jr<=jw)do2013-5-3122吴再陵第二十二页，共四十七页。BeginIf(ch[jw]='R')thenbeginch1:=Ch[jr];Ch[jr]:=ch[jw];ch[jw]:=ch1:jr:=jr+1;endelseifch[jw]='W'thenjw:=jw-1Elsebeginch1:=ch[jw];ch[jw]:=ch[jb];ch[jb]:=ch1;jw:=jw-1;jb:=jb-1;endend;2013-5-3123吴再陵第二十三页，共四十七页。fori:=1tondowrite(ch[i]);writeln;end.输入:10RBRBWWRBBR输出:RRRRWWBBBB2013-5-3124吴再陵第二十四页，共四十七页。完善程序题解题方法步骤：1.仔细阅读文字解释，理解题意和提供的解题思路2.根据问题的求解要求，了解输入、输出内容和问题处理方法3.先阅读主程序，了解输出变量和输出要求以及主程序中需要调用的过程或函数是哪些。4.阅读过程或函数，了解其完成的功能5.填空方法：一般从主程序最后输出要求，反推主程序中的变量填写或表达式、语句等的书写2013-5-3125吴再陵第二十五页，共四十七页。6.根据主程序参数与子程序参数传递关系，填写子程序的变量，根据子程序需要完成的功能，完成子程序填空。7.填写完毕，再将程序整个阅读、执行一遍，看能否完成问题提出的要求。2013-5-3126吴再陵第二十六页，共四十七页。

1.在A，B两个城市之间设有N个路站(如下图中的S1，且N<100)，城市与路站之间、路站和路站之间各有若干条路段(各路段数≤20，且每条路段上的距离均为一个整数)。2013-5-3127吴再陵第二十七页，共四十七页。

A，B的一条通路是指：从A出发，可经过任一路段到达S1，再从S1出发经过任一路段，…最后到达B。通路上路段距离之和称为通路距离(最大距离≤1000)。当所有的路段距离给出之后，求出所有不同距离的通路个数(相同距离仅记一次)。例如：下图所示是当N=1时的情况：2013-5-3128吴再陵第二十八页，共四十七页。从A到B的通路条数为6，但因其中通路5+5=4+6，所以满足条件的不同距离的通路条数为5。算法说明：本题采用穷举算法。数据结构：N：记录A，B间路站的个数

数组D[I，0]记录第I-1到第I路站间路段的个数

D[I，1]，D[I，2]，…记录每个路段距离

数组G记录可取到的距离2013-5-3129吴再陵第二十九页，共四十七页。程序清单：

PROGRAMCHU7_6；

VARI，J，N，S：INTEGER；

B：ARRAY[0..100]OFINTEGER；

D：ARRAY[0..100，0..20]OFINTEGER；

G：ARRAY[0..1000]OF0..1；2013-5-3130吴再陵第三十页，共四十七页。BEGIN

READLN(N)；

FORI:=1TON+1DO

BEGIN

READLN(D[I，0])；

FORJ:=1TOD[I，0]DO

READLN(D[I，J])；

END；

D[0，0]:=1；

FORI:=1TON+1DO

B[I]:=1；

B[0]:=0；

FORI:=0TO1000DO

G[I]:=0；

WHILE①DO2013-5-3131吴再陵第三十一页，共四十七页。BEGIN

S:=0；

FORI:=1TON+1DO

S:=②

G[S]:=1；J:=N+1；

WHILE③DOJ:=J-1；

B[J]:=B[J]+1；

FORI:=J+1TON+1DO

B[I]:=1；

END；

S:=0；

FORI:=1TO1000DO

④；

WRITELN(S)；READLN；

END.B[0]=0;S+D[I,B[I]];B[J]=D[J,0];S:=S+G[I];2013-5-3132吴再陵第三十二页，共四十七页。2.求子串位置。从键盘输入两个字符串x1,x2，要求查找出x2在x1字符串中的位置（起始位置）。算法说明：（1）用两个变量分别表示输入的字符串，并求出两个字符串的长度。（2）利用I,j变量作为扫描两个字符串的指针

（3）扫描两个字符串，当其相等时，将指针指向下一个字符，当j的值大于len2,则输出x2在x1中的位置（4）若子串位置不匹配，则使I的指针回溯，j指针重新指向子串的第一个字符。2013-5-3133吴再陵第三十三页，共四十七页。programexp4_1;varx1,x2:string;i,j,len1,len2,ps:integer;functionpos1(r1,r2:string;L1,L2:integer):integer;vari,j:integer;

begini:=1;j:=1;while(i<=L1)and(j<=L2)do2013-5-3134吴再陵第三十四页，共四十七页。

ifr1[i]=r2[j]thenbegin

③

；

④

endelsebegin⑤；⑥

；end;ifj>L2then

⑦

else

⑧

;end;beginreadln(x1);readln(x2);writeln(x1);

writeln(x2);len1:=

①

;len2:=

②

;ps:=pos1(x1,x2,len1,len2);writeln(ps:5);end.2013-5-3135吴再陵第三十五页，共四十七页。(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-3136吴再陵第三十六页，共四十七页。3.有k个人在银行排队等待存取钱，假如营业员接待每个人的时间为Ti，请编写一个程序，找出这k个人排队的一种顺序，使得k个人的平均等待时间最短。程序如下：programexp_6;vari,j,k,p,s:longint;a:array[1..200,1..2]oflongint;beginreadln(k);fori:=1tokdobeginread(a[i,1]);a[i,2]:=i;end;

2013-5-3137吴再陵第三十七页，共四十七页。fori:=1tok-1doforj:=i+1tokdoif_____(1)________thenbegina[i,1]:=a[i,1]+a[j,1];a[j,1]:=___(2)________;a[i,1]:=___(3)___________;p:=a[i,2];a[i,2]:=__(4)_____;a[j,2]:=__(5)____;end;2013-5-3138吴再陵第三十八页，共四十七页。fori:=1tokdoifi<kthenwrite(a[i,2],'')elsewriteln(a[i,2]);p:=0;s:=a[1,1];fori:=2tokdobeginp:=___(6)_____;s:=__

_(7)___;end;writeln(p/k:0:2);end.2013-5-3139吴再陵第三十九页，共四十七页。银行取钱，等待时间最短（贪心算法）（1）a[I,1]>a[j,1]（2）a[j,1]:=a[I,1]-a[j,1];（3）a[I,1]:=a[I,1]-a[j,1];（4）a[I,2]:=a[j,2];（5）a[j,2]:=p;（6）p:=p+s（7）s:=s+a[I,1];2013-5-3140吴再陵第四十页，共四十七页。4.设有一棵二叉树，如图所示，其中圈中的数字表示各个旅游景点旅游的人数，圈边上数字表示结点编号，现在需要建立一个旅馆，使所有旅游人所走的路程之和为最小，同时约定结点之间的距离为1，如图所示，若旅馆建在：1处，则距离和=4+12+2*20+2*40=1362处，则距离和=4*2+13+20+40=81…….输出最小距离和。程序如下：2013-5-3141吴再陵第四十一页，共四十七页。programexp_7;varw:array[1..100]oflongint;g:array[1..100,1..100]oflongint;n,i,j,k,l,r,min,s:longint;beginreadln(n);fori:=1tondoforj:=1tondog[I,j]:=1000000;

2013-5-3142吴再陵第四十二页，共四十七页。fori:=1tondobeging[I,I]:=0;readln(w[i],L,r);ifL>0thenbeging[I,l]:=1;g[l,i]:=1end;

2013-5-3143吴再陵第四十三页，共四十七页。ifr>0thenbeging[I,r]:=1;g[r,I]:=1endend;fork:=1tondofori:=1tondoifi<>kthenforj:=1tondo