信息学奥林匹克初赛辅导

信息学奥林匹克初赛辅导第一页，共六十六页，2022年，8月28日一、计算机的发展与应用二、计算机组成与工作原理和信息的表示与存储

三、多媒体应用

四、计算机网络使用基础

五、程序设计语言基础六、程序的阅读分析第二页，共六十六页，2022年，8月28日⑴计算机的发展历经了哪几个阶段；⑵按照功能和规模，可将计算机分成哪几大类，它们各自的分工是什么；⑶武装计算机的软件系统包括了哪些东西；⑷计算机的发展怎样促使人类走向丰富多彩的信息社会；⑸用户在使用计算机时应该遵守哪些道德规范；第三页，共六十六页，2022年，8月28日计算机发展史上的里程碑——计算机存储程序的工作原理美籍匈牙利数学家冯·诺依曼（vonNeumaml）在1946年提出的，其思想是，在计算机中设置存储器，将符号化的计算步骤存放在存储器中，然后依次取出存储的内容，由一个被称之为控制器的部件进行译码，译码结果在一个被称为运算器的部件中进行计算，从而实现计算机工作的自动化（运算器和控制器统称为CPU）。冯·诺依曼依据此原理设计出一个完整的计算机雏形，并确定了计算机的五大组成部分和基本的工作方法。第四页，共六十六页，2022年，8月28日第四代

VISI——大规模集成电路

CISC——复杂指令系统计算机

RCSC——精简指令系统计算机非冯·诺依曼式语言：lisp、prologo、f.p第五代NC——网络计算机（将整个网络看成一个巨大的磁盘驱动器，数据和文件存储在服务器）非冯·诺依曼式的计算机模型（以人脑神经系统处理信息的原理为基础）：生物计算机、光子计算机、量子计算机第五页，共六十六页，2022年，8月28日裸机系统软件应用软件用户第六页，共六十六页，2022年，8月28日操作系统是计算机系统中的一种系统软件，它能对计算机系统中的软件和硬件资源进行有效地管理和控制，合理地组织计算机的工作流程，为用户提供一个使用计算机的工作环境。

手工操作管理程序单道批处理系统多道批处理系统分时系统实时操作系统网络操作系统

第七页，共六十六页，2022年，8月28日DOS——单用户的唯一任务占用计算机上所有的硬件和软件资源，所能访问的主存地址空间太小。Windows——多作业、大内存管理、统一的图形用户界面，并且发展到网络环境使用UNIX操作系统、Linux操作系统、MacintoshOS第八页，共六十六页，2022年，8月28日数据库技术的特性⑴最小冗余⑵数据共享⑶数据独立性⑷安全性⑸完整性

数据库管理系统的类型⑴OLTP（联机事务处理）⑵DSS（决策支持系统）⑶EIS（行政信息系统）⑷OA（办公室自动化）⑸按其系统结构分为单机、Unix多用户、网络多用户、客户机／服务器、集中式、分布式、集中分布式等。目前，世界上比较流行的数据库管理系统（DMS）有⑴高档数据库产品，如Informix，Oracle，Sybase，Progress，Unify等⑵中、低档数据库产品，如DBASE，Paradox，Super－Base，Foxpro，Clipper，SQLBase，Focus等；⑶数据库开发工具，如Access，VisualBasic，Uniface，PowerBuilder，Q＋EDatabaseEditor等。第九页，共六十六页，2022年，8月28日计算机病毒的特征⑴能够将自身复制到其他程序中。⑵不独立以文件形式存在，仅附加在别的程序上。当调用该程序运行时，此病毒则首先运行。防治病毒的步骤：

⑴不要用软盘启动机器

⑵不要运行来路不明的软件

⑶定期备份重要系统数据

⑷重要的数据盘，程序盘应写保护

