计算机奥赛初赛知识讲座

计算机奥赛初赛知识讲座

一、计算机的发展与应用

二、计算机组成与工作原理和信息的表示与存储

三、多媒体应用

四、计算机网络使用基础

五、程序设计语言基础

六、程序的阅读分析

世界上的第一台计算机（ENIAC）于1946年诞生在美国宾夕法尼亚

大学，由物理学家约翰・莫克利和工程师普雷斯伯・埃克特研制的.

特点：体积大，功率大,重量大,1秒钟5000次加法

⑴计算机的发展历经了哪几个阶段；

年代元件处理速度

第一代1946-1958电子管几千条

第二代1959-1964晶体管几百万条

第三代1965-1970集成电路几千万条

第四代1971—至今大规模集成数亿条以上

电路

第五代

NC——网络计算机（将整个网络看成一个巨大的磁盘驱动器，数

据和文件存储在服务器）

非冯・诺依曼式的计算机模型（以人脑神经系统处理信息的原理为

基础）：生物计算机、光子计算机、量子计算机

我国的计算机发展情况

・我国从1956年开始计算机的科研和教学工作;

・1960年我国第一台自行设计的通用电子计算机107机诞生

1964年我国研制成大型通用电子计算机119机；

・1983年每秒运行一亿次的银河巨型计算机在国防科技大学诞生;

1992年研制成功每秒运行10亿次的“银河H”巨型计算机；

1997年又研制成功每秒运行130亿次的“银河III”巨型计算机；

.我国较有名的微型计算机品牌有：“联想”、“长城”、“方且

计算机发展史上的里程碑——计算机存储程

序的工作原理（冯•诺依曼原理）

美籍匈牙利数学家冯•诺依曼（vonNeumaml）在1946年提出的，其思想

是，在计算机中设置存储器，将符号化的计算步骤存放在存储器中，然

后依次取出存储的内容，由一个被称之为控制器的部件进行译码，译码

结果在一个被称为运算器的部件中进行计算，从而实现计算机工作的自

动化（运算器和控制器统称为CPU）。冯・诺依曼依据此原理设计出一个

完整的计算机雏形，并确定了计算机的五大组成部分和基本的工作方法。

其理论要点如下：

1、计算机硬件设备由存储器、运算器、控制器、输入设备和输出

设备5部分组成。

2、存储程序思想——把计算过程描述为由许多命令按一定顺序组

成的程序，然后把程序和数据一起输入计算机，计算机对已存入的

程序和数据处理后，输出结果。

什么叫cisc和rise?

Cisc:复杂指令系统计算机.

Rise:简单指令系统计算机

1.计算机的系统组成

计算机系统由软件和硬件两部分组成。硬件即构成计算机的电子元

器件；软件即程序和有关文档资料。

计算机硬件由五大部分组成：运算器、控制器、存储器、输入设备、

输出设备。

没有装载软件的计算机称为裸机

输入设备：键盘、鼠标、扫描仪，手写板，话筒，摄影机，触摸板,视频输

入设备•条形码扫描器等。

输出设备：显示器、打印机、绘图仪等。

中央处理器(CPUCentralProcessingUnit)

由运算器、控制器和一些寄存器组成；

运算器进行各种算术运算和逻辑运算；

控制器是计算机的指挥系统；

CPU的主要性能指标是主频和字长。

存储器：具有记忆功能的物理器件，用于存储信息。

存储器分为内存和外存

①内存是半导体存储器（主存）中央处理器能直接访问的存储器称为内部存储器：

它分为只读存储器（ROM）和随机存储器（RAM）和高速缓冲存储器（Cache）；

ROM:只能读，不能用普通方法写入，通常由厂家生产时写入，写入后数据不容

易丢失，也可以用特殊方法（如紫外线擦除（EPROM）或电擦除

（EEPROM」存储器）；断电后内容不丢失.

RAM:可读可写，断电后内容全部丢失；

Cache:因为CPU读写RAM的时间需要等待，为了减少等待时间，在RAM和CPU

间需要设置高速缓存Cache,断电后其内容丢失。

②外存：中央处理器不能直接访问的存储器称为外部存储器，外部存储器中的信

息必须调入内存后才能为中央处理器处理.

磁性存储器软盘和硬盘；光电存储器光盘，还有u盘,mp3,mp4,

