当前位置:首页 >> 学科竞赛 >>

2014NOIP初赛速成辅导(中国计算机学会出版)


一、 计算机的发展与应用

二、计算机组成与工作原理 和信息的表示与存储
三、多媒体应用 四、计算机网络使用基础

五、程序设计语言基础
六、程序的阅读分析

⑴计算机的发展历经了哪几个阶段; ⑵按照功能和规模,可将计算机分成哪几大 类,它们各自的分工是什么; ⑶武装计算机的软件系统包括了哪些东西

; ⑷计算机的发展怎样促使人类走向丰富多彩 的信息社会;

⑸用户在使用计算机时应该遵守哪些道德规 范;

计算机发展史上的里程碑——计算机存储程 序的工作原理
美籍匈牙利数学家冯· 诺依曼(von Neumaml)在1946年提出的,其思想 是,在计算机中设置存储器,将符号化的计算步骤存放在存储器中,然 后依次取出存储的内容,由一个被称之为控制器的部件进行译码,译码 结果在一个被称为运算器的部件中进行计算,从而实现计算机工作的自 动化(运算器和控制器统称为CPU)。冯· 诺依曼依据此原理设计出一个 完整的计算机雏形,并确定了计算机的五大组成部分和基本的工作方法。

第四代
VISI——大规模集成电路 CISC——复杂指令系统计算机 RCSC——精简指令系统计算机 非冯· 诺依曼式语言:lisp、prologo、f.p

第五代
NC——网络计算机(将整个网络看成一个巨大的 磁盘驱动器,数据和文件存储在服务器) 非冯· 诺依曼式的计算机模型(以人脑神经系统处 理信息的原理为基础):生物计算机、光子计算 机、量子计算机

用户
应用软件 系统软件

裸机

操作系统是计算机系统中的一种系统软件,它 能对计算机系统中的软件和硬件资源进行有效地 管理和控制,合理地组织计算机的工作流程,为 用户提供一个使用计算机的工作环境。 手工操作 管理程序 单道批处理系统 分时系统 网络操作系统

多道批处理系统 实时操作系统

DOS——单用户的唯一任务占用计算机上所 有的硬件和软件资源,所能访问的主存地址 空间太小。 Windows——多作业、大内存管理、统一 的图形用户界面 ,并且发展到网络环境使 用 UNIX操作系统 、Linux操作系统 、Macintosh OS

数据库技术的特性 ⑴最小冗余 ⑵数据共享

目前,世界上比较流行的数据库管 理系统(DMS)有
⑴高档数据库产品,如Informix,Oracle, Sybase,Progress,Unify等 ⑵中、低档数据库产品,如DBASE,Paradox, Super-Base,Foxpro,Clipper,SQL Base, Focus等; ⑶数据库开发工具,如Access,Visual Basic, Uniface,Power Builder,Q+EDatabase Editor 等。

⑶数据独立性
⑷安全性 ⑸完整性 数据库管理系统的类型
⑴OLTP(联机事务处理) ⑵DSS(决策支持系统) ⑶EIS(行政信息系统) ⑷OA(办公室自动化)

⑸按其系统结构分为单机、Unix多用户、网络多用户、客户机/服务器、 集中式、分布式、集中分布式等。

计算机病毒的特征
⑴能够将自身复制到其他程序中。 ⑵不独立以文件形式存在,仅附加在别的程序上。当调 用该程序运行时,此病毒则首先运行。 防治病毒的步骤:

⑴不要用软盘启动机器
⑵不要运行来路不明的软件 ⑶定期备份重要系统数据 ⑷重要的数据盘,程序盘应写保护 ⑸使用杀毒软件检查和清除病毒

计算机的组成和工作原理
1、存储程序——内存;执行程序——CPU 2、机器指令是计算机直接识别和执行操作的命 令,用其编写的程序称为机器语言程序,所 有指令的集合称为指令系统。格式:操作码 和地址码;类型:操作类指令和控制转移类 指令 3、计算机硬件系统由五个基本组成部分:运算 器、控制器、存储器、输入设备、输出设备 4、CPU由运算器(ALU)、数据寄存器(DR)、 指令寄存器(IR)程序计数器(PC)、地址 寄存器、操作控制器

