当前位置:首页 >> 学科竞赛 >>

计算机奥林匹克竞赛讲座


初中信息学奥林匹克竞赛
——方法与内容

2013-5-31

1

吴再陵

与同行们共商讨
一、组织方法 二、教师本身所具有的品质

三、教学进度与时间安排
四、教学方法

五、奥赛教学体会
六、初赛

r />七、复赛
2013-5-31 吴再陵 2

组织方法——三级制
? 市级——中级水平以上的培训 ? 学校——负责初级、中级及高级

? 年级——按年级组织课外活动小组,循序渐进,完成
教学任务

视学生水平和能力、师资力量、学校支持程度灵活组
织课外活动小组

2013-5-31

吴再陵

3

? 人员选拔是关键 :

初一新生 :
通过考试选拔——数学,新知识探究

分层次组班

2013-5-31

吴再陵

4

教师具备的素质
?1. 对事业的责任心、对工作的态度

?2. 对学生的爱心
?3. 自身学习能力、悟性

?4. 教学能力
?5. 组织能力

2013-5-31

吴再陵

5

时间与进度
? 总体目标设计:

(1)初一:基本知识与简单算法
初二(上)竞赛:初见成效

(2)初二:数据结构与算法
初三(上)竞赛:取得成果

充分利用寒暑假时间,保证有一定的培训时间
? 具体安排

2013-5-31

吴再陵

6

课程进度安排
1. 中级本:数组、过程

2. 中级本:集合、记录、文件
3. 数据结构:线性表、栈、队列+简单算法

4. 数据结构: 指针变量+线性链表+树、图基本知识+常 用算法
5. 数据结构+算法深入应用

2013-5-31

吴再陵

7

培训方法
? 1. 讲授法 ? 2. 上机实践

? 3. 小组讨论
? 4. 专题讲座 ? 5. 模拟练习 ? 6. 实战练习 其他综合性学习

2013-5-31

吴再陵

8

奥赛教学体会
? 1. 把握每一章的教学重点,解决难点,循序渐进、 脚踏实地开展基础知识教育

? 2. 培养学生良好的学习习惯,认真对待每一次上机
实习和练习,真诚对待每一个学生。 ? 3. 培养学生创新意识、思维方法,关注一题多解。 ? 4. 多用问题分析法、问题讨论的教学方法

2013-5-31

吴再陵

9

?

5. 适时、适当进行专题讲座与专题练习,加强与巩

固所学习知识

? 6. 分层次教学:起点不同、目标不同,根据实际情
况因材施教。

? 7. 教师间相互学习、相互协作,设计本校总体目标
培训计划,以求得到校领导、班主任和其他老师的支持, 建立友好的协作关系。

2013-5-31

吴再陵

10

教学重难点及解决方法:
? 1. 循环结构:循环应用 ? 2. 数组:元素与整体,应用(排序,选举)

? 3. 过程与函数:参数、变量、过程与函数调用
? 4. 递归程序设计及执行过程

? 5. 指针变量
? 6. 链表及应用:头指针 ? 7. 栈与队列的应用:栈与递归、栈与回溯 ? 队列与宽搜
2013-5-31 吴再陵 11

8. 哈夫曼树的生成算法及应用 9. 图的遍历及应用 10. 最短路径及应用 11. 查找与排序:快排、堆排序,哈希函数及应用 12. 回溯算法及应用 13. 搜索算法:时间与空间问题 14. 数学、递推及应用 15. 动态规划:转移方程的建立
2013-5-31 吴再陵 12

初赛复习(根据大纲)
? 1. 基本知识

? 2. 基本算法
? 3. 基本概念

? 4. 组合数学、数学推理
? 5. 阅读程序 ? 6. 完善程序

2013-5-31

吴再陵

13

阅读程序的技巧

阅读程序的结构:先主程序后子程序 1 阅读程序需要输出的结果或内容 2 用列表的方法,将程序中主要变量值的变化过程写出 来,找出变化规律,以快速求得程序的运行结果。 3 在阅读主程序时,需要注意主程序完成哪些操作任务, 其最后输出什么,它在调用过程或函数时,参数值是 什么。 4 阅读子程序时,主要掌握过程或函数完成什么样的功 能,其传递参数是什么样的参数(值参、变参) 5 值参、变参、局部变量、全程变量作用域、变化情况
2013-5-31 吴再陵 14

