信息学奥赛介绍
图片预览
文档简介
(共25张PPT)
知识体系
信息学奥赛辅导交流
省赛及联赛
资料推荐
市奥赛展望
信息学奥赛考察的知识与能力
总体目标：
培养学生如下几方面的能力：
l 想象力与创造力；
l 对问题的理解和分析能力；
l 数学能力和逻辑思维能力；
l 对客观问题和主观思维的口头和书面表达能力；
l 人文精神：包括与人的沟通能力，团队精神与合作能力，恒心和毅力，审美能力等。
返回
信息学奥赛考察的知识与能力
一、计算机基本常识
1．信息输入输出基本原理（信息交换环境、文字图形多媒体信息的输入输出方式）
2．信息的表示与处理（信息编码、微处理部件MPU、内存储结构、指令，程序，和存储程序原理、程序的三种基本控制结构）
3．信息的存储、组织与管理（存储介质、存储器结构、文件管理、数据库管理）
4．信息系统组成及互连网的基本知识（计算机构成原理、槽和端口的部件间可扩展互连方式、层次式的互连结构、互联网络、TCP/IP协议、HTTP协议、WEB应用的主要方式和特点）
5．人机交互界面的基本概念（窗口系统、人和计算机交流信息的途径（文本及交互操作））
6．信息技术的新发展、新特点、新应用等。
返回
信息学奥赛考察的知识与能力
二、程序设计基本知识
（1）数据结构
1．程序语言中基本数据类型(字符、整数、长整数、浮点)
2. 浮点运算中的精度和数值比较
3．一维数组（串）与线性表
4．记录类型（PASCAL）/ 结构类型（C）
5．指针类型 6．多维数组
7．单链表及循环链表 8．二叉树
9．文件操作（从文本文件中读入数据，并输出到文本文件中）
（2）程序设计语言 （3）结构化程序设计的基本概念
返回
信息学奥赛考察的知识与能力
三、程序设计基本能力
1．阅读理解程序的基本能力
2．具有将简单问题抽象成适合计算机解决的模型的基本能力
3．具有针对模型设计简单算法的基本能力
4．程序流程描述（自然语言/伪码/NS图/其他）
5．算法的实现能力
6．程序调试基本能力
7．设计测试数据的基本能力
8．程序的时间复杂度和空间复杂度的估计
返回
信息学奥赛考察的知识与能力
四、程序设计基本算法
1．初等算法（计数、统计、数学运算等）
2．排序算法（冒泡法、插入排序、合并排序、快速排序）
3．查找（顺序查找、二分法）
4．回溯算法
5．离散数学知识的应用（如排列组合、简单图论、数理逻辑）
6．分治思想
7．模拟法
8．贪心法
9．简单搜索算法（深度优先 广度优先）搜索中的剪枝
10．动态规划的思想及基本算法
返回
全国信息学奥赛联赛介绍
一、全国信息学奥赛联赛
全国信息学奥赛联赛全称是：全国青少年信息学奥林匹克竞赛联赛。每年举行一次，分初赛和复赛两试，均全国统一命题，统一时间进行。
初赛：以笔试的形式进行，题型包括：一、选择题；二、基本知识填空；三、写出程序结果；四、程序填空。可选用程序语言有：PASCAL、C、C++。通过初赛选拨参加复赛的人选，全省统一分数线，参加复赛的人数占参加初赛人数的15%左右。
复赛：全部为上机编程题，四大题，3个小时完成。由省派评委到分赛区监考和测试，全部用黑盒子测试的方式进行测试，根据复赛成绩评出全国一等奖和省二、三等奖（全国一等奖同时也是省赛区一等奖）。
返回
2004年 特刊
2004年 特刊
退出
不同进制之间转换的应用
1、不同进制之间数的大小比较
（化为同一进制后再比较）
如：将下面不同进制的数按由小到大排列: (110111)2 (125)10 (312)8
2、由P进制转化为Q进制
（先由P进制转化为十进制，再由十进制转化为Q进制）
如：二进制数11010转化为五进制数对应的值是
返回
求最大公约数的辗转相除法
求A和B的最大公约数
R=A MOD B
DO WHILE R<>0
A=B
B=R
R=A MOD B
LOOP
G=B{余数为0时的除数就是所求的最大公约数}
A与B的最小公倍数=A X B/ 最大公约数
返回
质数
也叫素数，是指除了1和它本身能整除它外，不能被别的数整除的数。
分解质因数：将一个数分解为质因数的乘积。
如：给出一个正整数N（N<=32767)，要求将其分解成质因子的连乘积。
例如：当N=24时 结果为：24=2*2*2*3（A）
又如；当N=13时 输出结果为：13=13 （B）
输入：N
输出：如（A）或（B）格式的结果
返回
分解质因数方法：
IPNUT "N=";N：S=0
FOR I=2 TO N-1
DO WHILE （N MOD I=0）
N=N/I：S=S+1： A(S)=I ：LOOP
NEXT I
IF A(1)=0 THEN PRINT N;"=";N : END
PRINT N;"=";A(1);
FOR J=2 TO S
PRINT "*";A(J);
NEXT J
END
返回
逻辑判断问题：
公安局拘留审查了四个有盗窃嫌凝的人：甲、乙、丙、丁。已知其中一人是罪犯，在警察审讯他们时，他们每人都说了两句话：
甲说：“乙没有偷，是丁偷的”；
乙说：“我没有偷，是丁偷的”；
丙说：“甲没有偷，是乙偷的”；
丁说：“我没有偷”。
事实表明，他们的话不是全对，就是全错，真正的罪犯是
返回
加法原理和乘法原理的应用
在A、B、C、D四个城市间，A到B有4条通路，B到C有3条通路，C到D有5条通路，则A到D共有 (2) 条通路。
A （4条）-> B （3条）->C 5条）-> D
在城市A与B之间，可乘汽车、火车、飞机，由A到达B。已知汽车有6班次，火车有4班次，飞机有3班次，问由A到B共有几种方案到达？ （汽车6班）
A --- （ 火车4班） B
（飞机3班）
返回
简单的排列、组合
从数字0、1、2、3四个数字中任意抽取3个数字组成三位数，可组成 个不同的三位的偶数（每个数字在同一个数中只能出现一次）。
从5个男同学，3个女同学中，抽出4位同学出来组成一个小组，小组中至少要有一位女同学，问有几种组成小组的方法？
返回
数字的拆分：
给出一个正整数N，将它的各位数字分离出来，并存入数组B中。
程序片段如下：
J=0: T=N
DO
J=J+1
B(J)=T MOD 10
T=INT(T/10)
LOOP UNTIL T=0
返回
枚举算法：
枚举法又叫列举法，算法思想是：根据问题中的条件（约束条件）将可能的解列举出来，然后一一验证是否符合题目要求，从而找到问题的解。应用枚举策略解题的关键是：根据问题的条件确定解的范围，和对可能的解进行验证。
例1＿4：最少余料问题
建筑师designer要将一根长度为L米的木材，截成长度规格分别为A米和B米两种短木料（S＞A＋B），每种木料至少截一根，为了节约起见，要求所剩余料最少。现在designer请你帮忙解决这个问题。要求输入木材的长度，和两种规格的单位长度，求出所剩余料最少情况下的最少余料值和两种规格各应截多少根。
返回
归纳法是根据问题中具体的数据，找出其中的规律，由具体推广到一般的思维方法。是由具体抽象到一般的方法。用归纳策略解题的关键点和难点是根据问题的具体数据，归纳出一般的规律。
归纳法：
例：兔子问题
兔子在出生两个月后就具有生殖后代的能力，假设有一对兔子，每个月都生一对兔子，出生后的每一对兔子在出生两个月后也每个月生一对兔子。那么，由一对兔子开始，满一年时，可以繁殖成多少对兔子？
设f(n)表示第n个月的兔子对数，通过分析有：f(1)=2,f(2)=3,f(3)=5,f(4)=8,f(5)=13,…。 再观察发现：从第2项开始，每项为它的前2项的和；推广到一般有：f(n)=f(n-1)+f(n-2)(n≥2)
返回
知识体系
信息学奥赛辅导交流
省赛及联赛
资料推荐
市奥赛展望
信息学奥赛考察的知识与能力
总体目标：
培养学生如下几方面的能力：
l 想象力与创造力；
l 对问题的理解和分析能力；
l 数学能力和逻辑思维能力；
l 对客观问题和主观思维的口头和书面表达能力；
l 人文精神：包括与人的沟通能力，团队精神与合作能力，恒心和毅力，审美能力等。
返回
信息学奥赛考察的知识与能力
一、计算机基本常识
1．信息输入输出基本原理（信息交换环境、文字图形多媒体信息的输入输出方式）
2．信息的表示与处理（信息编码、微处理部件MPU、内存储结构、指令，程序，和存储程序原理、程序的三种基本控制结构）
3．信息的存储、组织与管理（存储介质、存储器结构、文件管理、数据库管理）
4．信息系统组成及互连网的基本知识（计算机构成原理、槽和端口的部件间可扩展互连方式、层次式的互连结构、互联网络、TCP/IP协议、HTTP协议、WEB应用的主要方式和特点）
5．人机交互界面的基本概念（窗口系统、人和计算机交流信息的途径（文本及交互操作））
6．信息技术的新发展、新特点、新应用等。
返回
信息学奥赛考察的知识与能力
二、程序设计基本知识
（1）数据结构
1．程序语言中基本数据类型(字符、整数、长整数、浮点)
2. 浮点运算中的精度和数值比较
3．一维数组（串）与线性表
4．记录类型（PASCAL）/ 结构类型（C）
5．指针类型 6．多维数组
7．单链表及循环链表 8．二叉树
9．文件操作（从文本文件中读入数据，并输出到文本文件中）
（2）程序设计语言 （3）结构化程序设计的基本概念
返回
信息学奥赛考察的知识与能力
三、程序设计基本能力
1．阅读理解程序的基本能力
2．具有将简单问题抽象成适合计算机解决的模型的基本能力
3．具有针对模型设计简单算法的基本能力
4．程序流程描述（自然语言/伪码/NS图/其他）
5．算法的实现能力
6．程序调试基本能力
7．设计测试数据的基本能力
8．程序的时间复杂度和空间复杂度的估计
返回
信息学奥赛考察的知识与能力
四、程序设计基本算法
1．初等算法（计数、统计、数学运算等）
2．排序算法（冒泡法、插入排序、合并排序、快速排序）
3．查找（顺序查找、二分法）
4．回溯算法
5．离散数学知识的应用（如排列组合、简单图论、数理逻辑）
6．分治思想
7．模拟法
8．贪心法
9．简单搜索算法（深度优先 广度优先）搜索中的剪枝
10．动态规划的思想及基本算法
返回
全国信息学奥赛联赛介绍
一、全国信息学奥赛联赛
全国信息学奥赛联赛全称是：全国青少年信息学奥林匹克竞赛联赛。每年举行一次，分初赛和复赛两试，均全国统一命题，统一时间进行。
初赛：以笔试的形式进行，题型包括：一、选择题；二、基本知识填空；三、写出程序结果；四、程序填空。可选用程序语言有：PASCAL、C、C++。通过初赛选拨参加复赛的人选，全省统一分数线，参加复赛的人数占参加初赛人数的15%左右。
复赛：全部为上机编程题，四大题，3个小时完成。由省派评委到分赛区监考和测试，全部用黑盒子测试的方式进行测试，根据复赛成绩评出全国一等奖和省二、三等奖（全国一等奖同时也是省赛区一等奖）。
返回
2004年 特刊
2004年 特刊
退出
不同进制之间转换的应用
1、不同进制之间数的大小比较
（化为同一进制后再比较）
如：将下面不同进制的数按由小到大排列: (110111)2 (125)10 (312)8
2、由P进制转化为Q进制
（先由P进制转化为十进制，再由十进制转化为Q进制）
如：二进制数11010转化为五进制数对应的值是
返回
求最大公约数的辗转相除法
求A和B的最大公约数
R=A MOD B
DO WHILE R<>0
A=B
B=R
R=A MOD B
LOOP
G=B{余数为0时的除数就是所求的最大公约数}
A与B的最小公倍数=A X B/ 最大公约数
返回
质数
也叫素数，是指除了1和它本身能整除它外，不能被别的数整除的数。
分解质因数：将一个数分解为质因数的乘积。
如：给出一个正整数N（N<=32767)，要求将其分解成质因子的连乘积。
例如：当N=24时 结果为：24=2*2*2*3（A）
又如；当N=13时 输出结果为：13=13 （B）
输入：N
输出：如（A）或（B）格式的结果
返回
分解质因数方法：
IPNUT "N=";N：S=0
FOR I=2 TO N-1
DO WHILE （N MOD I=0）
N=N/I：S=S+1： A(S)=I ：LOOP
NEXT I
IF A(1)=0 THEN PRINT N;"=";N : END
PRINT N;"=";A(1);
FOR J=2 TO S
PRINT "*";A(J);
NEXT J
END
返回
逻辑判断问题：
公安局拘留审查了四个有盗窃嫌凝的人：甲、乙、丙、丁。已知其中一人是罪犯，在警察审讯他们时，他们每人都说了两句话：
甲说：“乙没有偷，是丁偷的”；
乙说：“我没有偷，是丁偷的”；
丙说：“甲没有偷，是乙偷的”；
丁说：“我没有偷”。
事实表明，他们的话不是全对，就是全错，真正的罪犯是
返回
加法原理和乘法原理的应用
在A、B、C、D四个城市间，A到B有4条通路，B到C有3条通路，C到D有5条通路，则A到D共有 (2) 条通路。
A （4条）-> B （3条）->C 5条）-> D
在城市A与B之间，可乘汽车、火车、飞机，由A到达B。已知汽车有6班次，火车有4班次，飞机有3班次，问由A到B共有几种方案到达？ （汽车6班）
A --- （ 火车4班） B
（飞机3班）
返回
简单的排列、组合
从数字0、1、2、3四个数字中任意抽取3个数字组成三位数，可组成 个不同的三位的偶数（每个数字在同一个数中只能出现一次）。
从5个男同学，3个女同学中，抽出4位同学出来组成一个小组，小组中至少要有一位女同学，问有几种组成小组的方法？
返回
数字的拆分：
给出一个正整数N，将它的各位数字分离出来，并存入数组B中。
程序片段如下：
J=0: T=N
DO
J=J+1
B(J)=T MOD 10
T=INT(T/10)
LOOP UNTIL T=0
返回
枚举算法：
枚举法又叫列举法，算法思想是：根据问题中的条件（约束条件）将可能的解列举出来，然后一一验证是否符合题目要求，从而找到问题的解。应用枚举策略解题的关键是：根据问题的条件确定解的范围，和对可能的解进行验证。
例1＿4：最少余料问题
建筑师designer要将一根长度为L米的木材，截成长度规格分别为A米和B米两种短木料（S＞A＋B），每种木料至少截一根，为了节约起见，要求所剩余料最少。现在designer请你帮忙解决这个问题。要求输入木材的长度，和两种规格的单位长度，求出所剩余料最少情况下的最少余料值和两种规格各应截多少根。
返回
归纳法是根据问题中具体的数据，找出其中的规律，由具体推广到一般的思维方法。是由具体抽象到一般的方法。用归纳策略解题的关键点和难点是根据问题的具体数据，归纳出一般的规律。
归纳法：
例：兔子问题
兔子在出生两个月后就具有生殖后代的能力，假设有一对兔子，每个月都生一对兔子，出生后的每一对兔子在出生两个月后也每个月生一对兔子。那么，由一对兔子开始，满一年时，可以繁殖成多少对兔子？
设f(n)表示第n个月的兔子对数，通过分析有：f(1)=2,f(2)=3,f(3)=5,f(4)=8,f(5)=13,…。 再观察发现：从第2项开始，每项为它的前2项的和；推广到一般有：f(n)=f(n-1)+f(n-2)(n≥2)
返回
同课章节目录