进位计数制之间的转换问题
1、R进制转换为十进制
基数为R的数字,只要将各位数字与它的权相乘,其积相加,和数就 是十进制数 (xp…x0.x-1…x-k)R=( 例:
i ??k p

?(x ? R )
i i

)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的那些位的权值相加,其和就是等效的十进制数。

2、十进制转换为R进制
将此数分成整数与小数两部分分别转换,然后再拼接起来。 +进制整数转换成R进制的整数,可用十进制数连续地除以R,其 余数即为R系统的各位系数。此方法称之除R取余法。例如:将 5710转换为二进制数

十进制小数转换成R进制时,可连续地乘以R,直到小数部分为0, 或达到所要求的精度为止(小数部分可能永不为零),得到的整 数即组成R进制的小数部分,此法称为“乘R取整” 例:将0.312510转换成二进制数 0.3125×2 =0.625 0.625×2 =1.25 0.25×2=0.5 0.5×2 =1.0

3、二、八、十六进制的相互转换 即每位八进制数相当于三位二进制数,每位十六进制数相当 于四位二进制数。在转换时,位组划分是以小数点为中心向 左右两边延伸,中间的0不能省略,两头不够时可以补0。
例如:将1011010.102转换成八进制和十六进制数 001 011 010. 100 1011010.102=132.48 1 3 2. 4 1011010.102=5A.816 0101 1010. 1000 5 A. 8

将十六进制数F7.28变为二进制数 F 7. 2 8 F7.2816=11110111.001012

1111 0111.0010 1000

将八进制数25.63转换为二进制数 2 5. 6 3 25.638=10101.1100112

10 101 . 110 011

三、在计算机中带符号数的表示法 1、机器数与真值
规定在数的前面增设一位符号位,正数符号位用“0”表示,负数符号位用“1”表 示。

为了区别原来的数与它在计算机中的表示形式,我们将已经数码化了的带符号数 称为机器数,而把原来的数称为机器数的真值。例如N1=+1001100、N2=-1001100为 真值,其在计算机中的表示 和11001100为机器数。 2、原码〈true form01001100 〉
在用二进制原码表示的数中,符号位为0表示正数,符号位为1表示负数,其余各 位表示数值部分。这种表示法称为原码表示法。字长为n的数(包括符号位)的 原码表示法可定义为[x]原=

若真值丨x丨<1,其原码表示法可定义为[x]原=

例如对于8位二进制原码
[+0]原=00000000,[-0]原=10000000 [-1101001]原=10000000-(-1101001)=11101001

3、补码(two’s complement)
即[x]补=模+x 对于正数, [x]补=x,正数的补码就是该正数本身。

对于负数, [x]补=2n+x(mod 2n)。
[+0]补=[-0]补=00…0 [-2n-1]补=2n-2n-1=2n-1

4、反码〈0ne’s Complement〉
对于正数,它的反码表示与原码相同。即[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]原。

5、补码的加减法运算 ⑴补码的加法运算
在计算机中进行两个带符号数的加法运算时,只要将给定的真值 用补码表示,就可以直接进行加法运算。在运算过程中不必判断加 数和被加数的正负,一律做加法,最后将结果转换为真值即可。

⑵补码的减法运算
对于补码的减法运算,由于存在x-y=x+(-y),因此

[x-y]补=[x+(-y)] 补=[x]补+[-y]补 (mod2n)
其中[-y]补=[[y]补]补。