移动硬盘等它们可以作为永久存器；

硬盘分为转速7200转/分和5400转/分等多种，容量为10G20G200G等

软盘：3.5英寸/1.44MB

光盘，等等

③存储器的两个D重V要D技CD术-R指O标M「存取速度和存储容量。内存的存取速度最快（与

CPU速度相匹配），软盘存取速度最慢。

存储容量是指存储的信息量，它用字节（Byte）作为基本单位，

1字节用8位二进制数表示，1KB=1024B,1MB=1024KB,IGB=1024MB

(2)计算机的软件系统

计算机的软件主要分为系统软件和应用软件两类：

①系统软件：为了使用和管理计算机的软件，主要有操作系统软件

如,WINDOWS95/98/2000/NT4.0/XP/VISTA、DOS6.0、

UNIXLINUX等；

WINDOWS95/98/2000/NT4.0是单用户多任务可视化图形界

面，而DOS是字符命令形式的单用户单任务的操作系统。

Unixlinux是多用户多任务的操作系统

②应用软件：为了某个应用目的而编写的软件，主要有辅助教学软

件(CAI)、辅助设计软件(CAD)、文字处理软件、工具软件以及其他

的应用软件。

操作系统是计算机系统中的一种系统软件，它

能对计算机系统中的软件和硬件资源进行有效地

管理和控制，合理地组织计算机的工作流程，为

用户提供一个使用计算机的工作环境。

手工操作n管理程序一单道批处理系统

=＞多道批处理系统一分时系统

二＞实时操作系统「网络操作系统

DOS——单用户的唯一任务占用计算机上所

有的硬件和软件资源，所能访问的主存地址

空间太小。

Windows多作业、大内存管理、统一

的图形用户界面，并且发展到网络环境使

用

UNIX操作系统、Linux操作系统、Macintosh

OS

应用软件

X

计算机的类型：

按通途的不同：通用机和专用机

按运算速度，字长，存储容量等多方面因素：大型通用机，巨型机,

小型机，微型机

大型机：以国家为单位研制使用的,计算速度极快

巨型机：巨型机的研制水平，生产能力已成为一个国家经济和科技实

小型机：比巨型机小菽但比微型机大（速度）；

微型机:又称微机,个人计算机,pc等等，是以微型处理器（中央处理器）

为基础组成的.

1971年,美国的intel公司生产了第一块微型处理器intel4004

并以此为基础组成了第一台微机mcs-4

微型机的主要技术指标

1字长：一次计算能够直接处理的二进制数据的位数。单位为位（bit

2主频：指计算机主时钟在一秒钟内发出的脉冲数，在很大程度上

决定了计算机的运算速度。

3内存容量：是标志计算机处理信息能力强弱的一向技术指标。单

位为字节（BYTE）o

8BIT=1BYTE1024B=1KB1024KB=1MB

4外存容量：一般指软盘、硬盘、光盘。

一些基本的概念

位：计算机只认识由o或1组成的二进制数，二进制数中的每个o或1就是信息的

最小单位，称为“位"（bit）。

字节：是衡量计算机存贮容量的单位。一个8位的二进制数据单元称一个

字节（byte）o在计算机内部，一个字节可以表示一个数据，也可以表示

一个英文字母或其他特殊字符，二个字节可以表示一个汉字。

字：在计算机中，作为一个整体单元进行存贮和处理的一组二进制数。一台计算

机，字的二进制数的位数是固定的。

字长：一个字中包含二进制数位数的多少称为字长。字长是标志计算机精度的一

项技术指标。

存贮器编址：为了便于对计算机内的数据进行有效的管理和存贮，需要对内存单

元编号，即给每个存贮单元一个地址。每个存贮单元存放一个字节

的数据。如果需要对某一个存贮单元进行存贮，必须先知道该单元

的地址，然后才能对该单元进行信息的存取。

计算机的特点

(1):运算速度快

(2)：计算精度高

(3)：具有记忆和逻辑判断能力

(4)：自动处理能力

计算机的应用

(1)数值计算

(2)数据处理

(3)实时控制

(4)辅助教育

(5)辅助设计

(6)办公自动化

输入设备

键盘，鼠标，话筒，扫描仪

输出设备显示器，打印机，绘图仪

计算机硬件\存储器内存，外存，光盘