1. pmgram Gxp3 (利用数学知识得到结果) Var d1,d2,X,Min:real; begin min:=10000;X:=3; while X<15 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; 输出: 15.00 writeln(Min:1O:2); end.
2013-5-31 吴再陵 15

2. program exam_3;

var a:array_[1…9] of string;
st,x:string;I,j,n,m:integer;

begin
repeat writeln('please input a string(length<10):’);

readln(st);
n:=length(st); until (n<10) and odd (n); m:=trunc((n+1)/2); for I:=l to n do

for j:=l to n do a[i, j]:=’ ‘;
2013-5-31 吴再陵 16

for I:=1 to m do { 取半 4}

for j:=i to n+l-I do
begin

x:=copy(st,J,1);a[i,J]:=x; a[n+1-i,n+l-j]:=x;
end; for j:=n downto l do

begin
for i:=1 to n do write(a[i,J]:2);writeln; end: end. 输入数据: please input a string (length<10) :

RUTYFPE
2013-5-31 吴再陵 17

用列表方法,找出规律,正确写出运行结果:
输出结果:

1
I=1,J=1TO 7 I=2, J=2TO 6 I=3,J=3TO 5 I=4,J=4TO 4 1 2 3 4 5 R

2
U U

3
T T T F

4
Y Y Y Y Y

5
F F F T

6
P P

7
E

6
7
2013-5-31

P
E P
吴再陵

F
F

Y
Y

T
T

U
U R
18

3. program exam_4; ( 9 分)

var a: array[1..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]; a[dep]:=i; if dep=m then inc(s)

else try (dep+1);
2013-5-31 吴再陵 19

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 吴再陵 20

Dep=1 , for I:=1 to 5 do

flag:=[1] , a[dep]=1

Dep=2 , for I:=2 to 5 do flag=[1,2], a[dep]=2
Dep=3, for I:=3 to 5 do flag=[1,2,3], a[dep]=3

Dep=4, for I:=4 to 5 do flag=[1,2,3,4] , a[dep]=4
此时满足 dep=m , 则 s:=s+1 , 回溯从集合中去掉当前 [I],用其后数据填入集合中 根据问题可以知道: 四重循环: 2*3*4*5=120

2013-5-31

吴再陵

21

4、program exp2;( 2002 初中) var n,jr,jw,jb:integer; ch1:char; ch:array[1..20]d char; begin readln(n); for i:=1 to n do read(ch[i]): jr:=1; jw=n; jb:=n; while (jr<=jw) do

2013-5-31

吴再陵

22

Begin If (ch[jw]='R') then begin ch1:=Ch[jr]; Ch[jr]:=ch[jw]; ch[jw]:=ch1: jr:=jr+1; end else if ch[jw]='W' then jw:=jw-1 Else begin ch1:=ch[jw]; ch[jw]:=ch[jb]; ch[jb]:=ch1; jw:=jw-1; jb:=jb-1; end end;
2013-5-31 吴再陵 23

for i:=1 to n do write(ch[i]); writeln; end. 输入:10 RBRBWWRBBR 输出: RRRRWWBBBB

2013-5-31

吴再陵

24

完善程序题解题方法
步骤: 1. 仔细阅读文字解释,理解题意和提供的解题思路 2. 根据问题的求解要求,了解输入、输出内容和问题处 理方法 3. 先阅读主程序,了解输出变量和输出要求以及主程序 中需要调用的过程或函数是哪些。

4. 阅读过程或函数,了解其完成的功能
5. 填空方法:一般从主程序最后输出要求,反推主程序

中的变量填写或表达式、语句等的书写
2013-5-31 吴再陵 25

6. 根据主程序参数与子程序参数传递关系,填写子程 序 的变量,根据子程序需要完成的功能,完成子程序填 空。 7. 填写完毕,再将程序整个阅读、执行一遍,看能否 完成问题提出的要求。

2013-5-31

吴再陵

26

1. 在A,B两个城市之间设有N个路站(如下图中 的S1,且N<100),城市与路站之间、路站和路站之 间各有若干条路段(各路段数≤20,且每条路段上的 距离均为一个整数)。

2013-5-31

吴再陵

27

A,B的一条通路是指:从A出发,可经过任一路 段到达S1,再从S1出发经过任一路段,…最后到达B。 通路上路段距离之和称为通路距离(最大距离≤1000)。当

所有的路段距离给出之后,求出所有不同距离的通路个
数(相同距离仅记一次)。

例如:下图所示是当N=1时的情况:

2013-5-31

吴再陵

28

从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-31

吴再陵

29

程序清单: PROGRAM CHU7_6; VAR I,J,N,S:INTEGER; B:ARRAY[0..100]OF INTEGER;

D:ARRAY[0..100,0..20] OF INTEGER;
G :ARRAY[0..1000] OF 0..1;

2013-5-31

吴再陵

30

BEGIN

READLN(N);
FOR I:=1 TO N+1 DO

BEGIN
READLN(D[I,0]); FOR J:=1 TO D[I,0]DO END; D[0,0]:=1; READLN(D[I,J]);

FOR I:=1 TO N+1 DO
B[0]:=0;

B[I]:=1;

FOR I:=0 TO 1000 DO G[I]:=0; WHILE 2013-5-31 ① DO
吴再陵 31

BEGIN S:=0; FOR I:=1 TO N+1 DO S:= ② G[S]:=1;J:=N+1; WHILE ③ DO J:=J-1; B[J]:=B[J]+1; FOR I:=J+1 TO N+1 DO B[I]:=1; END; (1) B[0]=0 ; S:=0; (2) S+D[I,B[I]] ; FOR I:=1 TO 1000 DO ④ ; (3) B[J]=D[J,0] ; WRITELN(S);READLN; (4) S:=S+G[I] ; END.
2013-5-31 吴再陵 32

2.

求子串位置。从键盘输入两个字符串x1,x2,要求查

找出x2在x1字符串中的位置(起始位置)。
算法说明:

(1)用两个变量分别表示输入的字符串,并求出两个字
符串的长度。 (2)利用I,j变量作为扫描两个字符串的指针 (3)扫描两个字符串,当其相等时,将指针指向下一个 字符,

当j的值大于 len2,则输出x2在x1中的位置
( 4)若子串位置不匹配,则使 I的指针回溯, j指针重新 指向子串的第一个字符。
2013-5-31 吴再陵 33

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

吴再陵

34

if r1[i] = r2[j] then begin ③





end

else begin
if j>L2 then ⑦ else




⑧ ;

⑥ ;end;

end;
begin writeln(x2);

readln(x1);
readln(x2); writeln(x1) ;

len1:=
len2:=




;
;

ps:=pos1(x1,x2,len1,len2);
writeln(ps:5); end.

2013-5-31

吴再陵

35

(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

吴再陵

36

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(a[i,1]); a[i,2]:=i; end;
2013-5-31 吴再陵 37

for i:=1 to k-1 do

for j:=i+1 to k do
if _____(1)________ then begin a[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-31 吴再陵 38

for i:=1 to k do if i<k then write(a[i,2],' ') else writeln(a[i,2]); p:=0; s:=a[1,1]; for i:=2 to k do begin p:=___(6)_____; s:=__ _(7)___ ; end; writeln(p/k:0:2); end.
2013-5-31 吴再陵 39

银行取钱,等待时间最短 (贪心算法) (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-31 吴再陵 40

4. 设有一棵二叉树,如图所示,其中圈中的数字表示 各个旅游景点旅游的人数,圈边上数字表示结点编号,现 在需要建立一个旅馆,使所有旅游人所走的路程之和为最 小,同时约定结点之间的距离为 1,如图所示,若旅馆建 在: 1处,则距离和=4+12+2*20+2*40=136 2处,则距离和=4*2+13+20+40=81 ……………………………………. 输出最小距离和。程序如下:

2013-5-31

吴再陵

41

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

g[I, j] := 1000000;

2013-5-31

吴再陵

42

for i := 1 to n do
begin g[ I , I ] := 0; readln(w[i], L, r); if L > 0 then begin g[I , l] := 1; g[l , i] := 1 end;

2013-5-31

吴再陵

43

if r > 0 then begin
g[I , r] := 1; g[r, 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

吴再陵

44

if (i <> j) and (k <> j) and ______(1)____________ then g[I , j] := _____(2)_________; min := maxlongint; ( 1 ) g[I,k] +g[k,j] < g[I,j] for i := 1 to n do (2)g[I,j]:=g[I,k]+g[k.j] begin ( 3 ) s:=s+g[I,j]*w[j] ; s:=0; (4)min:=s ; for j := 1 to n do s:=_____(3)________ ; (5)writeln( min ) if s < min then min := _____(4)______; end; writeln(_____(5)________); end.
2013-5-31 吴再陵 45

2013-5-31

吴再陵

46


相关文章:
中小学生计算机奥林匹克竞赛试题
中小学生计算机奥林匹克竞赛试题 (时间:90 分钟) 参赛证号 姓名 学校 总分 一、单项选择题(每小题 2 分,共 40 分) 1、操作系统是对( A、软件 B、硬件 ...
信息学奥林匹克竞赛培训教案(校本课程)
信息学奥林匹克竞赛培训教案第1章 计算机的发展与应用 1.1 计算机发展简史 1.1.1 第一台电子计算机的诞生 1946 年,世界上第一台数字式电子计算机由美国宾夕法...
信息学奥林匹克竞赛培训教案
信息学奥林匹克竞赛培训教案 (PASCAL 语言) 第 1 章 计算机的发展与应用 1.1 计算机发展简史 1.1.1 第一台电子计算机的诞生 1946 年,世界上第一台数字式...
高中信息学奥林匹克竞赛培训策略研究
【关键词】高中信息学 奥林匹克竞赛 培训策略 效率 青少年信息学奥林匹克竞赛旨在广大青少年中普及计算机教育, 推广计算机 应用的一项学科性竞赛活动。为促进计算机普及...
长沙市小学生计算机奥林匹克竞赛决赛试题(6题)
长沙市小学生计算机奥林匹克竞赛决赛试题(6题)_计算机软件及应用_IT/计算机_专业资料。长沙市小学生计算机奥林匹克竞赛决赛试题(6题) 测测你的水平!!!长沙市小学...
计算机奥林匹克竞赛初赛试题
计算机奥林匹克竞赛初赛试题_六年级其它课程_其它课程_小学教育_教育专区。aolinpike 2008 年长沙市小学生计算机奥林匹克竞赛初赛试题 作者:陈凯兵 来源:原创 人气:...
学校信息学奥林匹克竞赛培训计划
为了体现学校信息技术教育特色,丰富学生第二课堂活动,向中学生普及计算机基础知 识,培养学生学习计算机的兴趣,信息科组计划举办信息学奥林匹克竞赛培训班,组织培训 ...
信息学奥林匹克竞赛辅导Pascal语言
信息学奥林匹克竞赛辅导 Pascal 语言 淮北一中 秦护矿 第1页 信息学奥林匹克竞赛辅导 Pascal 语言秦护矿 信息技术组 安徽省淮北市第一中学 Ⅰ 第一部分:计算机...
信息学奥林匹克竞赛程序设计快速入门篇
信息学奥林匹克竞赛程序设计快速入门篇_IT/计算机_专业资料。错误!未指定书签。 错误!未指定书签。 实验一、 顺序结构程序设计 编写一个小程序,在屏幕上显示: *...
长沙市小学生计算机奥林匹克竞赛决赛题答案
2004年长沙市计算机奥林匹克竞赛决赛试题 2004年长沙市计算机奥林匹克竞赛决赛试题 年长沙 时间: 分钟) (时间:120 分钟) 一、求和(30 分) 由键盘输入正整数 N...
更多相关标签:
信息学奥林匹克竞赛 | 奥林匹克竞赛 | 头脑奥林匹克竞赛题目 | 化学奥林匹克竞赛 | 中国数学奥林匹克竞赛 | 2016数学奥林匹克竞赛 | 全国数学奥林匹克竞赛 | 全国化学奥林匹克竞赛 |