信息存储单位
⑴位(bit,缩写为b):度量数据的最小单位,表示一位二进制信息。 ⑵字节(byte,缩写为B):一个字节由八位二进制数字组成(l byte=8bit)。 字节是信息存储中最常用的基本单位。 计算机存储器(包括内存与外存)通常也是以多少字节来表示它的容量。 常用的单位有:KB 1K=1024,MB 1M=1024K,GB 1G=1024M ⑶字(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,而ASCIl码所用字节最高位保持0,然后由软件(或 硬件)根据字节最高位来作出判断。

“多媒体技术”就是用计算机交互地综合处理文本、 图形、图象、动画、音频及视频影象等多种信息,并 使这些信息建立逻辑连接。

多媒体计算机的功能
? 1、音频信号处理(声卡):录入、处理重放

信号;用MIDI技术合成音乐 ? 2、图形和图象处理:真彩色卡;图象采集卡; 图象信号压缩技术; ? 3、视频处理:实时录象和压缩视频图象的硬 件解压缩卡;软件解压缩技术

多媒体计算机的基本配置
?

WINDOWS 9X以上版本的操作系统和相 应的硬件标准

?CD—ROM(高密度盘,即光盘)

通过光学方式(使用激光束)读写信息 技术标准 1、数据传输率 2、平均搜索时间

显示模式
色彩数目 分辨率
16 256 65536 16M 640*480 800*600 1024*768 1284*1024

特点
Windows的最低配置、显示速度最快 性能虽好一些,但易产生调色板的冲突 全彩的显示模式,色彩逼真,不会再有调色板的 冲突。 高等级的3D绘图软件和专业级的视频录制人员使 用的真彩色模式,要求更多的RAM在显示卡和主 机板上,CPU最好也是顶级的。

显示卡
水平分辨率×垂直分辨率×色彩数目=显示存储空间 显示加速:VRAM、EDO RAM,Windows RAM,Ramlbus DRAM

显示器 1、屏幕由象素组成 2、主要部件(电子枪、荧光屏遮罩、荧 光屏) 3、电子束由左而右、由上而下周期性扫 描产生持续稳定的画面 4、红、绿、蓝三个电子枪的亮度决定颜 色 5、扫描频率更高、并能自动调整扫描频 率

数据压缩和解压缩技术
静止图像压缩标准JPEG(Joint Photographic ExpertsCroup) 动态图像压缩标准MPEG(Moving Picture Experts Croup) 多通道的动态图像压缩标准MP×64

相关名词
位图:由一点一点的像素点排成矩阵组成的,其中每一个像素点都可以是 任意颜色。 向量图:用向量代表图中所表现的元素。 像素 :图形的最小组成单位 真彩色:人的眼睛能够分辨出的颜色大约有1万6千多种,为了能表现出 这么多种色彩,我们得用24bit(224=16M)来描述一个像素的颜色,这种 显示模式就称为真彩色。 RGB模式:分别代表红、绿、蓝三种颜色,计算机以RGB模式来定义计算 机屏幕上的颜色。通过混色原理,不同比例的RGB色彩可调和出无穷多种 颜色。 HSB模式:分别表示色调(hue)、饱和度(saturation)、亮度(bright)。 不同的色调代表不同的颜色;饱和度指的是某区域中,该颜色量的多少, 饱和度越低,该区域看起来就越灰暗;亮度则是指颜色的亮、暗,极亮成 白色,极暗则成黑色。相对于RGB模式,HSB模式设定颜色的方式可产生 更好的视觉效果。

多媒体信息处理工具
图形制作平台FreeHand 图像处理平台Photoshop 动画制作平台 Animation Pro 数字动画的类型:
⑴基于模型的动画 ⑵帧动画

动画中加人声音的方法
⑴嵌人式—将声音文件经过转换合并到影片文件中去。 ⑵流式—声音与文件分开,在影片播放的各个时机启动声音文件

音乐
⑴波形音频文件 :通过现场录制和模数转化产生,存储量大 ⑵MIDI文件:使用键盘合成器和一个音序器 制作和编辑,存储量小

“雏形”:主机——终端系统 里程碑:APRANET网 广域网( WAN ):实现远距离的计算机之间的数据传输和 信息共享的计算机网络。通信线路一般租用电话线路或铺设 专用电缆。

局域网络(LIN):为一个单位,或一个相对独立的局部范围 内大量存在的微机能够相互通信、共享昂贵的外部设备(如 大容量磁盘、激光打印机、绘图议等)、共享数据信息和应 用程序而建立的计算机网络。通信线路一般不租用电话线路, 使用专门铺设的线路。
互联网(Internet):将遍布全球的子网通过连网协议集成 到一个共享的、开放的、易于管理的主干网。

功能
1、硬件资源共享 2、软件资源共享 3、数据和信息共享

定义
计算机网络是由地理位置分散的、具 有独立功能的多个计算机系统,经通讯 设备和线路互相连接,并配以相应的网 络软件,以实现通信和资源共享的系统

计算机网络的物理组成
网络中心主干机 、服务器 、网络工作站 共享的外部设备 网卡 通信线路(双绞线、同轴电缆和光缆、无线传输介质(如微波、红外
线和激光等))

局部网络通信设备(中继器、集线器 ) 网络互连设备 (网桥、路由器和网关 ) 网络软件 (对等式网络操作系统 、服务器上的网络操作系统)

计算机网络的拓扑结构
? 总线拓扑

? 星型拓扑

环型拓扑

树型拓扑

计算机网络的体系结构
?

所谓网络体系结构就是对构成计算机网络的各组成部分之间的关系及所要 实现功能的一组精确定义。国际标准化组织(ISO)提出的开放系统互联 参考模型(OSI)已成为网络体系结构的标准

Internet使用TCP/IP网络体系结构
TCP/IP的层号 TCP/IP的层次 名 对应OSI模型的层 次

3

应用层(ftp和 telnet等协议) 传输控制协议 TCP
网际协议IP

应用层、表示层、 会话层 传输层
网络层

2
1

计算机网络应用模式
? 客户机/服务器模型:将应用分成客户机和服务器两大部
分,并将它分配到整个网络上。由服务器提供资源,通常执行后台功能; 而客户机使用服务器,通常执行前台功能。

? 文件服务器:提供操作系统中文件管理的各种功能(网络文件的
访问方式:文件传输和文件访问 )

? 打印服务器:将一台或几台打印机物理地连接到打印服务器上,
可为多个客户机用户轮流使用

? 数据库服务器:侧重于传统数据库管理系统的功能(如数据的
定义及存取、数据的安全性与完整性、并发控制及事务处理等)的服务器

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

Internet 网络地址
?

IP地址:

网络数
A类网络 B类网络 C类网络 总计 126 16256 2064512 2084894

网络主机数 主机数
16387064 64516 254 2064770064 1048872096 524386048 3638028208

域名(或称主机名称):计算机主机名.子域名.子域名.最高层域名

Internet应用
? 文件传输 (使用匿名文件传输服务(匿名FTP)网上软件分类:公
共软件 、免费软件 、共享软件 )

? 远程登录(Telnet 命令) ? 电子邮政服务 (电子邮箱地址:用户名@计算机域名) ? 网络新闻与公告牌服务 (网络新闻是由USENET在Internet中
的新闻服务器节点之间进行传递的,阅读新闻组的软件有Outlook Express)

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

Wide Web),简称WWW,即基于“超文本”方式的信息查询技术)。 超文本:非顺序的文本呈现 超媒体:超文本和多媒体浏览环境下的应用 Mome page是由HTML语言编写的文本文件,经过WWW浏览器的解释 和处理后,网页显示在用户目前的是多媒体的超文本文件