⑸使用杀毒软件检查和清除病毒第十页，共六十六页，2022年，8月28日计算机的组成和工作原理1、存储程序——内存；执行程序——CPU2、机器指令是计算机直接识别和执行操作的命令，用其编写的程序称为机器语言程序，所有指令的集合称为指令系统。格式：操作码和地址码；类型：操作类指令和控制转移类指令3、计算机硬件系统由五个基本组成部分：运算器、控制器、存储器、输入设备、输出设备4、CPU由运算器（ALU）、数据寄存器（DR）、指令寄存器（IR）程序计数器（PC）、地址寄存器、操作控制器第十一页，共六十六页，2022年，8月28日1、R进制转换为十进制基数为R的数字，只要将各位数字与它的权相乘，其积相加,和数就是十进制数（xp…x0.x-1…x-k）R=（）10例：1101101.01012=1×2°＋0×21＋1×22+1×23十0×24＋1×25＋1×26+0×2-1+1×2-2＋0×2-3+1×2-4=109.3125当从R进制转换到十进制时，可以把小数点作为起点，分别向左右两边进行，即对其整数部分和小数部分分别转换。对于二进制来说，只要把数位是1的那些位的权值相加，其和就是等效的十进制数。进位计数制之间的转换问题第十二页，共六十六页，2022年，8月28日2、十进制转换为R进制

将此数分成整数与小数两部分分别转换，然后再拼接起来。＋进制整数转换成R进制的整数，可用十进制数连续地除以R，其余数即为R系统的各位系数。此方法称之除R取余法。例如：将5710转换为二进制数十进制小数转换成R进制时，可连续地乘以R，直到小数部分为0，或达到所要求的精度为止（小数部分可能永不为零），得到的整数即组成R进制的小数部分，此法称为“乘R取整”例：将0.312510转换成二进制数0.3125×2=0.6250.625×2=1.250.25×2=0.50.5×2=1.0第十三页，共六十六页，2022年，8月28日3、二、八、十六进制的相互转换即每位八进制数相当于三位二进制数，每位十六进制数相当于四位二进制数。在转换时，位组划分是以小数点为中心向左右两边延伸，中间的0不能省略，两头不够时可以补0。例如：将1011010.10­2转换成八进制和十六进制数001011010.1001011010.102＝132.48132.401011010.10001011010.102=5A.816

5A.8将十六进制数F7.28变为二进制数F7.28F7.2816=11110111.00101211110111.00101000

将八进制数25.63转换为二进制数25．6325.638＝10101.110011210101.110011

第十四页，共六十六页，2022年，8月28日三、在计算机中带符号数的表示法1、机器数与真值规定在数的前面增设一位符号位，正数符号位用“0”表示，负数符号位用“1”表示。为了区别原来的数与它在计算机中的表示形式，我们将已经数码化了的带符号数称为机器数，而把原来的数称为机器数的真值。例如N1=+1001100、N2=-1001100为真值，其在计算机中的表示01001100和11001100为机器数。2、原码〈trueform〉

在用二进制原码表示的数中，符号位为0表示正数，符号位为1表示负数，其余各位表示数值部分。这种表示法称为原码表示法。字长为n的数（包括符号位）的原码表示法可定义为[x]原=若真值丨x丨＜1，其原码表示法可定义为[x]原=例如对于8位二进制原码[+0]原=00000000，[-0]原=10000000[-1101001]原=10000000-(-1101001)=11101001第十五页，共六十六页，2022年，8月28日3、补码（two’scomplement）即[x]补＝模+x对于正数，[x]补=x，正数的补码就是该正数本身。对于负数，[x]补=2n+x(mod2n)。[+0]补＝[-0]补＝00…0[-2n-1]补=2n-2n-1=2n-1

4、反码〈0ne’sComplement〉对于正数，它的反码表示与原码相同。即[x]反=[x]原对于负数，则除符号位仍为“1”外，其余各位“1”换成”0”，”0”换成1”，即得到反码[X]反。例如[-1101001]反=10010110。对于0，它的反码有两种表示:[+0]反=00…0[-0]反=11…1当x为正数时，[x]反=[x]原=[x]补=x；当x为负数时，[x]补=2n+x=(2n-1)+x+1=[x]反+1，即[x]原除符号位外求反加1。若把[x]补除符号位外求反加1，就得到[x]原，即[[x]补]补=[x]原。例如x=-1101001。[x]原=11101001，[x]补=10010111,[[x]补]补=11101001=[x]原。第十六页，共六十六页，2022年，8月28日5、补码的加减法运算⑴补码的加法运算在计算机中进行两个带符号数的加法运算时，只要将给定的真值用补码表示，就可以直接进行加法运算。在运算过程中不必判断加数和被加数的正负，一律做加法，最后将结果转换为真值即可。⑵补码的减法运算

