信息学奥林匹克竞赛资料(初赛资料)
- 格式：doc
- 大小：633.50 KB
- 文档页数：81
青少年信息学竞赛简要介绍
青少年信息学（计算机）奥林匹克竞赛（早期称为青少年计算机程序设计竞赛）是旨在广大青少年中普及计算机教育，推广计算机应用的一项学科性竞赛活动。全国从1984年开始举办全国性竞赛。而自从1989年我国参加第一届国际信息学奥林匹克（International Olympiad
in Informatics, 简称IOI）以来，全国青少年计算机程序设计竞赛也更名为全国青少年信息学（计算机）奥林匹克（National Olympiad in Informatics, 简称NOI）。
全国信息学奥林匹克竞赛是经国家教委批准，中国科协具体领导，由中国计算机学会主办的。浙江省信息学奥林匹克竞赛活动从84年参加全国赛开始，由省科学技术协会、省教育厅和省计算机学会联合组织。
为促进计算机普及并兼顾提高，从95年开始全国举办信息学奥林匹克竞赛分区联赛，根据浙江实际情况，我省将分区联赛初、复赛作为省信息学奥赛的初赛和复赛。浙江省开始几年初赛试题自己命题，现在采用全国卷。
一．信息学奥林匹克竞赛的内容和考核方式：
对学生学习计算机理论知识和实践能力有一个整体性的全面要求，也即整个信息学（计算机）竞赛已成为智力和应用计算机能力的竞赛，涉及到有关计算机基础知识、计算机软件知识、程序设计知识、组合数学和运筹学的知识、人工智能初步知识以及计算机应用知识等，同时要求学生有较强的编程和上机调试的实践能力。
1． NOI全国分区联赛初赛 (每年10月左右)
对象：在校中学生， 分初中、高中组
考试形式：笔试 性质： 普及
确定获初级选手证书名单及进入复赛名单，在各地市举行。
2．NOI全国分区联赛复赛 (每年11月左右)
对象：初赛优胜者 分初中、高中组
考试形式：上机试 性质：普及兼顾提高
确定全国分区联赛一、二等奖，省各等奖及全国各级证书获得者名单，在杭州进行，省派评委协助测评。信息学奥林匹克竞赛复赛的考核方式是采用封闭式（连续3～4小时）上机编程解题的形式，编程语言基本限于BASIC与 PASCAL，竞赛难度较大。程序完成后要通过严格的数据测试，这就对同学们编程能力有更高的要求：不但要能编程，编好的程序能运行，而且所设计的程序还要能通过在各种边界条件下和各种环境下设置的测试数据。
二．全国青少年信息学奥林匹克联赛大纲竞赛大纲
一、初赛内容与要求：（＃表示普及组可不涉及，以下同）
计 基
算 本
机 常
的 识 *诞生与发展 *特点 *在现代社会中的应用
*计算机系统的基本组成 *计算机中的数的表示
*计算机的工作原理#
*计算机信息安全基础知识 *计算机网络 计 基
算 本
机 操
的 作 *常见操作系统的使用基础
*常用输入/输出设备的种类、功能、使用
*汉字输入/输出方法 *常用计算机屏示信息
程
序
设
计
基
本
知
识 程序的表示 *自然语言的描述 *PASCAL或BASIC语言
数据结构 *简单数据的类型 *构造类型：数组、字符串
*了解基本数据结构（线性表、队列与栈）
程序设计 *结构化程序的基本概念 *阅读理解程序的基本能力
*具有完成下列过程的能力：
现实世界（指知识范畴的问题）→信息世界（表达解法）
→计算机世界（将解法用计算机能实现的数据结构和算法描述出来）
基本算法
处
理 *简单搜索 *字串处理 *排序 *查找 *统计 *分类 *合并
*简单的回溯算法 *简单的递归算法
二、复赛内容与要求：
在初赛的内容上增加以下内容：
计算机
软 件 *操作系统的使用知识
*编程语言的使用
数据
结构 *结构类型中的记录类型 *指针类型 *文件（提高组必须会使用文本文件输入）
*链表 *树 *图#
程序
设计 *程序设计能力 *设计测试数据的能力
*运行时间和占用空间的估算能力#
算法
处理 *排列组合的应用 *进一步加深回溯算法、递归算法
*分治法 *搜索算法：宽度、深度优先算法
*表达式处理：计算、展开、化简等# *动态规划#
三、初赛试题类型：注：试题语言两者选一、高中学生必须参加提高组联赛。
（ 程序设计语言：基本BASIC或TURBO PASCAL）
*判断 *填空 *完善程序 *读程序写运行结果 *问答
四、推荐读物：
*分区联赛辅导丛书 *学生计算机世界报
三．Pascal语言
一、结构化程序设计
结构化程序设计实际上就是为了使程序具有合理的结构，以便保证和验证程序的正确性而规定的一套进行结构程序设计的方法。用结构化程序设计的方法设计出来的程序称为结构化程序。结构化程序设计语言就是反映了结构化程序设计的要求和限制，便于用来书写结构化程序的语言。用这种语言书写的程序易于保证正确性。
二、PASCAL语言的特色
从使用者的角度看，PASCAL语言有以下几个主要特点：
1、它是结构化语言 PASCAL语言是结构化的程序设计语言。PASCAL语言提供了直接实现3种基本结构的语句心以及定义子程序(“过程”和“函数”)的功能。可以方便的书写出结构化的程序。在编写程序时可以完全不使用转向语句。这就易于保证程序的正确性和易读性。PASCAL语言强调的是可靠性、易读性和概念性的清晰性。
2、有丰富的数据类型
PASCAL语言提供了整型、实型、字符型、布尔型、枚举型、子域型以及由以上类型构成的数组类型、集合类型、记录类型和文件类型。此外，还提供了指针类型。PASCAL语言所提供的丰富的数据结构和上述的结构化性质，使得它可以被方便地用来描述复杂的算法，得到质量较高的程序。
3、能适应于数值计算和非数值信息处理领域
在PASCAL语言出现之前，FORTRAN语言主要处理科学计算，而COBOL语言则主要用于非数值信息处理。PASCAL语言则兼顾了这两个不同领域的应用。PASCAL语言可广泛应用于各种领域，还可以用于计算机辅助教育、计算机绘图等应用领域。
4、PASCAL程序的书写格式比较自由
PASCAL允许一行写多个语句，一个语句可以分写在多行上，这样就可以使PASCAL程序写得像讲诗歌格式一样优美，便于阅读。
除了以上优点外，PASCAL语言还具有简单易学的特点，许多学校把PASCAL作为程序设计课程的第一种程序设计语言。
PASCA:L语言的主要缺点：不够灵活，书写较麻烦。
四．数据结构
数据结构是计算机专业基础课程之一，是十分重要的核心课程。计算机的所有系统软件和应用软件都要用到各种类型的数据结构。要想更好地运用计算机来解决实际问题，仅仅学习计算机语言而缺乏数据结构知识是远远不够的，而打好“数据结构”这门课程的扎实基础，对于学习计算机专业的其他课程都是十分重要的。
随着计算机应用领域不断扩大，非数值计算问题占据了当今计算机应用的绝大多数，简单的数据类型已经远远不能满足需要，各数据元素之间的复杂联系已经不是普通数学方程所能表达的。因此，掌握好数据结构方面的知识，对于提高我们解决实际问题的能力将会有莫大的帮助。实际上一个好的程序无非是选择一个合适的数据结构和好的算法，而好的算法的选择很大程度上取决于描述实际问题的数据结构的选取。所以，学好数据结构，将是进一步提高我们程序设计的关键之一。
五．算法例子
1．称小球重量：
有6个小球分别用1～6编号, 其中5个重量相同。现在有一架台称，一次能称出放在上面的若干物体的总重，要求编一个程序，让计算机找出一种称法，只要称3次就可以知道每个小球的重量。
具体操作时由操作者默想6个物体的重量，然后由计算机用编号提问若干物体的重量，如此3次后程序应能输出每个物体的重量。
PROGRAM EX02; VAR
S1, S2, S3, p: integer;
BEGIN
P:=0;
write(’请输入1号+2号+3号+4号的重量总和:’); read（s1）;
write(’请输入1号+2号+5号的重量总和:'); read（S2）；
IF 3*s1<>4*s2 THEN
BEGIN
write('请输入1号+3号的重量总和：’）; read(s3);
IF S1+S3=2*S2 THEN
BEGIN P:=1; Writeln(’第1号重’, S3+S2-S1,’其余重’,S2-S3);END;
IF S3+2*S2 =2*S1 THEN
BEGIN p:=1; writen(’第2号重’, 3*S2-2*S1, ’,其余重’,S1-S2); END;
IF 2*S2+3*S3＝3*S1 THEN
BEGIN p:=1; writeln(’第3号重’,S3-(S2 div 3),’,其余重’,S2 div 3); END;
IF 2*S2＝3*S3 THEN
BEGIN p:=1; writeln(’第4号重’,S1-3*(S3 div 2),’,其余重’,S3 div 2); END;
IF S1 =2*S3 THEN
BEGIN p:=1; writeln(’第5号重’,s2-2*(s3 div 2),’,其余重’, s3 div 2), END;
IF p:=0 THEN writeln('输入的数据不正确!');
END
ELSE IF 3*s1 = 4*s2 THEN
BEGIN write('请输入6号的重量:'); read（s3）;
writeln('第6号重',s3, '其余重' ,s2 div 3);
END;
Writeln;
END.
2．打印奇数阶幻方：
方法：M×M 阶奇数幻方,在最后一行（第 M行）的中间(M+1)/2处填上1,左下方向填2, ....,若前方已经有数,在原数的上方填入。 三阶: 2 9 4
7 5 3
程序如下: 6 1 8
program huafang;
var i,j,k,n :integer;
a: array[1..20,1..20] of integer; 五阶：9 2 25 18 11
begin 3 21 19 12 10
for i:= 1 to 20 do 22 20 13 6 4