程序设计语言的组成
?
? ?

程序设计语言的基础是一组记号和规则。根据规 则由记号构成的记号串的总体就是语言。 包括
语法:程序的结构或形式。编译系统会自动进行语法检验; 语义:程序的含义,亦即表示按照各种方法所表示的各个记号的特定 含义,但不涉及使用者。语义的错误是在源程序编译通过后的运行过程 中出现的,属于算法类的错误。 语用:程序和使用者的关系; ⑴数据成分,用以描述程序中所涉及的数据; ⑵运算成分,用以描述程序中所包含的运算; ⑶控制成分,用以描述程序中的控制构造; ⑷传输成分,用以表达程序中数据的传输。

?

? 语言的成分
? ? ?

?

语言和程序设计的发展
? 第一代语言——机器语言 ? 第二代语言——汇编语言

? 第三代语言——高级语言、算法语言(BASIC、

FORTRAN、COBOL、Pascal、C ) ? 第四代语言——非过程化语言(SQL语言) ? 第五代语言——智能性语言(PROLOG语言 、 LISP语言 )

面向对象方法的主要概念
⑴对象——系统中用来描述客观事物的一个实体,是 构成系统的一个基本单位,对象由两个主要因素组成: ? 属性:描述对象静态特征的一个数据项; ? 服务:描述对象动态特征的一个操作序列; ? ⑵消息——对象之间通过服务请求发生联系,这种向 对象发出的服务请求称为消息。 ? ⑶类——为了很好地控制软件的复杂度,将具有相同 属性和服务的一组对象组成类。
?