对于补码的减法运算，由于存在x-y=x+(-y)，因此[x-y]补=[x+(-y)]补=[x]补+[-y]补(mod2n)其中[-y]补=[[y]补]补。第十七页，共六十六页，2022年，8月28日信息存储单位⑴位（bit，缩写为b）：度量数据的最小单位，表示一位二进制信息。⑵字节(byte，缩写为B)：一个字节由八位二进制数字组成（lbyte＝8bit）。字节是信息存储中最常用的基本单位。计算机存储器（包括内存与外存）通常也是以多少字节来表示它的容量。常用的单位有：KB1K=1024，MB1M=1024K，GB1G=1024M⑶字（word）：字是位的组合，并作为一个独立的信息单位处理。字又称为计算机字，它的含意取决于机器的类型、字长以及使用者的要求。常用的固定字长有8位、16位、32位等。信息单位用来描述机器内部数据格式，即数据（包括指令）在机器内的排列形式，如单字节数据，可变长数据（以字节为单位组成几种不同长度的数据格式）等。⑷机器字长：在讨论信息单位时，还有一个与机器硬件指标有关的单位，这就是机器字长。机器字长一般是指参加运算的寄存器所含有的二进制数的位数，它代表了机器的精度。机器的功能设计决定了机器的字长。一般大型机用于数值计算，为保证足够的精度，需要较长的字长，如32位、64位等。而小型机、微型机、微机一般字长为16位、32位等。第十八页，共六十六页，2022年，8月28日非数值信息的表示西文字符编码⑴ASCII码——“美国信息交换标准代码”的简称。ASCII码包括0～9十个数字，大小写英文字母及专用符号等95种可打印字符，还有33种控制字符（如回车、换行等）。一个字符的ASCII码通常占一个字节，用七位二进制数编码组成，所以ASCII码最多可表示128个不同的符号。最高位作为校验码，以便提高字符信息传输的可靠性。数字和字母的ASCII码按照数字递增顺序或字典顺序排列排列，大写字母和小写字母的ASCII码是不同的。⑵EBCDIC码——美国IBM公司在它的各类机器上广泛使用的一种信息代码。一个字符的EBCDIC码占用一个字符，用八位二进制码表示信息，最多可以表示出256个不同代码。

中文信息编码目前的汉字编码方案有二字节、三字节甚至四字节的。下面我们主要介绍“国家标准信息交换用汉字编码”（CB2312-80标淮），以下简称国标码。国际码是二字节码，用二个七位二进制数编码表示一个汉字。目前国标码收人6763个汉字，其中一级汉字（最常用）3755个，二级汉字3008个，另外还包括682个西文字符、图符。在计算机内部，汉字编码和西文编码是共存的。区分的方法之一是对于二字节的国标码，将二个字节的最高位都置成1，而ASCIl码所用字节最高位保持0，然后由软件（或硬件）根据字节最高位来作出判断。第十九页，共六十六页，2022年，8月28日“多媒体技术”就是用计算机交互地综合处理文本、图形、图象、动画、音频及视频影象等多种信息，并使这些信息建立逻辑连接。

第二十页，共六十六页，2022年，8月28日1、音频信号处理（声卡）：录入、处理重放信号；用MIDI技术合成音乐2、图形和图象处理：真彩色卡；图象采集卡；图象信号压缩技术；3、视频处理：实时录象和压缩视频图象的硬件解压缩卡；软件解压缩技术多媒体计算机的基本配置WINDOWS9X以上版本的操作系统和相应的硬件标准多媒体计算机的功能第二十一页，共六十六页，2022年，8月28日CD—ROM（高密度盘，即光盘）通过光学方式（使用激光束）读写信息技术标准1、数据传输率2、平均搜索时间第二十二页，共六十六页，2022年，8月28日色彩数目分辨率特点16640*480Windows的最低配置、显示速度最快256800*600性能虽好一些，但易产生调色板的冲突655361024*768全彩的显示模式，色彩逼真，不会再有调色板的冲突。16M1284*1024高等级的3D绘图软件和专业级的视频录制人员使用的真彩色模式，要求更多的RAM在显示卡和主机板上，CPU最好也是顶级的。显示卡

