信息竞赛高手进

国际标准书号（International Standard Book Number）简称ISBN。
ISBN 978-7-107-17648-7 是普通高中课程标准实验教科书 《化学 必修2》的书号。
关于信息竞赛，请参考附档(无法插入文档，请参考以下内容）。
课 题： §1 信息竞赛及一些术语简介 备课：盖建华 审稿：
目标 （1）了解信息竞赛背景知识，掌握竞赛的知识结构。
（2）会初步运用信息科学的思想去考虑问题。
概要 重点：竞赛要掌握的知识结构、数据结构、算法的概念。
难点：一些术语及其内涵，要求深刻掌握数据结构、算法的概念。
背景知识 1 信息学奥赛的全称是青少年信息学（计算机）奥林匹克竞赛（早期称为青少年计算机程序设计竞赛），是旨在广大青少年中普及计算机教育，推广计算机应用的一项学科性竞赛活动。全国性的信息学奥赛可分为三个层次：先举办全国信息学(计算机)奥林匹克分区联赛（简称NOIP）,联赛分高中组,初中组进行, 以普及为主。在分区联赛的基础上,各省市组成自己的代表队(一般为3名选手),参加第二个层次的比赛，即全国青少年信息学奥林匹克竞赛 (简称 NOI), 第三个层次是从 NOI 中选拔优秀选手(一般为 15 人), 经过培训, 考试选拔,组成国家队(一般 4—5 人). 参加国际信息学奥林匹克竞赛, 即IOI, 这是国际性的最高水平的竞赛。 竞赛分两轮：初试和复试。初试形式为笔试，侧重考察学生的计算机基础知识和编程的基本能力，并对知识面的广度进行测试。初试为资格测试，各省初试成绩在本赛区前15%的学生进入复赛。复试形式为上机，着重考察学生对问题的分析理解能力，数学抽象能力，编程语言的能力和编程技巧、想象力和创造性等。各省联赛的等第奖在复试的优胜者中产生。
2 初赛内容与要求
▲计算机的基本常识
1．计算机和信息社会（信息社会的主要特征、计算机的主要特征、数字通信网络的主要特征、数字化）
2．信息输入输出基本原理（信息交换环境、文字图形多媒体信息的输入输出方式）
3．信息的表示与处理（信息编码、微处理部件MPU、内存储结构、指令，程序，和存储程序原理、程序的三种基本控制结构）
4．信息的存储、组织与管理（存储介质、存储器结构、文件管理、数据库管理）
5．信息系统组成及互连网的基本知识（计算机构成原理、槽和端口的部件间可扩展互连方式、层次式的互连结构、互联网络、TCP/IP协议、HTTP协议、WEB应用的主要方式和特点）
6．人机交互界面的基本概念（窗口系统、人和计算机交流信息的途径（文本及交互操作））
7．信息技术的新发展、新特点、新应用等。
▲计算机的基本操作
1. WINDOWS和LINUX的基本操作知识
2. 互联网的基本使用常识 （网上浏览、搜索和查询等）
3. 常用工具软件使用（文字编辑电子邮件收发等）
▲数据结构
1．程序语言中基本数据类型(字符、整数、长整数、浮点)
2. 浮点运算中的精度和数值比较
3．一维数组（串）与线性表
4．记录类型（PASCAL）/ 结构类型（C）
▲程序设计
1．结构化程序设计的基本概念
2．阅读理解程序的基本能力
3．具有将简单问题抽象成适合计算机解决的模型的基本能力
4．具有针对模型设计简单算法的基本能力
5．程序流程描述（自然语言/伪码/NS图/其他）
6．程序设计语言（PASCAL/C/C++，2003仍允许BASIC）
▲基本算法处理
1．初等算法（计数、统计、数学运算等）
2．排序算法（冒泡法、插入排序、合并排序、快速排序）
3．查找（顺序查找、二分法）
4．回溯算法
课前预习 说说对下列概念的理解
（1）TCP/IP协议 （2）数据结构
（3）PASCAL语言 （4）算法
思考
探究 1、思考回答下列情景题：
TCP/IP 是供已连接因特网的计算机进行通信的通信协议。TCP/IP 定义了电子设备（比如计算机）如何连入因特网，以及数据如何在它们之间传输的标准。数据以TCP/IP协议进行传输时，可以拿信件的处理过程来类比。数据好比是________。IP地址好比是________。TCP端口好比是_________。假如有人不按协议操作，或者是向所有群体发送大量信息，或者是向某个人发送大量信息，最终导致网络拥塞或者瘫痪，这叫做___________。

程序设计中，数组可以用数学上的数列来类比。假设数列{an}的通项公式为an=4n+1(n>=1)，则a[10]=____________。下面是计算机上存储的一个4*4的数阵，如果用数列的通项公式来表示，应该为_________________。如果把它看做一个4*4的表格，比如第4行第4列的数字为a[4,4]=8，则a[m,n](m，n取1..4)的通式为___________________ (用m,n来表示)。
1 4 9 16
1 2 3 4
25 36 49 64
5 6 7 8

递推算法是一种用若干步可重复的简单运算（规律）来描述复杂问题的方法。比如要把任何一个自然数的立方写成一串连续奇数之和。可以按如下方法递推：
13=1
23=3+5=8
33=7+9+11=27
43=13+15+17+19=64
……………………….
设n为输入的一个任意自然数，它的立方是由m个奇数之和构成的，其中第一个奇数为p，则n3=p+____+...+______。n+1立方是由____个奇数之和构成，其中第一个奇数为_______。另外当n=1时，m=_____，p= ______。
（1）把数组a[n]中的元素进行平方运算，得到的新的数组如何表达？
（2）把{1,5,9,11,8}按从大到小顺序排列。
（3）以信件来类比，数据按TCP/IP协议组装好后，应该包含哪些地址信息？
（4）如果有人不按业界定制的协议去实现自己的网络通信，那他用的是什么协议？
（5）如果不用递推算法，你能使用数学归纳法得出n3的表达方法吗？你能否从中体会到计算机处理方法和数学思考方法的一些区别？

新知探究 思考下列问题：
1 假设有一个数组(array)，里面有8个元素{1, 5, 10, 20, 15, 8, 6, 90}。
观察其特点，发现里面的元素都是_____，具有相同类型，并且他们是____的形式组织起来。我们把这些按序排列的同类数据元素的集合称为数组。
在整数数组的基础上，我们可以定义一些标准的操作，比如找最大最小数，排序等等。大家考察一下，在数组上还可以定义哪些操作？
因此，在计算机科学中，数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象（数据元素）以及它们之间的关系和运算等的学科，而且确保经过这些运算后所得到的新结构仍然是原来的结构类型。

另外，我们也可以从集合和函数的观点来考察数据结构。例如上述数组的元素可以组成一个集合，他们之间的先后关系、大小关系、排序等都可以理解为______关系。
数据结构可以形式地定义为（K，R）（或（D，S）），其中，K是数据元素的有限集，R是K上的关系的有限集。
2 通过上面递归算法的例题，我们总结一下算法的特征：
算法（Algorithm）是一系列解决问题的清晰指令，也就是说，能够对一规范的_____，在有限时间内获得所要求的____。算法可以理解为有基本运算及规定的运算顺序所构成的完整的解题步骤。或者看成按照要求设计好的有限的确切的计算序列，并且这样的步骤和序列可以解决一类问题。
　　一个算法应该具有以下五个重要的特征：
　　1、有穷性： 一个算法必须保证执行有限步之后结束；
　　2、确切性： 算法的每一步骤必须有确切的定义；
　　3、输入：一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身定除了初始条件；
4、输出：一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的；
5、可行性： 算法原则上能够精确地运行，用笔和纸做有限次运算后即可完成。
例题说明 [例1] 植树节那天，有五位参加了植树活动，他们完成植树的棵数都不相同。问第一位同学植了多少棵时，他指着旁边的第二位同学说比他多植了两棵；追问第二位同学，他又说比第三位同学多植了两棵；…如此，都说比另一位同学多植两棵。最后问到第五位同学时，他说自己植了10 棵。到底第一位同学植了多少棵树？

[例2]斐波列契数列（Faibonacci）0，1，1，2，3，5，8，13，21，34……求此数列第n项。

[例3]用筛法求出25以内的全部素数。

[例4]输入4名学生数学、物理、英语、化学、pascal五门课的考试成绩，求出每名学生的平均分，打印出表格。

当堂反馈练习 1、微型计算机的运算器、控制器及内存储器的总称是____。
A)CPU B)ALU
C)MPU D)主机
2、反映计算机存储容量的基本单位是____。
A)二进制位 B)字节
C)字 D)双字
3、十进制数123变换为等值的二进制数是____。
A)110101 B)110110
C)111011 D)110011
4、删除数组中的某元素，且右边的元素都向左平移一格。