面向对象语言分为两大阵营
?⑴Smalltalk和Eiffel为代表的纯粹型

面向对象语言,主要强调软件开发 的探索性和原型化开发方法; ?⑵以C++、Object Pascal为代表的 混合型面向对象语言,主要扩充现 有语言,强调运行时的时空效率;

程序设计的特点
? 构造性 :不同的人为解决同一问题编制的程序,其面貌颇不相
同,然而,程序的功效却是等价的。

? 严谨性:以上下文无关的形式语言实现。无法补充缺损信息、
去掉冗余信息、将暂时不懂的信息暂时搁置起来,待下文或经过 推理予以补充和理解

? 叠加性: 一般是将自己设计的子程序尽量分割成独立的、功能
明确单一的小模块,以便充分利用;甚至还会利用系统内的库函 数。

? 抽象性:把客观事物的描述抽象为数据和算法,并且利用抽象
使得程序能够正确的映射客观事物 。抽象是有层次的 ,不同层 次上的抽象是相互独立和互相作用的 。

计算程序的运行结果
? 一、直接推理

二、由流程图推断算法
三、动态模拟 四、由底向上阅读分析

对于一些语句少、结构简单且可读性较强的程序,不妨 通过分析程序流程,直接寻找其间蕴含的计算模型。
{$n+}

var m,n,I:integer; t:extended; begin

readln(n,m);
t:=1; for i:=1 to m do t:=t*(n-i+1)/i; writeln(t:0:0); end. 输入 10 5 输出:

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

t=

n ? i ?1 ? i ,即
i ?1

m

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类型。

对于一些易读性不十分好的程序,最 好的办法是画流程图。其步骤如下 ⑴跟着程序画流程图,一句一框; ⑵根据上下文的联系合并流程图。 若前几句计算值都要代入后一表达式, 则合并为一框。接连合并几次,使程 序成为一个大功能块; ⑶由大功能块推断算法; ⑷代入输入值,计算结果。

label 10,20,30; var s,p:string; i,k,n,j,m:integer;

30:
writeln(i); end. 输入 asabcdffdin fdi 输出

begin
readln(s); n:=length(s); readln(p); m:=length(p);

i:=0;
10: i:=i+1; j:=i; k:=1;

20: if s[j]<>p[k] then begin if i<n-m+1 then goto 10; end else if k<m then begin j:=j+1; k:=k+1; goto 20;end; i:=0; goto 30;

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

程序应输出8,即s[8]…s[10]=p=‘fdi’。

动态模拟方法是采用人工模仿机器执行程序的方 法计算结果值。首先选择程序中比较重要的变量 作为工作现场。人工执行程序时,只要按照时间 先后一步步记录下现场的变化,就能最后得出程 序的运算结果。其具体布置如下: ⑴画表,画出程序执行时要用的现场情况表; ⑵基本读懂各语句的功能 ⑶走程序,即动态模拟程序。主要根据各语句 的功能,按照程序执行路径的先后顺序逐项填写 现场情况表,直至得出最后结果; 动态模拟方法对简单程序、尤其是循环次数 少的程序是很有效的。但对语句多和计算过程长
的程序,这个方法则由于模拟速度太慢而不实用。

var

i,j:integer;
a:array[1..3,1..3]of integer; begin for i:=1 to 3 do begin for j:=1 to 3 do begin if i=3 then a[i,j]:=a[i-1,a[i-1,j]]+1 else a[i,j]:=j; write(a[i,j]); end;

writeln
end; readln end.

输出:

j

1

2

3

i

1

1

2

3

2

1

2

3

3

2

3

4

显然,最后应输出 123 123 234

var a,d:array[1..100] of integer; n,i,j,k,x,s:integer; begin n:=5;a[1]:=1;d[1]:=1; for i:=1 to n do begin s:=i+1;x:=0; for j:=1 to n+1-i do begin
3 4 2 3 i = 1 S= 2

外循环 d[i+1] 2 a[1]= 2 2 3 4 5 4 4 2 3 k= 2 3 4 5 6 3 4 5 x= 1 2 3 4 5 1 2 3

