信息学奥林匹克竞赛培训教案(校本课程)

信息学奥林匹克竞赛培训教案第1章计算机的发展与应用1.1计算机发展简史1.1.1第一台电子计算机的诞生1946年，世界上第一台数字式电子计算机由美国宾夕法尼亚大学的物理学家约翰·莫克利（JohnMauchly）和工程师普雷斯伯·埃克特（PresperEckert）领导研制成功，取名为ENIAC（ElectronicNumericalIntegratorAndCalculator）。它可以在1秒进行5000次加减运算，3毫秒便可以进行一次乘法运算，能存储20个字长为10位的十进制数。1.1.2计算机发展的几个阶段第一代（1946~1958）第二代（1958~1964）第三代（1964~1975）第四代（1975~至今）主要电子器件电子管晶体管中小规模集成电路大规模/超大规模集成电路内存汞延迟线磁芯存储器半导体存储器半导体存储器外存储器穿孔卡片、纸带磁带磁带、磁盘磁盘、光盘等大容量存储器处理速度（指令数/秒）几千条几百万条几千万条数亿条以上第四代计算机以大规模集成电路VLSI为计算机的主要功能部件，用16K、64K或集成度更高的半导体存储器作为主存储器。新机器要继承原有机器指令系统中的全部指令，使得同一系列计算机的指令系统越来越复杂，这些计算机被称为“复杂指令系统计算机”，简称CISC。日趋庞大的指令系统降低了系统性能，而机器中最常常的是一些简单指令，这些指令仅占指令系统中指令总数的20%，1975年提出了精简指令系统，简称RISC。冯·诺依曼型计算机是采用存储程序方式进行工作。研制中的第五代计算机，是一种智能计算机，具有自动识别自然语言、图形、图像有能力，具有理解和推理能力，具有知识获取、知识更新能力。研制朝两个方向努力：①创建非冯·诺依曼式语言，LISP、PROLOG、F.P.；②创建以人脑神经系统处理信息的原理为基础的非冯·诺依曼式的计算机模型，生物计算机、光子计算机、量子计算机。1.2计算机对现代社会的影响1.2.1计算机应用概述1、科学计算：利用计算机解决科学研究和工程技术中所提出的复杂的数学问题。2、数据处理：利用计算机对所获取的信息进行记录、整理、加工、存储和传输等。3、人工智能：利用计算机来模仿人类的智力活动。4、自动控制：利用计算机对动态的过程进行控制、指挥和协调。5、计算机辅助设计和制造：利用计算机来辅助工程师们设计和制造产品。1.2.2由信息高速公路热引发的全球信息化浪潮在现代，能源、材料与信息是社会发展的三大支柱。以蒸汽机为中心的动力革命，使人类的体力劳动大大得到了解放；以电子信息技术为先导、以计算机和现代通信产业为代表的信息革命使人类的脑力劳动得到解放。社会发展到每一阶段，都需要有相应的基础设施作支持。在农业社会，田地是社会的基础设施；19世纪进行的工业革命时代，很多国家通过建设高速公路和铁路等交通运输方面的基础设施取得了经济飞速发展；而在信息化时代，信息高速公路就自然成为国家重要的基础设施。1993年美国国家信息基础设施计划提出了一个具有大容量、高速度的电子数据传递系统。该系统由通信网络、信息设备、信息资源和信息环境组成。语言是交流的工具，人与人交流要用语言，其它动物之间交流也有特定的动物的语言，人与计算机交流就要用到一些符号，这些符号的集合形成了计算机的语言。计算机语言有一个发展过程,从机器语言开始,然后是汇编语言,现在则使用高级语言.机器语言和汇编语言属于低级语言,计算机容易懂,但人理解起来困难.高级语言人比较容易理解,因此使得计算机得以普及,当然这是指60年代.实际上,随着应用软件的发展,现在人们连语言也不用学了,也可以使用计算机,而且使用的很好.当然,高级语言,人虽然容易懂,但计算机又不懂,因此需要翻译.所以高级语言都提供了编译系统或解释系统或集成的开发系统,对高级语言进行翻译,使得计算机能够识别并运行程序.高级语言还在发展,比如面向对象的语言,可视化的语言,网络开发语言等.机器语言和汇编语言也可以称为低级语言.不要认为有了高级语言,低级语言就可以不用了.恰恰相反,在有些领域,低级语言更有用武之处,如控制领域,电子信息领域.因为这些领域对语言运行的速度和效率更感兴趣,这正是低级语言的特点.上述语言都称为形式化的语言,与之相对应的是自然语言,也就是人使用的语言.人与计算机之间能否通过自然语言交流呢?这个恐怕很难.因为按照现在计算机的原理,计算机只有执行程序才能够工作,语言就是用于编出程序来,指挥计算机的工作,没有程序,计算机就不能工作.除非在人与计算机交流时,计算机能把人的语言翻译成程序,否则,人与计算机之间永远也不能实现用自然语言进行交流.而目前这是不太可能的.要么就是改变现在计算机的结构,改变现在计算机的运行模式,那样的话,计算机就要真正的实现更新换代了.第1课认识PASCAL语言请参阅《全国信息学奥林匹克联赛培训教程（一）》P87第5章程序设计语言5.1程序设计语言基础5.1.1程序设计语言的组成PASCAL语言是一种高级语言。让我们先来看一个PASCAL程序，通过这个程序了解PASCAL的规则。例L1_1已知半径，求圆周长和面积的程序PROGRAMcircle(input,output);(*第1行：程序首部*){已知半径求圆周长和面积}(*第2行：注释*)CONST(*第3行：常量说明*)PI=3.14159;VAR(*第5行：变量说明*)r,l,s:real;BEGIN(*第7行：语句部分*)read(r);(*第8行：输入语句*)l:=2*PI*r;(*第9行：赋值语句*)s:=PI*r*r;write(r,l,s);(*第11行：输出语句*)END.(*第12行：语句部分以END.结束*)程序的第一行为程序首部，每个PASCAL程序都必须以PROGRAM开头；circle是本程序的名字，每个程序的名字可以不同；圆括号里的内容称为程序的参数，程序参数指明程序与外部联系的文件名，input是标准输入文件，例如键盘打字机，output是标准输出文件，指屏幕显示器或打印机，为了读入数据和输出结果，必须写上文件参数input和output。从第三行到最后一行为程序的分程序。分程序一般由说明部分和语句部分构成。说明部分可以包括多种类型的说明。此例包括以CONST开始的常量说明和以VAR开始的变量说明，常量说明必须以CONST开始，变量说明必须以VAR开始。语句部分必须以BEGIN开始，以END.结束，特别注意其中的小圆点（.）不可缺少。中间是一些用分号分开的语句。一个PASCAL程序由程序首部和分程序组成，分程序通常由说明部分和语句部分组成（在特殊情况下可以没有说明部分）。PROGRAMcircle(input,output);CONSTPI=3.14159;VARr,l,s:real;BEGINread(r);l:=2*PI*r;s:=PI*r*r;write(r,l,s);END.上例的第二行，大括号{}中的内容，称为注释。被小括号及星号（**）括起来的内容也是注释。注释除了给人看，以增加程序的可读性外，对编译和运行都不起作用，一个程序可以包含多个出现在不同地方的注释，也可以没有注释。程序的书写格式：1、PROGRAM写在最左边顶格；2、注释的大括号{、和CONST、VAR、BEGIN、END等语句上下对齐，且它们比PROGRAM向右移两个字符；3、各个语句和程序语句也是上下对齐，它们比第2点中的各语句又向右移两个字符；4、使用大写字母的语句：PROGRAM、CONST、VAR、BEGIN、END；5、使用大写字母的标识符：常量标识符。例L0_001输入三角形底边和高，求该三角形的面积。写出程序。第二课PASCAL的数据类型、标识符、表达式、语句PASCAL的数据类型数据对于一门程序语言是非常重要的，数据的一个非常重要的特征就是它的类型。PASCAL规定：程序中出现的变量必须先说明才能使用。PASCAL的标准数据类型数据类型类型标识符适用的数据举例实型real有小数表示法和指数表示法（科学表示法）1.25，132.67，0.0025，-1.561.3267e+2（=1.3267×102=132.67）整型integer包括正、负整数和零25，-32，0字符型char单个的字符‘A’，’b’，’C’，’0’，’4’，’+’布尔型boolean只有现个值，即true（真）和false（假）1、实型（real）实型是最常用的数据类型。在PASCAL，实数有两种表示方法：小数表示法和指数表示法（或称科学表示法）。1.25，132.67，0.0025，-1.56，0.0，100.0以科学表示法表示这些数，可以写成1.25e0，1.3267e+2，2.5e-3，-1.56e0，0e0，1e2在科学表示法中，e后的数字代表10的幂。上列各数可以解释成：1.25e0=1.25×100=1.25，1.3267e+2=1.3267×102=132.67，2.5e-3=2.5×10-3=0.0025，-1.56e0=-1.56×100=-1.56，0e0=0×100=0.0，1e2=1×102=100.02、整型（integer）整型数包括正、负整数和零。例如：25，-32，0。在整数中不得包括不数点（.）。3、字符型（char）字符型数是括在两个单引号中的一个字符。例如：‘A’，’b’，’C’，’0’，’4’，’+’，’*’，……‘’代表空字符‘’’’代表字符’‘abc’不是字符型数，因为单引号中只能有一个字符。所有字符都有一个序号与之对应。如‘0’对应48，‘1’对应49，‘A’对应65，‘B’对应66。与字符有关的几个函数函数功能举例ord()返回与字符对应的序号ord(‘A’)=65chr()返回与数字对应的字符chr(65)=’A’pred()返回前一字符pred(‘B’)=Asucc()返回后一字符succ(‘A’)=B用函数可取得对应的序号，用4、布尔型（boolean）布尔类型的值只有两个：false（假）和true（真）。且false的序号为0，true的序号为1。用于布尔量的运算有布尔运算（或称逻辑运算），它们是：AND（与），OR（或），NOT（非），基本运算规则如下：运算结果0AND0假AND假0false假0AND1假AND真0false假1AND0真AND假0false假1AND1真AND真1true真0OR0假OR假0false假0OR1假OR真1true真1OR0真OR假1true真1OR1真OR真1true真NOT0NOT假1true真NOT1NOT真0false假例L0-002写出下列PASCAL语句的执行结果A0:=(15);A1:=(15);writeln(A0ANDA0);writeln(A0ANDA1);writeln(A1ANDA0);writeln(A1ANDA1);writeln(A0orA0);writeln(A0orA1);writeln(A1orA0);writeln(A1orA1);标识符标识符是以字母开头的字母、数字组合，用来表示常量、变量、类型、文件、函数、过程或程序的名字。x，y，max，min，sum，a15，a3b7都是合法的标识符。而5x，x-y，α，π，ε，ex10.5都是非法的标识符。标识符的长度一般不要超过8个字符。标识符的选取最好有一定意义，这样便于记忆，也增加了程序的可读性。表达式和运算符运算符+，-，*，/AND，OR，NOT，，，，，，，，，，，，，，，，，，，表达式就是将数据和运算符结合使用，组成一组有意义的运算式。在PASCAL语言中规定，表达式按下列运算优先规则计算：1、所有括起来的子表达式必须先计算，且子表达式必须从里到外计算；2、在同一子表达式中的运算符按下列次序计算：①函数；②NOT；③AND，*，/，DIV，MOD；④OR，+，-；⑤，=，=，，=，3、在同一个子表达式中，同一优先级的运算按从左到右的次序进行。下面是几个PASCAL表达式的例子：例L0_003数学表达式PASCAL