水平分辨率×垂直分辨率×色彩数目＝显示存储空间显示加速：VRAM、EDORAM，WindowsRAM，RamlbusDRAM显示模式

第二十三页，共六十六页，2022年，8月28日1、屏幕由象素组成2、主要部件（电子枪、荧光屏遮罩、荧光屏）3、电子束由左而右、由上而下周期性扫描产生持续稳定的画面4、红、绿、蓝三个电子枪的亮度决定颜色5、扫描频率更高、并能自动调整扫描频率显示器第二十四页，共六十六页，2022年，8月28日数据压缩和解压缩技术

静止图像压缩标准JPEG（JointPhotographicExpertsCroup）动态图像压缩标准MPEG（MovingPictureExpertsCroup）多通道的动态图像压缩标准MP×64

第二十五页，共六十六页，2022年，8月28日相关名词

位图：由一点一点的像素点排成矩阵组成的，其中每一个像素点都可以是任意颜色。

向量图：用向量代表图中所表现的元素。像素：图形的最小组成单位

真彩色：人的眼睛能够分辨出的颜色大约有1万6千多种，为了能表现出这么多种色彩，我们得用24bit（224=16M）来描述一个像素的颜色，这种显示模式就称为真彩色。RGB模式：分别代表红、绿、蓝三种颜色，计算机以RGB模式来定义计算机屏幕上的颜色。通过混色原理，不同比例的RGB色彩可调和出无穷多种颜色。HSB模式：分别表示色调（hue）、饱和度（saturation）、亮度（bright）。不同的色调代表不同的颜色；饱和度指的是某区域中，该颜色量的多少，饱和度越低，该区域看起来就越灰暗；亮度则是指颜色的亮、暗，极亮成白色，极暗则成黑色。相对于RGB模式，HSB模式设定颜色的方式可产生更好的视觉效果。第二十六页，共六十六页，2022年，8月28日多媒体信息处理工具图形制作平台FreeHand图像处理平台Photoshop动画制作平台AnimationPro

数字动画的类型：⑴基于模型的动画⑵帧动画动画中加人声音的方法⑴嵌人式—将声音文件经过转换合并到影片文件中去。⑵流式—声音与文件分开，在影片播放的各个时机启动声音文件音乐

⑴波形音频文件：通过现场录制和模数转化产生，存储量大⑵MIDI文件：使用键盘合成器和一个音序器制作和编辑，存储量小第二十七页，共六十六页，2022年，8月28日“雏形”：主机——终端系统

里程碑：APRANET网

广域网（WAN）：实现远距离的计算机之间的数据传输和信息共享的计算机网络。通信线路一般租用电话线路或铺设专用电缆。

局域网络（LIN）：为一个单位，或一个相对独立的局部范围内大量存在的微机能够相互通信、共享昂贵的外部设备（如大容量磁盘、激光打印机、绘图议等）、共享数据信息和应用程序而建立的计算机网络。通信线路一般不租用电话线路，使用专门铺设的线路。

互联网（Internet）：将遍布全球的子网通过连网协议集成到一个共享的、开放的、易于管理的主干网。

第二十八页，共六十六页，2022年，8月28日功能1、硬件资源共享2、软件资源共享3、数据和信息共享定义

计算机网络是由地理位置分散的、具有独立功能的多个计算机系统，经通讯设备和线路互相连接，并配以相应的网络软件，以实现通信和资源共享的系统第二十九页，共六十六页，2022年，8月28日计算机网络的物理组成网络中心主干机、服务器、网络工作站

共享的外部设备网卡通信线路（双绞线、同轴电缆和光缆、无线传输介质（如微波、红外线和激光等））

局部网络通信设备（中继器、集线器

）

网络互连设备（网桥、路由器和网关）网络软件（对等式网络操作系统、服务器上的网络操作系统）

第三十页，共六十六页，2022年，8月28日计算机网络的拓扑结构

总线拓扑星型拓扑