内循环 a[j+1]= 3 6 10 15 21 5 9 14 输出a[j] 1 3 6 10 15 2 5 9

4
7 7 2 3 4 5 11 11 2 5 6

6
4 5 6 5 6 6

4
1 2 3 1 2 1

20
8 13 19 12 18 17

14
4 8 13 7 12 11

k:=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. 输出:

最后应输出 1 3 6 10 15 ? 2 5 9 14 ? 4 8 13 ? 7 12 ? 11 ?

由底向上分析的阅读分析方法就是在剖析了子程序和模块资 源的基础上,建立对高层程序结构的理解,从而完成整个程 序的阅读分析,即从最底层的子目标开始分析起,看它们做 了哪些事情;然后分析上一层的子目标,看这些子目标在下 一层子目标实现的基础上实现了哪些功能……。经过自底而 上的阅读分析,最后得出计算模型。

const limit = 3000;

procedure mult(var a:tdata;b:integer); var i, j:integer; begin for i:=0 to limit do a[i] := a[i] * b; update(a);

Begin read(n); fillchar(num, sizeof(num),0); for i:= 0 to n -1do begin add(i+1,-1);

type
tdata=array [0..limit] of longint; var ans ,num : tdata;

end;

add(n+n-i,1);
end;{for}

i,j,n:longint;
procedure update(var a:tdata); var int i; begin for i:=0 to limit-1 do begin inc(a[i+1],a[i] div 10); a[i] := a[i] mod 10; end; end;
procedure add(x, ob:longint); var i:longint;

add(n+1, -1); fillchar(ans,sizeof(ans),0); ans[0] := 1;

begin
for i:=2 to x do while (x mod i =0) do begin inc(num[i], ob);

for i:=2 to limit do
for j:=1 to num[i] do mult(ans,i); for i:=limit downto 0 do if (ans[i] > 0) then begin

x := x div i;
end; end;

for j:=i downto 0 do write(ans[j]);
writeln;break; end;{then} End. 输入 5 输出

update(var a)是将数组a规整为高精度的十进制数组
mult(var a,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))

完善程序
? 填空内容:
? ? ? ? ? 1、变量方面的填空 2、循环方面的填空 3、分支转移方面的填空 4、主程序和子程序关系方面的填空 5、输入输出方面的填空

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

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

?

求元素之和最大的子方阵:在m×n(m,n≤20)的正整数数字方阵中, 找出一个p×q的子阵(1≤p≤m,1≤q≤n)使其元素之和最大。例如, 下面5×4的数字阵中,元素之和最大的一个2×3子阵。 5×4数字阵 元素之和最大的2×3子阵为
3 8 4 22 5 21 6

11

1

7

9

5

21

6

2

10

3

8

10

3

8

9

2

7

12

3

var a:array[1..20,1..20] of integer;

for i:=1 to m-p+1 do for j:=1 to n-q+1 do begin ① ;

m,n,p,q,i,j,max,p1,q1,s,i1,j1:integer;
begin for i:=1 to 20 do for j:=1 to 20 do a[i,j]:=0; readln(m,n); for i:=1 to m do

for i1:=i to p+i-1 do for j1:=j to q+j-1 do ② ;

if s>max then begin ③ p1:=i; ;

begin
for j:=1 to n do read(a[i,j]); readln end;
end;

q1:=j
end;

for i:=p1 to



do

readln(p,q);
max:=0;

begin
for j:=q1 to write(a[i,j]:3); writeln ⑤ do

end;
readln end.

模块1(初始化,白色):方阵清零;读方阵规模; 读方阵;读子阵规模;子阵的最大数和初始化
模块2(湖蓝)通过枚举所有可能子阵,求数和最大 的子阵 。其中
子模块1(深蓝):累计(i,j)为左上角的子阵的数和 子模块2(淡绿):调整子阵的最大数和

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

由此得出解 ① s:=0 ② s:=s+a[i1,j1] ③ max:=s ④ p1+p-1 ⑤ q1+q-1

以下程序完成对数组每个元素向后移动 n 个 单位。数组元素的下标依次为0到m-1,对任 意一个数组元素a[i]而言,它的值移动后将存 储在数组元素a[(i+n) mod m]中。 例如, m=10,n=3,移动前数组中存储的数 据如下前一行所示,则程序运行后数组中存 储的数据如下后一行所示。