计(速度和容量

算

算

运

器

机^

系1中央处理器（CPU）

统

'操作系统

系统软件＜数据库管理程序

、计算机软件Y语言处理程序

应用软件OFFICE,FLASH,REALPLAY

计算机病毒

计算机病毒是一种程序，是人为设计的具有破坏性的程序

计算机病毒具有破坏性、传播性、可激发性、潜伏性、隐蔽性等特点

病毒的分类

(1)按病毒设计者的意图和破坏性大小，可将计算机病毒分为良性

毒和性病毒o

①良性病毒：这种而毒的目的不是为了破坏计算机系统，而只是

为了编制者表现自己。此类病毒破坏性较小，只是造成系统运

彳〒:市庶阵何工4介用户堂T作

②恶性病毒：金类病毒的目的是人4的破坏计算机系统的数据。

具有明显破坏目标，其破坏和危害性都很大，可能删除文件或

对硬盘进行非法的格式化。

(2)计算机病毒按照寄生方式可以分为下列四类：

①源码病毒：

②入侵病毒：

②操作系统病毒：

④外壳病毒：

病毒传染有两个条件：

(1)通过某个途径进入计算机：比如硬盘,软盘,U盘，网络下载，光盘，收发

电子邮件等等

(2)病毒是被激活的,一定要满足某个条件，病毒才会开始运行.比如某

个日期等等。

防治病毒的步骤：

⑴不要用软盘启动机器

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

⑶定期备份重要系统数据

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

⑸使用杀毒软件检查和清除病毒

进位计数制之间的转换问题

1、R进制转换为十进制

基数为R的数字，只要将各位数字与它的权相乘，其积相加,和数就

是十进制数

P

(xp...x0.x1...xk)R=(Z…)10

例：

1101101.01012

=1X2°+0X21+lX22+lX23-h0X24+lX25+lX26+0X2-1+lX2-2

+0义2-3+1X2-4

=109.3125

当从R进制转换到十进制时，可以把小数点作为起点，分别向左右

两边进行，即对其整数部分和小数部分分别转换。对于二进制来说,

只要把数位是1的那些位的权值相加，其和就是等效的十进制数。

2、十进制转换为R进制

将此数分成整数与小数两部分分别转换，然后再拼接起来。

+进制整数转换成R进制的整数，可用十进制数连续地除以R,其

余数即为R系统的各位系数。此方法称之除R取余法。例如：将

5710转换为二进制数

2|57余数

2128一1低位

%」；--二二二二：二S571产11100k

也31

2111_

01信1位

十进制小数转换成R进制时，可连续地乘以R,直到小数部分为0,

或达到所要求的精度为止（小数部分可能永不为零），得到的整

数即组成R进制的小数部分，此法称为“乘R取整”

例：将0.312510转换成二进制数

0.3125X2=0.6250.625X2=1.250.25X2=0.50.5X2=1.0

3、二、八、十六进制的相互转换

即每位八进制数相当于三位二进制数，每位十六进制数相当

于四位二进制数。在转换时，位组划分是以小数点为中心向

左右两边延伸，中间的0不能省略，两头不够时可以补0。

例如：将1011010.10-2转换成八进制和十六进制数

001011010.1001011010.10?=132.4„

132.4

01011010.10001011010.1029=5A.8,1,0

5A.8

将十六进制数F7.28变为二进制数

F7.28F7.28106=11110111.0010L2

11110111.00101000

将八进制数25.63转换为二进制数

25.6325.638o=10101.110011Z,

10101.110011

三、在计算机中带符号数的表示法

1、机器数与真值

规定在数的前面增设一位符号位，正数符号位用“0”表示，负数符号位用“1”表示。

为了区别原来的数与它在计算机中的表示形式，我们将已经数码化了的带符号数

称为机器数，而把原来的数称为机器数的真值。例如Ni=+1001100、2=-1001100为

真值，其在计算机中的表示01001100和11001100为机器数。

在计算机中，数据是以补码的形式存储的

2、原码〈trueform〉

在用二进制原码表示的数中，符号位为0表示正数，符号位为1表示负数，其余各

位表示数值部分。这种表示法称为原码表示法。

例如对于8位二进制原码

[+0]原=00000000,[-0]原=10000000

[-1101001]原=11101001

规律：正数的原码是它本身，负数的原码是取绝对值后，在最高位

（左端）补“1”。

3、反码(two5scomplement)

一个负数的原码符号位不变，其余各位按位取反就

是机器数的反码表示法。正数的反码与原码相同。

[+0]补=[-0]补=00…0

[-2仆1]补=2n-2n-l=2n-l

4、补码(One5sComplement)

(1)正数的补码表示与原码相同；

(2)负数的补码是将原码符号位保持“1”之后，其余各位

按位取反，末位再加1便得到补码，即取其原码的反码再加

“1”：冈补二冈反+1。

补码和反码之间的运算，可以先转换成原码，再计算出结果，再将结果转成相应的码制

信息存储单位

⑴位（bit,缩写为b）:度量数据的最小单位，表示一位二进制信息。

⑵字节（byte,缩写为B）：一个字节由八位二进制数字组成（lbyte=8bit）o

字节是信息存储中最常用的基本单位。

计算机存储器（包括内存与外存）通常也是以多少字节来表示它的容量。

常用的单位有：KB1K=1O24,MB1M=1O24K,GB1G=1O24M

⑶字（word）：字是位的组合，并作为一个独立的信息单位处理。字又称

为计算机字，它的含意取决于机器的类型、字长以及使用者的要求。常用

的固定字长有8位、16位、32位等。

信息单位用来描述机器内部数据格式，即数据（包括指令）在机器内的排

列形式，如单字节数据，可变长数据（以字节为单位组成几种不同长度的

数据格式）等。

⑷机器字长：在讨论信息单位时，还有一个与机器硬件指标有关的单位，

这就是机器字长。机器字长一般是指参加运算的寄存器所含有的二进制数

的位数，它代表了机器的精度。机器的功能设计决定了机器的字长。一般

大型机用于数值计算，为保证足够的精度，需要较长的字长，如32位、64

位等。而小型机、微型机、微机一般字长为16位、32位等。

非数值信息的表示

西文字符编码

⑴ASCII码——“美国信息交换标准代码”的简称。ASCII码包括0〜9十个数字，大小写

英文字母及专用符号等95种可打印字符，还有33种控制字符（如回车、换行等）。一个

字符的ASCII码通常占一个字节，用七位二进制数编码组成，所以ASCII码最多可表示

128个不同的符号。最高位作为校验码，以便提高字符信息传输的可靠性。

数字和字母的ASCII码按照数字递增顺序或字典顺序排列排列，大写字母和小写字母的

ASCII码是不同的。

⑵EBCDIC码——美国IBM公司在它的各类机器上广泛使用的一种信息代码。一个字符的

EBCDIC码占用一个字符，用八位二进制码表示信息，最多可以表示出256个不同代码。

中文信息编码

目前的汉字编码方案有二字节、三字节甚至四字节的。下面我们主要介绍“国家标准信

息交换用汉字编码”（CB2312-80标淮），以下简称国标码。

国际码是二字节码，用二个七位二进制数编码表示一个汉字。目前国标码收人6763个汉

字，其中一级汉字（最常用）3755个，二级汉字3008个，另外还包括682个西文字符、图

符。在计算机内部，汉字编码和西文编码是共存的。区分的方法之一是对于二字节的国

标码，将二个字节的最高位都置成1,而ASCII码所用字节最高位保持0,然后由软件（或

硬件）根据字节最高位来作出判断。N

“多媒体技术”就是用计算机交互地综合处理文本、

图形、图象、动画、音频及视频影象等多种信息，

并使这些信息建立逻辑连接。

多媒体计算机的功能

•1、音频信号处理（声卡）：录入、处理重放

信号；用MIDI技术合成音乐

•2、图形和图象处理：真彩色卡；图象采集卡;

图象信号压缩技术；

•3、视频处理：实时录象和压缩视频图象的硬

件解压缩卡；软件解压缩技术

多媒体计算机的基本配置

WINDOWS9X以上版本的操作系统和相

应的硬件标准

•CD-ROM（高密度盘，即光盘）

通过光学方式（使用激光束）读写信息

技术标准

1、数据传输率

2、平均搜索时间

CD-ROM650M

DVD3G~9G

显示模式

色彩数目分辨率特点

16640*480Windows的最低配置、显示速度最快

256800*600性能虽好•些，但易产生调色板的冲突

655361024*768全彩的显不模式，色彩逼真，不会再有调色板的

冲突。

16M1284*1024高等级的3D绘图软件和专业级的视频录匍J人员使

用的真彩色模式，要求更多的RAM在显示卡和主

机板上，CPU最好也是顶级的。

显示卡

水平分辨率X垂直分辨率X色彩数目=显示存储空间

显示加速：VRAM、EDORAM,WindowsRAM,RamlbusDRAM

常向显示芯片：ATINVIDIAIntel810/815ntel845/852/865SiSS3VIA

显示器

•1、屏幕由象素组成

•2、主要部件(电子枪、荧光屏遮罩、荧光屏)

•3、电子束由左而右、由上而下周期性扫描产生持

续稳定的画面

•4、红、绿、蓝三个电子枪的亮度决定颜色

•5、扫描频率更高、并能自动调整扫描频率

显示器分为：液晶显示器(LCD)纯平显示器

球面显示器(crt)

数据压缩和解压缩技术

静止图像压缩标准JPEG(Joint

PhotographicExpertsCroup)

动态图像压缩标准MPEG(Moving

PictureExpertsCroup)

多通道的动态图像压缩标准MPX64

相关名词

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

任意颜色。

向量图：用向量代表图中所表现的元素。

像素：图形的最小组成单位

真彩色：人的眼睛能够分辨出的颜色大约有1万6千多种，为了能表现出

这么多种色彩，我们得用24bit(224=16M)来描述一个像素的颜色，这种

显示模式就称为真彩色。

RGB模式：分别代表红、绿、蓝三种颜色，计算机以RGB模式来定义计算

机屏幕上的颜色。通过混色原理，不同比例的RGB色彩可调和出无穷多种

颜色。

HSB模式：分别表示色调(hue)、饱和度(saturation)、亮度(bright)。

不同的色调代表不同的颜色；饱和度指的是某区域中，该颜色量的多少，

饱和度越低，该区域看起来就越灰暗；亮度则是指颜色的亮、暗，极亮成

白色，极暗则成黑色。相对于RGB模式，HSB模式设定颜色的方式可产生

更好的视觉效果。

多媒体信息处理工具

图形制作平台FreeHand

图像处理平台PhotoshopACDSeeCorelDRAWAcrobatPro

Fireworks

动画制作平台AnimationProflashmaya3dsmax

视频处理软件primere绘声绘影moviemaker

MacromediaDirector

网页制作工具DreamweaverFrontPage

数据库中最常用的模型有：

层次模型，网状模型，关系模型，面向对象模型

一对多多对多二维表格结构表达实体集

常用的数据库系统：

accessoracledb2SQLVisualFoxpro

“雏形”：主机——终端系统

里程碑：APRANET网

广域网（WAN）：实现远距离的计算机之间的数据传输和

信息共享的计算机网络。通信线路一般租用电话线路或铺设

专用电缆。

局域网络（LAN）：为一个单位，或一个相对独立的局部范

围内大量存在的微机能够相互通信、共享昂贵的外部设备

（如大容量磁盘、激光打印机、绘图议等）、共享数据信息

和应用程序而建立的计算机网络。通信线路一般不租用电话

线路，使用专门铺设的线路。

互联网（Internet）：将遍布全球的子网通过连网协议集成到

一个共享的、开放的、易于管理的主干网。

功能

•1、硬件资源共享

・2、软件资源共享

・3、数据和信息共享

定义

计算机网络是由地理位置分散的、具

有独立功能的多个计算机系统，经通讯

设备和线路互相连接，并配以相应的网

络软件，以实现通信和资源共享的系统

简单讲：计算机网络是由计算机软件、计算机硬件与通信设备组成。

计算机网络的物理组成

•网络中心主干机、服务器、网络工作站

•共享的外部设备

•网卡

•通信线路（双绞线、同轴电缆和光缆、无线传输介质（如微波、红

外线和激光等））

•局部网络通信设备（中继器、集线器交换机）

•网络互连设备（网桥、路由器和网关）

•网络软件（对等式网络操作系统、服务器上的网络操作系统）

计算机网络的拓扑结构

•总线拓扑

环型拓扑

2/—中泰器

OL

3—4

5Q7怜输介质

树型拓扑

[5□

计算机网络的体系结构

・所谓网络体系结构就是对构成计算机网络的各组成部分之间的关系及所要

实现功能的一组精确定义。国际标准化组织（ISO）提出的开放系统互联

参考模型（OSI）已成为网络体系结构的标准

Internet使用TCP/lP网络体系结构

TCP/IP的层号TCP/IP的层次名对应OSI模型的层次

3应用层（ftp和应用层、表示层、

telnet等协议）会话层

2传输控制协议传输层

TCP

1网际协议IP网络层

计算机网络应用模式

•客户机/服务器模型：将应用分成客户机和服务器两大部分,

并将它分配到整个网络上。由服务器提供资源，通常执行后台功能；而客

户机使用服务器，通常执行前台功能。

•文件服务器：提供操作系统中文件管理的各种功能（网络文件的

访问方式：文件传输和文件访问）

•打印服务器：将一台或几台打印机物理地连接到打印服务器上，

可为多个客户机用户轮流使用

•数据库服务器：侧重于传统数据库管理系统的功能（如数据的

定义及存取、数据的安全性与完整性、并发控制及事务处理等）的服务器

・远程登录：通过用户帐号访问远地系统的资源

Internet网络地址

D1831

磅地址：0|网络号主机号

地址：

•1PD121631

B类地址：10网络号主机号

01：232431

C类地址：110网络号主机号

网络数网络主机数主机数

A类网络126163870642064770064

B类网络16256645161048872096

C类网络2064512254524386048

总计20848943638028208

域名（或称主机名称）：计算机主机名.子域名.子域名.最高层域名

Internet应用

•文件传输（使用匿名文件传输服务（匿名FTP）网上软件分类：公

共软件、免费软件、共享软件）

•远程登录（Telnet命令）

•电子邮政服务（电子邮箱地址：用户名@计算机域名）

•网络新闻与公告牌服务（网络新闻是由USENET在Internet中

的新闻服务器节点之间进行传递的，阅读新闻组的软件有Outlook

Express）

•信息查询服务（最为流行的信息查询服务系统是万维网（World

WideWeb）,简称WWW,即基于“超文本”方式的信息查询技术）。

•超文本：非顺序的文本呈现

•超媒体：超文本和多媒体浏览环境下的应用

•Momepage是由HTML语言编写的文本文件，经过WWW浏览器的解释

和处理后，网页显示在用户目前的是多媒体的超文本文件

语言和程序设计的发展

•第一代语言——机器语言

•第二代语言——汇编语言

•第三代语言——高级语言、算法语言（BASIC、

FORTRAN>COBOL、PascakC）

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

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

LISP语言）

计算程序的运行结果

•一、直接推理

二、由流程图推断算法

三、动态模拟

I、由底向上阅读分析

对于一些语句少、结构简单且可读性较强的程序，不妨

通过分析程序流程，直接寻找其间蕴含的计算模型。

{$n+)

var

m,n,I:integer;

t:extended;

begin

readln(n,m);

t:=l;

fori:=ltomdot:=t*(n-i+l)/i;

writeln(t:0:0);

end.

输入

105

输出：

【分析】由for循环可以看出

t=…即

/-I

i=l时，t=n；

i=2时,t=n*(n-l)/2；

i=3时，t=n*(n-l)/2*(n-2)/3；

i=m时,t=c(n,m)=n!/(m!*(n-m)!)

显然，这是求组合数。当输入n=10、m=5时，程序应输出252。

这个算法的效率不错，因为计算与n和m的大小有直接的关系。所以，我们

要设法使运算的中间结果尽可能地小。如果我们先把NMN-M+1)这M个连

续的自然数乘起来，再依次除以1〜M就是一种不太明智的选择。上述程序

先乘N除1,然后乘(N-1)除2,再乘(N-2)除3,……最后乘(N-M+1)除M。因

为连续的K个自然数的积一定能被K!整除，所以在这一过程中不会出现除

不尽的情况。同时也使得中间结果比较小，从而提高了运算速度。告诫读

者的是，对于上述算法来说，n和m不能超过102。如果超过了这个上限，t

就会溢出，尽管它采用了extended类型。

对于一些易读性不十分好的程序，最

好的办法是画流程图。其步骤如下

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

⑵根据上下文的联系合并流程图。

若前几句计算值都要代入后一表达式,

则合并为一框。接连合并几次，使程

序成为一个大功能块；

⑶由大功能块推断算法；

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

label10,20,30;30:

varwriteln(i);

s,p:string;end.

i,k,n,j,m:integer;输入输出

beginasabcdffdin

readln(s);n:=Iength(s);

fdi

readln(p);m:=length(p);

i:=0;

10:i:=i+l;j:=i;k:=l;

20:ifs[j]<>p[k]

thenbegin

ifi<n-m+lthengoto10;i:=0;goto30;

end

elseifk<m

thenbeginj:=j+l;k:=k+l;goto20;end;

1.readln(s);n：=length(s);

2.readln(p);m：=length(p),

3.i：=0;

4.10：

5.i：=i+l;

6.j：=i；

7.k：=l；

8.20：

9.ifs[j]Op[k]4—15行

,,.夕Hi环

10.t+henbegin

11.ifthengoto10;8—15行

12.i：=0；内循环

13.goto30;

14.end

15.elseifk<mthenbeginj：=j+l,k：=k+l,goto20;end;一」

16.30：

17.wxiteln(i);

这个程序的功能是计算s串中与p匹配的子串的首指针。当程序

输入

asabcdffdin

fdi

程序应输出8,即s[8]...s[10]=p=，fd『。回

动态模拟方法是采用人工模仿机器执行程序的方

法计算结果值。首先选择程序中比较重要的变量

作为工作现场。人工执行程序时，只要按照时间

先后一步步记录下现场的变化，就能最后得出程

序的运算结果。其具体布置如下：

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

⑵基本读懂各语句的功能

⑶走程序，即动态模拟程序。主要根据各语句

的功能，按照程序执行路径的先后顺序逐项填写

现场情况表，直至得出最后结果；

动态模拟方法对简单程序、尤其是循环次数

少的程序是很有效的。但对语句多和计算过程长

的程序，这个方法则由于模拟速度太慢而不实用。

var

i,j:integer;

a:array[1..3,1..3]ofinteger;

begin

fori:=lto3do

begin

forj:=lto3do

begin

ifi=3thena[i,j]:=a[i-l,a[i-l,j]]+l

elsea[i,j]:=j;

write(a[i,j]);

end;

writein

end;

readln

end.

输出:

123

1123

2123

3234

显然，最后应输出

123

123

234

var

外循环内循环

a,d:array[1..100|ofinteger;is=d[i+l]a[l]=k=x=a[j+l]=输出a[j]

n,i,j,k,x,s:integer;12222131

begin23263

343106

n:=5;a[l]:=l;d[l]:=l;

4541510

fori:=ltondo5652115

begin23443152

s:=i+l;x:=0;24295

353149

forj:=lton+l-ido

4642014

begin

34774184

k:=s+x;x:=x+l;a[j+l]:=a[j]+k;252138

write(a[j]/，)；3631913

45111151127

end;

2621812

writeln(,...*);d[i+1]:=d[i]+i;a[1]:=d[i+1];

56611711

end;最后应输出

end.1361015…

输出：

25914…

4813…

712…

11…

要轴妻《£

要能G

为了实期

要破C

为了实现从

「要做I

要做E

要做£

为了实现1,要做M

为了实眄I要做N

要做/

要做M

由底向上分析的阅读分析方法就是在剖析了子程序和模块资

源的基础上，建立对高层程序结构的理解，从而完成整个程

序的阅读分析，即从最底层的子目标开始分析起，看它们做

了哪些事情；然后分析上一层的子目标，看这些子目标在下

一层子目标实现的基础上实现了哪些功能..・・・.。经过自底而

上的阅读分析，最后得出计算模型。

constproceduremult(vara：tdata；b：integer)；Begin

varread(n)；

limit=3000；

i,j：integer；fillchar(numsizeoRnum),0)；

type9

beginfori：=0ton-Ido

tdata=arrayoflongint；

fori：=0tolimitdoa[i]：=a[i]*b；begin

varupdate(a)；add(i+l,-1)；

ans,num：tdata；end；add(n+n-i,1)；

i,j,n：longint；end；{for}

procedureadd(x,ob：longint)；add(n+l,-1)；

procedureupdate(vara：tdata)；

varfillcharfansysizeof(ans)90)；