第三十一页，共六十六页，2022年，8月28日环型拓扑树型拓扑

第三十二页，共六十六页，2022年，8月28日计算机网络的体系结构

所谓网络体系结构就是对构成计算机网络的各组成部分之间的关系及所要实现功能的一组精确定义。国际标准化组织（ISO）提出的开放系统互联参考模型（OSI）已成为网络体系结构的标准第三十三页，共六十六页，2022年，8月28日Internet使用TCP/IP网络体系结构TCP/IP的层号TCP/IP的层次名

对应OSI模型的层次3应用层（ftp和telnet等协议）应用层、表示层、会话层

2传输控制协议TCP传输层1

网际协议IP网络层

第三十四页，共六十六页，2022年，8月28日计算机网络应用模式

客户机/服务器模型：将应用分成客户机和服务器两大部分，并将它分配到整个网络上。由服务器提供资源，通常执行后台功能；而客户机使用服务器，通常执行前台功能。文件服务器：提供操作系统中文件管理的各种功能（网络文件的访问方式：文件传输和文件访问）打印服务器：将一台或几台打印机物理地连接到打印服务器上，可为多个客户机用户轮流使用数据库服务器：侧重于传统数据库管理系统的功能（如数据的定义及存取、数据的安全性与完整性、并发控制及事务处理等）的服务器远程登录：通过用户帐号访问远地系统的资源第三十五页，共六十六页，2022年，8月28日Internet网络地址

IP地址:

网络数网络主机数主机数A类网络126163870642064770064B类网络16256645161048872096C类网络2064512254524386048总计20848943638028208域名（或称主机名称）:计算机主机名.子域名.子域名.最高层域名第三十六页，共六十六页，2022年，8月28日Internet应用

文件传输

(使用匿名文件传输服务（匿名FTP）网上软件分类：公共软件、免费软件、共享软件)远程登录（Telnet命令）

电子邮政服务

（电子邮箱地址：用户名＠计算机域名）网络新闻与公告牌服务

（网络新闻是由USENET在Internet中的新闻服务器节点之间进行传递的，阅读新闻组的软件有OutlookExpress）信息查询服务

（最为流行的信息查询服务系统是万维网（WorldWideWeb），简称WWW，即基于“超文本”方式的信息查询技术）。超文本：非顺序的文本呈现超媒体：超文本和多媒体浏览环境下的应用Momepage是由HTML语言编写的文本文件，经过WWW浏览器的解释和处理后，网页显示在用户目前的是多媒体的超文本文件第三十七页，共六十六页，2022年，8月28日程序设计语言的组成

程序设计语言的基础是一组记号和规则。根据规则由记号构成的记号串的总体就是语言。包括语法：程序的结构或形式。编译系统会自动进行语法检验；

语义：程序的含义，亦即表示按照各种方法所表示的各个记号的特定含义，但不涉及使用者。语义的错误是在源程序编译通过后的运行过程中出现的，属于算法类的错误。

语用：程序和使用者的关系；

语言的成分⑴数据成分，用以描述程序中所涉及的数据；⑵运算成分，用以描述程序中所包含的运算；⑶控制成分，用以描述程序中的控制构造；⑷传输成分，用以表达程序中数据的传输。第三十八页，共六十六页，2022年，8月28日语言和程序设计的发展

第一代语言——机器语言

第二代语言——汇编语言

第三代语言——高级语言、算法语言（BASIC、FORTRAN、COBOL、Pascal、C）

第四代语言——非过程化语言（SQL语言）

第五代语言——智能性语言（PROLOG语言、LISP语言）

第三十九页，共六十六页，2022年，8月28日面向对象方法的主要概念

⑴对象——系统中用来描述客观事物的一个实体，是构成系统的一个基本单位，对象由两个主要因素组成：属性：描述对象静态特征的一个数据项；服务：描述对象动态特征的一个操作序列；⑵消息——对象之间通过服务请求发生联系，这种向对象发出的服务请求称为消息。⑶类——为了很好地控制软件的复杂度，将具有相同属性和服务的一组对象组成类。第四十页，共六十六页，2022年，8月28日面向对象语言分为两大阵营

