《信息学奥赛讲义》PPT课件

信息学奥赛讲义,基础篇,信息学奥赛简介,青少年信息学（计算机）奥林匹克竞赛（早期称为青少年计算机程序设计竞赛）是旨在广大青少年中普及计算机教育，推广计算机应用的一项学科性竞赛活动。全国从1984年开始举办全国性竞赛。而自从1989年我国参加第一届国际信息学奥林匹克（InternationalOlympiadinInformatics,简称IOI）以来，全国青少年计算机程序设计竞赛也更名为全国青少年信息学（计算机）奥林匹克（NationalOlympiadinInformatics,简称NOIP）。与此相应，各省青少年计算机竞赛更名为各省青少年信息学奥林匹克竞赛。从而形成了从省全国国际相衔接的系列性活动。全国信息学奥林匹克竞赛活动担负着选拔优秀学生参加国际学科奥林匹克竞赛任务，它是经国家教委批准，中国科协具体领导，由中国计算机学会主办的。,联赛命题宗旨,全国青少年信息学奥林匹克联赛（NOIP）是一项面向全国青少年的信息学竞赛和普及活动，旨在向那些在中学阶段学习的青少年普及计算机科学知识；给学校的信息技术教育课程提供动力和新的思路；给那些有才华的学生提供相互交流和学习的机会；通过竞赛和相关的活动培养和选拔优秀的计算机人才。竞赛的目的是为了在更高层次上推动普及。本竞赛及其相关活动遵循开放性原则，任何有条件和有兴趣的学校和个人，都可以在业余时间自愿参加。本活动不和现行的学校教学相冲突，也不列入教学计划，是课外性质的因材施教活动。参加者可为初高中学生或其他中等专业学校的青少年。普及的内容涉及计算机的基本组成；计算机工作的基本原理；计算机程序设计的基本方法；至少一门高级程序设计语言；程序设计中常用的数据结构。普及的重点是根据中学生的特点，培养学生学习计算机的兴趣，使得他们对信息技术的一些本质和核心的东西有更多的了解，提高他们创造性地运用程序设计知识解决实际问题的能力。对学生的能力培养注重想象力与创造力；对问题的理解和分析能力；数学能力和逻辑思维能力；对客观问题和主观思维的口头和书面表达能力；人文精神。包括与人的沟通和理解能力，团队精神与合作能力，恒心和毅力，审美能力等。,竞赛形式和成绩评定联赛分两个年龄组：初中组和高中组。每组竞赛分两轮：初试和复试。初试形式为笔试，侧重考察学生的计算机基础知识和编程的基本能力，并对知识面的广度进行测试。程序设计的描述语言采用Pascal或Basic。各省市初试成绩在本赛区前百分之十五的学生进入复赛，其分数不计入复赛的成绩。初赛时间为10月的最后一个星期六下午2:30-4:30举行。复试形式为上机，侧重考察学生对问题的分析理解能力，数学抽象能力，驾驭编程语言的能力和编程技巧、想象力和创造性等。程序设计语言可采用Pascal、Basic、C/C+或Java。各省市竞赛的等第奖在复试的优胜者中产生。时间为3小时。只进行一试，约在当年的11月的最后一个周六进行。,竞赛形式和成绩评定,试题形式每次联赛的试题分四组：初中组初试赛题；初中组复试赛题；高中组初试赛题；高中组复试赛题。其中，初中组初试赛题和高中组初试赛题类型相同，初中组复试赛题和高中组复试赛题类型相同，但初中组和高中组的题目不完全相同，高中组难度略高；以体现年龄特点和层次要求。初试：初试全部为笔试，满分100分。试题由四部分组成：1、选择题：共20题，每题15分，共30分。每题有5个备选方案；前10个题为单选题门每题有且只有一个正确答案），后10题为复选题（即每题有1至5个正确答案，只有全部选对才得分）。试题内容包括计算机基本组成与原理、计算机基本操作、信息科技与人类社会发展的关系等等。2、问题求解题：共2题，每题5分，共10分。试题给出一个叙述较为简单的问题，要求学生对问题进行分析，找到一个合适的算法，并推算出问题的解。答案以字符串方式给出，考生给出的答案与标准答案的字符串相同，则得分；否则不得分。3、程序阅读理解题：共4题，每题8分，共32分。题目给出一段程序（没有关于程序功能的说明），有时也会给出程序的输入，要求考生通过阅读理解该段程序给出程序的输出。输出以字符串的形式给出，如果与标准答案一致，则得分；否则不得分。4、程序完善题：共2题，每题14分，共28分。题目给出一段关于程序功能的文字说明，然后给出一段程序代码，在代码中略去了若干个语句并在这些位置给出空格，要求考生根据程序的功能说明和代码的上下文，填出被略去的语句。填对的，则得分；否则不得分。复试：复试的题型和形式向全国信息学奥赛（NOI）靠拢，全部为上机编程题，但难度略低。复试为决出竞赛成绩的最后一个环节。题目包括4道题，每题100分，共计400分。难度有易有难，既考虑普及面，又考虑选拔的梯度要求。每一道试题包括：题目、问题描述、样例说明（输入、输出及必要的说明）。测试时，测试程序为每道题提供了十组测试数据，考生程序每答对一组得10分；累计分即为该道题的得分。,试题形式,考试内容主要包括：计算机发展史、计算机组成、计算机基本原理、计算机程序设计、计算机日常应用等。要求考生掌握至少一门高级程序设计语言（详见竞赛大纲）。为了保持竞赛内容的相对连续性，试题涵盖的知识点和题型至少6O应出现在普及类的参考书目中，其余内容可能超出该范围。为了考核学生的基础知识、综合应用能力，激发学生的求知欲和创新思维，体现“与时俱进”的特点，竞赛题型在保持大纲相对稳定、优秀学生可能接受和理解的基础上，按照下述趋势适当变化1、增大与课内知识结合的紧密度；2、增大解题方法的多样性和灵活程度；3、增大开放性试题的比例。,试题的知识范围,计算机基础知识,计算机的诞生和发展计算机的特点计算机在现代社会中应用计算机的基本组成及其相互联系计算机的工作原理计算机中的数的表示计算机信息安全基础知识计算机软件知识,实例1,1、美籍匈牙利数学家冯诺依曼对计算机科学发展所做出的贡献是（）。提出理想计算机的数学模型，成为计算机科学的理论基础。是世界上第一个编写计算机程序的人。提出存储程序工作原理，并设计出第一台具有存储程序功能的计算机EDVAC。采用集成电路作为计算机的主要功能部件。指出计算机性能将以每两年翻一番的速度向前发展。（第十届全国青少年信息学奥林匹克联赛初赛试题普及组Pascal语言）,2、(2004)10+(32)16的结果是（）。(2036)10B.(2054)16C.(4006)10D.(100000000110)2E.(2036)16（第十届全国青少年信息学奥林匹克联赛初赛试题普及组Pascal语言）,c,c,实例2,3、图灵(AlanTuring)是()。A)美国人B)英国人C)德国人D)匈牙利人E)法国人（第九届全国青少年信息学奥林匹克联赛初赛试题普及组Pascal语言）,4、第一个给计算机写程序的人是()。AlanMathisonTuringAdaLovelaceJohnvonNeumannJohnMcCarthyEdsgerWybeDijkstra（第九届全国青少年信息学奥林匹克联赛初赛试题普及组Pascal语言）,B,B,是英国著名诗人拜伦的女儿,与计算机相关的几个重要人物,艾伦图灵（AlanTuring）英国科学家，他是计算机人工智能技术的鼻祖。1937年他提出了能思考的计算机图灵机的概念，推进了计算机理论的发展。图灵机模型是一种抽象计算模型，用来精确定义可计算函数，是实现机器人的最基本的一个理论模型。1950年，艾伦图灵发表题为计算机能思考吗的论文，设计了著名的图灵测验，解决了如何判定机器人是否具有同人类相等的智力的问题。,冯诺依曼（JohnVonNeumann）1945年，他写了一篇题为关于离散变量自动电子计算机的草案的论文，第一次提出了在数字计算机内部的存储器中存放程序的概念。这成为所有现代计算机的基础理论，被称为“冯诺依曼结构”。如今，各式各样的电脑无论看起来差别多大，实质上绝大多数是属于冯诺依曼结构的。,与计算机相关的几个重要人物,高登摩尔（GordonMoore）“每过18个月，计算机芯片依赖的集成电路由于内部晶体管数量的几何级数的增长，而使性能几乎提高一倍，同时集成电路的价格也恰好减少为原来的一半。”这就是计算机界著名的摩尔定律，他的发明人就是高登摩尔。1968年他与罗伯特诺伊斯一起率领一群工程师创建了一家叫集成电子的公司，简称“Intel”，这就是当今名震世界的英特尔公司。,法国人帕斯卡于17世纪制造出的一种机械式加法机，是世界上第一台机械式计算机。算盘是人类最早的手动计算工具，机械式计算机是在此之后出现的一种用机械技术来实现数学运算的计算工具。,CPU的发展历史,CPU(CentralProcessingUnit)，被称呼为中心处理器或者Microprocessor微处理器。CPU是计算机的核心，其重要性好比心脏对于人一样。实际上，处理器的作用和大脑更相似，因为它负责处理、运算计算机内部的所有数据，而主板芯片组则更像是心脏，它控制着数据的交换。CPU的种类决定了你使用的操作系统和相应的软件，CPU的速度决定了你的计算机有多强大，当然越快、越新的CPU会花掉你更多的钱。CPU从最初发展至今已经有二十多年的历史了，这期间，按照其处理信息的字长，CPU可以分为：四位微处理器、八位微处理器、十六位微处理器、三十二位微处理器以及六十四位微处理器等等。,CPU的发展历史,1978年6月，Intel推出4.77MHz的8086微处理器，标志着第三代微处理器问世。它采用16位寄存器、16位数据总线和29000个3微米技术的晶体管,1985年10月，Intel推出16MHz80386DX微处理器(最高33MHz主频)，可以直接访问4G字节的内存,并具有异常处理机制;虚拟86模式可以同时模拟多个8086处理器来加强多任务处理能力。80386的广泛应用,将PC机从16位时代带入了32位时代。此外它还具有比80286更多的指令集。发布时，80386的最快速版本的主频为20MHz，具备6.0MIPs，包含275,000个晶体管。,1993年3月22日：全面超越486的新一代586CPU问世，为了摆脱486时代微处理器名称混乱的困扰，英特尔公司把自己的新一代产品命名为Pentium(奔腾)以区别AMD和Cyrix的产品。,2000年11月21日，Intel在全球同步发布了其最新一代的微处理器Pentium4（奔腾4）。Pentium4系统总线仅为100Mhz，并且也是64位数据宽度,CPU的主要性能指标,主频即CPU的时钟频率(CPUClockSpeed)，这是我们最关心的，我们所说的3.2GHz、2.0GHz等就是指它，一般说来，主频越高，CPU的速度就越快，整机的就越高。FSB前端总线即CPU的外部时钟频率，由电脑主板提供，以前一般是133MHz，目前Intel公司最新的芯片组i925XE芯片组使用1066MHz的FSB。内部缓存（L1Cache）封闭在CPU芯片内部的高速缓存，用于暂时存储CPU运算时的部分指令和数据，存取速度与CPU主频一致，L1缓存的容量单位一般为KB。L1缓存越大，CPU工作时与存取速度较慢的L2缓存和内存间交换数据的次数越少，相对电脑的运算速度可以提高。外部缓存（L2Cache）以CPU主频的一半速度运行,CPU的主要性能指标,CPU(中央处理器)是电脑的核心，作为系统的心脏，CPU的档次决定了整台机器的处理水平，其性能的高低直接影响全局。电脑处理数据的能力和速度主要取决于CPU。通常用位长和主频评价CPU的能力和速度，如P300CPU能处理位长为32位的二进制数据，主频为300MHz。1、主频、倍频、外频：主频也就是CPU的时钟频率，英文全称是CPUClockSpeed，简单地说也就是CPU运算时的工作频率。一般说来，主频越高，一个时钟周期内完成的指令数也越多，当然CPU的速度也就越快了。不过由于各种各样的CPU它们的内部结构也不尽相同，所以并非所有的时钟频率相同的CPU的性能都一样。至于外频就是系统总线的工作频率；而倍频则是指CPU外频与主频相差的倍数。三者是有十分密切的关系的：主频=外频倍频。,存储器及分类,一般我们存放在外存（磁盘或各种存储介质）上的资料都要通过内存，再进入CPU进行处理。所以与内存之间的通道内存总线的速度对整个系统性能就显得很重要了，由于内存和CPU之间的运行速度或多或少会有差异，因此便出现了二级缓存，来协调两者之间的差异，而内存总线速度就是指CPU与二级（L2）高速缓存和内存之间的通信速度。,内存储器：简称内存，用于存放当前待处理的信息和常用信息的半导体芯片。容量不大，但存取迅速。内存包括RAM、ROM和Cache。1、RAM：RAM(随机存取存储器)是电脑的主存储器，人们习惯将RAM称为内存。RAM的最大特点是关机或断电数据便会丢失。内存越大的电脑，能同时处理的信息量越大。我们用刷新时间评价RAM的性能，单位为ns(纳秒)，刷新时间越小存取速度越快。586电脑常用RAM有EDORAM和SDRAM，存储器芯片安装在手指宽的条形电路板上，称之为内存条。内存条安装在主板上的内存条插槽中。按内存条与主板的连接方式有30线、72线和168线之分。目前装机常用168线、刷新时间为10ns、容量为32M(或64M)的SDRAM内存条。2、Cache：Cache(高速缓冲存储器)是位于CPU与主内存间的一种容量较小但速度很高的存储器。由于CPU的速度远高于主内存，CPU直接从内存中存取数据要等待一定时间周期，Cache中保存着CPU刚用过或循环使用的一部分数据，当CPU再次使用该部分数据时可从Cache中直接调用，这样就减少了CPU的等待时间，提高了系统的效率。Cache又分为一级Cache(L1Cache)和二级Cache(L2Cache)，L1Cache集成在CPU内部，L2Cache一般是焊在主板上，常见主板上焊有256KB或512KBL2Cache。3、ROM：ROM(只读存储器)是一种存储计算机指令和数据的半导体芯片，但只能从其中读出数据而不能写入数据，关机或断电后ROM的数据不会丢失。生产厂商把一些重要的不允许用户更改的信息和程序存放在ROM中，例如存放在主板和显示卡ROM中的BIOS程序。,各存储器速度比较,综上所述速度从快到慢次序为：寄存器（与CPU主频相同）高速缓存（CACHE，内存的一种）内存（RAM和ROM）硬盘光盘软盘,例：CPU访问内存的速度比访问下列哪个存储设备要慢（）A）寄存器B）硬盘C）软盘D）磁带E）光盘（第九届初赛试题）,数制转换,由于计算机内采用的是二进制而实际生活中采用十进制所以数制转换是常见的题目,十进制Decimalsystem(逢十进一)码：0，1，2，3，4，5，6，7，8，9基：10权：表达式：,二进制Binarysystem(逢二进一)码：0，1基：2权：表达式：,十六进制Hexadecimal码：0，1，2，3，4，5，6，7，8，9，A,B,C,D,E,F基：16权：表达式：,N进制码：0，1，2，3，4，5，6，-，（N-1）基：N权：表达式：,通常用数字右下角的角标来表示数制，以防混淆运算规则：满k进一，借一当k设数字N的k进制表示形式为则N的具体数值（含义）为数制不同，表达形式不同，但含义不变，如基数越大，表示形式越精练，但符号种类也越多,数制转换,非十进制数转换为十进制数十进制数转换为非十进制数非十进制数之间的转换,非十进制数转换为十进制数方法：多项式展开r进制的数，转换为十进制数：例如：,数制转换（1）,十进制数转换为非十进制数整数部分：除基取余，逆取例如：(53)10转换为二进制的过程如下：,数制转换（2）,十进制数转换为非十进制数小数部分：乘基取整，顺取例如：(0.6875)10转换为二进制的过程如下，二进制表示形式为0.1011,数制转换（3）,非十进制数之间的转换一般方法：先将r进制数转换为十进制数，再将十进制数转换为k进制数特殊情况二八进制二-十六进制,数制转换（4）,例题,计算机内数的表示,原码，反码，补码一字节数据可表示的范围是0-255，那么负数又怎么表示呢？原来在计算机中是这样规定的，用一个数的最高一位表示正负，0为正，1为负.如0111,1111转换为十进制为127，1111,1111为-127，由此我们知一字节的范围为-127-127，其他字节的范围类推.上面讲的都是原码表示法，可在计算机中的数据都是以补码存放的，只有这样才能减轻cpu的负担.提到补码，就不得不提反码了.计算机中是这样规定反码的，如果是正数，则按原码形式不变，如127仍为0111,1111；而如果为负数则，第一位为1，其他各位取反（即0变为1，1变为0），如原码-127（1111,1111），表示为1000,0000.补码同上，如果是正数，则按原码形式不变，如127仍为0111,1111；如果为负数则除第一位为1外，其他各位取反加1，如-127，先取反为1000,0000，然后加1，为1000,0001.但1000,0000比较特殊，用它来表示-128，由此我们知补码可表示的范围是-128-127。大家必须熟练掌握这三种码之间的相互转换如已知补码写出反码等。,原码，反码，补码举例,1、X补码=10011000，其原码为（）。011001111111010001110011001100101第七届NOIP提高组初赛试题（符号不变，其余各位取反加1）,2、已知x=（0.1011010）2，则X/2补=（）20.1011101111101100.01011010.100110第八届NOIP提高组试题分析：这是一个正小数，可以把第一0看成是符号位，除以2相当于整个右移，即为0.0101101而正数补码与原码相同所以正确答案为C,计算机内的编码,ASCII码(美国标准信息交换码)ASCII码就是字符在计算机内的编码。如果计算机采用的编码方式是ASCII的话，一个字符在计算机内实际上就是以它的ASCII码值储存的。例如，A的ASCII码是65。那么，计算机存了一个字符A，实际上是存了一个数字65。在计算机内两者没区别，A就是65，65就是A，,汉字及全角英、数字符编码,汉字在计算机内的编码通常用输入码（外码）、机内码、字模码描述。机内码中用于汉字的存储、处理交换等操作的计算机内部代码。一个汉字机内码通常用两个字节表示，且这两个字节的最高位均为1，以区别英文字符的ASCII码；输入码是用来输入汉字的编码。拼音、字形码、五笔字型、区位码等字模码是汉字的输出编码，计算机内的字库中存放的就是字模码；机内码与汉字字符是一一对应机内码与输入码是一对多关系，表明一个汉字的输入方法有多种；机内码与字模码也是一对多，表明一个汉字的输出形式有多种，即有不同的字体输出。,(A)国标码,国标标中所有符号按区位编排：94*94115区：西文字母、数字、图形符号，用户自定义的专用符号，如1015空，由用户自定义。16区55区：一级汉字，按拼音排序；56区87区：二级汉字，接部首排序，国标码用两个字节的十六进制表示，如国际码“啊”，3021H,（B）汉字机内码,以GB231280标准为基础，长度两个字节编码每个字节的低七位表示汉字信息，把最高位变成1，即成汉字内码例：“啊”国标码是3021H，其机内码B0A1H（十六进制表示）,第1字节第2字节0011000000100001高位置11011000010100001B0A1,特点：能与ASCII严格区分，ASCII码7F代码字长短与国标码有简单一一对应关系,(C)机外码,区位码：由汉字或字符的区号和位号所组成，用十进制表示；（第1字节为区号，第2字节为位号）无重码不好记代码短与国标码有简单的对应关系区位码与国标码、机内码关系：区位号（十六进制表示）+20H国标码（因为国标码从21H开始编）国标码+80H机内码，所以机内码总大于A1H例：“爱”的区位码为1614，国标码、机内码？1614的十六进制=100E分别+2020H=302E（国标码）302E+8080H=B0AE（机内码）,求：4687区位码对应机内码,CEF7,国标码：也可作汉字输入，特点同上首尾码：按汉字形状编码。代码短，两键；重码多；不易记拼音码不需记忆；重码多，代码有时长五笔字型码易记，重码少汉字键盘一键一字；键盘大联机手写输入不用学、不用记、操作方便，但识别困难、成本高语音输入进行语音识别，A/D转换,(C)机外码,(D)汉字编码与汉字点阵字模,汉字点阵字模：用二进制的1或0所表示出的汉字的点阵模型。有：简易型1616；普及型2424提高型3232；精密型4848汉字库:存储汉字点阵字模的存储器存在磁盘的汉字库软字库，用时调入内存存在ROM的汉字库硬字库（汉卡），不占内存汉字点阵存储方式一般为16点阵、24点阵,汉字库中寻找汉字字模时采用地址码汉字处理过程输入码机内码地址码字形码。全角的英、数字符相当于一个汉字，半角的一个英、数字符与全角的它们码长度不同，并且二码间无关系,实例,1、2KB的内存能存储（A）个汉字的机内码10245162048218,定点数和浮点数,1、定点数：在计算机中一个数的小数点的位置是固定的（1）纯小数表示法符号位.数值部分（2）整数表示法符号位数值部分.2、浮点数：在计算机中一个数的小数点的位置是浮动的。一个浮点数的表示分为阶码和尾数两个部分：NM2e其中e是一个二进制整数，M是二进制小数，这里称e为数N的阶码，M称为数N的尾数，M表示了数N的全部有效数字，阶码e指明了小数点的位置。,定点数和浮点数,计算机系统的发展过程中，曾经提出过多种方法表达实数。典型的比如相对于浮点数的定点数（FixedPointNumber）。在这种表达方式中，小数点固定的位于实数所有数字中间的某个位置。货币的表达就可以使用这种方式，比如99.00或者00.99可以用于表达具有四位精度（Precision），小数点后有两位的货币值。由于小数点位置固定，所以可以直接用四位数值来表达相应的数值。SQL中的NUMBER数据类型就是利用定点数来定义的。还有一种提议的表达方式为有理数表达方式，即用两个整数的比值来表达实数。定点数表达法的缺点在于其形式过于僵硬，固定的小数点位置决定了固定位数的整数部分和小数部分，不利于同时表达特别大的数或者特别小的数。最终，绝大多数现代的计算机系统采纳了所谓的浮点数表达方式。这种表达方式利用科学计数法来表达实数，即用一个尾数（Mantissa），一个基数（Base），一个指数（Exponent）以及一个表示正负的符号来表达实数。比如123.45用十进制科学计数法可以表达为1.2345102，其中1.2345为尾数，10为基数，2为指数。浮点数利用指数达到了浮动小数点的效果，从而可以灵活地表达更大范围的实数。提示:尾数有时也称为有效数字（Significand）。尾数实际上是有效数字的非正式说法。,在IEEE标准中，浮点数是将特定长度的连续字节的所有二进制位分割为特定宽度的符号域，指数域和尾数域三个域，其中保存的值分别用于表示给定二进制浮点数中的符号，指数和尾数。这样，通过尾数和可以调节的指数（所以称为浮点）就可以表达给定的数值了。具体的格式参见下面的图例：,在上面的图例中，第一个域为符号域。其中0表示数值为正数，而1则表示负数。第二个域为指数域，对应于我们之前介绍的二进制科学计数法中的指数部分。其中单精度数为8位，双精度数为11位。以单精度数为例，8位的指数为可以表达0到255之间的255个指数值。但是，指数可以为正数，也可以为负数。为了处理负指数的情况，实际的指数值按要求需要加上一个偏差（Bias）值作为保存在指数域中的值，单精度数的偏差值为127，而双精度数的偏差值为1023。比如，单精度的实际指数值0在指数域中将保存为127；而保存在指数域中的64则表示实际的指数值-63。偏差的引入使得对于单精度数，实际可以表达的指数值的范围就变成-127到128之间（包含两端）。我们不久还将看到，实际的指数值-127（保存为全0）以及+128（保存为全1）保留用作特殊值的处理。这样，实际可以表达的有效指数范围就在-127和127之间。在本文中，最小指数和最大指数分别用emin和emax来表达。图例中的第三个域为尾数域，其中单精度数为23位长，双精度数为52位长。除了我们将要讲到的某些特殊值外，IEEE标准要求浮点数必须是规范的。这意味着尾数的小数点左侧必须为1，因此我们在保存尾数的时候，可以省略小数点前面这个1，从而腾出一个二进制位来保存更多的尾数。这样我们实际上用23位长的尾数域表达了24位的尾数。比如对于单精度数而言，二进制的1001.101（对应于十进制的9.625）可以表达为1.00110123，所以实际保存在尾数域中的值为00110100000000000000000，即去掉小数点左侧的1，并用0在右侧补齐。值得注意