var

i：longint；ans[0]：=1；

inti；

beginfori：=2tolimitdo

beginfori：=2toxdoforj:=ltonum[i]domult(ansyi)；

fori：=0tolimit-1dowhile(xmodi=0)dofori：=limitdownto0do

beginbeginif(ans[i]>0)then

inc(num|ibob)；begin

inc(a[i+l],a[i]div10)；

x：=xdivi；forj:=idownto0dowrite(ans[j])；

a|i]：=a[i]mod10；

end；writein；break；

end；

end；end；{then}

end；End.

输入输出

5

第一层:主程序

第二层:

第三层:

update(vara)是将数组a规整为高精度的十进制数组

mult(vara,b)是将高精度的十进制数组a乘以整数b,积存

储在a中。

add(x,ob)计算因子表，ob=l,num—num*x；ob=-1,

num<—num/xo其中num[i]为因子i的个数

主程序计算Catalan数1/(n+1)*c(2*n,n)。显然n=5,则程

序输出42(1/62(10,5))

完善程序

•填空内容：

-1、变量方面的填空

-2、循环方面的填空

-3、分支转移方面的填空

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

-5、输入输出方面的填空

填空方法：

按照自顶向下的思维方法阅读程序一一从主程序开始，

沿控制层次向下阅读。在查到某一个子程序（子模块）时，比

