2017-2018信息学联赛初赛辅导(中国计算机学会)120172018NOIP初赛速成辅导(中国计算机学会出版)一、一、一、一、 计算机的发展与应用计算机的发展与应用计算机的发展与应用计算机的发展与应用二、计算机组成与工作原理二、计算机组成与工作原理二、计算机组成与工作原理二、计算机组成与工作原理 和信息的表示与存储和信息的表示与存储和信息的表示与存储和信息的表示与存储 三、多媒体应用三、多媒体应用三、多媒体应用三、多媒体应用 四、计算机网络使用基础四、计算机网络使用基础四、计算机网络使用基础四、计算机网络使用基础 五、程序设计语言基础五、程序设计语言基础五、程序设计语言基础五、程序设计语言基础 六、程序的阅读分析六、程序的阅读分析六、程序的阅读分析六、程序的阅读分析220172018NOIP初赛速成辅导(中国计算机学会出版)计算机的发展历经了哪几个阶段；计算机的发展历经了哪几个阶段；按按照照功功能能和和规规模模，可可将将计计算算机机分分成成哪哪几几大大类，它们各自的分工是什么；类，它们各自的分工是什么；武装计算机的软件系统包括了哪些东西；武装计算机的软件系统包括了哪些东西；计计算算机机的的发发展展怎怎样样促促使使人人类类走走向向丰丰富富多多彩彩的信息社会；的信息社会；用户在使用计算机时应该遵守哪些道德规用户在使用计算机时应该遵守哪些道德规范；范；320172018NOIP初赛速成辅导(中国计算机学会出版)计算机发展史上的里程碑计算机发展史上的里程碑计算机存储程计算机存储程序的工作原理序的工作原理美籍匈牙利数学家冯美籍匈牙利数学家冯 诺依曼（诺依曼（vonNeumamlvonNeumaml）在在19461946年提出的，其思想年提出的，其思想是，是，在计算机中设置存储器，将符号化的计算步骤存放在存储器中，然在计算机中设置存储器，将符号化的计算步骤存放在存储器中，然在计算机中设置存储器，将符号化的计算步骤存放在存储器中，然在计算机中设置存储器，将符号化的计算步骤存放在存储器中，然后依次取出存储的内容，由一个被称之为控制器的部件进行译码，译码后依次取出存储的内容，由一个被称之为控制器的部件进行译码，译码后依次取出存储的内容，由一个被称之为控制器的部件进行译码，译码后依次取出存储的内容，由一个被称之为控制器的部件进行译码，译码结果在一个被称为运算器的部件中进行计算，从而实现计算机工作的自结果在一个被称为运算器的部件中进行计算，从而实现计算机工作的自结果在一个被称为运算器的部件中进行计算，从而实现计算机工作的自结果在一个被称为运算器的部件中进行计算，从而实现计算机工作的自动化（运算器和控制器统称为动化（运算器和控制器统称为动化（运算器和控制器统称为动化（运算器和控制器统称为CPUCPU）。）。）。）。冯冯 诺依曼依据此原理设计出一诺依曼依据此原理设计出一个完整的计算机雏形，并确定了计算机的五大组成部分和基本的工作方个完整的计算机雏形，并确定了计算机的五大组成部分和基本的工作方法。法。420172018NOIP初赛速成辅导(中国计算机学会出版)第四代第四代 VISI大规模集成电路 CISC复杂指令系统计算机 RCSC精简指令系统计算机非冯诺依曼式语言：lisp、prologo、f.p第五代第五代NC网络计算机（将整个网络看成一个巨大的磁盘驱动器，数据和文件存储在服务器）非冯诺依曼式的计算机模型（以人脑神经系统处理信息的原理为基础）：生物计算机、光子计算机、量子计算机520172018NOIP初赛速成辅导(中国计算机学会出版)裸机裸机裸机裸机系统软件系统软件系统软件系统软件应用软件应用软件应用软件应用软件用户用户用户用户620172018NOIP初赛速成辅导(中国计算机学会出版)操作系统是计算机系统中的一种系统软件，它操作系统是计算机系统中的一种系统软件，它能对计算机系统中的软件和硬件资源进行有效地能对计算机系统中的软件和硬件资源进行有效地管理和控制，合理地组织计算机的工作流程，为管理和控制，合理地组织计算机的工作流程，为用户提供一个使用计算机的工作环境。用户提供一个使用计算机的工作环境。手工操作管理程序单道批处理系统多道批处理系统分时系统实时操作系统网络操作系统 720172018NOIP初赛速成辅导(中国计算机学会出版)DOS单用户的唯一任务占用计算机上所单用户的唯一任务占用计算机上所有的硬件和软件资源，所能访问的主存地址有的硬件和软件资源，所能访问的主存地址空间太小。空间太小。Windows多作业、大内存管理、统一多作业、大内存管理、统一的图形用户界面的图形用户界面，并且发展到网络环境使，并且发展到网络环境使用用UNIX操作系统操作系统、Linux操作系统操作系统、MacintoshOS820172018NOIP初赛速成辅导(中国计算机学会出版)数据库技术的特性数据库技术的特性数据库技术的特性数据库技术的特性最小冗余最小冗余最小冗余最小冗余 数据共享数据共享数据共享数据共享数据独立性数据独立性数据独立性数据独立性安全性安全性安全性安全性 完整性完整性完整性完整性 数据库管理系统的类型数据库管理系统的类型数据库管理系统的类型数据库管理系统的类型OLTPOLTP（联机事务处理）联机事务处理）DSSDSS（决策支持系统）决策支持系统）EISEIS（行政信息系统）行政信息系统）OAOA（办公室自动化）办公室自动化）按其系统结构分为单机、按其系统结构分为单机、UnixUnix多用户、网络多用户、客户机服务器、多用户、网络多用户、客户机服务器、集中式、分布式、集中分布式等。集中式、分布式、集中分布式等。目前，世界上比较流行的数据库管目前，世界上比较流行的数据库管目前，世界上比较流行的数据库管目前，世界上比较流行的数据库管理系统（理系统（理系统（理系统（DMSDMSDMSDMS）有有有有高档数据库产品，如高档数据库产品，如InformixInformix，OracleOracle，SybaseSybase，ProgressProgress，UnifyUnify等等中、低档数据库产品，如中、低档数据库产品，如DBASEDBASE，ParadoxParadox，SuperSuperBaseBase，FoxproFoxpro，ClipperClipper，SQLBaseSQLBase，FocusFocus等；等；数数据据库库开开发发工工具具，如如AccessAccess，VisualVisualBasicBasic，UnifaceUniface，PowerPowerBuilderBuilder，Q QEDatabaseEDatabaseEditorEditor等。等。920172018NOIP初赛速成辅导(中国计算机学会出版)计算机病毒的特征计算机病毒的特征计算机病毒的特征计算机病毒的特征能够将自身复制到其他程序中。能够将自身复制到其他程序中。 不独立以文件形式存在，仅附加在别的程序上。当调不独立以文件形式存在，仅附加在别的程序上。当调用该程序运行时，此病毒则首先运行。用该程序运行时，此病毒则首先运行。防治病毒的步骤：防治病毒的步骤：防治病毒的步骤：防治病毒的步骤：不要用软盘启动机器不要用软盘启动机器 不要运行来路不明的软件不要运行来路不明的软件定期备份重要系统数据定期备份重要系统数据重要的数据盘，程序盘应写保护重要的数据盘，程序盘应写保护使用杀毒软件检查和清除病毒使用杀毒软件检查和清除病毒1020172018NOIP初赛速成辅导(中国计算机学会出版)计算机的组成和工作原理计算机的组成和工作原理1、存储程序内存；执行程序CPU2、机器指令是计算机直接识别和执行操作的命令，用其编写的程序称为机器语言程序，所有指令的集合称为指令系统。格式：操作码和地址码；类型：操作类指令和控制转移类指令3、计算机硬件系统由五个基本组成部分：运算器、控制器、存储器、输入设备、输出设备4、CPU由运算器（ALU）、数据寄存器（DR）、指令寄存器（IR）程序计数器（PC）、地址寄存器、操作控制器1120172018NOIP初赛速成辅导(中国计算机学会出版)1 1、R R进制转换为十进制进制转换为十进制进制转换为十进制进制转换为十进制基数为基数为R R的数字，只要将各位数字与它的权相乘，其积相加的数字，只要将各位数字与它的权相乘，其积相加, ,和数就和数就是十进制数是十进制数（x xp pxx0 0.x .x11xxkk）R R= =（）1010例：例： 1101101.01011101101.01012 2=12=1202021 112122 2+12+123 3十十02024 412125 512126 6+02+0211+12+12220202 3 3+12+1244=109.3125=109.3125当从当从R R进制转换到十进制时，可以把小数点作为起点，分别向左右进制转换到十进制时，可以把小数点作为起点，分别向左右两边进行，即对其整数部分和小数部分分别转换。对于二进制来说，两边进行，即对其整数部分和小数部分分别转换。对于二进制来说，只要把数位是只要把数位是1 1的那些位的权值相加，其和就是等效的十进制数。的那些位的权值相加，其和就是等效的十进制数。 进位计数制之间的转换问题进位计数制之间的转换问题1220172018NOIP初赛速成辅导(中国计算机学会出版)2 2、十进制转换为、十进制转换为、十进制转换为、十进制转换为R R进制进制进制进制 将此数分成整数与小数两部分分别转换，然后再拼接起来。将此数分成整数与小数两部分分别转换，然后再拼接起来。 进制整数转换成进制整数转换成R R进制的整数，可用十进制数连续地除以进制的整数，可用十进制数连续地除以R R，其其余数即为余数即为R R系统的各位系数。此方法称之除系统的各位系数。此方法称之除R R取余法。例如：将取余法。例如：将57571010转换为二进制数转换为二进制数十进制小数转换成十进制小数转换成R R进制时，可连续地乘以进制时，可连续地乘以R R，直到小数部分为直到小数部分为0 0，或达到所要求的精度为止（小数部分可能永不为零），得到的，或达到所要求的精度为止（小数部分可能永不为零），得到的整数即组成整数即组成R R进制的小数部分，此法称为进制的小数部分，此法称为“ “乘乘R R取整取整” ”例：将例：将0.31250.31251010转换成二进制数转换成二进制数0.31252=0.6250.6252=1.250.252=0.50.52=1.00.31252=0.6250.6252=1.250.252=0.50.52=1.01320172018NOIP初赛速成辅导(中国计算机学会出版)3 3、二、八、十六进制的相互转换、二、八、十六进制的相互转换、二、八、十六进制的相互转换、二、八、十六进制的相互转换即每位八进制数相当于三位二进制数，每位十六进制数相当即每位八进制数相当于三位二进制数，每位十六进制数相当于四位二进制数。在转换时，位组划分是以小数点为中心向于四位二进制数。在转换时，位组划分是以小数点为中心向左右两边延伸，中间的左右两边延伸，中间的0 0不能省略，两头不够时可以补不能省略，两头不够时可以补0 0。例如：将例如：将1011010.101011010.102 2转换成八进制和十六进制数转换成八进制和十六进制数 001011010.1001011010.10001011010.1001011010.102 2132.4132.48 8132.4132.401011010.10001011010.1001011010.10001011010.102 2=5=5A.8A.81616 5A.85A.8将十六进制数将十六进制数F7.28F7.28变为二进制数变为二进制数F7.28F7.28F7.28F7.281616=11110111.00101=11110111.001012 211110111.0010100011110111.00101000将八进制数将八进制数25.6325.63转换为二进制数转换为二进制数25256325.636325.638 810101.11001110101.1100112 210101.11001110101.1100111420172018NOIP初赛速成辅导(中国计算机学会出版)三、在计算机中带符号数的表示法三、在计算机中带符号数的表示法三、在计算机中带符号数的表示法三、在计算机中带符号数的表示法1 1、机器数与真值、机器数与真值、机器数与真值、机器数与真值规定在数的前面增设一位符号位，正数符号位用规定在数的前面增设一位符号位，正数符号位用“0”“0”表示，负数符号位用表示，负数符号位用“1”“1”表表示。示。为了区别原来的数与它在计算机中的表示形式，我们将已经数码化了的带符号数为了区别原来的数与它在计算机中的表示形式，我们将已经数码化了的带符号数称为机器数，而把原来的数称为机器数的真值。例如称为机器数，而把原来的数称为机器数的真值。例如N N1 1=+1001100=+1001100、N N2 2=1001100=1001100为为真值，其在计算机中的表示真值，其在计算机中的表示0100110001001100和和1100110011001100为机器数。为机器数。 2 2、原码、原码、原码、原码trueformtrueform 在在用用二二进进制制原原码码表表示示的的数数中中，符符号号位位为为0 0表表示示正正数数，符符号号位位为为1 1表表示示负负数数，其其余余各各位位表表示示数数值值部部分分。这这种种表表示示法法称称为为原原码码表表示示法法。字字长长为为n n的的数数（包包括括符符号号位位）的的原码表示法可定义为原码表示法可定义为 xx原原= =若真值丨若真值丨x x丨丨1 1，其原码表示法可定义为，其原码表示法可定义为 xx原原= =例如对于例如对于8 8位二进制原码位二进制原码+0+0原原=00000000=00000000，00原原=10000000=1000000011010011101001原原=10000000(1101001)=11101001=10000000(1101001)=111010011520172018NOIP初赛速成辅导(中国计算机学会出版)3 3、补码（、补码（、补码（、补码（twotwo scomplementscomplement）即即 xx补模补模+ +xx 对于正数，对于正数， xx补补= =x x，正数的补码就是该正数本身。正数的补码就是该正数本身。 对于负数，对于负数， xx补补=2=2n n+x(mod2+x(mod2n n) )。 +0+0补补00补补00000022n1n1 补补=2=2n n22n1n1=2=2n1n1 4 4、反码、反码、反码、反码0 0nene sComplementsComplement 对于正数，它的反码表示与原码相同。即对于正数，它的反码表示与原码相同。即 xx反反=xx原原对于负数，则除符号位仍为对于负数，则除符号位仍为“1”“1”外，其余各位外，其余各位“1”“1”换成换成”0”0”，”0”0”换成换成1”1”，即得到反码，即得到反码 XX反。例如反。例如11010011101001反反=10010110=10010110。对于对于0 0，它的反码有两种表示，它的反码有两种表示:+0:+0反反=0000=0000反反=111=111当当x x为正数时，为正数时， xx反反=xx原原=xx补补= =x x；当当x x为负数时，为负数时， xx补补=2=2n n+x=(2+x=(2n n1)+x+1=x1)+x+1=x反反+1+1，即，即 xx原原除符号位外求反加除符号位外求反加1 1。若把。若把 xx补补除符号位外求反加除符号位外求反加1 1，就得到，就得到 xx原原，即即 xx补补 补补=xx原原。例如。例如x=1101001x=1101001。xx原原=11101001=11101001， xx补补=10010111,=10010111,xx补补 补补=11101001=11101001=xx原原。 1620172018NOIP初赛速成辅导(中国计算机学会出版)5 5、补码的加减法运算、补码的加减法运算、补码的加减法运算、补码的加减法运算 补码的加法运算补码的加法运算补码的加法运算补码的加法运算在计算机中进行两个带符号数的加法运算时，只要将给定的真值在计算机中进行两个带符号数的加法运算时，只要将给定的真值用补码表示，就可以直接进行加法运算。在运算过程中不必判断加用补码表示，就可以直接进行加法运算。在运算过程中不必判断加数和被加数的正负，一律做加法，最后将结果转换为真值即可。数和被加数的正负，一律做加法，最后将结果转换为真值即可。补码的减法运算补码的减法运算补码的减法运算补码的减法运算 对于补码的减法运算，由于存在对于补码的减法运算，由于存在xy=x+(y)xy=x+(y)，因此因此 xyxy补补=x+(y)x+(y)补补=xx补补+yy补补( (mod2n)mod2n)其中其中 yy补补=yy补补 补。补。 1720172018NOIP初赛速成辅导(中国计算机学会出版)信息存储单位信息存储单位信息存储单位信息存储单位位（位（位（位（bitbit，缩写为缩写为缩写为缩写为b b）：度量数据的最小单位，表示一位二进制信息。度量数据的最小单位，表示一位二进制信息。字节字节字节字节( (bytebyte，缩写为缩写为缩写为缩写为B)B)：一个字节由八位二进制数字组成（一个字节由八位二进制数字组成（lbytelbyte8bit8bit）。）。字节是信息存储中最常用的基本单位。字节是信息存储中最常用的基本单位。计算机存储器（包括内存与外存）通常也是以多少字节来表示它的容量。计算机存储器（包括内存与外存）通常也是以多少字节来表示它的容量。常用的单位有：常用的单位有：KB1K=1024KB1K=1024，MB1M=1024KMB1M=1024K，GB1G=1024MGB1G=1024M字（字（字（字（wordword）：）：）：）：字是位的组合，并作为一个独立的信息单位处理。字又称字是位的组合，并作为一个独立的信息单位处理。字又称为计算机字，它的含意取决于机器的类型、字长以及使用者的要求。常用为计算机字，它的含意取决于机器的类型、字长以及使用者的要求。常用的固定字长有的固定字长有8 8位、位、1616位、位、3232位等。位等。信息单位用来描述机器内部数据格式，即数据（包括指令）在机器内的排信息单位用来描述机器内部数据格式，即数据（包括指令）在机器内的排列形式，如单字节数据，可变长数据（以字节为单位组成几种不同长度的列形式，如单字节数据，可变长数据（以字节为单位组成几种不同长度的数据格式）等。数据格式）等。机器字长：机器字长：机器字长：机器字长：在讨论信息单位时，还有一个与机器硬件指标有关的单位，在讨论信息单位时，还有一个与机器硬件指标有关的单位，这就是机器字长。机器字长一般是指参加运算的寄存器所含有的二进制数这就是机器字长。机器字长一般是指参加运算的寄存器所含有的二进制数的位数，它代表了机器的精度。机器的功能设计决定了机器的字长。一般的位数，它代表了机器的精度。机器的功能设计决定了机器的字长。一般大型机用于数值计算，为保证足够的精度，需要较长的字长，如大型机用于数值计算，为保证足够的精度，需要较长的字长，如3232位、位、6464位等。而小型机、微型机、微机一般字长为位等。而小型机、微型机、微机一般字长为1616位、位、3232位等。位等。1820172018NOIP初赛速成辅导(中国计算机学会出版)非数值信息的表示非数值信息的表示非数值信息的表示非数值信息的表示西文字符编码西文字符编码西文字符编码西文字符编码ASCIIASCII码码码码“美国信息交换标准代码美国信息交换标准代码美国信息交换标准代码美国信息交换标准代码” ”的简称。的简称。的简称。的简称。ASCIIASCII码包括码包括码包括码包括0 09 9十个数字，大小写十个数字，大小写十个数字，大小写十个数字，大小写英文字母及专用符号等英文字母及专用符号等英文字母及专用符号等英文字母及专用符号等9595种可打印字符，还有种可打印字符，还有种可打印字符，还有种可打印字符，还有3333种控制字符（如回车、换行等）。一个字种控制字符（如回车、换行等）。一个字种控制字符（如回车、换行等）。一个字种控制字符（如回车、换行等）。一个字符的符的符的符的ASCIIASCII码通常占一个字节，用七位二进制数编码组成，所以码通常占一个字节，用七位二进制数编码组成，所以码通常占一个字节，用七位二进制数编码组成，所以码通常占一个字节，用七位二进制数编码组成，所以ASCIIASCII码最多可表示码最多可表示码最多可表示码最多可表示128128个个个个不同的符号。最高位作为校验码，以便提高字符信息传输的可靠性。不同的符号。最高位作为校验码，以便提高字符信息传输的可靠性。不同的符号。最高位作为校验码，以便提高字符信息传输的可靠性。不同的符号。最高位作为校验码，以便提高字符信息传输的可靠性。数字和字母的数字和字母的数字和字母的数字和字母的ASCIIASCII码按照数字递增顺序或字典顺序排列排列，大写字母和小写字母的码按照数字递增顺序或字典顺序排列排列，大写字母和小写字母的码按照数字递增顺序或字典顺序排列排列，大写字母和小写字母的码按照数字递增顺序或字典顺序排列排列，大写字母和小写字母的ASCIIASCII码是不同的。码是不同的。码是不同的。码是不同的。EBCDICEBCDIC码码码码美国美国美国美国IBMIBM公司在它的各类机器上广泛使用的一种信息代码。一个字符的公司在它的各类机器上广泛使用的一种信息代码。一个字符的公司在它的各类机器上广泛使用的一种信息代码。一个字符的公司在它的各类机器上广泛使用的一种信息代码。一个字符的EBCDICEBCDIC码占用一个字符，用八位二进制码表示信息，最多可以表示出码占用一个字符，用八位二进制码表示信息，最多可以表示出码占用一个字符，用八位二进制码表示信息，最多可以表示出码占用一个字符，用八位二进制码表示信息，最多可以表示出256256个不同代码。个不同代码。个不同代码。个不同代码。 中文信息编码中文信息编码中文信息编码中文信息编码目前的汉字编码方案有二字节、三字节甚至四字节的。下面我们主要介绍目前的汉字编码方案有二字节、三字节甚至四字节的。下面我们主要介绍目前的汉字编码方案有二字节、三字节甚至四字节的。下面我们主要介绍目前的汉字编码方案有二字节、三字节甚至四字节的。下面我们主要介绍“ “国家标准信息国家标准信息国家标准信息国家标准信息交换用汉字编码交换用汉字编码交换用汉字编码交换用汉字编码” ”（CB2312-80CB2312-80标淮），以下简称国标码。标淮），以下简称国标码。标淮），以下简称国标码。标淮），以下简称国标码。国际码是二字节码，用二个七位二进制数编码表示一个汉字。目前国标码收人国际码是二字节码，用二个七位二进制数编码表示一个汉字。目前国标码收人国际码是二字节码，用二个七位二进制数编码表示一个汉字。目前国标码收人国际码是二字节码，用二个七位二进制数编码表示一个汉字。目前国标码收人67636763个汉字，个汉字，个汉字，个汉字，其中一级汉字（最常用）其中一级汉字（最常用）其中一级汉字（最常用）其中一级汉字（最常用）37553755个，二级汉字个，二级汉字个，二级汉字个，二级汉字30083008个，另外还包括个，另外还包括个，另外还包括个，另外还包括682682个西文字符、图符。个西文字符、图符。个西文字符、图符。个西文字符、图符。在计算机内部，汉字编码和西文编码是共存的。区分的方法之一是对于二字节的国标码，在计算机内部，汉字编码和西文编码是共存的。区分的方法之一是对于二字节的国标码，在计算机内部，汉字编码和西文编码是共存的。区分的方法之一是对于二字节的国标码，在计算机内部，汉字编码和西文编码是共存的。区分的方法之一是对于二字节的国标码，将二个字节的最高位都置成将二个字节的最高位都置成将二个字节的最高位都置成将二个字节的最高位都置成1 1，而，而，而，而ASCIlASCIl码所用字节最高位保持码所用字节最高位保持码所用字节最高位保持码所用字节最高位保持0 0，然后由软件（或硬件），然后由软件（或硬件），然后由软件（或硬件），然后由软件（或硬件）根据字节最高位来作出判断。根据字节最高位来作出判断。根据字节最高位来作出判断。根据字节最高位来作出判断。 1920172018NOIP初赛速成辅导(中国计算机学会出版)“ “多媒体技术多媒体技术多媒体技术多媒体技术” ”就是用计算机交互地综合处理文本、就是用计算机交互地综合处理文本、就是用计算机交互地综合处理文本、就是用计算机交互地综合处理文本、图形、图象、动画、音频及视频影象等多种信息，并图形、图象、动画、音频及视频影象等多种信息，并图形、图象、动画、音频及视频影象等多种信息，并图形、图象、动画、音频及视频影象等多种信息，并使这些信息建立逻辑连接。使这些信息建立逻辑连接。使这些信息建立逻辑连接。使这些信息建立逻辑连接。 2020172018NOIP初赛速成辅导(中国计算机学会出版)1 1、音频信号处理（声卡）：录入、处理重放、音频信号处理（声卡）：录入、处理重放信号；用信号；用MIDIMIDI技术合成音乐技术合成音乐2 2、图形和图象处理：真彩色卡；图象采集卡；、图形和图象处理：真彩色卡；图象采集卡；图象信号压缩技术；图象信号压缩技术；3 3、视频处理：实时录象和压缩视频图象的硬、视频处理：实时录象和压缩视频图象的硬件解压缩卡；软件解压缩技术件解压缩卡；软件解压缩技术多媒体计算机的基本配置多媒体计算机的基本配置 WINDOWS 9X WINDOWS 9X以上版本的操作系统和相以上版本的操作系统和相应的硬件标准应的硬件标准多媒体计算机的功能多媒体计算机的功能2120172018NOIP初赛速成辅导(中国计算机学会出版)CDROM（高密度盘，即光盘）（高密度盘，即光盘） 通过光学方式（使用激光束）读写信息通过光学方式（使用激光束）读写信息技术标准技术标准1、数据传输率、数据传输率2、平均搜索时间、平均搜索时间2220172018NOIP初赛速成辅导(中国计算机学会出版)色彩数目色彩数目 分辨率分辨率特点特点16640*480Windows的最低配置、显示速度最快256800*600性能虽好一些，但易产生调色板的冲突655361024*768全彩的显示模式，色彩逼真，不会再有调色板的冲突。16M1284*1024高等级的3D绘图软件和专业级的视频录制人员使用的真彩色模式，要求更多的RAM在显示卡和主机板上，CPU最好也是顶级的。 显示卡显示卡水平分辨率水平分辨率 垂直分辨率垂直分辨率 色彩数目显示存储空间色彩数目显示存储空间显示加速：显示加速：VRAMVRAM、EDORAMEDORAM，WindowsRAMWindowsRAM，RamlbusDRAMRamlbusDRAM显示模式显示模式显示模式显示模式 2320172018NOIP初赛速成辅导(中国计算机学会出版)1、屏幕由象素组成2、主要部件（电子枪、荧光屏遮罩、荧光屏）3、电子束由左而右、由上而下周期性扫描产生持续稳定的画面4、红、绿、蓝三个电子枪的亮度决定颜色5、扫描频率更高、并能自动调整扫描频率显示器显示器2420172018NOIP初赛速成辅导(中国计算机学会出版)数据压缩和解压缩技术数据压缩和解压缩技术 静止图像压缩标准静止图像压缩标准JPEG（JointPhotographicExpertsCroup）动态图像压缩标准动态图像压缩标准MPEG（MovingPictureExpertsCroup）多通道的动态图像压缩标准多通道的动态图像压缩标准MP64 2520172018NOIP初赛速成辅导(中国计算机学会出版)相关名词相关名词位图：位图：位图：位图：由一点一点的像素点排成矩阵组成的，其中每一个像素点都可以是由一点一点的像素点排成矩阵组成的，其中每一个像素点都可以是任意颜色。任意颜色。 向量图：向量图：向量图：向量图：用向量代表图中所表现的元素。用向量代表图中所表现的元素。 像素像素像素像素 ：图形的最小组成单位：图形的最小组成单位 真彩色：真彩色：真彩色：真彩色：人的眼睛能够分辨出的颜色大约有人的眼睛能够分辨出的颜色大约有1 1万万6 6千多种，为了能表现出千多种，为了能表现出这么多种色彩，我们得用这么多种色彩，我们得用2424bitbit（2 22424=16M=16M）来描述一个像素的颜色，这种来描述一个像素的颜色，这种显示模式就称为真彩色。显示模式就称为真彩色。 RGBRGB模式：模式：模式：模式：分别代表红、绿、蓝三种颜色，计算机以分别代表红、绿、蓝三种颜色，计算机以RGBRGB模式来定义计算模式来定义计算机屏幕上的颜色。通过混色原理，不同比例的机屏幕上的颜色。通过混色原理，不同比例的RGBRGB色彩可调和出无穷多种色彩可调和出无穷多种颜色。颜色。HSBHSB模式：模式：模式：模式：分别表示色调（分别表示色调（huehue）、）、饱和度（饱和度（saturationsaturation）、）、亮度（亮度（brightbright）。）。不同的色调代表不同的颜色；饱和度指的是某区域中，该颜色量的多少，不同的色调代表不同的颜色；饱和度指的是某区域中，该颜色量的多少，饱和度越低，该区域看起来就越灰暗；亮度则是指颜色的亮、暗，极亮成饱和度越低，该区域看起来就越灰暗；亮度则是指颜色的亮、暗，极亮成白色，极暗则成黑色。相对于白色，极暗则成黑色。相对于RGBRGB模式，模式，HSBHSB模式设定颜色的方式可产生模式设定颜色的方式可产生更好的视觉效果。更好的视觉效果。2620172018NOIP初赛速成辅导(中国计算机学会出版)多媒体信息处理工具 图形制作平台图形制作平台FreeHand FreeHand 图像处理平台图像处理平台PhotoshopPhotoshop动画制作平台动画制作平台 Animation ProAnimation Pro 数字动画的类型：数字动画的类型：数字动画的类型：数字动画的类型：基于模型的动画基于模型的动画 帧动画帧动画 动画中加人声音的方法动画中加人声音的方法动画中加人声音的方法动画中加人声音的方法嵌人式嵌人式嵌人式嵌人式将声音文件经过转换合并到影片文件中去。将声音文件经过转换合并到影片文件中去。流式流式流式流式声音与文件分开，在影片播放的各个时机启动声音文件声音与文件分开，在影片播放的各个时机启动声音文件音乐音乐音乐音乐 波形音频文件波形音频文件波形音频文件波形音频文件 ：通过现场录制和模数转化产生，存储量大通过现场录制和模数转化产生，存储量大MIDIMIDI文件：文件：文件：文件：使用键盘合成器和一个音序器使用键盘合成器和一个音序器 制作和编辑，存储量小制作和编辑，存储量小2720172018NOIP初赛速成辅导(中国计算机学会出版)“ “雏形雏形雏形雏形” ”：主机主机终端系统终端系统里程碑：里程碑：里程碑：里程碑：APRANETAPRANET网网广域网（广域网（广域网（广域网（ WANWAN ）：）：）：）：实现远距离的计算机之间的数据传输和实现远距离的计算机之间的数据传输和信息共享的计算机网络。通信线路一般租用电话线路或铺设信息共享的计算机网络。通信线路一般租用电话线路或铺设专用电缆。专用电缆。局域网络（局域网络（局域网络（局域网络（LINLIN）：）：）：）：为一个单位，或一个相对独立的局部范围为一个单位，或一个相对独立的局部范围内大量存在的微机能够相互通信、共享昂贵的外部设备（如内大量存在的微机能够相互通信、共享昂贵的外部设备（如大容量磁盘、激光打印机、绘图议等）、共享数据信息和应大容量磁盘、激光打印机、绘图议等）、共享数据信息和应用程序而建立的计算机网络。通信线路一般不租用电话线路，用程序而建立的计算机网络。通信线路一般不租用电话线路，使用专门铺设的线路。使用专门铺设的线路。互联网（互联网（互联网（互联网（InternetInternet）：）：）：）：将遍布全球的子网通过连网协议集成将遍布全球的子网通过连网协议集成到一个共享的、开放的、易于管理的主干网。到一个共享的、开放的、易于管理的主干网。 2820172018NOIP初赛速成辅导(中国计算机学会出版)功能功能1、硬件资源共享2、软件资源共享3、数据和信息共享定义定义 计算机网络是由地理位置分散的、具有独立功能的多个计算机系统，经通讯设备和线路互相连接，并配以相应的网络软件，以实现通信和资源共享的系统2920172018NOIP初赛速成辅导(中国计算机学会出版)计算机网络的物理组成计算机网络的物理组成网络中心主干机网络中心主干机网络中心主干机网络中心主干机 、服务器服务器服务器服务器 、网络工作站网络工作站网络工作站网络工作站 共享的外部设备共享的外部设备共享的外部设备共享的外部设备 网卡网卡网卡网卡 通信线路通信线路通信线路通信线路（双绞线、同轴电缆和光缆、无线传输介质（如微波、红外线（双绞线、同轴电缆和光缆、无线传输介质（如微波、红外线（双绞线、同轴电缆和光缆、无线传输介质（如微波、红外线（双绞线、同轴电缆和光缆、无线传输介质（如微波、红外线和激光等）和激光等）和激光等）和激光等） 局部网络通信设备局部网络通信设备局部网络通信设备局部网络通信设备（中继器、集线器（中继器、集线器（中继器、集线器（中继器、集线器 ） 网络互连设备网络互连设备网络互连设备网络互连设备 （网桥（网桥（网桥（网桥、路由器和网关路由器和网关路由器和网关路由器和网关 ）网络软件网络软件网络软件网络软件 （对等式网络操作系统（对等式网络操作系统（对等式网络操作系统（对等式网络操作系统 、服务器上的网络操作系统）、服务器上的网络操作系统）、服务器上的网络操作系统）、服务器上的网络操作系统） 3020172018NOIP初赛速成辅导(中国计算机学会出版)计算机网络的拓扑结构计算机网络的拓扑结构总线拓扑总线拓扑星型拓扑星型拓扑 3120172018NOIP初赛速成辅导(中国计算机学会出版)环型拓扑环型拓扑环型拓扑环型拓扑 树型拓扑树型拓扑树型拓扑树型拓扑 3220172018NOIP初赛速成辅导(中国计算机学会出版)计算机网络的体系结构计算机网络的体系结构 所谓网络体系结构就是对构成计算机网络的各组成部分之间的关系及所要所谓网络体系结构就是对构成计算机网络的各组成部分之间的关系及所要所谓网络体系结构就是对构成计算机网络的各组成部分之间的关系及所要所谓网络体系结构就是对构成计算机网络的各组成部分之间的关系及所要实现功能的一组精确定义。国际标准化组织（实现功能的一组精确定义。国际标准化组织（实现功能的一组精确定义。国际标准化组织（实现功能的一组精确定义。国际标准化组织（ISOISO）提出的开放系统互联提出的开放系统互联提出的开放系统互联提出的开放系统互联参考模型（参考模型（参考模型（参考模型（OSIOSI）已成为网络体系结构的标准已成为网络体系结构的标准已成为网络体系结构的标准已成为网络体系结构的标准 3320172018NOIP初赛速成辅导(中国计算机学会出版)Internet使用使用TCP/IP网络体系结构网络体系结构TCP/IPTCP/IP的层号的层号的层号的层号TCP/IPTCP/IP的层次的层次的层次的层次名名名名对应对应对应对应OSIOSI模型的层模型的层模型的层模型的层次次次次3 3应用层（应用层（ftpftp和和telnettelnet等协议）等协议）应用层、表示层、应用层、表示层、会话层会话层2 2传输控制协议传输控制协议TCPTCP传输层传输层1 1网际协议网际协议IPIP网络层网络层3420172018NOIP初赛速成辅导(中国计算机学会出版)计算机网络应用模式计算机网络应用模式 客户机客户机/服务器模型：服务器模型：将应用分成客户机和服务器两大部将应用分成客户机和服务器两大部分，并将它分配到整个网络上。由服务器提供资源，通常执行后台功能；分，并将它分配到整个网络上。由服务器提供资源，通常执行后台功能；而客户机使用服务器，通常执行前台功能。而客户机使用服务器，通常执行前台功能。 文件服务器：文件服务器：提供操作系统中文件管理的各种功能（网络文件提供操作系统中文件管理的各种功能（网络文件的访问方式：文件传输和文件访问的访问方式：文件传输和文件访问 ） 打打印印服服务务器器：将将一一台台或或几几台台打打印印机机物物理理地地连连接接到到打打印印服服务务器器上上，可为多个客户机用户轮流使用可为多个客户机用户轮流使用 数数据据库库服服务务器器：侧侧重重于于传传统统数数据据库库管管理理系系统统的的功功能能（如如数数据据的的定义及存取、数据的安全性与完整性、并发控制及事务处理等）的服务器定义及存取、数据的安全性与完整性、并发控制及事务处理等）的服务器远程登录：远程登录：通过用户帐号访问远地系统的资源通过用户帐号访问远地系统的资源3520172018NOIP初赛速成辅导(中国计算机学会出版)Internet 网络地址网络地址 IPIPIPIP地址地址地址地址: : : : 网络数网络数网络数网络数网络主机数网络主机数网络主机数网络主机数主机数主机数主机数主机数A A类网络类网络12612620647700642064770064B B类网络类网络1625616256645166451610488720961048872096C C类网络类网络254254524386048524386048总计总计36380282083638028208域名（或称主机名称）域名（或称主机名称）域名（或称主机名称）域名（或称主机名称）: : : :计算机主机名计算机主机名. .子域名子域名. .子域名子域名. .最高层域名最高层域名 3620172018NOIP初赛速成辅导(中国计算机学会出版)Internet应用应用 文件传输文件传输文件传输文件传输 ( (使用匿名文件传输服务（匿名使用匿名文件传输服务（匿名FTPFTP）网上软件分类：网上软件分类：公公公公共软件共软件共软件共软件 、免费软件免费软件免费软件免费软件 、共享软件共享软件共享软件共享软件 ) )远程登录远程登录远程登录远程登录（Telnet Telnet 命令）命令） 电子邮政服务电子邮政服务电子邮政服务电子邮政服务 （电子邮箱地址：用户名计算机域名）（电子邮箱地址：用户名计算机域名）网络新闻与公告牌服务网络新闻与公告牌服务网络新闻与公告牌服务网络新闻与公告牌服务 （网络新闻是由（网络新闻是由USENETUSENET在在InternetInternet中中的新闻服务器节点之间进行传递的，阅读新闻组的软件有的新闻服务器节点之间进行传递的，阅读新闻组的软件有Outlook Outlook ExpressExpress）信息查询服务信息查询服务信息查询服务信息查询服务 （最为流行的信息查询服务系统是万维网（最为流行的信息查询服务系统是万维网（World World Wide WebWide Web），），简称简称WWWWWW，即基于，即基于“ “超文本超文本” ”方式的信息查询技术）。方式的信息查询技术）。 超文本：非顺序的文本呈现超文本：非顺序的文本呈现超媒体：超文本和多媒体浏览环境下的应用超媒体：超文本和多媒体浏览环境下的应用Mome pageMome page是由是由HTMLHTML语言编写的文本文件，经过语言编写的文本文件，经过WWWWWW浏览器的解释浏览器的解释和处理后，网页显示在用户目前的是多媒体的超文本文件和处理后，网页显示在用户目前的是多媒体的超文本文件3720172018NOIP初赛速成辅导(中国计算机学会出版)程序设计语言的组成程序设计语言的组成 程程程程序序序序设设设设计计计计语语语语言言言言的的的的基基基基础础础础是是是是一一一一组组组组记记记记号号号号和和和和规规规规则则则则。根根根根据据据据规规规规则由记号构成的记号串的总体就是语言。则由记号构成的记号串的总体就是语言。则由记号构成的记号串的总体就是语言。则由记号构成的记号串的总体就是语言。 包括包括包括包括语法语法语法语法：程序的结构或形式。编译系统会自动进行语法检验；程序的结构或形式。编译系统会自动进行语法检验； 语语语语义义义义：程程序序的的含含义义，亦亦即即表表示示按按照照各各种种方方法法所所表表示示的的各各个个记记号号的的特特定定含含义义，但但不不涉涉及及使使用用者者。语语义义的的错错误误是是在在源源程程序序编编译译通通过过后后的的运运行行过过程程中出现的，属于算法类的错误。中出现的，属于算法类的错误。 语用语用语用语用：程序和使用者的关系；程序和使用者的关系； 语言的成分语言的成分语言的成分语言的成分数据成分数据成分数据成分数据成分，用以描述程序中所涉及的数据；，用以描述程序中所涉及的数据；运算成分，运算成分，运算成分，运算成分，用以描述程序中所包含的运算；用以描述程序中所包含的运算；控制成分，控制成分，控制成分，控制成分，用以描述程序中的控制构造；用以描述程序中的控制构造；传输成分，传输成分，传输成分，传输成分，用以表达程序中数据的传输。用以表达程序中数据的传输。 3820172018NOIP初赛速成辅导(中国计算机学会出版)语言和程序设计的发展语言和程序设计的发展 第一代语言第一代语言第一代语言第一代语言机器语言机器语言机器语言机器语言 第二代语言第二代语言第二代语言第二代语言汇编语言汇编语言汇编语言汇编语言 第三代语言第三代语言第三代语言第三代语言高级语言、算法语言（高级语言、算法语言（高级语言、算法语言（高级语言、算法语言（BASICBASIC、FORTRANFORTRAN、COBOLCOBOL、PascalPascal、C C ） 第四代语言第四代语言第四代语言第四代语言非过程化语言（非过程化语言（非过程化语言（非过程化语言（SQLSQL语言）语言）语言）语言） 第五代语言第五代语言第五代语言第五代语言智能性语言（智能性语言（智能性语言（智能性语言（PROLOGPROLOG语言语言语言语言 、LISPLISP语言语言语言语言 ） 3920172018NOIP初赛速成辅导(中国计算机学会出版)面向对象方法的主要概念面向对象方法的主要概念 对象对象对象对象系统中用来描述客观事物的一个实体，是系统中用来描述客观事物的一个实体，是构成系统的一个基本单位，对象由两个主要因素组成：构成系统的一个基本单位，对象由两个主要因素组成：属性属性属性属性：描述对象静态特征的一个数据项；描述对象静态特征的一个数据项； 服务服务服务服务：描述对象动态特征的一个操作序列；描述对象动态特征的一个操作序列；消息消息消息消息对象之间通过服务请求发生联系，这种向对象之间通过服务请求发生联系，这种向对象发出的服务请求称为消息。对象发出的服务请求称为消息。 类类类类为了很好地控制软件的复杂度，将具有相同为了很好地控制软件的复杂度，将具有相同属性和服务的一组对象组成类。属性和服务的一组对象组成类。 4020172018NOIP初赛速成辅导(中国计算机学会出版)面向对象语言分为两大阵营面向对象语言分为两大阵营 Smalltalk和Eiffel为代表的纯粹型面向对象语言，主要强调软件开发的探索性和原型化开发方法；以C+、Object Pascal为代表的混合型面向对象语言，主要扩充现有语言，强调运行时的时空效率；4120172018NOIP初赛速成辅导(中国计算机学会出版)程序设计的特点程序设计的特点构造性构造性构造性构造性 : :不同的人为解决同一问题编制的程序，其面貌颇不相不同的人为解决同一问题编制的程序，其面貌颇不相同，然而，程序的功效却是等价的。同，然而，程序的功效却是等价的。 严谨性严谨性严谨性严谨性: :以上下文无关的形式语言实现。无法补充缺损信息、以上下文无关的形式语言实现。无法补充缺损信息、去掉冗余信息、将暂时不懂的信息暂时搁置起来，待下文或经过去掉冗余信息、将暂时不懂的信息暂时搁置起来，待下文或经过推理予以补充和理解推理予以补充和理解 叠加性叠加性叠加性叠加性: : 一般是将自己设计的子程序尽量分割成独立的、功能一般是将自己设计的子程序尽量分割成独立的、功能明确单一的小模块，以便充分利用；甚至还会利用系统内的库函明确单一的小模块，以便充分利用；甚至还会利用系统内的库函数。数。抽象性抽象性抽象性抽象性: :把客观事物的描述抽象为数据和算法，并且利用抽象把客观事物的描述抽象为数据和算法，并且利用抽象使得程序能够正确的映射客观事物使得程序能够正确的映射客观事物 。抽象是有层次的。抽象是有层次的 ，不同层，不同层次上的抽象是相互独立和互相作用的次上的抽象是相互独立和互相作用的 。4220172018NOIP初赛速成辅导(中国计算机学会出版)计算程序的运行结果计算程序的运行结果 一、直接推理一、直接推理二、由流程图推断算法二、由流程图推断算法三、动态模拟三、动态模拟 四、由底向上阅读分析四、由底向上阅读分析 4320172018NOIP初赛速成辅导(中国计算机学会出版)对对于于一一些些语语句句少少、结结构构简简单单且且可可读读性性较较强强的的程程序序，不不妨妨通过分析程序流程，直接寻找其间蕴含的计算模型。通过分析程序流程，直接寻找其间蕴含的计算模型。$n+n+ varvarm,n,I:integer;m,n,I:integer;t:extended;t:extended;beginbeginreadln(n,m);readln(n,m);t:=1;t:=1;fori:=1tomdot:=t*(ni+1)/i;fori:=1tomdot:=t*(ni+1)/i;writeln(t:0:0);writeln(t:0:0);end.end.输入输入105105输出：输出：4420172018NOIP初赛速成辅导(中国计算机学会出版)【分析】【分析】【分析】【分析】由由forfor循环可以看出循环可以看出t=t=，即即i=1i=1时，时，t=nt=n；i=2i=2时，时，t=n*(n1)/2t=n*(n1)/2；i=3i=3时，时，t=n*(n1)/2*(n2)/3t=n*(n1)/2*(n2)/3；i=mi=m时，时，t=c(n,m)=n!/(m!*(nm)!)t=c(n,m)=n!/(m!*(nm)!) 显然，这是求组合数。当输入显然，这是求组合数。当输入n=10n=10、m=5m=5时，程序应输出时，程序应输出252252。这这个个算算法法的的效效率率不不错错，因因为为计计算算与与n n和和mm的的大大小小有有直直接接的的关关系系。所所以以，我我们们要要设设法法使使运运算算的的中中间间结结果果尽尽可可能能地地小小。如如果果我我们们先先把把N(NM+1)N(NM+1)这这MM个个连连续续的的自自然然数数乘乘起起来来，再再依依次次除除以以11MM就就是是一一种种不不太太明明智智的的选选择择。上上述述程程序序先先乘乘N N除除1 1，然然后后乘乘( (N1)N1)除除2 2，再再乘乘( (N2)N2)除除3 3，最最后后乘乘( (NM+1)NM+1)除除MM。因因为为连连续续的的K K个个自自然然数数的的积积一一定定能能被被K!K!整整除除，所所以以在在这这一一过过程程中中不不会会出出现现除除不不尽尽的的情情况况。同同时时也也使使得得中中间间结结果果比比较较小小，从从而而提提高高了了运运算算速速度度。告告诫诫读读者者的的是是，对对于于上上述述算算法法来来说说，n n和和mm不不能能超超过过10102 2。如如果果超超过过了了这这个个上上限限，t t就会溢出，尽管它采用了就会溢出，尽管它采用了extendedextended类型。类型。4520172018NOIP初赛速成辅导(中国计算机学会出版)对于一些易读性不十分好的程序，最对于一些易读性不十分好的程序，最好的办法是画流程图。其步骤如下好的办法是画流程图。其步骤如下 跟着程序画流程图，一句一框；跟着程序画流程图，一句一框； 根据上下文的联系合并流程图。根据上下文的联系合并流程图。若前几句计算值都要代入后一表达式，若前几句计算值都要代入后一表达式，则合并为一框。接连合并几次，使程则合并为一框。接连合并几次，使程序成为一个大功能块；序成为一个大功能块； 由大功能块推断算法；由大功能块推断算法； 代入输入值，计算结果。代入输入值，计算结果。 4620172018NOIP初赛速成辅导(中国计算机学会出版)label10,20,30;label10,20,30;varvars,p:string;s,p:string;i,k,n,j,m:integer;i,k,n,j,m:integer;beginbeginreadln(s);n:=length(s);readln(s);n:=length(s);readln(p);m:=length(p);readln(p);m:=length(p);i:=0;i:=0;10:i:=i+1;j:=i;k:=1;10:i:=i+1;j:=i;k:=1;20:ifsjpk20:ifsjpkthenbeginthenbeginifin-m+1thengoto10;i:=0;goto30;ifin-m+1thengoto10;i:=0;goto30;endendelseifkmelseifk0)thenif(ansi0)thenbeginbeginforj:=idownto0dowrite(ansj)forj:=idownto0dowrite(ansj)；writelnwriteln；breakbreak；endend；thenthenEnd.End.输入输入输入输入输出输出输出输出55 5420172018NOIP初赛速成辅导(中国计算机学会出版)update(vara)update(vara)是将数组是将数组a a规整为高精度的十进制数组规整为高精度的十进制数组 mult(varamult(vara，b)b)是将高精度的十进制数组是将高精度的十进制数组a a乘以整数乘以整数b b，积存积存储在储在a a中。中。 add(xadd(x，ob)ob)计算因子表，计算因子表，ob=1,numnum*xob=1,numnum*x；ob=1ob=1，numnum/xnumnum/x。其中其中numinumi为因子为因子i i的个数的个数 主程序计算主程序计算catalancatalan数数1/1/（n+1n+1）*c(2*n,n)*c(2*n,n)。显然显然n=5n=5，则程则程序输出序输出42(1/6*42(1/6*c(10,5)c(10,5)5520172018NOIP初赛速成辅导(中国计算机学会出版)完善程序完善程序 填空内容：填空内容：填空内容：填空内容： 1 1、变量方面的填空、变量方面的填空、变量方面的填空、变量方面的填空 2 2、循环方面的填空、循环方面的填空、循环方面的填空、循环方面的填空 3 3、分支转移方面的填空、分支转移方面的填空、分支转移方面的填空、分支转移方面的填空 4 4、主程序和子程序关系方面的填空、主程序和子程序关系方面的填空、主程序和子程序关系方面的填空、主程序和子程序关系方面的填空 5 5、输入输出方面的填空、输入输出方面的填空、输入输出方面的填空、输入输出方面的填空 填空方法：填空方法：填空方法：填空方法： 按照自顶向下的思维方法阅读程序按照自顶向下的思维方法阅读程序按照自顶向下的思维方法阅读程序按照自顶向下的思维方法阅读程序从主程序开始，从主程序开始，从主程序开始，从主程序开始，沿控制层次向下阅读。在查到某一个子程序沿控制层次向下阅读。在查到某一个子程序沿控制层次向下阅读。在查到某一个子程序沿控制层次向下阅读。在查到某一个子程序( (子模块子模块子模块子模块) )时，比时，比时，比时，比照题目给出的说明和调用它的照题目给出的说明和调用它的照题目给出的说明和调用它的照题目给出的说明和调用它的“父程序父程序父程序父程序( (父模块父模块父模块父模块) )”，弄清该，弄清该，弄清该，弄清该子程序子程序子程序子程序( (子模块子模块子模块子模块) )究竟要达到什么样的子目标，然后查程序，究竟要达到什么样的子目标，然后查程序，究竟要达到什么样的子目标，然后查程序，究竟要达到什么样的子目标，然后查程序，看它是如何实现这个子目标的。如果该子程序看它是如何实现这个子目标的。如果该子程序看它是如何实现这个子目标的。如果该子程序看它是如何实现这个子目标的。如果该子程序( (子模块子模块子模块子模块) )有空有空有空有空格，则按照算法的逻辑进行填空。依次类推，直至最底层的格，则按照算法的逻辑进行填空。依次类推，直至最底层的格，则按照算法的逻辑进行填空。依次类推，直至最底层的格，则按照算法的逻辑进行填空。依次类推，直至最底层的子程序（子模块）中的空格全部填完为止。子程序（子模块）中的空格全部填完为止。子程序（子模块）中的空格全部填完为止。子程序（子模块）中的空格全部填完为止。5620172018NOIP初赛速成辅导(中国计算机学会出版)1、完善不含子程序的程序、完善不含子程序的程序 首先划分各个子模块的层次结构，并确定每个子模块的子首先划分各个子模块的层次结构，并确定每个子模块的子首先划分各个子模块的层次结构，并确定每个子模块的子首先划分各个子模块的层次结构，并确定每个子模块的子目标。然后自顶向下，根据子目标和上层子模块给出的线索，目标。然后自顶向下，根据子目标和上层子模块给出的线索，目标。然后自顶向下，根据子目标和上层子模块给出的线索，目标。然后自顶向下，根据子目标和上层子模块给出的线索，对当前层次的各个模块进行填空。依次类推，直至最底层的子对当前层次的各个模块进行填空。依次类推，直至最底层的子对当前层次的各个模块进行填空。依次类推，直至最底层的子对当前层次的各个模块进行填空。依次类推，直至最底层的子模块中的空格全部填完为止。模块中的空格全部填完为止。模块中的空格全部填完为止。模块中的空格全部填完为止。求求元元素素之之和和最最大大的的子子方方阵阵：在在mnmn（mm，n20n20）的的正正整整数数数数字字方方阵阵中中，找找出出一一个个pqpq的的子子阵阵（11pmpm，1qn1qn）使使其其元元素素之之和和最最大大。例例如如，下面下面5454的数字阵中，元素之和最大的一个的数字阵中，元素之和最大的一个2323子阵。子阵。 54 54数字阵数字阵 元素之和最大的元素之和最大的2323子阵为子阵为3 38 84 4222211111 17 79 95 521216 62 210103 38 89 92 27 712123 35 521216 610103 38 85720172018NOIP初赛速成辅导(中国计算机学会出版)vara:array1.20,1.20ofinteger;vara:array1.20,1.20ofinteger;m,n,p,q,i,j,max,p1,q1,s,i1,j1:integer;m,n,p,q,i,j,max,p1,q1,s,i1,j1:integer;beginbeginfori:=1to20dofori:=1to20doforj:=1to20doforj:=1to20doai,j:=0;ai,j:=0;readln(m,n);readln(m,n);fori:=1tomdofori:=1tomdobeginbeginforj:=1tondoread(ai,j);forj:=1tondoread(ai,j);readlnreadlnend;end;readln(p,q);readln(p,q);max:=0;max:=0;fori:=1tom-p+1dofori:=1tom-p+1doforj:=1ton-q+1doforj:=1ton-q+1dobeginbegin; ;fori1:=itop+i-1dofori1:=itop+i-1doforj1:=jtoq+j-1doforj1:=jtoq+j-1do; ;ifsmaxthenbeginifsmaxthenbegin; ;p1:=i;p1:=i;q1:=jq1:=jend;end;end;end;fori:=p1tofori:=p1tododobeginbeginforj:=q1toforj:=q1tododowrite(ai,j:3);write(ai,j:3);writelnwritelnend;end;readlnreadlnend.end.5820172018NOIP初赛速成辅导(中国计算机学会出版)模模模模块块块块1 1（初初始始化化，白白白白色色色色）：方方阵阵清清零零；读读方方阵阵规规模模；读方阵；读子阵规模；子阵的最大数和初始化读方阵；读子阵规模；子阵的最大数和初始化模块模块模块模块2 2（湖蓝）（湖蓝）（湖蓝）（湖蓝）通过枚举所有可能子阵，求数和最大通过枚举所有可能子阵，求数和最大的子阵的子阵 。其中。其中子模块子模块1 1（深蓝）（深蓝）（深蓝）（深蓝）：累计（：累计（i,ji,j）为左上角的子阵的数和为左上角的子阵的数和 子模块子模块2 2（淡绿）（淡绿）（淡绿）（淡绿）：调整子阵的最大数和：调整子阵的最大数和 模块模块3 3（红色）（红色）（红色）（红色）输出最大数和的子阵。输出最大数和的子阵。 由此得出解由此得出解 s:=0s:=0s:=s+ai1,j1s:=s+ai1,j1max:=smax:=sp1+p1p1+p1q1+q1q1+q15920172018NOIP初赛速成辅导(中国计算机学会出版)以下程序完成对数组每个元素向后移动n个单位。数组元素的下标依次为0到m1，对任意一个数组元素ai而言，它的值移动后将存储在数组元素a(i+n)modm中。例如，m=10，n=3，移动前数组中存储的数据如下前一行所示，则程序运行后数组中存储的数据如下后一行所示。0386202767311637421637420386202767316020172018NOIP初赛速成辅导(中国计算机学会出版)constmaxm=10000;constmaxm=10000;varvari,k,m,n,rest,start,temp:longinti,k,m,n,rest,start,temp:longint; ; a:arraya:array0.maxm0.maxmofoflongint;longint;beginbeginwrite(inputm,n:);write(inputm,n:);readln(m,n);readln(m,n);forfori:=0i:=0totom-1m-1dodoai:=random(100);ai:=random(100);writeln(beforemove);writeln(beforemove);forfori:=0i:=0totom-1m-1dodowrite(ai:5);write(ai:5);writeln;writeln;rest:=m;start:=0;rest:=m;start:=0;whilewhiledodobeginbegink:=start;k:=start;repeatk:=(k+n)modmuntilk=start;repeatk:=(k+n)modmuntilk0rest0或或 rest0rest0k=startk=startrest:=rest1rest:=rest1a(k+n)modm:=tempa(k+n)modm:=temp或或 a(start+n)modm:=a(start+n)modm:=temptempstart:=start+1start:=start+16220172018NOIP初赛速成辅导(中国计算机学会出版)完善含子程序结构的程序完善含子程序结构的程序 如果子模块采用过程或函数，则通常以子程序为单位划分层次结构，这样可以使得其层次性相对不含子程序的程序来说要清晰一些。 程程序序的的任任务务是是用用0 09 9中中的的n n个个数数字字填填入入如如下下乘乘法法运运算算的的* *处处，数数字字可可重重复复使使用用，且所用的数字至少有一个是素数，要求输出满足下列算式的方案数。且所用的数字至少有一个是素数，要求输出满足下列算式的方案数。*6320172018NOIP初赛速成辅导(中国计算机学会出版)constp:setof0.9=2,3,5,7;constp:setof0.9=2,3,5,7;varvars:setof0.9;s:setof0.9;n:integer;n:integer;ans:longint;ans:longint;f:text;f:text;procedureinit;procedureinit;varvari:integer;i:integer;t:byte;t:byte;beginbeginreadln(n);s:=;readln(n);s:=;fori:=1tondofori:=1tondobeginbeginread(t);s:=s+t;read(t);s:=s+t;end;end;close(f);close(f);end;end; functionfunctionok(x,l:integer):boolean;ok(x,l:integer):boolean; 此函数判断此函数判断此函数判断此函数判断x x是否符合条件是否符合条件是否符合条件是否符合条件 vart:byte;vart:byte;beginbeginok:=false;ok:=false; ifif _ll thenthenexit;exit;whilex0dowhilex0dobeginbegint:=xmod10;t:=xmod10;ifnot(tins)thenexit;ifnot(tins)thenexit;x:=xdiv10;x:=xdiv10;end;end;ok:=true;ok:=true;end;end; functionfunctioninset(x:integer):boolean;inset(x:integer):boolean; 此函数判断此函数判断此函数判断此函数判断x x中是否包含素数字中是否包含素数字中是否包含素数字中是否包含素数字 vart:byte;vart:byte;beginbegininset:=false;inset:=false;while_while_do_dobeginbegint:=xmod10;t:=xmod10;iftinptheniftinpthenbeginbegininset:=true;inset:=true;exit;exit;end;end;_end;end;end;end; 6420172018NOIP初赛速成辅导(中国计算机学会出版)procedurework;procedurework;vari,i1,i2,i3,j1,j2:integer;vari,i1,i2,i3,j1,j2:integer;beginbeginans:=0;ans:=0;fori1:=1to9dofori1:=1to9doifi1insthenifi1insthenfori2:=1to9dofori2:=1to9doifi2insthenifi2insthenfori3:=1to9dofori3:=1to9doifi3insthenifi3insthenbeginbegin_forj1:=1to9doforj1:=1to9doif(j1ins)andok(j1*i,3)thenif(j1ins)andok(j1*i,3)thenforj2:=1to9doforj2:=1to9doif(j2ins)andok(j2*i,3)and_if(j2ins)andok(j2*i,3)and_then_thenbeginbeginifif(i1(i1ininp)p)oror(i2(i2ininp)p)oror(i3(i3ininp)p)oror(j1(j1ininp)p)oror(j2inp)orinset(j1*i)orinset(j2*i)(j2inp)orinset(j1*i)orinset(j2*i)theninc(ans);theninc(ans);end;end;end;end;writeln(ans);writeln(ans);end;end;beginbegininit;init;work;work;end.end.6520172018NOIP初赛速成辅导(中国计算机学会出版)模块模块模块模块11初始化。读入数字个数初始化。读入数字个数n n和和n n个整数，并将它们送入集合个整数，并将它们送入集合s(inits(init过程过程) )。 模块模块模块模块22计算和输出方案数计算和输出方案数ansans（workwork过程）过程） 在在s s集集合合中中枚枚举举所所有有可可能能的的被被乘乘数数i1i1i2i2i3i3和和所所有有可可能能的的乘乘数数j1j1j2,j2,被被乘乘数数和和乘乘数数必必须须满满足足如下条件如下条件j1*ij1*i的的积积和和j2*ij2*i的的积积分分别别为为3 3位位，（j1j1j2j2）*i*i的的积积为为4 4位位，且且积积的的每每一一位位数数字字在在集集合合s s中中。在在workwork过过程程中中，通通过过调调用用布布尔尔函函数数ok(xok(x，l) l)来来判判别别数数字字x x是是否否满满足足各各位位数数字字在在集集合合s s且且位位数为数为l l位的条件位的条件i1i1、i2i2、i3i3、j1j1、j2j2、j1*ij1*i的的各各位位数数、j2*ij2*i的的各各位位数数中中至至少少有有一一个个为为素素数数。在在workwork过过程程中中，通过调用布尔函数通过调用布尔函数inset(x)inset(x)来判别多位数来判别多位数x x中是否存在素数字中是否存在素数字 由此得出解为由此得出解为trunctrunc（lnln（x x）/ln/ln（1010）+1+1x0x0x:=xdiv10x:=xdiv10 i:=i1*100+i2*10+i3i:=i1*100+i2*10+i3okok（j1*i*10+j2*ij1*i*10+j2*i，4 4）6620172018NOIP初赛速成辅导(中国计算机学会出版)菲菲菲菲波波波波拉拉拉拉契契契契数数数数列列列列为为为为1,1,2,3,5,8,13,21,1,1,2,3,5,8,13,21,其其其其元元元元素素素素产产产产生生生生的的的的规规规规则则则则是是是是前前前前两两两两个个个个数数数数为为为为1 1，第第第第三三三三个个个个数数数数开开开开始始始始每每每每个个个个数数数数等等等等于于于于它它它它前前前前面面面面两两两两个个个个数数数数之之之之和和和和。已已已已知知知知任任任任意意意意一一一一个个个个正正正正整整整整数数数数可可可可以以以以表表表表示示示示为为为为若若若若干干干干个互不相同的菲波拉契数之和。个互不相同的菲波拉契数之和。个互不相同的菲波拉契数之和。个互不相同的菲波拉契数之和。 例如：例如：例如：例如：36=21+13+236=21+13+2 下下下下面面面面的的的的程程程程序序序序是是是是由由由由键键键键盘盘盘盘输输输输入入入入一一一一个个个个正正正正整整整整数数数数n n，输输输输出出出出组组组组成成成成n n的互不相同的菲波拉契数的互不相同的菲波拉契数的互不相同的菲波拉契数的互不相同的菲波拉契数寻寻寻寻找找找找小小小小于于于于等等等等于于于于n n的的的的最最最最大大大大菲菲菲菲波波波波拉拉拉拉契契契契数数数数a a，并并并并以以以以a a作作作作为为为为组组组组成成成成n n的一个数；的一个数；的一个数；的一个数；若若若若nana，则则则则以以以以n na a作作作作为为为为n n的的的的新新新新值值值值，重重重重复复复复步步步步骤骤骤骤(1)(1)。若若若若a an n，则结束：则结束：则结束：则结束： 6720172018NOIP初赛速成辅导(中国计算机学会出版)varn:integer;varn:integer;first:boolean;first:boolean; functionfunctionfind(n:integer):integer;find(n:integer):integer;vara,b,c:integer;vara,b,c:integer;beginbegina:=1;b:=1;a:=1;b:=1;repeatrepeatc:=c:=;a:=b;b:=c;a:=b;b:=c;untilb=n;untilb=n;ifb=nthenfind:=ifb=nthenfind:=elsefind:=elsefind:=end;end; procedurep(n:integer);procedurep(n:integer);vara:integer;vara:integer;beginbegina:=find(n);a:=find(n);iffirstthenbeginiffirstthenbeginwrite(a:4);first:=falsewrite(a:4);first:=falseendendelsewrite(+,a:4);elsewrite(+,a:4);ifanthenpifanthenp; ;end;end;beginbeginreadln(n);first:=true;readln(n);first:=true;设定表达式首项标志设定表达式首项标志设定表达式首项标志设定表达式首项标志 write(n:5,=);p(n);write(n:5,=);p(n);writeln;readlnwriteln;readlnend.end.6820172018NOIP初赛速成辅导(中国计算机学会出版)p(n)的功能：计算和输出n对应的表达式。p(n)的子函数find(n)的功能：寻找小于等于n的最大菲波拉契数由此得出解为a+bn(或b,c)a(na)6920172018NOIP初赛速成辅导(中国计算机学会出版)