小结 1、学好信息科学，一方面要大体上了解计算机组成、网络、操作系统等知识，另一方面要学会编程，这样才能让计算机听你的指令。另外数据结构和算法是信息竞赛的灵魂。
2、大家可以从递推算法上深刻体会到信息科学的思维特征。
学生反思
课后作业 1、猴子吃枣问题：猴子摘了一堆枣，第一天吃了一半，还嫌不过瘾，又吃了一个；第二天，又吃了剩下的一半零一个；以后每天如此。到第十天，猴子一看只剩下一个了。问最初有多少个枣子？
2、楼梯有N 级台阶，上楼可以一步上一阶，也可以一步上二阶。计算共有多少种不同走法？
3、兔子在出生两个月以后，就具有生殖后代的能力。假设一对兔子，每月都能生一对兔子，生出来的每一对小兔子，在出生两个月后，也每月生一对兔子。那末，由一对刚出生的小兔子开始，连续不断地繁殖下去，在某个指定的月份有多少对兔子？
4、给一维数组输入M个整数，假设M=6，数组元素分别为 7 4 8 9 1 5 ，
要求建立一个如下数组（矩阵）：
7 4 8 9 1 5
4 8 9 1 5 7
8 9 1 5 7 4
9 1 5 7 4 8
1 5 7 4 8 9
5 7 4 8 9 1

太难