照题目给出的说明和调用它的“父程序（父模块）”，弄清该

子程序（子模块）究竟要达到什么样的子目标，然后查程序，

看它是如何实现这个子目标的。如果该子程序（子模块）有空

格，则按照算法的逻辑进行填空。依次类推，直至最底层的

子程序（子模块）中的空格全部填完为止。

1、完善不含子程序的程序

首先划分各个子模块的层次结构，并确定每个子模块的子

目标。然后自顶向下，根据子目标和上层子模块给出的线索，

对当前层次的各个模块进行填空。依次类推，直至最底层的子

模块中的空格全部填完为止。

求元素之和最大的子方阵：在mxn(m,n<20)的正整数数字方阵中,

找出一个pXq的子阵14q《n)使其元素之和最大。例如，

下面5X4的数字阵中，元素之和最大的一个2X3子阵。

5X4数字阵元素之和最大的2X3子阵为

38422

11179

52162

10389

27123

fori:=ltom-p+1do

vara:array[1..20,1..20]ofinteger;

forj:=lton-q+1do

m,n,p,q,i,j,max,pl,ql,s,il,jl：integer;

begin

beginJ；

fori:=lto20doforil:=itop+i-1do

forj:=lto20doforjl:=jtoq+j-1do

a[i,j]：=0;②；