⑴Smalltalk和Eiffel为代表的纯粹型面向对象语言，主要强调软件开发的探索性和原型化开发方法；⑵以C++、ObjectPascal为代表的混合型面向对象语言，主要扩充现有语言，强调运行时的时空效率；第四十一页，共六十六页，2022年，8月28日程序设计的特点

构造性:不同的人为解决同一问题编制的程序，其面貌颇不相同，然而，程序的功效却是等价的。严谨性:以上下文无关的形式语言实现。无法补充缺损信息、去掉冗余信息、将暂时不懂的信息暂时搁置起来，待下文或经过推理予以补充和理解叠加性:

一般是将自己设计的子程序尽量分割成独立的、功能明确单一的小模块，以便充分利用；甚至还会利用系统内的库函数。抽象性:把客观事物的描述抽象为数据和算法，并且利用抽象使得程序能够正确的映射客观事物。抽象是有层次的，不同层次上的抽象是相互独立和互相作用的。第四十二页，共六十六页，2022年，8月28日计算程序的运行结果

一、直接推理二、由流程图推断算法三、动态模拟

四、由底向上阅读分析

第四十三页，共六十六页，2022年，8月28日对于一些语句少、结构简单且可读性较强的程序，不妨通过分析程序流程，直接寻找其间蕴含的计算模型。{$n+}

varm,n,I:integer;t:extended;beginreadln(n,m);t:=1;fori:=1tomdot:=t*(n-i+1)/i;writeln(t:0:0);end.输入105输出：

第四十四页，共六十六页，2022年，8月28日【分析】由for循环可以看出t=，即i=1时，t=n；i=2时，t=n*(n-1)/2；i=3时，t=n*(n-1)/2*(n-2)/3；………i=m时，t=c(n,m)=n!/(m!*(n-m)!)

显然，这是求组合数。当输入n=10、m=5时，程序应输出252。这个算法的效率不错，因为计算与n和m的大小有直接的关系。所以，我们要设法使运算的中间结果尽可能地小。如果我们先把N~(N-M+1)这M个连续的自然数乘起来，再依次除以1~M就是一种不太明智的选择。上述程序先乘N除1，然后乘(N-1)除2，再乘(N-2)除3，……最后乘(N-M+1)除M。因为连续的K个自然数的积一定能被K!整除，所以在这一过程中不会出现除不尽的情况。同时也使得中间结果比较小，从而提高了运算速度。告诫读者的是，对于上述算法来说，n和m不能超过102。如果超过了这个上限，t就会溢出，尽管它采用了extended类型。第四十五页，共六十六页，2022年，8月28日对于一些易读性不十分好的程序，最好的办法是画流程图。其步骤如下

⑴跟着程序画流程图，一句一框；

⑵根据上下文的联系合并流程图。若前几句计算值都要代入后一表达式，则合并为一框。接连合并几次，使程序成为一个大功能块；

⑶由大功能块推断算法；

⑷代入输入值，计算结果。

第四十六页，共六十六页，2022年，8月28日label10,20,30;vars,p:string;i,k,n,j,m:integer;beginreadln(s);n:=length(s);readln(p);m:=length(p);i:=0;10:i:=i+1;j:=i;k:=1;20:ifs[j]<>p[k]thenbeginifi<n-m+1thengoto10;i:=0;goto30;endelseifk<mthenbeginj:=j+1;k:=k+1;goto20;end;30:writeln(i);end.输入输出

asabcdffdinfdi第四十七页，共六十六页，2022年，8月28日这个程序的功能是计算s串中与p匹配的子串的首指针。当程序输入asabcdffdinfdi程序应输出8，即s[8]…s[10]=p=‘fdi’。第四十八页，共六十六页，2022年，8月28日动态模拟方法是采用人工模仿机器执行程序的方法计算结果值。首先选择程序中比较重要的变量作为工作现场。人工执行程序时，只要按照时间先后一步步记录下现场的变化，就能最后得出程序的运算结果。其具体布置如下：

⑴画表，画出程序执行时要用的现场情况表；

⑵基本读懂各语句的功能

⑶走程序，即动态模拟程序。主要根据各语句的功能，按照程序执行路径的先后顺序逐项填写现场情况表，直至得出最后结果；