0 3 86 20 27 67 31 16 37 42
16 37 42 0 3 86 20 27 67 31

const maxm=10000;

repeat

k:=(k+n) mod m until k<=start;

var i,k,m,n,rest,start,temp:longint;
a:array longint; begin write('input m,n:'); readln(m,n); for i:=0 to m-1 a[i]:=random(100); writeln('before move'); for i:=0 to m-1 do write(a[i]:5); writeln; do [0..maxm] of

if



then

begin temp:=a[k]; repeat a[k]:=a[(m*n+k-n) mod m]; k:=(m*n+k-n) mod m; ③

until k=start;
④ end; ⑤

rest:=m; start:=0;
while begin k:=start; ① do

end;
writeln('after move'); for i:=0 to m-1 do write(a[i]:5); writeln end.

模块1——初始化 模块2——移动计算 ,其中
子模块1:判断以a[k]开始的的循环链上的元素是否都未移 动过 子模块2:若以a[k]开始的的循环链上的元素都未移动过, 则该循环链进行移动

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

模块3——输出移动后的数组 由此得出解为 ① rest>0 或 rest<>0 ② k=start ③ rest:=rest-1

④ a[(k+n) mod m]:=temp 或 a[(start+n) mod m]:=temp
⑤ start:=start+1

完善含子程序结构的程序
? 如果子模块采用过程或函数,则通常以子程

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

----------------* * * * * * ----------------* * * *

const p:set of 0..9=[2,3,5,7]; var s:set of 0..9; n:integer; ans:longint; f:text; procedure init; var i:integer;

function ok(x,l:integer):boolean; {此函数判断x是否符合条件}

var t:byte;
begin ok:=false; if exit; _______①________< >l then

inset:=false;
while ______②_______ do begin t:=x mod 10;

if t in p then
begin inset:=true; exit; end; ________③________ end; end;

while x<>0 do begin t:=x mod 10; if not (t in s) then exit; x:=x div 10;

t:byte;
begin readln(n); s:=[];

end; ok:=true; end;

for i:=1 to n do begin read(t); end; close(f); end; s:=s+[t];

function inset(x:integer):boolean; {此函数判断x中是否包含素数字} var t:byte; begin

procedure work; var i,i1,i2,i3,j1,j2:integer; begin ans:=0; for i1:=1 to 9 do if i1 in s then for i2:=1 to 9 do if i2 in s then for i3:=1 to 9 do if (i1 in p) or (i2 in p) or (i3 in p) or (j1 in p) or (j2 in p) or inset(j1*i) or inset(j2*i) then inc(ans); end; end;

writeln(ans);
end; begin init; work; end.

if i3 in s then
begin _________④_________ for j1:=1 to 9 do if (j1 in s) and ok(j1*i,3) then for j2:=1 to 9 do

if (j2 in s) and ok(j2*i,3) and _________⑤_________ then begin

模块1——初始化。读入数字个数n和n个整数,并将它们送入集合s(init过程)。
模块2——计算和输出方案数ans(work过程)
在s集合中枚举所有可能的被乘数i1 i2 i3和所有可能的乘数j1 j2,被乘数和乘数必须满足 如下条件 ⑴j1*i的积和j2*i的积分别为3位,(j1 j2)*i的积为4位,且积的每一位数字在集合s中。 在work过程中,通过调用布尔函数ok(x,l)来判别数字x是否满足各位数字在集合s且位 数为l位的条件 ⑵i1、i2、i3、j1、j2、j1*i的各位数、j2*i的各位数中至少有一个为素数。在work过程中, 通过调用布尔函数inset(x)来判别多位数x中是否存在素数字

由此得出解为

①trunc(ln(x)/ln(10))+1
④ i:=i1*100+i2*10+i3

②x>0



x:=x div 10

⑤ ok(j1*i*10+j2*i,4)