ifs>maxthenbegin

readln(m,n);

fori:=ltomdo

pl：=i；

begin

qi：=j

forj:=ltondoread(a[i,j]);end;

readlnend;

end;fori:=plto(4)do

readln(p,q);begin

forj:=qlto(5)do

max:=0;

write(a[i,j]:3);

writein

end;

readln

end.

模块1（初始化，白色）：方阵清零；读方阵规模；

读方阵；读子阵规模；子阵的最大数和初始化

模块2（湖蓝）通过枚举所有可能子阵，求数和最大

的子阵。其中

子模块1（深蓝）：累计（i,j）为左上角的子阵的数和

子模块2:调整子阵的最大数和

模块3（红色）——输出最大数和的子阵。

由此得出解

①s:=0②s:=s+a[il,jl]③max:=s④pl+p-1⑤ql+q-1

以下程序完成对数组每个元素向后移动n个

单位。数组元素的下标依次为0到m-1,对任

意一个数生元素a[i]而言，它的值移动后将存

储在数组元素a[(i+n)modm]中。

例如，m=10,n=3,移动前数组中存储的数

据如下前一行所示，则程序运行后数组中存

储的数据如下后一行所示。

038620276731163742

163742038620276731

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

var

i,k,m,n,rest,start,temp:longint;

a:array[O..maxm]of

longint;

begin

write(*input

readln(m,n);

fori:=0tom-1do

a[i]:=random(100);

writeln('beforemove*);

fori:=0tom-1dowrite(a[i]:5);

writein;⑤

rest:=m;start:=0;end;

while①dowriteln(,aftermove1);

beginfori:=0tom-1dowrite(a[i]:5);

k:=start;writeln

end.

模块1——初始化

模块2——移动计算，其中

子模块1：判断以a[k]开始的的循环链上的元素是否都未移