动态模拟方法对简单程序、尤其是循环次数少的程序是很有效的。但对语句多和计算过程长的程序，这个方法则由于模拟速度太慢而不实用。

第四十九页，共六十六页，2022年，8月28日vari,j:integer;a:array[1..3,1..3]ofinteger;beginfori:=1to3dobeginforj:=1to3dobeginifi=3thena[i,j]:=a[i-1,a[i-1,j]]+1elsea[i,j]:=j;write(a[i,j]);end;writelnend;readlnend.输出：

第五十页，共六十六页，2022年，8月28日ji123112321233234显然，最后应输出123123234第五十一页，共六十六页，2022年，8月28日vara,d:array[1..100]ofinteger;n,i,j,k,x,s:integer;beginn:=5;a[1]:=1;d[1]:=1;fori:=1tondobegins:=i+1;x:=0;forj:=1ton+1-idobegink:=s+x;x:=x+1;a[j+1]:=a[j]+k;write(a[j],'');end;writeln('...');d[i+1]:=d[i]+i;a[1]:=d[i+1];end;end.输出：

外循环内循环i=S=d[i+1]a[1]=k=x=a[j+1]=输出a[j]1222213123263343106454151056521152344315224295353149464201434774184252138363191345111151127262181256

611711最后应输出1361015…25914…4813…712…11…

第五十二页，共六十六页，2022年，8月28日由底向上分析的阅读分析方法就是在剖析了子程序和模块资源的基础上，建立对高层程序结构的理解，从而完成整个程序的阅读分析，即从最底层的子目标开始分析起，看它们做了哪些事情；然后分析上一层的子目标，看这些子目标在下一层子目标实现的基础上实现了哪些功能……。经过自底而上的阅读分析，最后得出计算模型。第五十三页，共六十六页，2022年，8月28日constlimit=3000；typetdata=array[0..limit]oflongint；varans，num：tdata；i，j，n：longint；procedureupdate(vara：tdata)；

varinti；beginfori：=0tolimit-1dobegininc(a[i+1]，a[i]div10)；

a[i]：=a[i]mod10；end；end；proceduremult(vara：tdata；b：integer)；

vari，j：integer；beginfori：=0tolimitdoa[i]：=a[i]*b；update(a)；end；

procedureadd(x，ob：longint)；

vari：longint；beginfori：=2toxdowhile(xmodi=0)dobegininc(num[i]，ob)；x：=xdivi；end；end；Beginread(n)；

fillchar(num，sizeof(num)，0)；fori：=0ton-1dobeginadd(i+1，-1)；add(n+n-i，1)；end；{for}add(n+1，-1)；

fillchar(ans，sizeof(ans)，0)；ans[0]：=1；

fori：=2tolimitdoforj:=1tonum[i]domult(ans，i)；

fori：=limitdownto0doif(ans[i]>0)thenbeginforj:=idownto0dowrite(ans[j])；writeln；break；end；{then}End.输入输出5

第五十四页，共六十六页，2022年，8月28日update(vara)是将数组a规整为高精度的十进制数组mult(vara，b)是将高精度的十进制数组a乘以整数b，积存储在a中。add(x，ob)计算因子表，ob=1,num←num*x；ob=-1，num←num/x。其中num[i]为因子i的个数主程序计算catalan数1/（n+1）*c(2*n,n)。显然n=5，则程序输出42(1/6*c(10,5))第五十五页，共六十六页，2022年，8月28日完善程序

填空内容：1、变量方面的填空2、循环方面的填空

3、分支转移方面的填空

4、主程序和子程序关系方面的填空

5、输入输出方面的填空

填空方法：

按照自顶向下的思维方法阅读程序——从主程序开始，沿控制层次向下阅读。在查到某一个子程序(子模块)时，比照题目给出的说明和调用它的“父程序(父模块)”，弄清该子程序(子模块)究竟要达到什么样的子目标，然后查程序，看它是如何实现这个子目标的。如果该子程序(子模块)有空格，则按照算法的逻辑进行填空。依次类推，直至最底层的子程序（子模块）中的空格全部填完为止。第五十六页，共六十六页，2022年，8月28日1、完善不含子程序的程序