菲波拉契数列为1,1,2,3,5,8,13,21,……, 其元素产生的 规则是前两个数为 1,第三个数开始每个数等于它前 面两个数之和。已知任意一个正整数可以表示为若 干个互不相同的菲波拉契数之和。
例如:36=21+13+2 下面的程序是由键盘输入一个正整数 n,输出组成n 的互不相同的菲波拉契数 ⑴寻找小于等于n的最大菲波拉契数 a,并以a作为组 成n的一个数; ⑵若n≠a,则以n-a作为n的新值,重复步骤(1)。若a =n,则结束:

var n:integer;

procedure p(n:integer);

first:boolean;
function find(n:integer):integer; var a,b,c:integer; begin a:=1;b:=1; repeat c:= ① ;

var a:integer;
begin a:=find(n); if first then begin write(a:4); first:=false end else write('+',a:4); if a<n then p end; begin ④ ;

a:=b;b:=c; until b>=n;

if b=n then find:=
else find:= ③ end;



readln(n); first:=true;{设定表达式首项标志}
write(n:5,'='); p(n); writeln; readln

end.

p(n)的功能:计算和输出n对应的表达式。
p(n)的子函数find(n)的功能:寻找小于 等于n的最大菲波拉契数 由此得出解为 ① a+b ② n (或 b , c ) ③a ④ (n-a)


相关文章:
2014 NOIP 实用算法(中国计算机学会编)
2014 NOIP 实用算法(中国计算机学会编)_学科竞赛_高中教育_教育专区。权威机构编写...NOIP 初赛曾考察过归并排序。问题大意是:找出一个算法,使五个数在n 次比较(...
2014 NOIP信息学奥赛——算法快速入门教程(中国计算机学会出版)
2014 NOIP信息学奥赛——算法快速入门教程(中国计算机学会出版)_学科竞赛_高中教育...NOIP(普及组)初赛复习资... 70页 免费 算法复杂度分析 43页 免费©...
2014_NOIP算法快速入门教程(中国计算机学会编)
2014_NOIP算法快速入门教程(中国计算机学会编)_计算机软件及应用_IT/计算机_专业...2014NOIP初赛速成辅导(中... 暂无评价 69页 3下载券 中华人民共和国环境保护...
noip2014初赛普及组Pascal试题
noip2014初赛普及组Pascal试题_学科竞赛_初中教育_教育专区。noip2014初赛普及组...s:=b+c 20. 计算机界的最高奖是( )。 A.菲尔兹奖 B.诺贝尔奖 C.图灵...
2014NOIP(pascal)典型算法设计题集(中国计算机学会出版)
2014 NOIP(pascal)典型算法设计题集 (中国计算机学会出版)第一章第一节 算法的初步程序设计与算法 一、算法 算法是解决问题方法的精确描述,但是并不是所有问题都...
关于调整NOIP初赛费用的通知
关于调整 NOIP 初赛费用的通知 CCF NOI 各省组织单位并特派员: 中国计算机学会全国青少年信息学奥林匹克联赛(CCF NOIP)组织工作近年来不断改革, 逐步规范,较过去有...
2014 noip 计算机 it
2014 noip 计算机 it_IT认证_资格考试/认证_教育专区。2014 noip 计算机2014 NOIP 算法 快速入门 中国计算机学会中国计算机学会 2014 2014 2014 算法基础篇学习...
信息学竞赛初赛模拟试题(附答案)
一套非常棒的NOIP初赛模拟题!!!中学信息学竞赛模拟题 信息学竞赛初赛模拟试题,...2014全国计算机等级考试 全国计算机等级考试一级练习题 公共基础知识辅导 全国...
信息学竞赛辅导资料
是中国科协和教育部委托并批准中国计算机学会举办的...NOIP 是同一时间在全国各个省份同时开展的比赛,1995...回溯算法 基本算法 复赛内容与要求: 在初赛内容的...
NOIP初赛知识点复习总结
NOIP初赛知识点复习总结_学科竞赛_高中教育_教育专区...初赛试卷题型分析初赛考的知识点,大纲说:计算机基本...需要学会的运算: 交集,并集,补集,差集 集合论集合...
更多相关标签:
noip初赛速成 | noip2016初赛 | noip2015提高组初赛 | noip2016提高组初赛 | noip2016普及组初赛 | noip2016初赛试题 | noip2016初赛成绩 | noip2016浙江初赛成绩 |