首先划分各个子模块的层次结构，并确定每个子模块的子目标。然后自顶向下，根据子目标和上层子模块给出的线索，对当前层次的各个模块进行填空。依次类推，直至最底层的子模块中的空格全部填完为止。

求元素之和最大的子方阵：在m×n（m，n≤20）的正整数数字方阵中，找出一个p×q的子阵（1≤p≤m，1≤q≤n）使其元素之和最大。例如，下面5×4的数字阵中，元素之和最大的一个2×3子阵。5×4数字阵元素之和最大的2×3子阵为384221117952162103892712352161038第五十七页，共六十六页，2022年，8月28日vara:array[1..20,1..20]ofinteger;m,n,p,q,i,j,max,p1,q1,s,i1,j1:integer;beginfori:=1to20doforj:=1to20doa[i,j]:=0;readln(m,n);fori:=1tomdobeginforj:=1tondoread(a[i,j]);readlnend;readln(p,q);max:=0;

fori:=1tom-p+1doforj:=1ton-q+1dobegin

①;

fori1:=itop+i-1doforj1:=jtoq+j-1do

②;

ifs>maxthenbegin

③;p1:=i;q1:=jend;end;

fori:=p1to

④

dobeginforj:=q1to

⑤

dowrite(a[i,j]:3);writelnend;readlnend.第五十八页，共六十六页，2022年，8月28日模块1（初始化，白色）：方阵清零；读方阵规模；读方阵；读子阵规模；子阵的最大数和初始化模块2（湖蓝）通过枚举所有可能子阵，求数和最大的子阵。其中子模块1（深蓝）：累计（i,j）为左上角的子阵的数和子模块2（淡绿）：调整子阵的最大数和

模块3（红色）——输出最大数和的子阵。由此得出解①

s:=0②s:=s+a[i1,j1]③max:=s④p1+p-1⑤q1+q-1第五十九页，共六十六页，2022年，8月28日以下程序完成对数组每个元素向后移动n个单位。数组元素的下标依次为0到m-1，对任意一个数组元素a[i]而言，它的值移动后将存储在数组元素a[(i+n)modm]中。例如，m=10，n=3，移动前数组中存储的数据如下前一行所示，则程序运行后数组中存储的数据如下后一行所示。038620276731163742163742038620276731第六十页，共六十六页，2022年，8月28日constmaxm=10000;vari,k,m,n,rest,start,temp:longint;a:array[0..maxm]oflongint;beginwrite('inputm,n:');readln(m,n);fori:=0tom-1doa[i]:=random(100);writeln('beforemove');fori:=0tom-1dowrite(a[i]:5);writeln;rest:=m;start:=0;while①dobegin

k:=start;repeatk:=(k+n)modmuntilk<=start;

if

②

thenbegintemp:=a[k];repeata[k]:=a[(m*n+k-n)modm];k:=(m*n+k-n)modm;

③

untilk=start;

④

end;

⑤

end;writeln('aftermove');fori:=0tom-1dowrite(a[i]:5);writelnend.第六十一页，共六十六页，2022年，8月28日模块1——初始化

模块2——移动计算，其中子模块1：判断以a[k]开始的的循环链上的元素是否都未移动过

子模块2：若以a[k]开始的的循环链上的元素都未移动过，则该循环链进行移动

子模块3：寻找下一个未移动过的循环链

模块3——输出移动后的数组

由此得出解为①

rest>0或rest<>0②k=start③rest:=rest-1④a[(k+n)modm]:=temp或a[(start+n)modm]:=temp⑤start:=start+1第六十二页，共六十六页，2022年，8月28日完善含子程序结构的程序

如果子模块采用过程或函数，则通常以子程序为单位划分层次结构，这样可以使得其层次性相对不含子程序的程序来说要清晰一些。程序的任务是用0…9中的n个数字填入如下乘法运算的*处，数字可重复使用，且所用的数字至少有一个是素数，要求输出满足下列算式的方案数。***×**

******

****第六十三页，共六十六页，2022年，8月28日constp:setof0..9=[2,3,5,7];vars:setof0..9;n:integer;ans:longint;f:text;procedureinit;v