当前位置:首页 >> 学科竞赛 >> 青少年信息学竞赛简要介绍

青少年信息学竞赛简要介绍


青少年信息学竞赛简要介绍
青少年信息学(计算机)奥林匹克竞赛(早期称为青少年计算机程序设计竞赛)是旨在广 大青少年中普及计算机教育,推广计算机应用的一项学科性竞赛活动。全国从 1984 年开始举 办全国性竞赛。 而自从 1989 年我国参加第一届国际信息学奥林匹克 (International Olympiad in Informatics, 简称 IOI)以来,全国青

少年计算机程序设计竞赛也更名为全国青少年信息 学(计算机)奥林匹克(National Olympiad in Informatics, 简称 NOI) 。 全国信息学奥林匹克竞赛是经国家教委批准, 中国科协具体领导, 由中国计算机学会主办 的。浙江省信息学奥林匹克竞赛活动从 84 年参加全国赛开始,由省科学技术协会、省教育厅 和省计算机学会联合组织。 为促进计算机普及并兼顾提高,从 95 年开始全国举办信息学奥林匹克竞赛分区联赛,根 据浙江实际情况,我省将分区联赛初、复赛作为省信息学奥赛的初赛和复赛。浙江省开始几年 初赛试题自己命题,现在采用全国卷。

一.信息学奥林匹克竞赛的内容和考核方式:
对学生学习计算机理论知识和实践能力有一个整体性的全面要求, 也即整个信息学 (计算 机) 竞赛已成为智力和应用计算机能力的竞赛, 涉及到有关计算机基础知识、 计算机软件知识、 程序设计知识、组合数学和运筹学的知识、人工智能初步知识以及计算机应用知识等,同时要 求学生有较强的编程和上机调试的实践能力。 1. NOI 全国分区联赛初赛 (每年 10 月左右) 对象:在校中学生, 分初中、高中组 考试形式:笔试 性质: 普及 确定获初级选手证书名单及进入复赛名单,在各地市举行。 2.NOI 全国分区联赛复赛 (每年 12 月左右) 对象:初赛优胜者 分初中、高中组 考试形式:上机试 性质:普及兼顾提高 确定全国分区联赛一、二等奖,省各等奖及全国各级证书获得者名单,在杭州进行,省派 评委协助测评。信息学奥林匹克竞赛复赛的考核方式是采用封闭式(连续 3~4 小时)上机编 程解题的形式,编程语言基本限于 BASIC 与 PASCAL,竞赛难度较大。程序完成后要通过严格 的数据测试,这就对同学们编程能力有更高的要求:不但要能编程,编好的程序能运行,而且 所设计的程序还要能通过在各种边界条件下和各种环境下设置的测试数据。

二.全国青少年信息学奥林匹克联赛大纲竞赛大纲
一、初赛内容与要求: 表示普及组可不涉及,以下同) 初赛内容与要求: 表示普及组可不涉及,以下同) 初赛内容与要求 (#表示普及组可不涉及 (# 计 算 机 的 基 本 常 识 *诞生与发展 *特点 *计算机系统的基本组成 *计算机的工作原理# *计算机信息安全基础知识 *在现代社会中的应用 *计算机中的数的表示 *计算机网络

-1-

计 算 机 的

基 本 操 作

*常见操作系统的使用基础 *常用输入/输出设备的种类、功能、使用 *汉字输入/输出方法 *常用计算机屏示信息 程序的表示 *自然语言的描述 *PASCAL 或 BASIC 语言

程 序 设 计 基 本 知 识

数据结构

*简单数据的类型 *构造类型:数组、字符串 *了解基本数据结构(线性表、队列与栈) *结构化程序的基本概念 *阅读理解程序的基本能力 *具有完成下列过程的能力: 现实世界(指知识范畴的问题)→信息世界(表达解法) →计算机世界(将解法用计算机能实现的数据结构和算法描述出来) *简单搜索 *字串处理 *排序 *查找 *统计 *简单的回溯算法 *简单的递归算法 *分类 *合并

程序设计

基本算法 处 理

二、复赛内容与要求: 复赛内容与要求: 在初赛的内容上增加以下内容: 计算机 软 件 数据 结构 程序 设计 算法 处理 *操作系统的使用知识 *编程语言的使用 *结构类型中的记录类型 *指针类型 *文件(提高组必须会使用文本文件输入) *链表 *树 *图# *程序设计能力 *设计测试数据的能力 *运行时间和占用空间的估算能力# *排列组合的应用 *进一步加深回溯算法、递归算法 *分治法 *搜索算法:宽度、深度优先算法 *表达式处理:计算、展开、化简等# *动态规划#

三、初赛试题类型:注:试题语言两者选一、高中学生必须参加提高组联赛。 初赛试题类型: 试题语言两者选一、高中学生必须参加提高组联赛。 选一 ( 程序设计语言:基本 BASIC 或 TURBO PASCAL) *判断 *填空 *完善程序 *读程序写运行结果 *问答 推荐读物: 四、推荐读物: *分区联赛辅导丛书 *学生计算机世界报

三.Pascal 语言
一、结构化程序设计 结构化程序设计实际上就是为了使程序具有合理的结构, 以便保证和验证程序的正确性而 规定的一套进行结构程序设计的方法。 用结构化程序设计的方法设计出来的程序称为结构化程 序。 结构化程序设计语言就是反映了结构化程序设计的要求和限制, 便于用来书写结构化程序 的语言。用这种语言书写的程序易于保证正确性。 二、PASCAL 语言的特色 从使用者的角度看,PASCAL 语言有以下几个主要特点: 1、它是结构化语言

-2-

PASCAL 语言是结构化的程序设计语言。PASCAL 语言提供了直接实现 3 种基本结构的语句 心以及定义子程序(“过程”和“函数”)的功能。可以方便的书写出结构化的程序。在编写程 序时可以完全不使用转向语句。这就易于保证程序的正确性和易读性。PASCAL 语言强调的是 可靠性、易读性和概念性的清晰性。 2、有丰富的数据类型 PASCAL 语言提供了整型、实型、字符型、布尔型、枚举型、子域型以及由以上类型构成 的数组类型、集合类型、记录类型和文件类型。此外,还提供了指针类型。PASCAL 语言所提 供的丰富的数据结构和上述的结构化性质, 使得它可以被方便地用来描述复杂的算法, 得到质 量较高的程序。 3、能适应于数值计算和非数值信息处理领域 在 PASCAL 语言出现之前,FORTRAN 语言主要处理科学计算,而 COBOL 语言则主要用于非 数值信息处理。PASCAL 语言则兼顾了这两个不同领域的应用。PASCAL 语言可广泛应用于各种 领域,还可以用于计算机辅助教育、计算机绘图等应用领域。 4、PASCAL 程序的书写格式比较自由 PASCAL 允许一行写多个语句,一个语句可以分写在多行上,这样就可以使 PASCAL 程序写 得像讲诗歌格式一样优美,便于阅读。 除了以上优点外,PASCAL 语言还具有简单易学的特点,许多学校把 PASCAL 作为程序设计 课程的第一种程序设计语言。 PASCA:L 语言的主要缺点:不够灵活,书写较麻烦。

四.数据结构
数据结构是计算机专业基础课程之一, 是十分重要的核心课程。 计算机的所有系统软件和 应用软件都要用到各种类型的数据结构。 要想更好地运用计算机来解决实际问题, 仅仅学习计 算机语言而缺乏数据结构知识是远远不够的,而打好“数据结构”这门课程的扎实基础,对于 学习计算机专业的其他课程都是十分重要的。 随着计算机应用领域不断扩大, 非数值计算问题占据了当今计算机应用的绝大多数, 简单 的数据类型已经远远不能满足需要, 各数据元素之间的复杂联系已经不是普通数学方程所能表 达的。因此,掌握好数据结构方面的知识,对于提高我们解决实际问题的能力将会有莫大的帮 助。 实际上一个好的程序无非是选择一个合适的数据结构和好的算法, 而好的算法的选择很大 程度上取决于描述实际问题的数据结构的选取。所以,学好数据结构,将是进一步提高我们程 序设计的关键之一。

五.算法例子
1.称小球重量: 有 6 个小球分别用 1~6 编号, 其中 5 个重量相同。现在有一架台称,一次能称出放在上 面的若干物体的总重,要求编一个程序,让计算机找出一种称法,只要称 3 次就可以知道每个 小球的重量。 具体操作时由操作者默想 6 个物体的重量, 然后由计算机用编号提问若干物体的重量, 如 此 3 次后程序应能输出每个物体的重量。 PROGRAM EX02;

-3-

VAR S1, S2, S3, p: integer; BEGIN P:=0; write(’请输入 1 号+2 号+3 号+4 号的重量总和:’); read(s1); write(’请输入 1 号+2 号+5 号的重量总和:'); read(S2) ; IF 3*s1<>4*s2 THEN BEGIN write('请输入 1 号+3 号的重量总和:’); read(s3); IF S1+S3=2*S2 THEN BEGIN P:=1; Writeln(’第 1 号重’, S3+S2-S1,’其余重’,S2-S3);END; IF S3+2*S2 =2*S1 THEN BEGIN p:=1; writen(’第 2 号重’, 3*S2-2*S1, ’,其余重’,S1-S2); END; IF 2*S2+3*S3=3*S1 THEN BEGIN p:=1; writeln(’第 3 号重’,S3-(S2 div 3),’,其余重’,S2 div 3); END; IF 2*S2=3*S3 THEN BEGIN p:=1; writeln(’第 4 号重’,S1-3*(S3 div 2),’,其余重’,S3 div 2); END; IF S1 =2*S3 THEN BEGIN p:=1; writeln(’第 5 号重’,s2-2*(s3 div 2),’,其余重’, s3 div 2), END; IF p:=0 THEN writeln('输入的数据不正确!'); END ELSE IF 3*s1 = 4*s2 THEN BEGIN write('请输入 6 号的重量:'); read(s3); writeln('第 6 号重',s3, '其余重' ,s2 div 3); END; Writeln; END. 2.打印奇数阶幻方: 方法: M×M 阶奇数幻方,在最后一行 (第 M 行) 的中间(M+1)/2 处填上 1,左下方向填 2, ...., 若前方已经有数,在原数的上方填入。 三阶: 2 9 4 7 5 3 程序如下: 6 1 8 program huafang; var i,j,k,n :integer; a: array[1..20,1..20] of integer; 五阶:9 2 25 18 11 begin 3 21 19 12 10 for i:= 1 to 20 do 22 20 13 6 4 for j:= 1 to 20 do a[i,j]:=0; 16 14 7 5 23 write('Input n:'); readln(n); 15 8 1 24 17

-4-

while (n mod 2=1) and (n<=19) do begin i:=n; j:=(n div 2)+1; a[i,j]:=1; for k:= 2 to n*n do begin i:=i+1; j:=j-1; if i=n+1 then i:=1; if j=0 then j:=n; if a[i,j]=0 then a[i,j]:=k else begin i:=i-2; j:=j+1; if i<0 then i:=i+n; if j=n+1 then j:=1; a[i,j]:=k; end; end; for i:= 1 to n do begin for j:= 1 to n do write(a[i,j]:4); writeln; end; exit; end; write('Error!'); end. 3.13 个人编号围成一圈,从 1 开始,4 个一数,数到者出列,打印出列的顺序。 (方法一: ) Program EX1301; Const m=13;t=4; Var i,k,p :integer; A:array[1..m] of integer; Begin For i:= 1 to m do a[i]:=1; I:=0; k:=0; p:=0; Repeat I:=i+1;if i=m+1 then i:=1; K:=k+a[i]; If k=t then

-5-

Begin Write(i:4);a[i]:=0; p:=p+1; k:=0; End; Until p=m; Writeln; End. (方法二:链接表) Program EX1302; Const m=13;t=4; Var i,j,k,p :integer; A:array[1..m] of integer; Begin For i:= 1 to m-1 do a[i]:=i+1; A[m]:=1; i:=m; k:=1; p:=0; Repeat i:=a[i]; k:=k+1; If k=t then Begin Write(a[i]:4); a[i]:=a[a[i]]; p:=p+1; k:=1; End; Until p=m; writeln; End. 出列顺序: 4 8 12 3 9 1 7 2 11 10 13 6 5

-6-

计算机的数制、码制及其运算
1.计算机是智能化的电器设备
计算机就其本身来说是一个电器设备,为了能够快速存储、处理、传递信息,其内部采用 了大量的电子元件, 在这些电子元件中, 电路的通和断, 电压高和低, 这两种状态最容易实现, 最稳定;也最容易实现对电路本身的控制。我们将计算机所能表示这样的状态,用 0,1 来表 示,就形成了用二进制数表示计算机内部的所有运算和操作。 计算机内部是以二进制形式表示数据的(指令、被处理的数据)。 二进制数的运算规则: 0+0=0 0+1=1 1+0=1 1+1=10; 0×0=0 0×1=0 1×0=0 1×1=1

2.进位基数和位权值
⑴数的进制与基数 计数的进制不同,则它们的基数也不相同,用到的数码也不一样。如表 1-1 所示。 进制 二进制 三进制 四进制 八进制 十进制 十六进制 基数 2 3 4 8 10 16 数码 01 012 0123 01234567 0123456789 0123456789ABCDEF

进制基数:指的是该进位记数制中可能用到的数码个数。 对于任意计数进制:每一位计满这个基数后,都应向高位进位。 二进制,逢二进一;八进制,逢八进一; 十进制,逢十进一;十六进制,逢十六进一; R 进制(R 为任意正整数):数码个数为 R 个,分别为 0~R-1,每一位数当计满 R 后,应向 高位进位。 ⑵数的权 不同进制的数,基数不同,其每位上所代表的值的大小也不相同,我们称之为“权” 。 2 1 0 如:(219)10=2×10 +1×10 +9×10 (按权展开式) 2 在百位上代表 2 个 100 即 200;1 在十位上代表 1 个 10 即 10;9 在个位上代表 9 个 1 即 9。 注:以后我们用下标来注明圆括号内数的进制。 4 3 2 1 0 (11010)2=1×2 +1×2 +0×2 +1×2 +0×2 2 1 0 (273)8=2×8 +7×8 +3×8 2 1 0 (27B)16=2×16 +7×16 +11×16 任意 R 进制 S: S=knkn-1…k0.k-1k-2…k-m n n-1 0 -1 -2 -m = kn×R +kn-1×R +…k0×R +.k-1×R +k-2×R +…k-m×R i R 为进位基数,R 是对应的权值。

-7-

3.任意进制的数转换成十进制整数
将任意进制数转换成十进制数的基本方法是按权展开, 然后求和——按权相加法。 因为在 上式中基数我们已经转换成了相应的十进制数,所以展开式即是一个十进制数的表达式。 4 3 2 1 0 (11010)2=1×2 +1×2 +0×2 +1×2 +0×2 =(26)10 2 1 0 (123)8=1×8 +2×8 +3×8 =(83)10 (1AB)16=(427)10

4.十进制整数转换成任意进制数
⑴将十进制整数转换成任意进制数的基本方法是: 将十进制数除以所给定的进制的基数, 再反 向取余。 例如:将十进制数 39 用二进制数表示,用除二反向取余法。

(39)10=(100111)2 (245)10=(365)8 ⑵减权定位法: 把十进制数展开成所指定进制的基数的整数次幂之和, 然后找到对应位上取值。 例如:将十进制数 123 用二进制数表示。 (123)10=64+32+16+8+0+2+1 6 5 4 3 2 1 0 =1×2 +1×2 +1×2 +1×2 +0×2 +1×2 +1×2 =(1111011)2

5.十进制小数转换成任意进制数
常用把给定的十进制小数乘以给定进制数的基数, 取积的整数部分, 得到给定进制小数的 小数点的第 1 位;乘积的小数部分再乘以基数,积的整数部分为小数点后的第 2 位;一直重复 做下去,就可以得到希望的进制小数。 例如:①将十进制小数 0.75 转换成二进制小数。 (0.75)10=(0.11)2 0.75×2=1.5 0.5×2=1 ②(0.315)10=(0..0101)2 不是所有的十进制小数都可以用一个精确的二进制小数表示。

6.二进制与八进制之间的转换
三位二进制,正好能完全表示八进制的 8 个数码。 二进制 八进制 000 0 001 1 010 2 011 3 100 4 101 5 110 6 111 7

二进制数转换成八进制数的方法是:从小数点开始,分别向左向右,每 3 位二进制数为一 组,用八进制来书写。若左侧位数不是 3 的倍数,则最左侧用 0 补充,若右侧位数不是 3 的倍

-8-

数,则最右侧用 0 补充。 例如:(10110111.01101)2=(267.32)8 反过来,八进制数转换成二进制数的方法:将每个八进制数用 3 位二进制数来书写。 例如:(1234.45)8=(1010011.100101)2

7.二进制与十六进制之间的转换
二进制 十六进制 0000 0 0001 1 0010 2 … … 1001 9 1010 A 1011 B 1100 C 1101 D 1110 E 1111 F

每四位二进制数可以用一位十六进制数表示。 二进制数转换成十六进制数方法: 从小数点开始, 分别向左向右, 4 位二进制数为一组, 每 用十六进制来书写。 若左侧位数不是 4 的倍数, 则最左侧用 0 补充, 若右侧位数不是 4 的倍数, 则最右侧用 0 补充。 例如:(110110111.01101)2=(1B7.68)16 十六进制数转换成二进制数方法: 将每个十六进制数用 4 位二进制来书写, 其最左或最右 侧的 0 可以省去。 例如:(7AC.DE)16=(11110101100.1101111)2 综合例子: ①(3/32)10 转换成二进制 -5 解:(3/32)10=3×2 =(11)2×(0.00001)2=(0.00011)2 总之:十进制数与二进制数之间的转换必须用前面讲的繁琐方法进行,因为 10 不能用 2 的整数次幂进行表示。 也就是不能象八进制或十六进制数那样用几位二进制数表示十进制数的 十个数码。 ②把十进制数 27.625 转换成二进制、八进数和十六进制数。 解:(27)10=(11011)2 (0.625)10=(0.101)2 (27.625)10=(11011.101)2=(33.5)8=(1B.A)16 要把一个十进制数转换为八进制数或十六进制, 最先把它转换成二进制数, 再由二进制数 转换成八进制或十六进制。 课后练习: ①请用等号或不等号联接下列不同进位制数值的大小。 (98.375)10 (142.3)8 (58.5)16 (1011000.0101)2 ②下面四个不同进制的数,最小的数是 。 A (11011001)2 B (75)10 C (37)8 D (A7)16 ③小张用十六进制、八进制和十进制写了如下一个等式:52-19=33 式中三个数是各不相同进 位制的数,请问 52、19、33,分别为 。 A 八进制,十进制,十六进制 B 十进制,十六进制,八进制 C 八进制,十六进制,十进制 D 十进制,八进制,十六进制 ④十进制算术表达式:3*512+7*64+4*8+5 的运算结果,用二进制表示为( ) A 10111100101 B 11111100101 C 11110100101 D 11111101101

-9-

二进数在计算机内的表示
数值数据是用于表示数量的大小, 经常用到数值范围和数据精度。 数值范围指的是一种类型的 数据所能表示的最大值和最小值; 数据精度通常用实数所能指出的有效数字位数来表示。 与用 多少个二进制位表示某类数据,以及怎么对这些位进行编码有关。 机器数与真值 计算机中数的符号用数码表示。一般情况下,用 0 表示正,用 1 表示负。且符号位放在 数的最高位。 ————真值数 例:X1=(+1011011)2 X2=(-1011011)2 0 1 1 1 0 0 1 1 1 1 0 0 1 1 1 1

————机器数 连同符号位在一起作为一个数,称为机器数。而它的数值部分称为真值数。

一、数的定点和浮点表示
计算机在处理数据时,要考虑到小数点的位置。如果将小数点固定在某一位置,则称为 定点表示;如果小数点可以任意移动,则称为浮点表示。 数的定点表示法—— ——定点小数和定点整数 1. 数的定点表示法——定点小数和定点整数 ⑴定点小数格式: 小数点的位置固定在最高数据位的左边, 小数点前面再设一位符号位。 任何 m 位二进制小数在计算机中用 m+1 位二进制表示。

Ns



N-1

N-2





N-m+1 N-m

符号位

小数点

数值部分

由于小数点总是在符号位与最高数据位之间,因此在计算机中不明确表示出来 ⑵定点整数格式:小数点位置固定在最低数据位的右边。 整数又分为带符号和不带符号的两类。 带符号的整数,符号位安排在最高(最左)位。 Ns Nn-1 Nn-2 … N1 N0

符号位 n 位数值 小数点 由于小数点固定在最低数据右边,因此在计算机中不明确表示出来。n 位带符号整数 N=NsNn-1…Nn-2N1N0 在计算机中用 n+1 位二进制表示。 对于不带符号的整数,把所有 n+1 位二进制位全部视为数值。 在不同计算机中,使用多种位数的整数。16 位,32 位,64 位,64 位二进制来表示一个 整数。 2. 数的浮点表示法 .

- 10 -

浮点数是指小数点数据中的位置可以左右移动的数。一个数 N 要用浮点数表示可以写: E N=M*R M:浮点数的尾数。 E:浮点数的指数或阶码。 R:浮点数的基数,是常数一般取 2、8 或 16 一旦机器的浮点部件设计好了,基数的大小也就确定了,不能再改变了,基数在浮点数 表示中不出现,是隐含的。 ⑴浮点数的表示方法: Es Em……E2E1 Ms Mn……M2M1 阶符阶码 数符数码 M:尾数。用定点小数表示,表示浮点数的有效位,其位数 n 的大小决定了浮点数的精 度。 E:阶码。用定点整数表示。阶码用于表示小数点在浮点数中的位置。其位数 m 的大小反 映此浮点数所能表示的数的范围。 ⑵浮点数的规格化:规定计算机内浮点数的尾数用纯小数形式给出,而且当尾数的值不 为 0 时,其绝对值应大于或等于 0.5,不符合这一规定的浮点数要进行规格化。 (通过修改阶 码的大小并同时左右移尾数的办法使其满足要求。 ) ①正数:1/2≤S<1,二进制表示 S=0.1…… ②负数:-1/2≥S>-1,二进制表示 S=1.1…… ③机器零:尾数为 0,不论其阶码为何值。 阶码的值遇到比它所能表示的最小值还小时,不管尾数为何值。 阶码、尾数全变成 0。 ④浮点数常用格式: 符号位 阶码 尾数 总位数 短浮点数: 1 8 23 32 长浮点数: 1 11 52 64 临时浮点数: 1 15 64 80

二、二进制数值数据的编码方法
编码方法是研究在计算机中如何方便的表示定点小数,定点整数和浮点数的正数、负数 和零。 最常用的编码方法有原码表示法、 补码表示法、 反码表示法三种。 我们以定点小数为例: ㈠原码表示法: 原码表示法: 1、定义:用机器数的最高(左)一位代表符号,其余各位给出数值(真值)的绝对值。 X (0≤X<1) [X]原= 1-X (-1<X≤0) 1+|X| 例:X1=0.1011 X2=-0.1011

- 11 -

[X1]原=01011

[X2]原=11011

符号 数值 符号 数值 2.真值零的原码表示法 [+0]原=00000 [-0]原=10000 3.原码表示的范围 如果用 n 位二进制表示定点小数,其中一位符号位。 -(n-1) 最大数:+(1-2 ) -(n-1) 最小数:-(1-2 ) n 原码编码个数:2 -1 0 点两个编码 例 n=8 最大数:01111111 -(8-1) 对应 1-2 =1-0.0000001=0.1111111=127/128 最小数:11111111 -(8-1) 对应-(1-2 )=-0.1111111=-127/128 ㈡反码表示法 1、定义:用机器数的最高一位代表符号,数值位是对负数值各位取反的表示方法。 取反 0→1 1→0 X (0≤X<1) [X]反= -n (2-2 )+X (-1<X≤0) [X1]反=01011 例: X1=0.1011 X2=-0.1011 [X2]反=10100 把任何一个二进制负数的绝对值与它的反码相加,得到的和永远 1.1111,若在最后位上 加 1,恒等于 2。 2、 真值零的反码表示法 [-0]反=11111 [+0]反=00000 反码同原码一样,零的表示不是唯一的,有两个。 ㈢补码表示法 1、模的概念 例:11 点→6 点 ①往回拨 5 格 11-5=6 ②往前拨 7 格 11+7=18 18-12=6 舍掉进位的情况下:从 11 点中减去 5 和往 11 上加 7 结果是一样的。 例:9-3=6 9+7=16 16-10=6 (十进制) 而 7=12-5 →对于 12 进制计数的基数 12(模数)7 是 5 对于 12 的补码。 7=10-3 →对于 10 进制计数的基数 10(模数)7 是 3 对于 10 的补码。

- 12 -

在计算机中,机器表示的数据字长是固定的,对于 n 位数来说,模数大小是 n 位数全为 1,且在最末位再加 1。实际上模数的值已超出计算机所能表示的数的范围,因此模数在机器 中是表示不出来的,若运算结果大模数,则模数自动丢掉。如果是 n 位整数(包括符号位) , n 则它的模数是 2 ,若 n 位小数,则它的模数总是 2。 同理:在二进制定点小数减法运算中,减去一个二进制数,也可以化为加上这个数对于 模数 2 的补码。 2、定义:用机器数的最高(左)一位表示符号位,其余各位给出负数数值按 2 取模的结果。 X (0 ≤X<1) [X]补= 2+X ( -1≤X≤0) 2-|X| 例:X1=0.1011 [X1]补=01011 [X2]补=10101=10-0.1011 X2=-0.1011 3、真值零的补码表示法 [+0]补=00000 [-0]补=10-0.0000=00000 [+0]补=[-0]补 4、在补码表示法中数的表示范围 -(n-1) 定点小数:最大:1-2 最小:-1 [-1]补=10-1.0000=10000 -7 n=8 最大:1-2 =0.1111111 补码 01111111 最小:-1 补码 10000000 n 由于在补码表示法中零有唯一的编码,n 位二进制能表示 2 个补码数。 5、补码的求法 ⑴、 从反码求补码 |X|+[X]反+0.0001=10 [X]反+0.0001=10-|X|=[X]补 ⑵、从原码→反码→补码 ⑶、补码→原码 除符号位外反转,再在未位加 1。 小结 1、如果真值 X 为正数,则[X]原=[X]补=[X]反 2、如果真值 X 为负数,[X]原、[X]补、[X]反表示不同。 3、如果 X=0,则[X]补有唯一编码, [X]原有两个不同表示方法, [X]反有两个不同表示方法。 4、在定点小数中,原码和反码的表示范围为-1<X<1 补码的表示范围为-1≤X<1

三、整数的编码方法
可用原码、补码、反码三种方法进行编码。

- 13 -

1、 整数的编码方法与小数的编码方法的区别 ⑴小数点位置 ⑵表示范围 ⑶模数的差别 2、 整数的编码方法

四、浮点的编码方法
Es E Ms M M 部分采用定点小数形式,可以用原码表示,也可以用补码表示。 阶码多采用整数形式的移码表示。 1、 移码的表示方法 ⑴移码定义 n n n [X]移=2 +X -2 ≤X≤2 ⑵将这一定义与整数补码相比较 n X 0≤X≤2 [X]补= n+1 n -2 ≤X≤0 2 +X n n n 当 0≤X≤2 时,[X]移=2 +X=2 +[X]补 n n n+1 n 当-2 ≤X≤0 时,[X]移=2 +X=(2 +X)-2 →[X]移是将[X]补的符号位变反。 例:X=+1010101 [X]补=01010101 [X]移=11010101 [X]移=00101011 X=-1010101 [X]补=10101011 2、 移码的特点:符号位在最高位,正用 1 表示,负用 0 表示。

五、ASCII 码和 BCD 码
ASCII 码 在人们通常接触和处理信息中,有相当一部分是用字符或字符的组合来表示的。字符是 指字母、数字以及其它一些可打印显示的符号。 计算机和外部设备之间进行通讯联系时,还需要一些控制功能的特殊符号。例如,控制 打印机的走纸符、换行符等。 在计算机内部,上述字符必须用一种二进制代码来表示。日前,在国际上广泛采用的是 美国标准信息交换代码 (American Standard Code for Information Interchange) 简称 ASCII , 码。 7 ASCII 码是 7 位二进制编码,它可以表示 2 =128 个字符。

- 14 -

由于标准的 7 位 ASCII 码所能表示的字符较少,不能满足有些信息处理的需要,于是在 ASCII 码地基础上又设计了一种扩充的 ASCII 码。扩充的 ASCII 码是一种 8 位二进制编码,它 可以表示 256 个字符。 BCD 码 十进制数在键盘输入和打印时,往往是将各个数字以 ASCII 码来表示的。但是它在计算 机内运算时, 是以二进制形式进行的。 为了便于转换, 设计了一些二进制编码来表示十进制数, 称为二—十进制码,即 BCD 码(Binary Coded Decimal) 。BCD 码是用四位二进制代码来表示 一位十进制数。从 16 个四位二进制代码 0000~1111 中,只须选择其中 10 个作为十进制数的 10 个数字的代码就可以了。这样就有多种 BCD 码:如 8421 码、2421 码、余 3 码和格雷码等。 十进制数字 8421 码 2421 码 余3码 格雷码 0 0000 0000 0011 0000 1 0001 0001 0100 0001 2 0010 0010 0101 0011 3 0011 0011 0110 0010 4 0100 0100 0111 0110 5 0101 0101 1000 1110 6 0110 0110 1001 1010 7 0111 0111 1010 1000 8 1000 1110 1011 1100 9 1001 1111 1100 0100 由于 8421 码最常用,因此通常就把它称为 BCD 码。例如,十进制数 315 用 BCD 码表示为 001100010101。注意:用 BCD 码表示的数,形式上像二进制数,但不是真正的二进制数。例如, 315 转换成二进制数是 100111011B。 在计算机中,可以把用 BCD 码表示的十进制数转化成真正的二进制数后,再进行运算, 也可以直接对用 BCD 码表示的十进制数进行计算。但需要进行“十进制调整” ,以符合“逢十 进一”的十进制运算规则。

- 15 -

PASCAL 程序设计初步
PASCAL 从 1971 年正式推出至今,已成为世界上最广泛使用的程序设计语言之一,PASCAL 语言全面地体现了结构化程序设计的概念, 具有丰富完备的数据类型、 简明灵活的语句和清晰 明了的模块结构,书写格式自由,运行效率高,查错能力强,移植性好,程序设计风格优美, 有助于养成结构化程序设计的良好习惯。我们选择的是 Turbo Pascal 6.0 的版本的教材。 要使用计算机解决实际问题, 除了会理解题目和设计算法外, 关键的一点就是要会编写程 序。 程序其实就是用计算机语言来表述我们所设计的算法过程。 计算机语言与我们的语言相类 似,有着多种多样的语言,不过这些语言最终的目的都是一致的,都是为了让计算机看懂我们 所设计的得算法。

一.Pascal 程序形式:
Program 程序名(程序参数表) ; Label 标号说明; Const 常量说明; Type 类型说明; 说明部分 Var 变量说明; Function 函数说明; Procedure 过程说明; Begin 程序语句; 程序体 ……; 程序语句; End.

1. 每一个完整语句由分号结束。 2. 具 体 程 序 不 一 定 包 括 全 部 说 明,但如果出现,必须按这里 所指定的前后次序编写。 3. 程序体不可少, 程序体以 END. 结束,且最后一个句号不能漏 掉。 4. END 前一句语句的分号可有可 无,有则编译时多一个空行。

二.基本程序结构和几个概念:
例: program pname; const n=4; type ar=array [1..4] of integer; var i:integer; a:ar; begin for i:=1 to n do read(a[i]); readln;

- 16 -

for i:=n downto 1 do write(a[i]:4); writeln; end. 以上是一个 PASCAL 程序。从键盘读入 4 个数据,逆序输出。 一般来说,一个 PASCAL 程序包括以下几个部分: 程序头:program pname; 其中,program 是保留字,表示程序从这个地方开始,pname 是标识符,是程序的名字,可由程序员自定。保留字是 PASCAL 选定的,具有固定意义和用法 的专用单词或缩写,这些单词不允许作其它使用。如上, “program”就有“程序从这里开始” 这样一种特别的意义,而“const”就有“常量说明从这里开始”的意义。我们不能再用 “program”、 “const”来作为其它变量、常量等的名字。标识符是以字母开头的字母数字串。 用来表示常量、变量、类型、文件、过程、函数和程序的名字。如“pname”、 “i”、 “j”、 “a1”就是合法的标识符;但“1a”、 “#a”是非法的标识符。有一点要注意的是,在 PASCAL 中,字母除了作为字符值或字符串值之外,其大小写是无关的。如标识符“A1”和“a1”在 PASCLA 看来是同一标识符。在 PASCAL 中除了保留字和自定义的标识符外,还有一类有特殊含 义的标识符,这类标识符称为标准标识符。它们是用来标记程序中经常引用的处理对象,如常 量、函数。 (PASCAL 定义的保留字和标准标识符附后) 标识符在命名的时候要注意:1、名字要易记易读,有意义。如 8 皇后问题程序名可以是 “queen”也可以是“huanghou”等;2、不能用保留字、标准标识符作为自定义的标识符。 说明部分:const n=4; type ar=array [1..4] of integer; var i:integer; a:ar; 其中,const 部分是常量说明,说明一些在以下部分用到的,在整个程序执行过程不改变 值的量。这些量 PASCAL 称为常量。在程序中用到这个值的地方均用常量名来代替。如上题中 定义 “n=4”指本程序处理 4 个数值, 在下面的程序体中就用 “n”来代替具体的值 (如 for i:=1 to n) 。如果要改变处理数据个数,则只在常量说明部分修改“n=4”这一句就行了,而不用在 程序中每一个用到的地方都加以修改。 这样不但在编写程序的时候很方便, 也增加了程序的可 读性,修改时更方便。 常量说明在保留字“const”下开始。可以有多个语句。常量说明语句的格式是: “常量名 =值;。如“n=4;。n 是常量名,4 是该常量的值, ”是语句分隔符。 ” ” “; type 部分是类型说明,说明一些在以下部分用到的数据类型。如数组、记录、指针等。 类型说明在保留字“type”下开始。可以有多个语句。类型说明语句的格式是: “类型名= 类型说明;。如“ar=array [1..4] of integer;。ar 是类型名,array [1..4] of integer ” ” 是类型说明, ”是语句分隔符。 “; var 部分是变量说明。变量是指在程序执行过程中可以通过赋值语句或读语句来改变值的 量。所有在程序中使用的变量都应该先在变量说明部分说明。PASCAL 中引用的每个变量都有 “名字”和“类型”属性。变量说明“说明”的主要工作是告诉 PASCA 下面程序中要用到这个 名字的量,同时这个量的类型是什么。 变量说明在保留字“var”下开始。可以有多个语句。变量说明语句的格式是: “变量名: 变量类型;。其中,如果有多个变量同一类型,则变量名与变量名之间用逗号分隔,变量名与 ”

- 17 -

变量类型之间用冒号分隔。 “i: 如 integer; i 是变量名, ” ( integer 是类型名) i、 integer; 、 j: “ ” (i、j 是变量名,integer 是类型名)…… 变量说明要注意:1、变量名称必须以字母开头;2、在同一个有效范围内变量名称必须唯 一。 各个说明部分均以该部分的保留字开始。如“const”开始常量说明; “type”开始类型说 明; “var”开始变量说明。一个程序包含多少种类型的说明,看需要而定,不是每一个程序都 必须同时包含这三种说明。如果程序不须要用到常量,则常量说明部分可以省略;如果不须要 用到类型说明,则类型说明可省…… PASCAL 还有一条规则:先说明后引用。即所有在程序体中用到的“名字”必须都在说明 部分说明过才能引用,否则就会出错,通不过编译,也执行不了。如上,类型“ar”先在类型 说明中定义,然后在变量说明中引用;变量 i 在变量说明中定义,在程序中引用。 程序体:begin for i:=1 to n do read(a[i]); readln; for i:=n downto 1 do write(a[i]:4); writeln; end. 程序体是以 begin end.括起来的语句系列。 “end”后面是一个小圆点,标识着程序结 束,整个程序只有一个是一个程序的主要部分。编程要完成的工作大部分都在这里完成。程序 体中每一语句均以“; ”作为结束符。在书写程序时,以“分层缩进”的风格来写,以便提高 程序的可读性。所谓的“分层缩进”是指在逻辑上同一级的语句其起始点对齐,下一级的语句 向右缩进。

三.运算符

表达式

PASCAL 中的运算符有算术运算符和关系运算符。和我们在数学课中学的基本一样但在写 法上有些不同,在写程序时要特别注意写法的不同: + 加号 - 减号 * 乘号( 数学中写为 × ) / 除号( 数学中写为 ÷) MOD 取余 如 8 MOD 2=0 7 MOD 2=1 2 MOD 3=2 DIV 取整 如 8 DIV 2=4 7 DIV 2=3 2 DIV 3=0 在 PASCAL 只有上面 6 种数学运算。 其它的就只能利用这 6 种运算的组合通过语句来实现。 如 a^2(a 的平方)可以化成 a*a。 > 大于 < 小于 <> 不等于(数学中写为 ≠) <= 小于等于(数学中写为≤) >= 大于等于(数学中写为 ≥) 变量、 常量通过运算符连接起来的式子我们称为表达式。 一个单独的变量或常量也是表达 式。如 a、a+3、a*3+b 都是表达式。写表达式时要注意 PASCAL 表达式跟我们已经熟悉的数学 表达式在格式上的区别: 数学表达式 PASCAL 表达式 注意 2a 2*a *号不能省略

- 18 -

a÷b a/b 除号的写法 a≠b a<>b 不等号的写法 a≤b a<=b 小于等于号的写法 标准数据类型:整型 实型 字符型 布尔型 数据类型可以理解为一个取值范围和定义在这取值范围上的运算规则。 想一想我们对于数 的理解:小学学自然数,范围是从 0 开始,那时候不知道有小数,也不知道有负数,允许的运 算是+、-、×、÷,而且对于减法规定被减数要大于减数。到了中学,数的范围扩大了,整数 包括正数和负数,减法运算也不再有额外的规定的了。同理,在 PASCAL 中“数据类型”也是 一个取值范围和在它上面定义的运算规则。PASCAL 中定义好的标准数据类型一共有 4 个:整 型、实型、字符型、布尔型,分别用保留字 integer、real、char、boolean 来标记它们。其 取值范围和运算如下: 整型(integer):范围 -32768——32767;运算 + - * / mod div 实型(real):范围 运算 + - * / 字符型(char):范围 可显示的 ASCII 字符 布尔型(boolean):范围 true false 运算 and or not 在 PASCAL 中可使用的基本符号有: (1)大写字母 A—Z ;小写字母 a—z ;数字 0—9 (2)其它字符 + — * / = > < >= <= <> := ( ) [ ] . , : $ ^ (* *) { } ‘ 其中,有些符号是以双字符作为一个整体,拆开后就失去原有的意义。如“<>”是一个表 示“不等于”的关系运算符,如拆开后就变成了两个关系运算符,分别表示“小于”“大于” 、 。 PASCAL 使用的保留字有: AND ARRAY BEGIN CASE CONST DIV DO DOWNTO ELSE END FILE FOR FUNCTION GOTO IF IN LABEL MOD NIL NOT OF PACKED PROCEDURE PROGRAM RECORD REPEAT SET THEN TO TYPE UNTIL VAR WHILE WITH FORWARD 常用的标准标识符有: 标准常量:FALSE TRUE MAXINT MAXLONGINT 标准类型:INTEGER BOOLEAN REAL CHAR TEXT 标准文件:INPUT OUTPUT 标准函数:ABS ACTAN CHR COS EOF ELON EXP LN ODD ORD PRED ROUND SIN SQR SQRT SUCC TRUNC 标准过程:ASSIGN GET NEW DISPOSE PACK PUT READ READLN RESET REWRITE UNPACK WRITE WRITELN 练习题:

- 19 -

一、判断以下标识符的合法性: a3 3a a17 abcd ex9.5 α β 二、将下列的数学表达式改写成 PASCAL 表达式: b^2-4ac 三、求下列表达式的值: 20 mod 19 15 mod 9 7 div 8 19 div 3 (4>5) and (7<8) (8>9) or ( 9<10) 2 and ((3=3) or (3<7))

λ

四.赋值语句、读语句、写语句
㈠赋值语句 语法分析〗 〖语法分析〗 PASCAL 有两个语句可以改变变量的值。赋值语句是其中之一(另一个是读语句) 。赋值, 顾名思义,就是把一个值赋予某个量。可以这理解:变量相当于装东西的容器,赋值的过程就 是把东西放进容器的过程。赋值语句格式如下: 变量:=表达式; 写赋值语句有以下几点要注意: 1、赋值号“:=” 赋值号由两个字符构成,是一个运算符。如果把这两个字符拆开,那么这两个字符就是 别的意思了: ”是分隔符而“=”是关系运算符,判定两个对象是否相等。刚刚写程序的同 “: 学要特别注意这一点。 例:a,b:integer;——是一个说明语句。 ”是变量表和变量类型的分隔符 “: a=b——是一个表达式。它的值是一个布尔类型的量:TRUE 或 FALSE a:=3;——是一个语句。把整型常量值 3 赋给整型变量 a 2、变量要先说明 在赋值号左边出现的变量,要在程序头的说明部先加以说明,否则编译时出错。 3、表达式必须要有确定的值 赋值号右边出现的表达式,必须是可以求值的。也就是说,经过运算之后,能得出一个具 体的、确定的值出来。大家想一想,如果连表达式自己都不知道自己的值是多少,怎么还能把 值“赋予”别人呢? 4、赋值号两边的数据类型必须相同或相容 我们知道,PASCAL 中的量不管是变量还是常量都有一个属性称为“数据类型” 。数据类型 相同的或相容的才可以相互赋值。 怎么来理解这句话呢?打个比方,我们沏功夫茶用的是小茶杯,装饭时用饭碗。如果用 饭碗来泡功夫茶,用小茶杯来装饭,那情形一定很滑稽而且是不可行的。回到 PASCAL 中来, 赋值号左边变量如果是整型, 右边表达式的值的类型也要是整型; 赋值号左边变量如果是字符 型,右边表达式的值的类型也要是字符型……否则的话,也要出错了。这是数据类型相同的情 况。

- 20 -

对于数据类型相容的,我们也可以用一个例子来帮助理解。我们都喝过功夫茶,也喝过大 杯茶。 把功夫茶倒在大茶杯里, 一般不会出什么问题; 但如果把大杯里的茶倒在功夫茶杯里呢? 可能小茶杯装不下大茶杯里的茶,茶“溢出”了。在 PASCAL 中也会出现这种情况。当一种数 据类型的取值范围包含着另一种数据类型的取值范围时, 就可能出现类型相容的情况。 如实型 与整型,整型、字符型与它们各自的子界类型……如果把整型值赋给实型变量,把整型子界值 赋给整型变量,不会出错;但如果反过来,就会出现“溢出” ,出错了。 因此,我们在写赋值语句时,要注意两边的类型是否匹配。 例:有程序如下: var a,b:integer;c:real;d:0..100; begin a:=100; b:=a; {-------------以上是相同数据类型进行赋值} d:=100; b:=d; c:=b; {-------------以上是相容数据类型进行赋值} d:=b; a:=c; {-------------以上两个赋值语句都出现溢出,编译时出错} end. ㈡读语句 语法分析〗 〖语法分析〗 读语句(read 语句)和赋值语句一样,能够改变变量的值。与赋值语句不同,读语句从 键盘或文件接收值赋予变量,而赋值语句则直接由程序语句获得。读语句格式如下: read(变量名表); readln(变量名表); readln; 读语句是编程中用得最多的语句之一。在使用时有几点要注意: 1、变量名表。写在括号中的变量,都要在变量说明中先预以说明;变量与变量之间,以 “,”分隔; 例: var a,b:integer; read(a,b); 2、从键盘接收数据时,要注意各种不同数据类型数据的分隔符不同。所谓分隔符就是两 个完整的数值之间的标记,也可以这样理解,当计算机从键盘读入数据时,一旦碰到分隔符, 就认为当前的数据读入已完成,可以把它赋给相应的变量了。各种数据类型的分隔符如下: 数值型(包括整型、实型以及它们的子界类型)以空格或回车符作为分隔符; 数值型 字符型不需分隔符(因为字符型数据的长度固定,只有一个) ; 字符型

- 21 -

字符串以回车符作为分隔符。 字符串 3、注意 read 与 readln 的区别 例:有两段程序有相同的变量说明如下,不同的读语句,我们可以通过比较它们执行结果 的异同来理解 read 与 readln 的区别。 变量说明 程序段一 var a,b,c,d:integer; 执行结果 a read(a); readln(b,c); read(d); readln(a); read(b,c); read(d) 1 2 3 4 5 6 7 8 1 b 2 c 3 d 6

程序段二

1

6

7

8

输入数据

在程序段一执行时, “read(a);”语句接收了第一个数据 1 并将它赋给变量 a;接着执行第二 个语句“readln(b,c);”,接收了第一行数据中的 2、3 并把它们分别赋给变量 b,c,同时, 把本行其它数据全部屏蔽掉,也就是宣布它们全部作废。程序段二的执行情况也是如此。 因此,我们可以得出结论:语句 read 只管接收数据,语句 readln 接收完数据后,还把同 行的其它数据全部宣布作废。 4、 “readln;”语句从键盘接收一个回车符。这个语句通常用在需要暂停的地方。如输出 时用来等待程序员看清结果。 ㈢写语句 语法分析〗 〖语法分析〗 写 (write) 语句是 Pascal 中唯一能将运算结果送出显示在显示器屏幕的语句。 格式如下: write(输出量表);{输出后不换行} writeln(输出量表);{输出后换行} writeln;{输出一个回车符} 使用写语句时也有一些小问题需要注意。 1、输出量可以是: 变量。输出变量的值。输出多个变量时,变量间用“,”分隔。 表达式。输出的是表达式的值。 常量。直接输出常量值。 2、场宽的限制在输出不同格式的数值时的作用: 例 1:输出多个空格。 write('':n);句子的意思是以 n 个字符宽度输出冒号前数据项,如果数据项长度不足 n, 则前面以空格补齐;如果数据项长度大于 n,则以实际长度输出。如上语句句输出 n 个空格。 例 2:数据项间隔。 如输出最多四位的数据:write(x:5)。则数据间至少分隔一个空格。

- 22 -

例 3:实型数据小数位数的确定。 实型数据不带格式限制时,以科学计数法的形式输出,和我们的一般书写习惯不同。如果 加上场宽的限制,则可以有不同的效果: var a:real; begin a:=15/8; writeln(a);{输出 1.8750000000E+00} wiiteln(a:0:2);{输出 1.88 整数部分按实际位数输出, 小数部分保留两位小数, 末位四 舍五入.} writeln(a:0:0):{输出 2 只输出整数部分,小数部分四舍五入} end. 3、 “writeln;”语句通常用于输出多组数据时在屏幕上输出空行来分隔数据组。 赋值语句、读语句、写语句习题: 1、a,b,c 分别等于 1、12、123,把它们按向左对齐、向右对齐的方式打印出来。 2、输入一个四位整数,把它的各位数字倒序输出。 (提示:用 MOD 和 DIV 运算完成) 3、从键盘上读入小写的"pascal",利用 CHR()和 ORD()函数,输出大写的"PASCAL"。 4、从键盘上读入一个实数,利用 ROUND()和 TRUNC()函数,输出该实数本身、整数部分、 小数部分、四舍五入后的值。 要求:分三行输出;输出实数本身时,格式与读入时相同;整数部分、小数部分在同一行输出; 其它各占一行。 5、从键盘上读入长方形的边长 a,b,计算它的面积和周长,输出。 6、输入一个时、分、秒,把它转换为一个秒数。

五.条件语句(if 语句)
〖语法分析〗 语法分析〗 条件语句用于响应一个条件的两个方面。 例如:今天如果下雨,我们就在家;否则(不下雨)我们就去旅游。 又如:如果已经搜索得到结果,就打印出答案;否则(还没得到结果)就继续搜索。 IF 语句的一般格式是: IF 条件 THEN 语句 1{条件为真时的响应、处理} ELSE 语句 2;{条件为假时的响应、处理} 使用条件语句时要注意: 1、条件语句是一个语句。IF、THEN、ELSE 都是语句的一个部分。所以它只能有一个“; ” 作为分隔符,放在句子的结束,特别要注意不能放在 ELSE 之前。 2、如果我们的程序只需对条件为真的情况作出处理,不需要处理条件为假的情况,则 IF 语句省略 ELSE 分句,格式变成: IF 条件 THEN 语句 1;{条件为真时的响应、处理} 如:如果数 a 大于等于 0 则输出它的平方根。

- 23 -

if a>=0 then writeln(sqrt(a)); 对以上的例子,条件为假时不需处理,于是我们干脆省去 ELSE 分句。 3、if 语句可以多层嵌套。嵌套时为了避免误解,可以用 begin ,end 括起嵌套部分;else 分句一般和最近的 if 分句配套: IF 条件 THEN BEGIN if 条件 1 then …… else ……; END {这里没有分号} ELSE BEGIN if 条件 2 then …… else ……; end; 〖例题分析〗 1、输入两个数 a,b,输出较大的数。 program tt; var a,b:integer; begin write('please input a,b:'); readln(a,b); if a>b then writeln(a) else writeln(b); end. 条件语句练习题: 1、从键盘上读入长方形的边长 a,b,计算它的面积和周长,输出。 2、 从键盘读入一个数,判断它的正负。是正数,则输出"+",是负数,则输出"-"。 3、 输入两个数 a,b,输出较大数的平方值。 4、 铁路托运行李规定:行李重不超过 50 公斤的,托运费按每公斤 0.15 元计费;如超 50 公斤,超过部分每公斤加收 0.10 元。编一程序完成自动计费工作。 5、 某超市为了促销,规定:购物不足 50 元的按原价付款,超过 50 不足 100 的按九折付 款,超过 100 元的,超过部分按八折付款。编一程序完成超市的自动计费的工作。 6、 输入 a,b,c 三个不同的数,将它们按由小到大的顺序输出。 7、 当前小学生的成绩单由以前的百分制改为优秀、良好、合格、不合格四个等级的等级 制。编一程序完成分数的自动转换工作。转换规则如下:60 分以下的为不合格;60 到 69 分为 合格;70 到 89 分为良好;90 分以上的为优秀。 (提示:可以利用 DIV 运算来使程序更简明)

六.分情况(CASE)语句
〖语法分析〗 语法分析〗 分情况语句适用于对一个条件的多种情况的响应。 格式: case 表达式 of 值表 1:语句 1;

- 24 -

值表 2:语句 2; …… 值表 n:语句 n; else 语句 n+1 end; case 语句在使用时有几点要注意: 1. end 与 case 对应;值表与语句之间用“: ”分隔;else 与语句之间不用分隔符。 2. 表达式必须是有序类型(整型、字符型、布尔型、枚举型、子界型) 3.值表必须是一些由逗号分开的常量,其类型与表达式的类型一致 4. 语句可以是多个语句,但必须用语句括号(begin……end)括起 5. case 语句也可以嵌套 例 1: 某全自动加油站 a,b,c 三种汽油的单价(元/kg)分别是 1.50、1.35 和 1.18,也提 供了“自己加”或“协助加”两个服务等级,这样用户可以得到 5%或 10%的优惠。编一个程序, 用户输入加油量、汽油品种和服务类型(f-自动,m-自己,e-协助),然后计算应付款。 program pcase1; var oil,help:char; kg,total:real; begin write('Enter the amount in kilograms(kg):'); readln(kg); write('Which type of the gasoline(a,b,c):'); readln(oil); wirte('Which type for service(f,m,e):'); readln(help); case oil of 'a': total:=1.50*kg; 'b': total:=1.35*kg; 'c': total:=1.18*kg; else writeln('Input Error!') end; {——————处理汽油的类型} case help of 'f':; 'm': total:=total*(1-0.05); 'e': total:=total*(1-0.10); else writeln('Input Error!') end; {——————处理服务类型} writeln; writeln('Total is ',total:10:2); end.

- 25 -

例 2:从键盘上读入年和月,输出该月有多少天。 program pcase2; var year,month,day:integer; runnian:boolean; begin write('Enter year and month:'); readln(year,month); case month of 1,3,5,7,8,10,12: day:=31; 4,6,9,11: day:=30;{————以上处理 31 天和 30 天的情况} 2:begin runnian:=(year mod 400=0) or ((year mod 4=0) and (year mod 100<>0)); case runnian of true: day:=29; false: day:=28; end; end; {————以上处理 2 月的情况:闰年 29 天,平年 28 天} end; end. 练习题: 1、 编程模拟剪刀、石头、布游戏:用 S 表示剪刀,用 R 表示石头,用 P 表示布。规则是: 剪刀剪布,石头砸剪刀,布包石头。游戏者分别把自己的选择输入,计算机给出结果。

七.各种循环语句的运用
〖语法分析〗 语法分析〗 在 PASCAL 语言中,有 3 种循环语句。所谓循环,就是不断地重复某一段程序段。这三种 语句分别是 FOR,REPEAT-UNTIL,WHILE。 循环语句 1、 FOR 循环语句 FOR 语句构成的循环有递增和递减循环两种形式: 1. 递增型 FOR 循环。 FOR 循环控制变量:=循环初值 TO 循环终值 DO 循环的语句 (或语段) 例: FOR I:=5 TO 10 DO WRITELN (I); 输出的结果为: 5 6 7 8 9 10 即循环一共执行了 6 次 如果要重复多个语句,一定要用 BEGIN-END 形式: 例: FOR I:=1 TO 10 DO BEGIN WRITELN (I); WRITELN (10-I); END; 2. 递减型 FOR 循环 FOR 循环控制变量:=循环初值 DOWNTO 循环终值 DO 循环语句

- 26 -

递减型 FOR 循环与递增型 FOR 循环基本相同,只是循环控制变量每次递减。 3. FOR 循环的几点注意内容: (1)循环控制变量必须是顺序类型的变量。所谓顺序类型的变量,就是指整型,字符型, 枚举型,子界型,不允许是实型。 (2)不允许在循环体内再对循环控制变量赋值。 例如: A:=10;B:=50; FOR K:=A TO B DO BEGIN K:=K+1;{这一句是错误的!!!! !!!!} WRITELN (K); END; (3)当循环初值或循环终值中包含变量时, 允许在循环体内改变这些变量的值, 但并不改 变原定的循环次数。 例: A:=1;B:=10; FOR I:=A TO B DO BEGIN A:=5;B:=4; END; 在上面例子中,A,B 的值在循环的内部发生了变化,但并不影响循环的次数,依然是 10 次。 4. 多重循环 循环体由 PASCAL 语句构成, 当然也可以包含 FOR 语句, 这就构成了循环的嵌套, 形成多重循环。 例如,以下 FOR 循环输出 5 行,每行输出 10 个星号(*) FOR i:=1 to 5 DO BEGIN FOR j:=1 TO 10 DO Write('*'); END; 初学者应当特别注意,内层的循环变量不能和外层的循环变量相同。也就是说,嵌套的各层循 环应当使用不同的变量作为循环变量。 循环练习题: FOR 循环练习题: 1、计算下列式子的值: (1)1+2+……+100 (2)1+3+5+……+97+99 2、输入一个四位数,求它各位上数字的和。 3、求水仙花数。所谓水仙花数,是指一个三位数 abc,如果满足 a^3+b^3+c^3=abc,则 abc 是水仙花数。 4、宰相的麦子:相传古印度宰相达依尔,是国际象棋的发明者。有一次,国王因为他的

- 27 -

贡献要奖励他,问他想要什么。达依尔说: “只要在国际象棋棋盘上(共 64 格)摆上这么些麦 子就行了:第一格一粒,第二格两粒,……,后面一格的麦子总是前一格麦子数的两倍,摆满 整个棋盘,我就感恩不尽了。 ”国王一想,这还不容易,刚想答应,如果你这时在国王旁边站 着,你会不会劝国王别答应,为什么? 2、 WHILE 类型的循环 1.WHILE 循环的执行形式:WHILE 布尔表达式 DO 语句 例如: k:=10; WHILE k>0 DO BEGIN Writeln (k); k:=k-1 END; 其中 (1)WHIlE 和 DO 是 PASCAL 保留关键字,是 WHILE 循环语句的组成部分。 (2)保留关键字 DO 后面的“语法”只能是一条语句,称为“循环体” ;如果循环体中需要 包含多个语句则应该如上例所示,采用一条复合语句。 2.WHILE 循环的执行功能 当执行到 WHILE 语句时 (1)求出布尔表达式的值 (2)若布尔表达式的值为真,则执行循环体内的语句;若为“假” ,执行步骤 4 (3)重复步骤 1 和 2 (4)循环结束,执行循环后面的语句。 循环练习题: WHILE 循环练习题: 1、输入一个整数,计算它各位上数字的和。 (注意:是任意位的整数) 2、输入一整数 A,判断它是否质数。 (提示:若从 2 到 A 的平方根的范围内,没有一个数 能整除 A,则 A 是质数。 ) 3、求两个数的最小公倍数和最大公约数。 (提示:公约数一定小于等于两数中的小数,且 能整除两数中的大数。公倍数一定大于等于两数中的大数,且是大数的倍数,又能给两数中的 小数整除。 ) 4、编写一个译码程序,把一个英语句子译成数字代码。译码规则是以数字 1 代替字母 A, 数字 2 代替字母 B,……,26 代替字母 Z,如遇空格则打印一个星号‘*’ ,英文句子以‘.‘结 束。 5、 “百钱买百鸡”是我国古代的著名数学题。题目这样描述:3 文钱可以买 1 只公鸡,2 文钱可以买一只母鸡,1 文钱可以买 3 只小鸡。用 100 文钱买 100 只鸡,那么各有公鸡、母鸡、 小鸡多少只?与之相似,有"鸡兔同笼"问题。 REPEAT3、 REPEAT-UNTIL 类型的循环 1.REPEAT-UNTIL 类型的循环的执行形式 REPEAT

- 28 -

语句 1 语句 2 …… 语句 n UNTIL 布尔表达式 例如:以下循环求 n=1+2+3+……+100 n:=0;t:=i; REPEAT n:=n+t; t:=t+1; UNTIL t>100; 其中 (1)REPEAT 和 UNTIL 是 PASCAL 保留关键字。 (2)在 REPEAT 和 UNTIL 之间的语句构成循环。在它们之间可以有任意多个语句,这一点 和 FOR,WHILE 循环不同,FOR,WHILE 循环体在语法上只允许一条语句。 2.REPEAT-UNTIL 循环的执行功能 (1)遇到 REPEAT 语句后,即进入循环体,顺序执行循环体内的语句。 (2)遇到 UNTIL 语句后,求布尔表达式的值。若值为假,则返回步骤 1;若为“真” ,执 行步骤 3 (3)循环结束,执行 UNTIL 后面的下一条语句。 循环练习题: REPEAT 循环练习题: 1、输入一个正整数 N,把它分解成质因子相乘的形式。 如:36=1 X 2 X 2 X 3 X 3; 19=1 X 19 (提示:设因子为 I,从 2 开始到 N,让 N 重复被 I 除,如果能整除,则用商取代 N,I 为一个因子;如果不能整除,再将 I 增大,继续以上操作,直到 I 等于 N。 )

八.一维数组
〖语法分析〗 语法分析〗 在编程时用到一批类型相同的数据, 为了处理上的方便, 通常以数组的形式来定义这一批 数据。 1、 数组的定义格式: var a:array [1..10] of integer; 其中:a 是这一批数据的名称,称为数组名;array、of 是定义数组的保留字;中括号中 的数字是数据编号的下限和上限,同时也说明了数据的个数(上限-下限) ;最后一个是数据的 基类型,如 integer,char,real,boolean。 2、 数组元素的输入: 数组名代表的并不是一个变量,而是一批变量,因而,不能直接整个数组读入,而是要逐个数 组元素读入,通常用循环结构来完成这一功能。下面是几个常用输入数组元素的例子: for i:=1 to 10 do read(a[i]); {————从键盘读入数组元素的值;最常用的方法}

- 29 -

for i:=1 to 10 do a[i]:=i; {————数组元素 a[1]到 a[10]的值分别为 1 到 10;数据赋初值} for i:=1 to 10 do a[i]:=0; {————数组元素清 0;最常用的数据初始化的方法} for i:=1 to 10 do a[i]:=random(100); {————随机产生 10 个 100 以内的数,赋给各数组元素} 3、 数组元素的输出: 和数组元素的输入相同, 数组元素的输出也不能由一个 write 语句直接完成。 同样要逐个 数组元素输出。通常也用循环结构来完成这一功能: for i:=1 to 10 do write(a[i],' ');{————数组元素之间用空格分隔} writeln; 4、 数组的应用: 例 1:从键盘输入 10 个数,将这 10 个数逆序输入,并求这 10 个数的和,输出这个和。 program p1; var a:array [1..10] of integer; i,s:integer; begin for i:=1 to 10 do read(a[i]); for i:=10 downto 1 do write(a[i],' '); writeln; s:=0; for i:=1 to 10 do s:=s+a[i]; writeln('s=',s); end. 例 2:用筛法求 100 以内的素数(质数) 。 分析:素数是除了 1 和它本身以外没有其它约数的数。用筛法求素数的方法是:用质数筛 去合数: 从第一个素数 2 开始, 把它的倍数去掉; 这样 2 以后的第一个非 0 数就一定也是素数, 把它的倍数也删了……重复这个删数过程, 直到在所找到的素数后再也找不到一个非 0 数。 把 所有非 0 数输出。 program p2; var a:array [1..100] of integer; i,j,k:integer; begin for i:=1 to 100 do a[i]:=i; a[1]:=0;i:=2; while i<=100 do begin k:=i;

- 30 -

while k<=100 do begin k:=k+i; a[k]:=0; end; {————上面将所有 a[i]的倍数清 0} i:=i+1; while a[i]=0 do i:=i+1; {————查找接下来的第一个非 0 数} end; for i:=1 to 100 do if a[i]<>0 then write(a[i],' '); end. 练习题: 随机产生 20 个 100 以内的数,输出;按从小到大的顺序排序,输出。

九.二维数组
〖语法分析〗 语法分析〗 一维数组在编程中多用于描述线性的关系:如一组数;一组成绩;一组解答等。数组元素 只有一个下标,表明该元素在数组中的位置。二维数组在编程中多数用于描述二维的关系:如 地图、棋盘、城市街道、迷宫等等。而二维数组元素有两个下标:第一个下标表示该元素在第 几行,第二个下标表示在第几列。二维数组的定义格式如下: var a:array[1..10,1..5] of integer; 其中:a 是数组名,由程序员自定;array 和 of 是定义数组的保留字; (这两点和一维数 组定义的格式一样)中括号中的两个范围表示二维数组共有多少行、多少列(第一个范围表示 行数,第二个范围表示列数) ;最后一个表示数组元素的类型,规定和一维数组一样。如上例, 定义了一个二维数组 a,共有 10 行 5 列。 使用二维数组要注意: 1、数组元素的指称:数组名[行号,列号]。如第三行第四个元素:a[3,4]。 对某一行进行处理。如累加第 4 行的数据。则固定行号为 4。如:for i:=1 to 5 do s:=s+a[4,i]; 对某一列进行处理。如累加第 4 列的数据。则固定列号为 4。如:for i:=1 to 10 do s:=s+a[i,4]; 2、二维数组的输入输出要用双重循环来控制: for i:=1 to 10 do{————控制行数} begin for j:=1 to 5 do read(a[i,j]){————第一行读入 5 个元素} readln;{————读入一个换行符} end; {————最常用的方法:从键盘读入数据初始化二维数组} for i:=1 to 10 do for j:=1 to 5 do a[i,j]:=0;

- 31 -

{————最常用的方法:将二维数组清 0} for i:=1 to 10 do begin for j:=1 to 5 do write(a[i,j]:4); writeln; end; {————最常用的输出方法:按矩阵形式输出二维数组的值} 3、 二维数组的应用: 例 1:竞赛小组共有 20 位同学,这学期每位同学共参与了三项比赛,请统计每位同学的 平均分。 分析: 定义一个 20 行 3 列的二维数组来存放这些成绩。 定义一个 20 个元素的一维数组来 存放平均分。 program p1; var a:array [1..20,1..3] of integer; b:array [1..20] of real; i,j:integer; begin for i:=1 to 20 do begin for j:=1 to 3 do read(a[i,j]); readln; end; {————从键盘上读入 20 个同学的三次竞赛成绩} for i:=1 to 20 do b[i]:=0; {————先将平均分数组清 0} for i:=1 to 20 do begin for j:=1 to 3 do b[i]:=b[i]+a[i,j];{————计算总分} b[i]:=b[i]/3;{————计算平均分} end; for i:=1 to 20 do write(b[i]:5:1); {————输出平均分} writeln; end.

- 32 -

十.字符串
〖语法分析〗 语法分析〗 字符串用于存放整批的字符数据。 通常编程中使用字符串存放字符化了的数字数据。 如高 精度运算时存放操作数和运算结果。字符串可以看作是特殊的字符串数组来处理。当然,它也 有自已的特点。下面是字符串定义的格式: var s:string; s1:string[15]; 字符串定义时,如不指定长度,则按该类型的最大长度(255 个字符)分配空间,使用时 最大可用长度为 255 个;如果在中括号中给出一个具体的值(1—255 之间) ,则按这个值的大 小分配空间。使用时,最大的可用长度即为该值。 1、 字符串的输入、输出: 字符串类型既可按数组方式输入、输出,也可直接输入、输出:readln(s);writeln(s); 多个字符串输入时以回车作为数据间的分隔符;每个 readln 语句只能读入一个字符串。 2、 有关字符串的操作:
操作 length(s) 类型 函数 作用 求字符串 s 的长度 复制 s 中从 w 开始的 k 位 返回值 整型 例子 s:='123456789'; l:=length(s);{l 的值为 9} s:='123456789'; s1:=copy(s,3,5);{s1 的值是'34567'} var s:string;k,code:integer; 将字符串 s 转为数值, val(s,k,code) 过程 存在 k 中; code 是错误 代码 begin s:='1234'; val(s,k,code); write(k);{k=1234} i:=1234; str(i,s) 过程 将数值 i 转为字符串 s str(i,s); write(s);{s='1234'} 在 s 中删除从第 w 位开 始的 k 个字符 s := 'Honest Abe Lincoln'; Delete(s,8,4); Writeln(s); { 'Honest Lincoln' } S := 'Honest Lincoln'; Insert(s1, S, w) 过程 将 s1 插到 s 中第 w 位 Insert('Abe ', S, 8); { 'Honest Abe Lincoln' } Pos(c, S) 函数 求字符 c 在 s 中的位置 整型 S := ' 123.5'; i :=Pos(' ', S);{i 的值为 1} s1:='1234'; s2:='5678'; s:=s1+s2;{'12345678'}

copy(s,w,k)

函数

字符串

Delete(s,w,k)

过程

+

运 算 符

将两个字符串连接起 来

- 33 -

练习题: 1、做一个加法器。完成 30000 以内的加法,两个加数间用“+”连接,可以连加,回车表 示式子输入完成; “#”表示结束运算,退出加法器。 循环结构、数组综合练习题: 循环结构、数组综合练习题: 1、 数学黑洞 6174 已知:一个任意的四位正整数。将数字重新组合成一个最大的数和最小的数相减,重复这 个过程,最多七步,必得 6174。即:7641-1467=6174。将永远出不来。 求证:所有四位数数字(全相同的除外) ,均能得到 6174。输出掉进黑洞的步数。 2、 随机产生 20 个三位数,将这 20 个数按从小到大的顺序排列,要求在排列中,用尽可 能少的交换次数。 3、 输入 10 个学生的姓名,编一程序将它们按字母的顺序排列。 4、有一组数,其排列形式如下:11,19,9,12,5,20,1,18,4,16,6,10,15,2, 17,3,14,7,13,8,且尾部 8 和头部 11 首尾相连,构成环形的一组数,编程找出相邻的 4 个数,其相加之和最大,并给出它们的起始位置。 5、 有一组数其排列顺序如下: (设有 N 个)3,6,11,45,23,70,67,34,26,89, 90,15,56,50,20,10。编一程序交换这组数中任意指定的两段。 6、 输入一个十进制数,将其转换成二进制数。

十一.过程和函数(子程序)
一、子程序设计的需要: 1.细化算法的过程,可以将每一个子问题运用一段相对独立的小程序来解决; 2.一些具有相同或功能相似的程序段在程序中的不同位置反复出现, 可以将这样的程序段 做成一个整体, 用一个标识符给它起一个名字, 凡是需要这个程序段的地方只要简单地引用其 标识符即可。 3.子程序包括过程和函数两种形式。 二、函数 1.标准函数 :由 Pascal 定义的函数。如我们熟悉的 ord,chr 等,程序员编程时直接引用 就行了。 2.自定义函数:由程序员在程序中定义后再使用。 (1)自定义函数的定义 function 函数名(形参表):函数类型; { ————函数首部} var {————局部变量说明部分} begin {————函数体} ... {————函数语句} ... 函数名:=表达式 end; (2)函数的调用:函数在语法上相当于一个表达式,所以,调用时,函数不能独立成为一个 语句;它可以出现在任何表达式可以出现的地方。

- 34 -

例如赋值语句的右边: X:=函数名(实在参数表); {————X 的类型与函数类型必须一致} 又,如果函数类型是 boolean,则还可以出现在条件语句中,充当条件表达式: if 函数名(实在参数表) then …… (3)例:编写一个函数,返回布尔值判别输入三个字符是按序或无序排列。程序中若输入 abc 则显示顺序排列,若输入 cba 则显示逆序排列,其他情况显示无序排列,当输入***程序 结束。(pfun1.pas) 三、过程 1.标准过程:由 Pascal 定义的过程。如我们熟悉的 read,write 等,程序员编程时直接引 用就行了。 2.自定义过程:由程序员在程序中定义后再使用。 (1)过程的定义 procedure 过程名(形式参数表); {————过程首部} var {————说明部分} begin {————过程体} ... ... end; (2)过程的调用:过程在语法上相当于一个语句,所以,调用时,直接写下就行: 过程名(实在参数表); (3)例 1:某部队举行一次军事演习, B 两队约好在同一时间从相距 100 公里的各自驻地 A、 出发相向运动。A 队的速度为 10 公里/小时,B 队的速度为 8 公里/小时。一通讯员骑马从 A 地同时出发为行进中的两队传递消息,速度为 60 公里/小时。每遇一队立即折回驶向另一队, 当两队距离小于 0.5 公里时,停下来不再传递消息。求此时通讯员跑了多少趟(从一队到另一 队为一趟)? (4)例 2:已知二个合数 A=18 和 B=96,键入 N 个[10,400]之间的自然数,求这 N 个数中所 有合数与 A、B 的最大公约数。 四、子程序中的参数 1.局部变量和全局变量 在子程序中定义的变量称为局部变量,在程序的一开始定义的变量称为全局变量。 2.变量的作用域 (1)变量的作用域和它被定义的位置有关: 在哪里被定义,它的作用范围就在那里:全局变量作用域是整个程序;局部变量作用域是 定义该变量的子程序 (2)全局变量与局部变量同名时: 在定义局部变量的子程序内,局部变量起作用;在其它地方全局变量起作用。 3.值形参和变量形参 值形参——传值 变量形参——传地址 五、综合练习

- 35 -

前提知识:计算任意三角形(三条边的长度分别为 a、b、c)的面积 S 可以用海伦公式: S=sqrt((x-a)(x-b)(x-c)) 其中:x=(a+b+c)/2 题目描述:从键盘输入三个数,判断以这三个数为边能否组成一个三角形,若不能,则给 出适当信息;若能,则输出是否为等边、等腰或直角三角形,并输出其面积。 编程要求: 1. 将从键盘输入三个数设计成一个过程,过程名为 input,带三个变量参数 a,b,c; 2. 将判断三个数能否组成三角形(包括是什么三角形)设计成一个函数,函数为 ang, 参数为在 input 中接收到的三个数,返回的值表明了能否组成三角形或三角形的类型; 3. 将计算三角形面积设计成一个函数,函数名 area,带三个值参数,返回的值为三角形 的面积; 4. 要求使程序的主程序的结构明快些,并要求在程序中的适当的说明。

★集合
一. 集合的定义: type 类型名=set of 基类型 例如: type num=set of char; var n:num; 或 var n: set of char; 二. 集合的运算: 1. 集合的表示: 用一组方括号括号一组元素来表示,元素之间用逗号分隔。如: [A,B,C,D]--有四个枚举量的集合 ['A','B','C','D']--有四个字符的集合 [1..20]--包含了 1 到 20 中所有整数的集合 [0]--只有一个元素 0 的单元素集 []--空集 2. 集合的运算: (1)赋值(:=): ll:=['A'..'C']; (2)并(+): [0..7]+[0..4]的值为[0..7] (3)交(*): [0..7]*[0..4]的值为[0..4] (4)差(-):

- 36 -

[0..7]-[0..4]的值为[5..7] (5)相等(=): [0..7]=[0..4]的值为 false (6)不等(<>): [0..7]<>[0..4]的值为 true (7)包含于(<=): [0..7]<=[0..4]的值为 false (8)包含(>=): [0..7]>=[0..4]的值为 true (9)成员(in): 1 in [0..4]的值为 true 3. 注意: (1)集合运算相当快,在程序中常用集合表达式来描述复杂的测试。如 A)条件表达式: (ch='T') or (ch='t') or (ch='Y') or (ch='y') 可用集合表达式 表示为: ch in ['T','t','Y','y'] B)if (ch>=20) and (ch<=50) then ...; 可写成: if ch in [20..50] then ...; (2)集合类型是一种使用简便,节省内存面又运算速度快的数据类型。 (3)Turbo Pascal 规定集合的元素个数不超过 256 个(当实际问题所需的元素个数大于 256 时,可采用布尔数组代替集合类型)。所以如下定义是错误的: var i: set of integer; (4)集合类型变量不能进行算术运算,了不允许用读/写语句直接输入/输出集合。 所以 集合的建立: A)要通过赋值语句实现; B)或先初始化一个集合,然后通过并运算向集合中逐步加入各个元素. (5)集合元素是无序的,所以 ord,pred 和 succ 函数不能用于集合类型的变量。 4. 例 1:建立两个集合,然后对它们进行多种集合运算,并且输出结果。 5. 例 2:运用集合完成筛法找素数。 三、练习: 1.编程读入两个字符串,然后输出如下信息: (1)出现在某一个字符串中至少一次的字母和数字; (2)同时出现在两个字符串中至少一次的字母和数字; (3)出现在一个字符串中而不出现在另一个字符串中的字母和数字; (4)不出现在任何字符串中的字母和数字。

★记录
一.记录的定义: type 类型标识符=record 字段名 1:类型 1;

- 37 -

字段名 2:类型 2; ... 字段名 n:类型 n; end; 如: type studata=record num:string[6]; name:string[8]; sex:boolean; s:array[1..5] of real; end; var student:studata; students:array[1..10] of studata; 二.记录的运用: 1.对记录中和个域的引用,要写出记录名和域名,如:student.num 2.开域语句:with。 with 记录名 do 语句; 或 with 记录名 1,记录名 2,... do 语句; 注意: (1) 在 do 后面语句中使用的记录的域时, 只要简单地写出域名就可以了, 域名前的 记录变量和"."均可省略。 (2) 在关键字 with 后面,语句可以是一个简单语句,了可以是一个复合语句。 (3) 虽然在 with 后可以有多个记录变量名, 但一般在 with 后只使用一个记录变量名。

★文件
文件是一种构造型的数据类型。在程序中都需要产生一些输出,也需要接受若干个输入。 这些输入、 输出实际上是用文件的方法来实现的, Pascal 中用标准文件 在 “input” “output” 和 来实现,它们分别对应标准输入设备和标准输出设备(可省略不写)这也就是一些程序的程序 书写如下的原因了: program ex(input,output); ... 但有时大量数据的读入和输出都是来是磁盘文件, 这就要求我们必须熟练掌握对磁盘文件 的操作。 对于我们来说,我们只必须掌握文本文件(或称正文文件,text)的读写即可: 1.文本文件的定义: 文本文件不是简单地由某类型的元素序列所组成, 它的基本元素是字符, 由它们构成行, 若干行组成一份原文。由于各行的长度可以不同,所以文本文件只能顺序地处理。文本文件的

- 38 -

定义如下: var fp:text; 2.文本文件的读操作: (1)调用 assign 过程,把磁盘文件赋予文本文件变量; assign(fp,filename); (2)调用 reset 过程,为读操作做准备; reset(fp); (3)在需要读数据的位置调用 read 过程或 readln 过程。 readln(fp,var1,var2,...,varn); 3.文本文件的写操作: (1)调用 assign 过程,把磁盘文件赋予文本文件变量; assign(fp,filename); (2)调用 rewrite 过程,为读操作做准备; rewrite(fp); (3)在需要读数据的位置调用 write 过程或 writeln 过程。 writeln(fp,var1,var2,...,varn); 4.文本文件的关闭操作: close(fp); 5.文本文件的其他操作: (1)EOF(fp)—布尔函数,用于判断文件结束否。 (2)EOLN(fp)—布尔函数,用于判断行结束否。 例:从文件 ex.in 中输入 n 个数,并将它们按照逆序输出到文件 ex.out 中。 输入文件 ex.in 的格式: 第一行是一个数 n; 第二行是 n 个整数; …… 当读到的 n 值为 0,表示文件结束。 练习: 1.编写程序从磁盘上读取一个由 100 个实数组成的实型数据文件(indata.dat), 以此文件 中所有大于平均值的实数建立一个名为 “above.dat” 的文件, 其余的建立一个名为 “rest.dat” 的文件。 2.写一个程序,把文本文件中所有 GOOD 改为 BAD。

- 39 -

十二.程序设计的方法
模块化: 1. 模块化: (1) 把一个较大的程序划分为若干子程序,每一个子程序解决一个总是独立成为一个模 块; (2) 每一个模块又可继续划分为更小的子模块; (3) 程序具有一种层次结构。 注:运用这种编程方法,考虑问题必须先进行整体分析,避免边写边想。 自顶向下: 2. 自顶向下: (1) 先设计第一层(即:顶层),然后步步深入,逐层细分,逐步求精,直到整个问题可用 程序设计语言明确地描述出来为止。 (2) 步骤: 首先对问题进行仔细分析,确定其输入、输出数据,写出程序运行的主要过 程和任务; 然后从大的功能方面把一个问题的解决过程分成几个问题,每个子问题形成一个 模块。 (3) 特点:先整体后局部,先抽象后具体。 自底向上: 3. 自底向上: (1) 即先设计底层,最后设计顶层; (2) 优点:由表及里、由浅入深地解决问题; (3) 不足:在逐步细化的过程中可能发现原来的分解细化不够完善; (4) 注意:该方法主要用于修改、优化或扩充一个程序。 例子: 之间的素数。 4. 例子:求 1 到 n 之间的素数。 解:要求 1 到 n 之间的素数,程序要做的事就是从 1 开始依次找,判断是否是素数,是则打印 出来,否则继续往下找,直到 n 为止。于是初步设想成: begin read(n); number:=2; while number〈n do begin if number 是一个素数 then write(number); number 取下一个值; end end. 第二步:细化“number 是一个素数”及“number 取下一个值” 。 (1) 细化“number 是一个素数” : “number 是一个素数” 这是一个布尔值, number 是一个素数时为 true, 当 否则为 false。 细化如下: k:=2; lim:=number-1; repeat if nubmer 能被 k 整除 then prim:=false else begin k:=k+1;prim:=true;end;

- 40 -

until not(prim) or (k 达到 lim); (2) 细化“number 取下一个值” : number:=number+1; 第三步:细化“number 能被 k 整除”及“k 达到 lim”。 (1) 细化“number 能被 k 整除” : number mod k=0; (2) 细化“k 达到 lim”: k<=lim; 第四步:补充完整程序。 第五步:从所有的素数除了 2 之外都是奇数的角度出发优化程序。

十三.程序设计步骤
1.分析问题: 对要解决的问题,首先必须分析清楚,明确题目的要求,列出所有已知量,找出题目的求解范 围、解的精度等。例兔子的繁殖问题,必须找出其繁殖规律。 2.建立数学模型: 对实际问题进行分析之后, 找出它的内在规律, 就可以建立数学模型。 只有建立了模型的问题, 才能可能利用计算机来解决。如上例,可推出递推公式 u[n]=u[n-1]+u[n-2](这是菲波那契数 列) 3.选择算法: 建立数学模型后,还不能着手编程序,必须根据数据结构,解决问题的算法。一般选择算法要 注意: (1) 算法的逻辑结构尽可能简单; (2) 算法所要求的存贮量应尽可能少; (3) 避免不必要的循环,减少算法的执行时间; (4) 在满足题目条件要求下,使所需的计算量最小。 4.编写程序: 把整个程序看作一个整体,先全局后局部,自顶向下,一层一层分解处理,如 果某些子问题的算法相同而仅参数不同,可以用子程序来表示。 5.调试运行; 6.分析结果; 7.写出程序的文档: 主要是对程序中的变量、函数或过程作必要的说明,解释编程思路,画出框图,讨论运行结果 等。 8.例 1:输入奇数 n,计算并输出 n 位的魔方阵。(ppro2.pas) 说明: (1) 魔方阵就是 n*n 个不同的正整数按方阵排列时, 它的每一行, 每一列以及沿对角线的几个 数的和具有同一性质的方阵。 (2) 由 1 到 n*n 个自然数数构成的魔方阵是最基本的,又称为“幻方” ,这种方阵的每行、每 列和每个对角线上的元素的和全部相等,亦即等于一个常数。该常数是 n(n*n+1)/2。 (3) 方法: 首先确定 1 的位置,通常放在第一行的中间位置; 然后当前自然数的右上方放下 一个自然数; 如果当前自然数在第一行但不在最右侧,则下一个自然数在最后一行,列

- 41 -

数右移一列; 如果当前自然数在第一行最右侧,则下一个自然数在当前自然数的下侧; 如果当前自然数在其它行的最右侧,则下一个自然数在上一行的最左侧。 9.例 2:任何一个整数的立方都可以写成一串奇数之和。 说明: (1)这是著名的尼科梅切斯定理。即 1^3=1 2^3=3+5=8 3^3=7+9+11=27 …… (2)数据间关系的规律: n^3 是 n 个奇数之和,如 2^3 是 2 个奇数之和,3^3 是 3 个奇数之和; 这 n 个奇数是相邻的,只要知道各式的第一个奇数也就知道所有的 n 个奇数: 组成 1^3 的 1 个奇数是奇数序列中的第 1 个奇数; 组成 2^3 的 2 个奇数中最大的奇数是奇数序列中的第 3(3=1+2)个奇数(值为 5); 组成 3^3 的 3 个奇数中最大的奇数是奇数序列中的第 6(6=1+2+3)个奇数(值为 11); 由此推出: 组成 n^3 的 n 个奇数中最大的奇数是奇数序列中的第 m(m=1+2+3+...+n)个奇数,即: m=n(n+1)/2 奇数序列中第 m 个奇数的值是:modd=2m-1 modd 表示“第 m 个奇数” ,是组成 n^3 的奇数序 列中最大的一个奇数。 例如,第 2 个奇数是 3,第 6 个奇数是 11。 n^3=modd+(modd-2)+(modd-4)+...(modd-2(n-1))

- 42 -

数据结构基础
一、基本概念和术语
数据(Data) 数据是信息的载体。 它能够被计算机识别、 存储和加工处理, 是计算机程序加工的"原料"。 数据元素(Data Element) 数据元素是数据的基本单位。数据元素也称元素、结点、顶点、记录。 一个数据元素可以由若干个数据项(也可称为字段、域、属性)组成。 数据项是具有独立含义的最小标识单位。 数据结构(Data Structure) 数据结构指的是数据之间的相互关系,即数据的组织形式。 1.数据结构一般包括以下三方面内容: ① 数据元素之间的逻辑关系,也称数据的逻辑结构(Logical Structure) ; 数据的逻辑结构是从逻辑关系上描述数据,与数据的存储无关,是独立于计算机的。数据 的逻辑结构可以看作是从具体问题抽象出来的数学模型。 ② 数据元素及其关系在计算机存储器内的表示,称为数据的存储结构(Storage Structure) ; 数据的存储结构是逻辑结构用计算机语言的实现(亦称为映象) ,它依赖于计算机语言。 对机器语言而言,存储结构是具体的。一般,只在高级语言的层次上讨论存储结构。 ③ 数据的运算,即对数据施加的操作。 数据的运算定义在数据的逻辑结构上, 每种逻辑结构都有一个运算的集合。 最常用的检索、 插入、删除、更新、排序等运算实际上只是在抽象的数据上所施加的一系列抽象的操作。 2.数据的逻辑结构分类 在不产生混淆的前提下, 常将数据的逻辑结构简称为数据结构。 数据的逻辑结构有两大类: (1)线性结构 线性结构的逻辑特征是:若结构是非空集,则有且仅有一个开始结点和一个终端结点,并 且所有结点都最多只有一个直接前趋和一个直接后继。 线性表是一个典型的线性结构。栈、队列、串等都是线性结构。 (2)非线性结构 非线性结构的逻辑特征是:一个结点可能有多个直接前趋和直接后继。广义表、树和图等 数据结构都是非线性结构。 3.数据的四种基本存储方法 数据的存储结构可用以下四种基本存储方法得到: (1)顺序存储方法 该方法把逻辑上相邻的结点存储在物理位置上相邻的存储单元里, 结点间的逻辑关系由存 储单元的邻接关系来体现。由此得到的存储表示称为顺序存储结构 (Sequential Storage Structure) ,通常借助程序语言的数组描述。该方法主要应用于线性的数据结构。非线性的数 据结构也可通过某种线性化的方法实现顺序存储。 (2)链接存储方法 该方法不要求逻辑上相邻的结点在物理位置上亦相邻, 结点间的逻辑关系由附加的指针字 段表示。由此得到的存储表示称为链式存储结构(Linked Storage Structure),通常借助于

- 43 -

程序语言的指针类型描述。 (3)索引存储方法 该方法通常在储存结点信息的同时,还建立附加的索引表。 索引表由若干索引项组成。 若每个结点在索引表中都有一个索引项, 则该索引表称之为稠 密索引(Dense Index) 。若一组结点在索引表中只对应一个索引项,则该索引表称为稀疏索引 (Spare Index)。索引项的一般形式是:(关键字、地址)。关键字是能唯一标识一个结点的那 些数据项。 稠密索引中索引项的地址指示结点所在的存储位置; 稀疏索引中索引项的地址指示 一组结点的起始存储位置。 (4)散列存储方法 该方法的基本思想是:根据结点的关键字直接计算出该结点的存储地址。 四种基本存储方法,既可单独使用,也可组合起来对数据结构进行存储映像。 同一逻辑结构采用不同的存储方法, 可以得到不同的存储结构。 选择何种存储结构来表示 相应的逻辑结构,视具体要求而定,主要考虑运算方便及算法的时空要求。 4.数据结构三方面的关系 数据的逻辑结构、 数据的存储结构及数据的运算这三方面是一个整体。 存储结构是数据结 构不可缺少的一个方面:同一逻辑结构的不同存储结构可冠以不同的数据结构名称来标识。 【例】线性表是一种逻辑结构,若采用顺序方法的存储表示,可称其为顺序表;若采用链 式存储方法,则可称其为链表;若采用散列存储方法,则可称为散列表。 数据的运算也是数据结构不可分割的一个方面。在给定了数据的逻辑结构和存储结构之 后,按定义的运算集合及其运算的性质不同,也可能导致完全不同的数据结构。 【例】若对线性表上的插入、删除运算限制在表的一端进行,则该线性表称之为栈;若对 插入限制在表的一端进行, 而删除限制在表的另一端进行, 则该线性表称之为队列。 更进一步, 若线性表采用顺序表或链表作为存储结构, 则对插入和删除运算做了上述限制之后, 可分别得 到顺序栈或链栈,顺序队列或链队列。

二、

线性结构——数组、栈和队列

线性结构是最简单且最常用的数据结构。 一、 线性表 从表的定义不难看出表具有以下数学性质: 除了表头和表尾外, 表中的每一个元素有且仅 有唯一的前驱和唯一的后继,表头有且只有一个后继,表尾有且只有一个前驱。 存储结构:顺序存储结构、链式存储结构。 注意:表和数组的区别 从概念上来看,表是一种抽象数据类型;数组是一种具体的数据结构。

☆顺序存储: 当需要在顺序存储的线性表中插入一个数据元素时,需要顺序移动后续的元素以“腾”出 某个合适的位置放置新元素。删除元素呢?

- 44 -

☆链式存储:

插入新元素的时候只需要改变指针所指向的地址。 ⒈表的数组实现 既简单又自然的顺序存储方法是将表中的元素逐个存放于数组的一些连续的存储单元中。 在这种表示方式下,容易实现对表的遍历。要在表的尾部插入一个新元素,也很容易。但是要 在表的中间位置插入一个新元素, 就必须先将其后面的所有元素都后移一个单元, 才能腾出新 元素所需的位置。执行删除运算的情形类似。如果被删除的元素不是表中最后一个元素,则必 须将它后面的所有元素前移一个位置,以填补由于删除所造成的空缺。 ⒉表的指针实现 实现表的另一种方法是用指针将存储表元素的那些单元依次串联在一起。 这种方法避免了 在数组中用连续的单元存储元素的缺点, 因而在执行插入或删除运算时, 不再需要移动元素来 腾出空间或填补空缺。 然而我们为此付出的代价是, 需要在每个单元中设置指针来表示表中元 素之间的逻辑关系,因而增加了额外的存储空间的开销。 ⒊循环链表 我们在用指针实现表时,表中最后一个元素所在单元的指针域(next)为空指针 nil。如果 将这个空指针改为指向表头单元的指针就使整个链表形成一个环。 这种首尾相接的链表称为循 环链表。在循环链表中,从任意一个单元出发可以找到表中其他单元。

(a)非空表

(b)空表

⒋双链表 如果我们希望能快速确定表中任一元素的前驱和后继元素所在的单元, 可以在链表的每个 单元中设置两个指针,一个指向后继,另一个指向前驱,形成双向链表或简称为双链表。

二、一维数组 1.一维数组的存储 由于数组中所有元素属于同一类型,所以每个元素在存储器中占用的空间大小相同。 假设数组的第一个元素存放的位置为 LOC(k[1]),每个元素占用的空间大小为 S,则 k[i] 的存放位置为:

- 45 -

LOC(k[i])=LOC(k[1])+S*(i-1) 2.一维数组的操作——元素的插入和删除 由于需要保持运算结果仍然是顺序存储, 所以在进行元素的插入和删除时可能要移动一系 列元素。例子:Josephus(约瑟夫)问题。 3.例题: (1)猴子选大王——n 只猴子选大王,选举办法如下:从头到尾 1,2,3 报数,凡报 3 的退 出,余下的从尾到头 1,2,3 报数,凡报 3 的退出..如此类推,当剩下两只猴子时,取这时报 . 1 的为王,若想当猴王,请问当初应占据什么位置? (2)狐狸捉兔子——围绕着山顶有 10 个洞,狐狸要吃兔子,兔子说: “可以,但必须找到 我,我就藏身于这十个洞中,你从 10 号洞出发,先到 1 号洞找,第二次隔 1 个洞找,第三次 隔 2 个洞找,以后如此类推,次数不限。 ”但狐狸从早到晚进进出出了 1000 次,仍没有找到兔 子。问兔子究竟藏在哪个洞里? (3)约瑟夫问题——设有 n 个人围坐在一个圆桌周围,现从第 s 个人开始报数,数到第 m 的人出列,然后从出列的下一个人重新开始报数,数到第 m 的人又出列,……,如此重复直到 所有的人全部出列为止。 对于任意给定的 n,s 和 m, 求出按出列次序得到的 n 个人员的顺序表。 三、多维数组 多维数组是在一维数组的基础上发展起来的, 可以看成由多个一维数组组成。 储存一个数 组中的所有元素,可以用线性序列来表示。以二维数 Amn 为例,储存元素的规律通常有“行优 先”和“列优先” 。 A32 = a11 a12 a13 a21 a22 a23 a31 a32 a33 按“行优先”的顺序:a11 a12 a13 a21 a22 a23 a31 a32 a33 按“列优先”的顺序:a11 a21 a31 a12 a22 a32 a13 a23 a33 将二维数组 Amn 按“行优先”顺序储存在内存以后,元素 aij 的地址计算函数为: LOC(aij)=LOC(a11)+(i-1)*n+(j-1) 按“列优先”顺序储存在内存以后,元素 aij 的地址计算数为: LOC(aij)=LOC(a11)+(j-1)*m+(i-1) 三维数组 Almn 按“行优先”为:LOC(aijk)=LOC(a111)+(i-1)*m*n+(j-1)*n+(k-1) 按“列优先”为:LOC(aijk)=LOC(a111)+(k-1)*l*m+(j-1)*l+(i-1) 四、 栈 1.栈的特点: 栈是一种线性表,对于它所有的插入和删除都限制在表 的同一端进行,这一端叫做栈的“顶” ,另一端则叫做栈的 “底” ,其操作特点是“后进先出”(Last In First Out)表, 简称为 LIFO 表。不含任何元素的栈称为空栈。 2.栈的一般定义: type stack=record

- 46 -

data:array[1..m] of datatype; t:0..m end; var s:stack; 3.栈的基本运算: (1)栈的插入 push(s,x):往栈 st 中推入一个值为 x 的项目; 若 t=m 则 print('overflow') 否则 t:=t+1;data[t]:=x; (2)栈的弹出 pop(s):从栈 st 中弹出一个项目; 若 t=0 则 print('underflow') 否则 t:=t-1; (3)读栈顶元素 top(s,x):把栈顶元素的值读到变量 x 中,栈保持不变; 若 t=0 则 print('error') 否则 x:=data[t]; (4)判栈是否为空 sempty(s):这是一个布尔函数,当栈 st 中没有元素(即 t=0)时,称它为空 栈,函数取真值,否则值为假。 若 t=0 则 sempty:=true 否则 sempty:=false;

上图展示了顺序栈中数据元素和栈顶指针之间的对应关系。 4。栈的应用之一——计算表达式的值。 表达式求值是程序设计语言编译中的一个最基本问题。它的实现是栈应用的一个典型例 子。这里介绍一种简单直观,广为使用的算法,通常成为“算符优先法” 。 要把一个表达式翻译成正确求值的一个机器指令序列, 或直接对表达式求值, 首先要能够 正确解释表达式要对表达式求值,首先要了解算术四则运算的规则。即: 1)先乘除,后加减; 2)从左算到右; 3)先括号内,后括号外。 算符优先法就是根据这个运算优先关系的规定来实现对表达式的编译或解释执行的。 任何一个表达式都是由数, 运算符和界限符组成的, 我们称它们为单词。 为了叙述的简洁, 我们 仅讨论简单算术表达式的求值问题。这种表达式只含加,减,乘,除等四种运算符。读 者不难将它推 广到一般的表达式上。

- 47 -

我们把运算符和界限符统称为算符,它们构成的集合命名为 OP。根据上述三条运算规则, 在运算 的每一步中, 任意两个相继出现的算符θ1 和θ2 之间的优先关系至多是下面三种关系 之一;θ1<θ2 θ1 的优先权低于θ2 θ1="θ2 θ1 的优先权等于θ2" θ1>θ2 θ1 的优先 权高于θ2 下表定义了算符之间的这种优先关系。

为实现算符优先算法,可以使用两个工作栈。一个称作 OPTR,用以寄存运算符;另一个 称作 POND ,用以寄存操作数或运算结果。算法的基本思想是: 1)首先置操作数栈为空,表达式起始符"#"为运算栈的栈底元素; 2)依此读入表达式中每个字符,若是操作数则进 OPND 栈,若是运算符,则和 OPTR 栈的栈 顶 运算符比较优先权后作相应操作,直至整个表达式求值完毕(即 OPTR 栈的栈顶元素和当前 读入的字符均为"#")。 以下算法描述了这个求值过程。 FUNC exp_reduce:operandfype; {算术表达式求值的算符优先算法。 假定从终端输入的表达式无语法错误, 以"#"作结束符。 设 OPTR 和 OPND 分别为运算符栈和操作数栈,OP 为运算符的集合} INISTACK(OPTR);PUSH(OPTR,'#');INISTACK(OPND); {栈初始化,并在运算符栈的栈底压入表达式左端的虚设字符'#'} read(w);{从终端接受一个字符} WHILE NOT ((w='#')AND(GETTOP(OPTR)='#'))DO IF w NOT IN op THEN PUSH(OPND,w) ELSE CASE precde(GETTOP(OPTR),w)OF '<':[PUSH(OPTR,w);read(w)];{栈顶元素优先权低} '=":[x: =POP(OPTR);read(w)];{脱括弧并接受下一字符} ">':[theta:=POP(OPTR); b:=POP(OPND); a:=POP(OPND); PUSH(OPND,operate(a,theta,b))]{退栈并将运算结果入栈} ENDC; RETURN(GETTOP(OPND)) ENDF;{exp_reducde} 算法中还调用了两个函数。 其中 precede 是判定运算符栈的栈顶运算符θ1 与读入的运算 符θ2 之间优先关系的函数;orerate 为进行二元运算 aθb 的函数,如果是编译表达式,则产 生这个运算的一组相应指令并返回存放结果的中间变量名; 如果是解释执行表达式, 则直接进 行该运算,并返回运算结果。

- 48 -

例:利用算法 exp_reducde 对算术表达式 3*(7-2)求值,操作过程如下所示。

5. 栈的应用之二——递归算法的非递归实现。 栈的另一个重要应用是在程序设计语言中实现递归过程。 一个直接调用自己或通过一系列 的过程语句间接地调用自己的过程,称做递归过程。 例如, PROCEDURE A; BEGIN A; END; 过程 A 中的语句 A 直接调用了过程 A 本身,这叫做直接递归调用。又如: PROCEDURE B; PROCEDURE C; BEGIN BEGIN C; C; END; END; 在过程 B 中调用了过程 C,而过程 C 又调用了过程 B.这两个过 程都通过另一个过程调用了它们自己, 这就叫做间接调用。 递归是程序设计中一个强有力的工具。 其一,有很多数学函数是递归定义的,如大家熟悉的阶乘函数 Fact(n)=1 若 n = 1 Fact(n)= nFact(n-1) 若 n >1 2 阶 Fibonacci 数列 Fib(n)=0 若 n=0 Fib(n)=1 若 n=1 Fib(n)=Fib(n-1)+Fib(n-2) 其 它 情 形 和 Ackerman 函 数 Ack(m,n)=n+1 m=0 Ack(m,n)=Ack(m-1,1) n=0 Ack(m,n)=Ack(m-1,Ack(m,n-1)) 其它情形等; 其二,有的数据结构,如二叉树,广义表等,由于结构本身固有的递归特性,则它们的操作可 递归地描述; 其三,还有一类问题,虽则问题本身没有明显的递归结构,但用递归求解比迭代求解更简单, 如八皇后问题,Hanio 塔问题等. 练习: (1998)栈 S 初始状态为空,现有 5 个元素组成的序列{1,2,3,4,5},对该序列在栈 练习: S 上一次进行如下操作(从序列中的 1 开始,出栈后不再进栈) :进栈、进栈、进栈、出栈、 进栈、出栈、进栈。问出栈的元素序列是______D (A){5,4,3,2,1} (B) {2,1} (C) {2,3} (D) {3,4} 五、 队列 1.队列的特点: 队列也是一种线性表, 对于它所有的插入都在队列的一端进行, 所有的删除都在另一端进 行,进行删除的一端叫队列的“头” ,进行插入的一端叫队列的“尾” ,其操作特点是“先进先 出”(First In First Out)表,简称 FIFO 表。

2.队列的一般定义:

- 49 -

type queue=record data:array[1..m] of datatype; head,tail:1..m end; var q:queue; 3.队列的基本操作: (1)队列的插入 enq(q,x):在队列 q 中插入一个值为 x 的元素,也称为进队; q[tail]:=x; 若 tail=m 则 tail:=1 否则 tail:=tail+1; 若 tail=head 则 print('overflow') (2)队列的删除 deq(q):从队列 q 中删除一个元素,也称为出队; 若 tail=head 则 print('underflow') 否则 若 head=m 则 head:=1 否则 head:=head+1; (3)读队头元素 head(q,x):将队列 q 中头部元素的值读到 x 中; 若 tail=head 则 print('error') 否则 x:=q[head]; (4)判队列是否为空 qempty(q):这是一个布尔函数,当 q 是空队列时,取真值,否则取假值。 若 tail=head 则 qempty:=true 否则 qempty:=false; ☆ 循环队列 头指针指向队列中队头元素的前一个位置,尾指针指示队尾元素在队列中的当前位置。

(R-F+N) mod N

六、 串 一.串的概念 串又称为字符串,是由 0 个或多个字符组成的有限序列。长度为 0 的串称为空串,它不包 含任何字符。串用'和'括起来。 二.串的运算

- 50 -

1.串的定义: 一般用一维数组实现串的运算,由此串的定义也用数组的形式来实现: type stringtype=packed array[1..80] of char; var s:stringtype; 另外,还有一种更简便的定义方法,利用 turbo pascal 中的 string 类型: var s:string; 但是 string 类型有一个限制:运用 string 类型定义的数据长度只能是 1——255,也就 是说不能超过 255 个字符。 2.串的标准函数 在 turbo pascal 中有如下标准函数可实现串的运算: copy(s,x,y):获取从 s 的第 x 个位置开始的 y 个字符 concat(s1,s2,...,sn):相等于 s1+s2+...+sn delete(s,x,y):将 s 中从第 x 个位置开始的 y 个字符删去 insert(s1,s,x):将 s1 插到 s 中的第 x 个位置 length(s):获取 s 的长度 3.串的基本运算 (1)赋值 (2)连接 (3)求串长 (4)取子串 (5)求子串序号 (6)插入 (7)删除 (8)置换 三.串的匹配算法 四.练习题: 1.读入一英文句子,单词之间用空格或逗号隔开,统计其中单词个数,并输出各个字母出 现的频率。(句子末尾不一定用"."结束)

三、重要的数据结构——树
1、树的一些基本知识 树是一种重要的非线性结构, 它为计算机中出现的具有层次关系和分支关系的数据提供了 一种自然的表示,在解决各种算法问题中具有广泛的应用。 ①树的定义:树是 N 个结点的有限集合。 在一棵非空树中: Ⅰ有且仅有一个特定的称为根的结点。 Ⅱ当 N>1 时,其他结点可分为 M(M>0)个互不相交的有限集

- 51 -

T1,T2,……,TM,其中每一个集合本身又是一棵树,并且称为根的子树。 这是一个递归的定义,即在树的定义中又用到树的概念,道出了树的固有特性。 ②基本术语 Ⅰ结点:包含一个数据元素及若干指向其子树的分支。 Ⅱ结点的度:一个结点拥有的子树的个数。 Ⅲ树叶:度为 0 的结点。 Ⅳ孩子和双亲:结点的各子树称为该结点的子女,相应地该结点称为其子女的双亲。 Ⅴ结点的层次:根为第一层,其他任何结点的层数等于它的双亲结点的层数加 1。 Ⅵ树的度:树内各结点的度的最大值。 Ⅶ树的深度:树中结点的最大层次。 Ⅷ树的宽度:同一层上结点数的最大值。 2、二叉树: 二叉树: 如果将树中结点的各子树看成从左至右是有次序的(即不能交换) ,则称该树是有序树, 否则称为无序树。 二叉树: 特点是每个结点至多只有二棵子树 (即二叉树中不存在度大于 2 的结点) 并且, , 二叉树的子树有左右之分, 其次序不能任意颠倒。 即使结点只有一棵子树, 也要说明是左子树, 还是右子树。

结论:Ⅰ二叉树第 I 层最多有 2 结点。 k Ⅱ深度为 K 的二叉树,它的结点数一定小于等于 2 -1 Ⅲ对任何一棵二叉树,如果其叶子为 n0,度为 2 的结点为 n2,则 n0=n2+1。 (思考) 特例:Ⅰ空树和只有根结点的树也为二叉树。 Ⅱ如果一棵二叉树每一层上的结点个数都达到最大值,则该树称为满二叉树。 Ⅲ若一棵二叉树中,只有最下两层的结点的度小于 2,且最下层的结点都集中在最左 边的若干位置,则该二叉树称为完全二叉树(满二叉树也是完全二叉树) n 性质:具有 N 个结点的完全二叉树的深度为[log2 ]+1 二叉树的遍历: 3、二叉树的遍历: 限定先左后右:先序遍历、中序遍历、后序遍历。 ⒈先序遍历:访问根结点→先序遍历根结点的左子树→先序 遍历根结点的右子树。ABDFGCEH ⒉中序遍历:中序遍历根结点的左子树→访问根结点→中序遍历 根结点的右子树。BFDGACHE

i-1

- 52 -

⒊后序遍历:后序遍历根结点的左子树→后序遍历根结点的右子树→访问根结点。 FGDBHECA 哈夫曼树: 4、哈夫曼树: 树的路径长度:叶结点到根结点的路径长度之和。 在结点数相同的二叉树中,完全二叉树的路径最短。 二叉树的带权路径长度定义为所有叶结点的权与它到根结点路径长度的乘积之和。 使二叉树带权路径长度取最小值的树称为哈夫曼树或最优二叉树。 构建哈夫曼树的思路应该是由叶结点逐次合并成二叉树。 先合并最小的两个结点成一体, 并得新权,再合并最小的两个结合,……,以此类推,一直到所有结点被合并。 (见过程) 二叉树的存储结构: 5、二叉树的存储结构: 完全二叉树的顺序存储:基于完全二叉树的结构特点,通常采用顺序存储方式,对于有 n 个结点的完全二叉树,把所有的结点从 1 到 n 编号,一般情况下,按结点层次从小到大,同 一层从左到右顺序排列。 例: A 存储表示: 1 A 2 B 3 C 4 D 5 E 6 # 7 F 8 # 9 # 10 G

B

C

E F 1.在这一方式下,从一个结点的编号就可以推测其双亲, D 左右子女的编号。 G 2.从表示一棵二叉树的线性序列,可画出些二叉树。 题目:下面是一个利用完全二叉树特性,用顺序表来存储的一棵二叉树,结点数据为字 符形(#表示空结点,@表示存储数据结束) 。 现要求画出该存储结构对应的二叉树示意图。
1 A 2 B 3 C 4 # 5 # 6 D 7 E 8 # 9 # 10 # 11 # 12 # 13 G 14 F 15 @

分析: 画出具有 15 个结点的完全二叉树, 然后在对应的完全二叉树结点位置上填上字符。 (见表) 解析信息学竞赛中出现的与树的竞赛题: 6、解析信息学竞赛中出现的与树的竞赛题: ①一棵二叉树的高度为 h,所有结点的度为 0,或为 2,则此树最少有( )个结点。 (第七届 分区联赛初赛选择题第 19 题) h B 2h-1 C 2h+1 D h+1 A 2 -1 分析:此题主要考学生对树的基本概念。 树的高度:树中结点的最大层次数。 树的度:结点拥有的子树的个数。 画出符合条件的二叉树的基本形状。 (见过程) ————————————————————————— ②在有 N 个叶子节点的哈夫曼树中,结点总数为( ) (第六届初赛选择题第 12 题) A 不确定 B 2N-1 C 2N+1 D 2N 分析:1 哈夫曼树在构建过程中,是没有度为 1 的结点。 二叉树结点总数为:M=N0+N1+N2(N0、N1、N2 分别表示度为 0、1、2 的结点)

- 53 -

除根结点以外,其他结点一定是子女结点: M=N1+2N2+1 N0=N2+1 N2=N0-1 M=2N0-1 2 其实上题就是一棵哈夫曼树,叶结点数等于树的深度。 ————————————————————————— ③已知一棵二叉树的结点名为大写英文字母,其中序与后序遍历的顺序为:CBGEAFHDIJ 与 CGEBHFJIDA 则该二叉树的先序为: (第七届初赛问题求解第 1 题) 分析:1 要求学生掌握二叉树的遍历。 2 由树的遍历可知: 中序遍历的字符串构成为:左子树结点+根结点+右子树结点 后序遍历的字符串构成为:左子树结点+右子树结点+根结点 可以看出: 后序遍历最后一个字符为根结点 在中序遍历中,根结点左边的是左子树,根结点右边的是右子树。分出左右子树,根据 树的遍历的递归性,再对左右子树进行建树。 (见过程) 最后得先序遍历:ABCEGDFHIJ ————————————————————————— ④问题描述:给出一棵二叉树的中序与后序排列,求出它的先序排列。 (约定树结点用不同的 大写字母表示,长度<=8) 。 样例:输入:BADC BDCA 输出:ABCD(第七届分区联赛复赛普及组第 3 题) 分析:⒈根据上题的分析我已明白了求解过程。但是我们来推导求解的,现在要求是让 计算机来求解。树的遍历本身就是递归定义的,因此解决树的遍历最直接的方法就是递归。考 虑到本题的规模比较小(树的结点个数不超过 8) ,故可以直接用递归实现。 ⒉参考程序(简化了程序,不判断错误的输入,改用二字符接收输入) program fiststr(input,output); var mstr,sstr:string; procedure make(midstr,sucstr:string); var i:integer; begin write(copy(sucstr,length(sucstr),1));*输出根结点 i:=pos(copy(sucstr,length(sucstr),1),midstr);*测试根结点在中序遍历字符串中的 位置 if i>1 then make(copy(midstr,1,i-1),copy(sucstr,1,i-1));*如果有左子字符串 则处理左子字符串 if i<length(sucstr) then make(copy(midstr,i+1,length(midstr)-i), copy(sucstr, i, length(midstr)-i));*如果有右子字符串则处理右子字符串 end;

- 54 -

begin write('input data:'); readln(mstr); readln(sstr); make(mstr,sstr); end. 程序中相应的函数 length(string):求字符串长度 copy(string,n1,n2):从字符串 string 的第 n1 个字符开始复制 n2 个字符 pos(substring,string):测试字符 substring 在 string 中的起始位置 相应的其他一些函数: concat(s1,s2,…):将字符串连接起来 delete(substring,string):在字符串中删去 substring insert(substring,string,n):在字符串 string 的第 n 个位置插入 substring 考虑:由该题是否可以得出已知先序遍历和后序遍历能否唯一决定二叉树的结论? 答案:并不能! 例:二叉树 A A 先序遍历都是 AB,后序遍历都是 BA 而先序遍历和中序遍历,可确定一棵二叉树。 B B ———————————————————————— ⑤已知:按中序遍历二叉树的结果为 ABC 问:有多少种不同形态的二叉树可以得到这一遍历结果,并画出这些树。 (第六届分区赛 初赛问题求解第 1 题) 分析:中序遍历为:按中序遍历左子树+根结点+按中序遍历右子树。 因为先序遍历为 ABC,故该只有 3 个结点。 画出深度为 3 的满二叉树,对任意相邻的三个点画出先序遍历方向。 (见分析过程) ————————————————————— ⑥完成程序: (第三届分区联赛初赛阅读程序写出正确结果第 2 题) 问题描述: 求出一棵树的深度和广度。例如有如下的一棵树: 其树的深度为从根结点开始到叶结点结束的最大深度, 树的宽度为同一层上结点数的最大值。在上图中树的深度为 4,宽度为 3。 用邻接表来表示树,上图中的树的邻接表见表 1。

1

2

3

4

5

6

7

1 2 3 4 5

2 0 5 6 0

3 0 0 0 0

4 0 0 0 0

0 0 0 0 0

0 0 0 0 0

- 55 -

6 7

7 0

0 0

0 0

0 0

0 0

程序说明: 数组 tree 表示树,用邻接表来表示(假设树的度为 4) 数组 q 表示队列,其中 SP1——取出指针,SP2——存入指针,q[I,0]表示层数。 数组 d,统计同一层上的结点数(假设<=20 层) 。 程序清单: PROGRAM NOI00_6; VAR I,J,SP1,SP2,L,MAX:INTEGER; TREE:ARRAY[1..20,1..6] OF INTEGER; Q:ARRAY[1..100,0..6] OF INTEGER; D:ARRAY[0..20] OF INTEGER; BEGIN FOR I:=1 TO 14 DO FOR J:=1 TO 6 DO TREE[I,J]:=0; FOR J:=1 TO 14 DO TREE[J,1]:=J; TREE[1,2]:=2; TREE[1,3]:=3;TREE[1,4]:=4; TREE[2,2]:=5; TREE[2,3]:=6; TREE[3,2]:=7;TREE[3,3]:=8; TREE[4,2]:=9; TREE[4,3]:=10; TREE[4,4]:=11;TREE[7,2]:=12; TREE[7,3]:=13; TREE[13,2]:=14; SP1:=1;SP2:=1; FOR I:=1 TO 6 DO Q[1,I]:=TREE[1,I]; Q[1,0]:=1; WHILE SP1<=SP2 DO BEGIN L:= Q[SP1,0]+1 ; J:=2; WHILE Q[SP1,J]<>0 DO BEGIN SP2:=SP2+1;Q[SP2,0]:=L;Q[SP2,1]:=Q[SP1,J]; FOR I:=2 TO 6 DO Q[SP2,I]:=TREE[Q[SP1,J],I]; J:=J+1 END; SP1:=SP1+1; END; WRITELN (Q[SP2,0]) ; FOR I:=0 TO 20 DO D[I]:=0; FOR I:=1 TO SP2 DO D[Q[I,0]]:= D[Q[I,0]]+1 ; MAX:=D[1]; FOR I:=2 TO 20 DO IF D[I]>MAX THEN MAX:=D[I]; WRITELN(MAX); READLN; END.

- 56 -

四、图
1、图的定义和术语 图是一种数据结构,它的形式化定义为 Graph=(v,r) 其中 V={ x|x<<dataobject} R={VR} VR={ <x,y> | P( x,y )^( x,y <<V)} 在图中的数据元素通常称作顶点 (vertex) 是顶点的有穷非空集合,VR 是两个顶点之 ,V 间的关系的集合。若<x,y><<VR,则 <x,y> 表示从 x 到 y 的一条弧(arc),且称 x 为弧尾 (tail)或初始点(initial node)称 Y 为弧头(head)或终端点(TERMINAL NODE) 此时的图称 为有向图(DIGRAPH) 。若〈X,Y 〉〈VR 必有〈Y,X〉〈VR,即 VR 是对称的,则一无序对(X, 〈 〈 Y)代替这两个有序对表示 X 和 Y 之间的一条边〈EDGE 此时的图称为无向图(UNDIGRPAH) 。 例如图 7.1(A)中 G1 是有向图,-定义此图的谓词 P(X,Y)则表示从 X 到 Y 的一条单向 通路.例如图 7.1(A)中 G1 是有向图, 定义此图的谓词 P(X, Y)则表示从 X 到 Y 的一条单向通路. G1=(V1,{A1}) 其中: V1={V1,V2,V3,V4} A1={(<V1,V2>,<V1,V3>,<V3,V4>,<V4,V1>)} 图 7.1(B)中 G2 为无向图。 G2=(V2{E2}) 其中: V2={V1,V2,V3,V4,V5} E2={(V1,V2),(V1,V4)(V2,V3),(V2,V5)(V3,V4),(V3,V5)}

我们用 N 表示图中顶点数目, E 表示边或弧的数目.在下面的讨论中我们不考顶点到其 用 自身的弧或边,即若<Vi,Vj><<VR,则 Vi!=Vj,那么对于无向图,e 的取值范围是 0 到 1/2 N*(N-1).有 1/2 N*N(N-1)条边的无向图称为完全图(Completed graph);对于有向图,e 的取 值范围是 0 到 n*(n-1).具有 n*(n-1)条弧的有向图称为有向完全图.有很少条边或弧,(如 e<nlogn)的图称为稀疏图(sparse graph),反之称为稠密图(dense graph). 有时图的边或弧具有与它相关的数,这种与图的边或弧相关的数叫做权(weight).这些全 可以表示从一个顶点到另一个顶点的距离或耗费.这种带权的图通常称为网(subgraph) 2、图的存储结构 1)数组表示法 用两个数组分别存储数据元素(顶点)的信息和数据元素之间的关系(边或弧)的信息。 其形式定 义如下: const vtxnum=...,{图的顶点数} type vtxptr=1..vtxnum;bit=0..1

- 57 -

vertex=record ...{和顶点相关的信息} end; arc=record adj:bit;{表示两个顶点之间是否存在关系} ... {和弧(或边)相关的其它信息} end; graph=record vexs:array[vtxptr]of vertex; arcs:array[vtxptr,vtxptr]ofarc end; 若图中顶点只有 1 至 vtxnum 的编号,弧(或边)上亦无权及其它相关信息,则只要以一个二维 数组表示图的邻接矩阵即可,此时的存储结构可简单说明如下:

type adjmatrix=array[vtxptr,vtxptr]of bit; 2)邻接表 邻接表(adhacency)是图的一种链式存储结构。在邻接表中,对图中每个顶点建立一个 单链表,第 i 个单链表中的结点表示依附于顶点 vi 的边(对有向图是以顶点 vi 为尾的弧) 。 若无向图中有 n 个顶点,e 条边,则它的邻接表需 n 个头结点和 2e 个表结点。

在无向图的邻接表中,顶点 vi 的度恰为第 i 个链表中的结点数;而在有向图中,第 i 个链表 中的结点个数只是顶点 vi 的出度。 3)邻接多重表 邻接多重表是无向图的另一种链式存储结构。 其中,mark 为标志域,可用以标记该条边是否被搜索过;ivex 和 jvex 为该条边依附的两个顶 点在图中的位置; ilink 指向下一条依附于顶点 ivex 的边; jlink 指向下一条依附于顶点 jvex

的边。每一个顶点也用一个结点表示,它由如下所示的两个域组成: 其中,data 域存储和该顶点相关的信息,firstedge 域知识第一条依附于该顶点的边。 邻接多重表的类型说明如下: TYPE edgeptr=↑enode;

- 58 -

enode=RECORD mark:0..1; ivex,jvex:vtxptr; ilink,jlink:edgeptr; END; vexnode=RECORD data:vertextype; firstedge:edgeptr; END; adjmulist=ARRAY[vxtptr] OF vexnode;

五、查找
检索又称为查找,是计算机最重要的应用之一。检索的结果有两种可能:找到满足条件的 结点,查找成功;找不到满足要求的结点,查找失败。 动态查找表和静态查找表 若在查找的同时对表做修改操作(如插入和删除), 则相应的表称之为动态查找表。 否则称 之为静态查找表。 内查找和外查找 若整个查找过程都在内存进行,则称之为内查找;反之,若查找过程中需要访问外存,则 称之为外查找。 一、线形查找 线形查找又称顺序查找,对给定的一个关键码值 K,从线形表的一端开始,依次检查 表中每个元素的关键码值,直至找到所需的记录或到达表的另一端。 顺序查找方法既适用于线性表的顺序存储结构, 也适用于线性表的链式存储结构 (使用单 链表作存储结构时,扫描必须从第一个结点开始) 。 平均查找长度为 (n+…+2+1)/n=(n+1)/2 即查找成功时的平均比较次数约为表长的一半。 顺序查找的优点 算法简单,且对表的结构无任何要求,无论是用向量还是用链表来存放结点,也无论结点 之间是否按关键字有序,它都同样适用。 顺序查找的缺点 查找效率低,因此,当 n 较大时不宜采用顺序查找。 二、二分查找 如果被查找的线形表中各记录是按关键码有序的,可以先用表的中间位置上的记录 R[(1+n)/2]的关键码与已知值 K 比较,若相等,则查找成功;否则,根据比较的结果确定下 一步在表的前半部还是后半部中继续查找,这一查找方法称为二分查找。又称折半查找,它是 一种效率较高的查找方法。 二分查找要求:线性表是有序表,即表中结点按关键字有序,并且要用向量作为表的存储 结构。不妨设有序表是递增有序的。 二分查找的基本思想是: (设 R[low..high]是当前的查找区间)

- 59 -

(1)首先确定该区间的中点位置: (2)然后将待查的 K 值与 R[mid].key 比较:若相等,则查找成功并返回此位置,否则须 确定新的查找区间,继续二分查找。 三、分块查找 分块查找又称索引顺序查找。 分块查找是把被查找的表分成若干块, 每块中记录的存放顺序是任意的, 但块与块之间必 须按关键码有序。 即第一块中任一记录的关键码都小于第二块中各记录的关键码, 而第二块中 任一记录的关键码都小于第三块中各记录的关键码,......,等等。这种查找方法要求除被查 找的表本身外,还需建立一个索引表,索引表中的一项对应与表中的一块,它含有这一块中的 最大关键码和指向块内第一个记录位置的指针。 索引表中各项按关键码有序。 分块查找过程分 两步进行,先查索引表(可以用顺序查找方法或二分查找法)确定要找的记录在哪一块。然后 再在相应的块中查找。 四、Hash 查找 散列是一项广泛使用的查找技术。 以上的几种查找方法总要进行关键码的比较, 而散列方 法根据关键码值 K 计算出函数值 H (K) 这个值就是关键码为 K 的记录的存储位置。 , 函数 H (K) 称为散列函数,用这种方法建立的表称为散列表。 当用线性表作为表的组织形式时,可以有三种查找法。其中以二分查找效率最高。但由于 二分查找要求表中结点按关键字有序,且不能用链表作存储结构,因此,当表的插入或删除操 作频繁时,为维护表的有序性,势必要移动表中很多结点。这种由移动结点引起的额外时间开 销,就会抵消二分查找的优点。也就是说,二分查找只适用于静态查找表。若要对动态查找表 进行高效率的查找, 可采用下面介绍的几种特殊的二叉树或树作为表的组织形式。 不妨将它们 统称为树表。下面将分别讨论在这些树表上进行查找和修改操作的方法。 五、二叉排序树 1、二叉排序树的定义 二叉排序树又称二叉查找(搜索)树。其定义为:二叉排序树或者是空树,或者是满足如下 性质的二叉树: ①若它的左子树非空,则左子树上所有结点的值均小于根结点的值; ②若它的右子树非空,则右子树上所有结点的值均大于根结点的值; ③左、右子树本身又各是一棵二叉排序树。 2、二叉排序树的特点 (1) 二叉排序树中任一结点 x,其左(右)子树中任一结点 y(若存在)的关键字必小(大) 于 x 的关键字。 (2) 二叉排序树中,各结点关键字是惟一的。 注意: 实际应用中, 不能保证被查找的数据集中各元素的关键字互不相同, 所以可将二叉排序树 定义中的"小于"改为"大于等于",或将"大于"改为"小于等于",甚至可同时修改这两个性质。 (3) 按中序遍历该树所得到的中序序列是一个递增有序序列。 【例】下图所示的两棵树均是二叉排序树,它们的中序序列均为有序序列:2,3,4,5, 7,8。

- 60 -

六、排序
一、插入排序(Insertion Sort) 1. 基本思想: 每次将一个待排序的数据元素, 插入到前面已经排好序的数列中的适当位置, 使数列依然有 序;直到待排序数据元素全部插入完为止。 2. 排序过程: 【示例】 : [初始关键字] [49] 38 65 97 76 13 27 49 J=2(38) [38 49] 65 97 76 13 27 49 J=3(65) [38 49 65] 97 76 13 27 49 J=4(97) [38 49 65 97] 76 13 27 49 J=5(76) [38 49 65 76 97] 13 27 49 J=6(13) [13 38 49 65 76 97] 27 49 J=7(27) [13 27 38 49 65 76 97] 49 J=8(49) [13 27 38 49 49 65 76 97] Procedure InsertSort(Var R : FileType); //对 R[1..N]按递增序进行插入排序, R[0]是监视哨// Begin for I := 2 To N Do //依次插入 R[2],...,R[n]// begin R[0] := R[I]; J := I - 1; While R[0] < R[J] Do //查找 R[I]的插入位置// begin R[J+1] := R[J]; //将大于 R[I]的元素后移// J := J - 1 end R[J + 1] := R[0] ; //插入 R[I] // end End; //InsertSort // 二、选择排序 1. 基本思想: 每一趟从待排序的数据元素中选出最小(或最大)的一个元素,顺序放在已排好序的数列 的最后,直到全部待排序的数据元素排完。 2. 排序过程: 【示例】 : 初始关键字 [49 38 65 97 76 13 27 49] 第一趟排序后 13 [38 65 97 76 49 27 49] 第二趟排序后 13 27 [65 97 76 49 38 49] 第三趟排序后 13 27 38 [97 76 49 65 49] 第四趟排序后 13 27 38 49 [49 97 65 76]

- 61 -

第五趟排序后 13 27 38 49 49 [97 97 76] 第六趟排序后 13 27 38 49 49 76 [76 97] 第七趟排序后 13 27 38 49 49 76 76 [ 97] 最后排序结果 13 27 38 49 49 76 76 97 Procedure SelectSort(Var R : FileType); //对 R[1..N]进行直接选择排序 // Begin for I := 1 To N - 1 Do //做 N - 1 趟选择排序// begin K := I; For J := I + 1 To N Do //在当前无序区 R[I..N]中选最小的元素 R[K]// begin If R[J] < R[K] Then K := J end; If K <> I Then //交换 R[I]和 R[K] // begin Temp := R[I]; R[I] := R[K]; R[K] := Temp; end; end End; //SelectSort // 三、冒泡排序(BubbleSort) 1. 基本思想: 两两比较待排序数据元素的大小, 发现两个数据元素的次序相反时即进行交换, 直到没有 反序的数据元素为止。 2. 排序过程: 设想被排序的数组 R[1..N]垂直竖立,将每个数据元素看作有重量的气泡,根据轻气泡 不能在重气泡之下的原则,从下往上扫描数组 R,凡扫描到违反本原则的轻气泡,就使其向上 "漂浮",如此反复进行,直至最后任何两个气泡都是轻者在上,重者在下为止。 【示例】 : 49 13 13 13 13 13 13 13 38 49 27 27 27 27 27 27 65 38 49 38 38 38 38 38 97 65 38 49 49 49 49 49 76 97 65 49 49 49 49 49 13 76 97 65 65 65 65 65 27 27 76 97 76 76 76 76 49 49 49 76 97 97 97 97 Procedure BubbleSort(Var R : FileType) //从下往上扫描的起泡排序// Begin For I := 1 To N-1 Do //做 N-1 趟排序// begin NoSwap := True; //置未排序的标志// For J := N - 1 DownTo 1 Do //从底部往上扫描//

- 62 -

begin If R[J+1]< R[J] Then //交换元素// begin Temp := R[J+1]; R[J+1 := R[J]; R[J] := Temp; NoSwap := False end; end; If NoSwap Then Return//本趟排序中未发生交换,则终止算法// end End; //BubbleSort// 四、快速排序(Quick Sort) 1. 基本思想: 在当前无序区 R[1..H]中任取一个数据元素作为比较的"基准"(不妨记为 X),用此基准将当 前无序区划分为左右两个较小的无序区:R[1..I-1]和 R[I+1..H],且左边的无序子区中数据元素 均小于等于基准元素,右边的无序子区中数据元素均大于等于基准元素,而基准 X 则位于最 终排序的位置上, R[1..I-1]≤X.Key≤R[I+1..H](1≤I≤H), R[1..I-1]和 R[I+1..H]均非空时, 即 当 分别对它们进行上述的划分过程,直至所有无序子区中的数据元素均已排序为止。 2. 排序过程: 【示例】 : 初始关键字 [49 38 65 97 76 13 27 49] 第一次交换后 [27 38 65 97 76 13 49 49] 第二次交换后 [27 38 49 97 76 13 65 49] J 向左扫描,位置不变,第三次交换后 [27 38 13 97 76 49 65 49] I 向右扫描,位置不变,第四次交换后 [27 38 13 49 76 97 65 49] J 向左扫描 [27 38 13 49 76 97 65 49] (一次划分过程) 初始关键字 [49 38 65 97 76 13 27 49] 一趟排序之后 [27 38 13] 49 [76 97 65 49] 二趟排序之后 [13] 27 [38] 49 [49 65]76 [97] 三趟排序之后 13 27 38 49 49 [65]76 97 最后的排序结果 13 27 38 49 49 65 76 97 各趟排序之后的状态 Procedure Parttion(Var R : FileType; L, H : Integer; Var I : Integer); //对无序区 R[1,H]做划分,I 给以出本次划分后已被定位的基准元素的位置 // Begin I := 1; J := H; X := R[I] ;//初始化,X 为基准// Repeat While (R[J] >= X) And (I < J) Do begin J := J - 1 //从右向左扫描,查找第 1 个小于 X 的元素//

- 63 -

If I < J Then //已找到 R[J] 〈X// begin R[I] := R[J]; //相当于交换 R[I]和 R[J]// I := I + 1 end; While (R[I] <= X) And (I < J) Do I := I + 1 //从左向右扫描,查找第 1 个大于 X 的元素/// end; If I < J Then //已找到 R[I] > X // begin R[J] := R[I]; //相当于交换 R[I]和 R[J]// J := J - 1 end Until I = J; R[I] := X //基准 X 已被最终定位// End; //Parttion // Procedure QuickSort(Var R :FileType; S,T: Integer); //对 R[S..T]快速排序// Begin If S < T Then //当 R[S..T]为空或只有一个元素是无需排序// begin Partion(R, S, T, I); //对 R[S..T]做划分// QuickSort(R, S, I-1);//递归处理左区间 R[S,I-1]// QuickSort(R, I+1,T);//递归处理右区间 R[I+1..T] // end; End; //QuickSort// 五、堆排序(Heap Sort) 1. 基本思想: 堆排序是一树形选择排序,在排序过程中,将 R[1..N]看成是一颗完全二叉树的顺序存储结 构,利用完全二叉树中双亲结点和孩子结点之间的内在关系来选择最小的元素。 2. 堆的定义: N 个元素的序列 K1,K2,K3,...,Kn.称为堆,当且仅当该序列满足特性: Ki≤K2i Ki ≤K2i+1(1≤ I≤ [N/2])

六、几种排序算法的比较和选择 1. 选取排序方法需要考虑的因素:

- 64 -

(1) 待排序的元素数目 n; (2) 元素本身信息量的大小; (3) 关键字的结构及其分布情况; (4) 语言工具的条件,辅助空间的大小等。 2. 小结: (1) 若 n 较小(n <= 50),则可以采用直接插入排序或直接选择排序。由于直接插入排序所需的 记录移动操作较直接选择排序多,因而当记录本身信息量较大时,用直接选择排序较好。 (2) 若文件的初始状态已按关键字基本有序,则选用直接插入或冒泡排序为宜。 (3) 若 n 较大,则应采用时间复杂度为 O(nlog2n)的排序方法:快速排序、堆排序或归并排序。 快速排序是目前基于比较的内部排序法中被认为是最好的方法。 (4) 在基于比较排序方法中,每次比较两个关键字的大小之后,仅仅出现两种可能的转移,因 此可以用一棵二叉树来描述比较判定过程,由此可以证明:当文件的 n 个关键字随机分布时, 任何借助于"比较"的排序算法,至少需要 O(nlog2n)的时间。 (5) 当记录本身信息量较大时,为避免耗费大量时间移动记录,可以用链表作为存储结构。

- 65 -

竞赛练习题一 一、填空 1、由于运行速度不同,计算机的CPU不能直接与输入输出设备交换数据,而是要通过 来进行。 2、表示一个四位十进制数,至少需要 位二进制数。 3、 计算机所处理的数有 (A) 二进制数、 (B) 进制数, (C) 进制数和 (D) 进 制数,其中 和 本质上是(A) ,它们分别将每三位或每四位(A) 划分成小段,写成便于阅读的形式。 来区分的。 4、迄今为止数字电子计算机已发展了四代,它们主要是以 5、十进制63可写成二进制的 ;十进制32可写成二进制的 ;二进 制11110可写成十进制的 6、表示一个三位十进制数至少需要 位二进制数。 字节;32 位地址线的计算机其最大内存配置为 MB;若该 7、16MB 内存即为 机的数据线为 32 位,则其最大内存配置为 字。 、 (B) 、 (C) 三大 8、计算机语言通常分为(A) 类,其中使用(A)来编程序,计算机能够不用“翻译” ,就可直接识别和执行,而(B) 是用一些称为“助记符”的字母指令的,使用权用(B)来编程序,计算机要把它“翻译” 成(A)才能执行,这个过程称为(D) 。把用 PASCAL 语言“翻译”成(A) 指令代码,有(E) 和(F) 两种方式。人们把(D)(E)执行结 、 程序,而将用(B) (C)编写的程序称作 , 果所产生(A)程序称作 程序。 9、在计算机系统中,根据与中央处理单元联系的密切程度将存贮器分为(A) 、和 两大类,微型计算机中的(A)又分为 存贮器 (B) 和 存贮器。

竞赛例题解析
一、基础部分 一、程序设计基本方法一 1、ASCⅡ码字符输出 2、求自然数 n 的不同因数的个数 3、已知因数个数,求 n 4、求一元多项式在 Xo 处的值 5、NOI'95 第三题 6、统计输入的字符串中的字母频率 7、NOI'95 第一题 8、链表排序问答 二、程序设计基本方法二 1、线性表基本操作单元 2、合并线性表 3、以基准数重量排顺序 4、带头结点的线性表基本操作单元 5、逆序合并链表 6、数组元素逆时针方向赋值 7、求幂集 8、自然数 n 的拆分表达式 9、求 n 的拆分数目

- 66 -

二、提高部分 一、自顶向下逐步求精 1、求最大数、最小数和平均值 2、Faibonacci 数列 3、求 2 个数的最大公因数 4、换钱问题 5、求素数 6、求完全数 7、Nicomachus 定理及应用 8、字符串统计问题 9、字符串加密 10、统计字符串中字符出现的频率 11、数的排列 12、求出数列的 n 项 13、奇数幻方 14、全排列问题 二、回溯算法 1、骑士的游历 1 2、骑士的游历 2 3、迷宫问题 4、砝码问题 5、钱币问题 6、四色问题 7、无根树的编码 8、背包问题(1) 三、动态规划 1、最短路径问题 2、求最长不下降序列 3、最小代价子母树 4、背包问题(2) 5、四塔问题 6、最小代价 7、挖地雷 四、多精度计算 1、多精度加法 2、多精度减法 3、多精度与单精度乘法 4、多精度与多精度乘法 5、多精度与单精度除法 6、多精度与多精度除法(1) 7、多精度与多精度除法(2) 8、数塔问题 9、计算 e 五、递归方法 1、钢板分割成小正方形问题 2、用递归方法求解 8 皇后问题 3、平面直线交点问题 4、推广的哈夫曼编码 5、表达式去括号 六、其他问题 1、过河问题 2、行程问题(1) 3、行程问题(2) 4、求出方程 xn+yn=sn+tn 的最小整数解 5、最小转弯问题 6、士兵排队问题 7、逻辑集成电路 8、平面地砖曲线问题 9、1×2 的骨牌问题 10、钢板切割零件问题 11、工厂零件生产问题 12、取数问题(1) 13、称球问题 14、堆塔问题 15、取数问题(2)

- 67 -

ASCⅡ码字符串输出
一、问题描述 已知两个字符串及其长度,要求将这两个字符串按 ASCⅡ码顺序排列输出。 二、算法设计 输入: 字符串的长度可以设为 m ,n ; 存储的两个字符串可设为数组 A[1..m],B[1..n]。 判断方法: i 从 1 开始,比较 A[i] 和 B[i]: A[i] > B[i] 则 B 在前,A 在后; A[i] < B[i] 则 A 在前,B 在后; A[i] = B[i] 继续对 A[i+1] 和 B[i+1] 比较。 可能发生的情况是逐个字符比较时都相等, 这时短的字符串便排在前面; 如果两个字符相 同而且长度相同,那么它们的排列顺序也无所谓谁在前,谁在后。 特殊情况是字符串长度( m 或 n )≤0 ,这种情况可以作为出错处理。 三、程序设计 比较两个字符串的顺序可以用一个过程 comp 来实现, 比较结果可借助于一个变量参数 k 来存储。 例如:可以约定: K=2 用于控制比较进行(循环控制变量) K=-1 表示 A 在 B 前,比较结束 K=0 表示 B 在 A 前,比较结束 四、程序清单 Pascal: PROGRAM e101; CONST maxlen=20; TYPE a=ARRAY[1..maxlen] OF CHAR; VAR m, n, i, j, k: integer; a, b: s; PROCEDURE comp (A, B: s; m, n: integer; VAR k: integer); VAR i: integer; BEGIN i:=1;k:=2; WHILE K=2 DO BEGIN IF i=m+1 THEN K:=-1 ELSE IF i=n+1 THEN k:=1 ELSE BEGIN IF A[i] < B[i] THEN k:=-1; IF A[i] > B[i] THEN k;=1;

- 68 -

END END END; BEGIN REPEAT writeln ('Input length two string:'); readln(m ,n); IF (m<=0) or (n<=0) THEN writeln('Length >0!!') UNTIL (m>0) and (n>0); writeln('Input first string:'); FOR j:=1 to m DO read(A[j]); readln; writeln('Input second string:'); FOR j:=1 to n DO read(B[j]); readln; comp (A, B, m, n, k); IF k=-1 THEN BEGIN FOR i:=1 TO m DO write(A[i]); write(','); FOR i:=1 TO n DO write(B[j]);writeln; END IF k=1 THEN BEGIN FOR i:=1 TO m DO write(B[i]); write(','); FOR i:=1 TO n DO write(A[j]);writeln; END readln END.

求自然数 n 的不同因数的个数
一、问题描述 任给一个自然数,求出这个自然数不同因数的个数 m。 二、问题分析 下面列举出若干个 n 和 m 的值先看一看: n= 1 2 3 4 5 6 7 8 …… m= 1 2 2 3 2 4 2 4 …… 显然,自然数 1 处于特殊地位;任何素数(大于 1,只有 1 和自己为自然数的因数)的因 数个数都是 2;合数的因数个数 >2,究竟多大则较难寻找出规律来。为此,可以通过试除法 来求出 m。 三、算法设计 当 n=1 时 m=1,是特例: 其他情况的处理如下: m:=2; for i:=2 to k do

- 69 -

if n mod i=0 then m=m+2 其中 k:=trunc(sqrt(n)) 这里取 m=m+2 是因为如果发现 n 的一个小于 √n 的因数, 必然同时有一个大于 √n 的因 数。但对于 n 正好是完全平方数时,上述的 m 应减去 1。 四、程序设计 程序中根据输入的 n,输出因数个数 m。 五、程序清单 Pascal PROGRAM e102-1; VAR n, i, j, k: longint; m: integer; BEGIN REPEAT write('Input N='); readln(n); IF n<=0 THEN writeln('N>0!!') UNTIL n>0 IF n=1 THEN writeln('N=',1:10,'M=',1) ELSE BEGIN j:=n; m:=2; K:=trunc(sqrt(j)); FOR i:=2 to k DO IF j MOD i =0 THEN m:=m+2; IF j=sqr(k) THEN m:=m-1 witeln('N=',j:10,'M=',m); END END.

- 70 -

网络与 Internet
二、网络的定义: 所谓计算机网络, 就是利用通信线路和设备, 把分布在不同地理位置上的多台计算机连接 起来。 计算机网络是现代通信技术与计算机技术相结合的产物。 网络中计算机与计算机之间的通信依靠协议进行。协议是计算机收、发数据的规则。 TCP/IP:用于网络的一组通讯协议。包括 IP(Internet Protocol)和 TCP(Transmission Control Protocol) 三、网络的发展 计算机网络的发展过程大致可以分为三个阶段: 远程终端联机阶段:主机—终端 计算机网络阶段:计算机—计算机 Internet 阶段: Internet 四、网络的主要功能: (1)信息资源共享 (2)数据信息传输 (3)分布处理 (4)综合信息服务 五、网络的分类 按覆盖地域分:局域网、城域网、广域网、Internet 局域网:Local Area Network,简写为 LAN 城域网:Metropolitan Area Network,简写为 MAN 广域网:Wide Area Network,简写为 WAN 按拓扑结构分: (网络拓扑结构是指网络中节点间的物理连接方式) 总线形、星形、环形、 树形、网状形、混合形。 六、网络的体系结构 OSI 七层体系结构(开放式系统互联参考模型) 相互联系,相互制约,下层为上层服务。 每一层汇集着大量协议,由协议来完成该层的功能。 (七层) 应用层 为用户提供操作环境。 (六层) 表示层 格式定义(格式转换,语法转换) (五层) 会话层 源设备与目标设备建立逻辑连接(等效层通讯)保证安全性。 (四层) 传输层 应用程序与网络程序转换。 决定数据用何种方式发送(通过协议决定)。 还 可分割、组合数据,提供数据校验。 (三层) 网络层 产生路由,并对路由进行控制,逻辑地址转化为物理地址,但不把物理地 址加入数据包。 (二层) 数据链路层(硬件) 修复物理层上可能产生的错误, 封装成数据帧。 将物理地址加 入数据包,并且转化为数据位流。包括:逻辑链路控制层(LLC)、介质访问控制层(MAC) (一层) 物理层 电信特性与机械特性。 把数据位流根据网卡内建的介质访问方式, 把数据 位流发送到网络里。

- 71 -

数据产生到发送是自上层(七层)到下层(一层)的顺序添加。而接收是自下到上层层剥离。 七、网络互连设备 把两个或两个以上的网络互连叫互连网。 OSI 七层体系结构中:应用层、表示层、会话层与用户相关。 传输层、网络层、数据链路层、物理层与网络相关。 1.中继器(重发器) 作用:对信号进行放大。 中继器属于物理层设备与协议无关, 只对信号进行简单的增强, 因此中继器不能够隔离错 误。信号经过中继器不产生延时。使用中继器连接的网段是同一个网络,只能把两个同种的以 太网段连到一起。广播能通过中继器。 2.网桥(桥接器):是数据链路层设备(交换机也是数据链路层设备) 具备中继器所有好处同时还具有: A.可以把网络连的更远。 B.可直接读取物理地址,高效快速发送数据帧。 C.可以隔离错误,从而使网络运行更为稳定。 D.网桥会和网卡驱动程序配合使用,可以拦截一些不该转发的数据帧,可使网络变得更 安全。 网卡:网卡属于数据链路层设备,功能是实现计算机设备间的相互通讯。 驱动程序:是硬件与软件间的协议,使用网卡必顺安装驱动程序。 NDIS 驱动程序(网络数据接口标准)用于 windows,unix 操作系统。 ODI 驱动程序(开放式数据接口)是 Novell 公司开发的,用于 netware 操作系统。 E.广播能通过网桥。 F.网桥分类: 本地网桥:由服务器充当网桥,优点是安装容易管理方便,缺点是服务器负担较重时本地 网桥会影响网络性能。 远程网桥:由网络内的一台计算机,通过通讯端口与其它网络连接,并行使网桥功能。 3.路由器(选径器) 使用最广泛,工作在 OSI 网络层,可提供不同类型网络的互连,可对网络层以下的协议进 行转换。拥有网桥的全部功能,并且功能更强大。广播不能通过路由器。路由器有路由表,是 负责管理维护网络信息。路由器有路由选择功能,这是最主要的功能。 4.网关(协议转换器):功能最强大最复杂 拥有路由器全部功能,可以对高层协议进行转换。网关只有专用的,没有通用的,是针对 具体网络的。它工作在传输层。 八、常用协议 1.Netbeui(网络基本输入输出系统,扩展用户接口) IBM 公司 1985 年发布的高速局域网协议,是基于广播的,目前最快的。Internet 不能使 用。 2.Nwlink 是 netware 公司的 IPS/XPS 兼容协议。可使计算机在不用网关情况下直接连到 netware 服务器上。

- 72 -

3.TCP/IP 协议(传输控制协议及 Internet 协议) 功能最强大、完善、复杂的协议,是 Internet 的基础协议。 IPX 协议是网络号+物理地址。TCP/IP 是网络号+主机号。 4.DLC 协议(数据链路控制协议) ⒈可使包含网络内置端口的设备直接连入网络。例:多数段。 ⒉可利用它的运算、存储设备。 九、数据通信中的几个主要指标 a.数据传输速率 是指每秒能传输的二进制代码的位数,单位为位/秒(记为 bit/s 或 bit per second,简 写为 bps) 。如调制解调器的传输速率为 56Kbps。 b.误码率 是衡量数据通信系统在正常工作情况下传输可靠性的指标, 指的是二进制码元传输出错的 概率。如收到 100000 个码元,经检查后发现有一个错了,则误码率为十万分之一。 c.信道容量 表示一个信道的传输能力, 对数字信号用数据传输速率作为指标, 是以信道每秒钟能传输 的比特为单位的,记为比特/秒或位/秒。 十、局域网的工作方式 客户机/服务器(Client/Server): 提供资源并管理资源的计算机称为服务器;使用共享资源的计算机称客户机。 对等(Peer-to-Peer): 不使用服务器来管理网络共享资源,所以的计算机处于平等的地位。 十一、Internet 的形成与发展 又称国际互联网,规范的译名是“因特网” ,指全球范围内由众多网络相互连接而成的计 算机网络。 我国 Internet 的发展情况: 八十年代末,九十年代初才起步。 1989 年我国第一个公用分组交换网 CNPAC 建成运行。 我国已陆续建成与 Internet 互联的四个全国范围的公用网络: 中国公用计算机互联网(CHINANET) 、中国金桥信息网(CHINAGBN) 中国教育和科研计算机网(CERNET) 、中国科学技术网(CSTNET) 十二、Internet 的服务与工具 Internet 的服务有:电子邮件、远程登陆、文件传输、信息服务等 电子邮件(E_mail) : 电子邮件地址格式为:收信人邮箱名@邮箱所在主机的域名例:winner01@ 21cn.com 第一部分是用户的帐号,最后一部分提供该电子邮箱网站的域名地址,两部分要用@连接 起来。 远程登陆(Telnet) :指通过 Internet 与其它主机连接。 登陆上另一主机,你就可以使用该主机对外开放的各种资源,如联机检索、数据查询。 文件传输(FTP) :用于在计算机间传输文件。如下载软件等。 全球信息网(WWW-World Wide Web) :又称万维网,是一个全球规模的信息服务系统,由

- 73 -

遍布于全世界的数以万计的 Web 站点组成。 十三、TCP/IP 基础 ㈠TCP/IP 四层模型 TCP/IP 这个协议遵守一个四层的模型概念:应用层、传输层、互联层和网络、接口层。 ①网络接口层 模型的基层是网络接口层。负责数据帧的发送和接收,帧是独立的网络信息传输单元。网 络接口层将帧放在网上,或从网上把帧取下来。 ②互联层 互联协议将数据包封装成 internet 数据报,并运行必要的路由算法。 这里有四个互联协议: ⑴网际协议 IP:负责在主机和网络之间寻址和路由数据包。 ⑵地址解析协议 ARP:获得同一物理网络中的硬件主机地址。 ⑶网际控制消息协议 ICMP:发送消息,并报告有关数据包的传送错误。 ⑷互联组管理协议 IGMP:被 IP 主机拿来向本地多路广播路由器报告主机组成员。 ③传输层 传输协议在计算机之间提供通信会话。传输协议的选择根据数据传输方式而定。 两个传输协议: ⑴传输控制协议 TCP: 为应用程序提供可靠的通信连接。 适合于一次传输大批数据的情况。 并适用于要求得到响应的应用程序。 ⑵用户数据报协议 UDP:提供了无连接通信,且不对传送包进行可靠的保证。适合于一次 传输小量数据,可靠性则由应用层来负责。 ④应用层 应用程序通过这一层访问网络。 ㈡用户使用 TCP/IP 协议离不开三方面,缺一不可。 A.IP 地址 B.子网掩码 C.缺省网关 ⒈IP 地址 IP 地址是逻辑地址,32 位二进制数,用来标识计算机在网格里的位置。IP 地址必顺是唯 一的。32 位数人为的分成四部分,每部分 8 位数,再转化为十进制数,就是 IP 地址。(四组 0~255 之间的数字),其中包括网络号、主机号。网络号总在前面,主机号在后面。IP 地址是 由 INIC 管理机构分配的,INIC 是负责管理全球 IP 地址的机构,为了便于管理,把网络分为 几类,IP 地址的第一组数代表是第几类网络。 第一组 第二组 第三组 第四组 A 类网: 1 ~ 126 用户定义 用户定义 用户定义 可容纳 255 的三次方台计算机 B 类网: 128~191 给定的 用户定义 用户定义 可容纳 255 的二次方台计算机 C 类网: 192~223 给定的 给定的 用户定义 可容纳 254 台计算机 特殊的 IP 地址: ‘0’代表本地网络地址,无实际意义,代表本机或本网络。(第一个网号代表 本地) ‘127’回环测试用,代表本地计算机。利用‘127’只在主板和网卡之间行成回路。是 测试网卡专用号。(指的是在第一组里,在其它组不起此作用) ‘223’以上是在实验室作实验

- 74 -

专用的。 ‘255’代表广播。(最后的网号代表广播) A 类网 IP 主要分配给各国政府机构。网络号不同时不能直接通讯。 ⒉子网掩码 功能:①可以和 IP 地址进行逻辑运算,正确划分网络号与主机号。子网掩码也是 32 位, 用‘1’标识网络,用‘0’标识主机。 ‘1’总是在前, ‘0’总是在后。也就是网络标识在前, 主机标识在后。把 32 位划分为四部分,每部分 8 位,转换成十进制数字就是子网掩码。 二 进 制 十 进 制 A 类网:11111111.00000000.00000000.00000000 255. 0. 0. 0 B 类网:11111111.11111111.00000000.00000000 255.255. 0. 0 C 类网:11111111.11111111.11111111.00000000 255.255.255. 0 功能:②可通过改变子网掩码,改变对网络划分子网。 例: I P 子网掩码 A 169.254.1.1 255.255.0.0 B 169.254.2.9 255.255.0.0 子网掩码前二部分是 255(十进制)也就是 11111111(二进制)。 ‘1’代表网络号,所以代表 前两部分数字是网络号,而后面的是主机号。A 与 B 的网络号都是前两部分。再看 IP 地址, 前两部分相同,代表 A 与 B 的网络号相同,是处在同一网络内的,A 与 B 可直接通讯。而后两 部分不同,代表主机号不同,代表是两台不同的主机。 例: I P 子网掩码 A 169.254.1.1 255.255.255.0 B 169.254.2.9 255.255.255.0 子网掩码前三部分是 255, 代表 IP 前三部分是网络号,而最后一部分是主机号。IP 前三 部分不是一样的,所以 A 与 B 不处在同一网络内,A 与 B 不能直接能讯。 在子网划分时必然会损失 IP 地址。 例: 子网掩码:11111111.11111111.11100000.00000000 255.255.224.0 第三部分的前三位以前为 网络号,后面为主机号。对网络号 I P:130.5.0.0(十进制) 10000010.00000101.00000000. 00000000(二进制) 进行子网划分,能划分出如下个子网: 10000010.00000101.00000000.00000000 10000010.00000101.00100000.00000000 10000010.00000101.01000000.00000000 10000010.00000101.01100000.00000000 10000010.00000101.10000000.00000000 10000010.00000101.10100000.00000000 10000010.00000101.11000000.00000000 10000010.00000101.11100000.00000000 共划分出八种,其中第一种和最后一种方法不能用。 第一种子网络号 000,表示本网络,最后一种子网络号 111,是子网屏蔽,均不能用。所

- 75 -

以可划分出六个子网。 即: IP: 130.5.0.0 子网掩码 : 255.255.224.0 划分为 IP: 130.5.32.0 130.5.64.0 130.5.96.0 130.5.128.0 130.5.160.0 130.5.192.0 ⒊缺省网关(用来标识网络路由器的地址) 网络通讯离不开网卡和协议,协议要和网卡协调工作,不能独立存在。协议是依附在网卡 上的,协议与网卡协调工作的过程叫协议的绑定。当一个 IP 地址在本网络找不到时,就会自 动找到本网缺省网关,向其它网络查找。缺省网关是网络与网络之间的出入口。(缺省网关也 是 IP 地址,它指向路由器) 一个网络里的 A 机发送数据帧给另一个网络里的 C 机,当在本网络找不到 C 机的 IP 时, 自动找到本网缺省网关即:163.168.45.6 (是已设定的)。这个 IP 地址是路由器的地址,所以 把数据帧发送到缺省网关指定的路由器,在由路由器把数据帧发送到 C 机所在的网络(C 机网 络的缺省网关已存在路由器里),C 机就会接收到不同网络里 A 机发来的数据帧。 ㈢域名(DN) : 虽然可以通过 IP 地址来访问每一台主机,但是要记住那么多枯糙的数字串显然是非常困 难的, 为此, Internet 提供了域名(Domain Name)。 域名解析需要由专门的域名解析服务器 (DNS) 来完成,整个过程是自动进行的。 域名也由若干部分组成,采用层次结构,一个域名一般有 3-5 个子段,各部分之间用小 数点分开。如:www.sina.com.cn 顶级域名有三类: 国家顶级域名,如 cn(中国) 、us(美国) 、uk(英国) ; 国际顶级域名—— int ,国际性组织可在 int 下注册; 通用顶级域名,如:com、net、edu、gov、…… .com 用于商业公司 .org 用于组织、协会等 .net 用于网络服务 .edu 用于教育机构 .gov 用于政府部门 .mil 用于军事领域

- 76 -

计算机病毒
计算机病毒:一种人为制造的、在计算机运行中对计算机信息或系统起破坏作用的程序。 特点:寄生性、传染性、潜伏性、隐蔽性、破坏性。 防范:数据备份、安装防病毒软件、复制文件前先查病毒、不要轻易打开不认识的人寄来 的电子邮件、上网时使用防火墙。

计算机法规
1991,2002 年《计算机软件保护条例》用来保护软件的著作权。 1994 年《中华人民共和国计算机信息系统安全保护条例》为了保护计算机信息系统的安 全,促进计算机的应用和发展。 2000 年《互联网信息服务管理办法》为了规范互联网信息服务活动,促进互联网信息服 务健康有序发展。 四、练习 1.计算机软件保护法是用来保护软件( )的。 A)编写权 B)复制权 C)使用权 D)著作权 2.计算机病毒是( ) A)通过计算机传播的危害人体健康的一种病毒 B)人为制造的能够侵入计算机系统并给计算机带来故障的程序或指令集合 C)一种由于计算机元器件老化而产生的对生态环境有害的物质 D)利用计算机的海量高速运算能力而研制出来的用于疾病预防的新型病毒 3.Email 邮件本质上是一个( )(第七届) A)文件 B)电报 C)电话 D)传真 4.计算机病毒的特点( ) A.传播性、潜伏性、易读性与隐蔽性 B.破坏性、传播性、潜伏性与安全性 C.传播性、潜伏性、破坏性与隐蔽性 D.传播性、潜伏性、破坏性与易读性 5.Internet 的规范译名应为( ) A.英特尔网 B.因特网 C.万维网 D.以太网 6 、Internet 上使用的两个最基本的协议是( ) A、TCP 和 IP B、TCP 和 SPX C、IP 和 SPX D、TCP 和 IPX 7、TCP/IP 协议共有( )层协议 A)3 B)4 C)5 D)6

- 77 -

算法
1、如何用计算机解决实际问题 目前,计算机已广泛地使用到日常生活中的每一个角落,但无论用计算机来解决哪一方面 的问题, 我们都必须把实际问题的解决归结为计算机能够执行的若干个步骤, 然后再把这些步 骤用一组计算机的指令进行描述,最后交给计算机来完成,这些指令就是我们所说的程序。 要设计出解决实际问题的程序,通过可以有以下的几个步骤: ①、 明确问题要求。 即先要对问题进行分析, 明确问题的要求是什么, 要计算机做些什么, 已知什么数据,还有一些什么其他要求。只有弄清问题,才能发现问题的特点与实质,以便采 取有效的方法来解决。 ②、确定计算方法。为了计算机可以解决实际问题,我们必须先用数学方法来描述或模拟 实际问题,把复杂的问题简单化,并且用合理的数学公式来描述。在这个过程中,我们必须比 较精确地知道我们要解决的问题的目标,明确问题的输入与输出,明确问题的约束限制条件, 才能选择、制定好恰当的计算方法。 ③、 算法设计。 当我们确定了计算的方法后, 我们就要在这个基础上设计出解题的步骤(即 算法),并用算法描述工具将算法描述出来。 ④、编写程序。所谓程序,其实就是用计算机语言来描述算法。编写程序的过程实际上就 是用算法描述工具表示的算法转换成计算机语言来描述。 ⑤、调试程序。用上述步骤得到的程序并不能保证其正确性,只有通过上机调试,才能比 较彻底地发现程序中的语法错误与逻辑错误。 ⑥、结果分析。即使程序调试通过,得到运行结果,仍不能说明程序是正确的,还要对运 行的结果进行分析, 看看输出的结果是否符合题目的要求, 以及程序所执行的功能是否与要求 一致。如果发现错误与偏差,则要找出问题出现在哪一个步骤。 2、什么是计算机算法 简单的来说,利用计算机解决实际问题的方法就叫做算法。一般来说,一个算法应具备下 面几个特征: ①、包含有限个操作步骤。 ②、每一个步骤的含义都必须是清楚无误的,不能模棱两可。 ③、每一个步骤都应该是允许使用、可以执行并且最后能得出确定的结果。 ④、有零个或多个输入。 ⑤、有一个或多个输出。没有输出的算法是没有意义的。 3、计算机能做些什么 一个程序由计算机能够执行的基本操作组成。计算机能够执行以下基本操作: ①、数据传送:将数据由输入设备或外存传到内存,由内存送到输出设备或外存,由内存 的一个单元送到另一个单元。 ②、逻辑运算:与、或、非 ③、算术运算:加、减、乘、除、乘方等 ④、比较、判断和转移 4、算法举例 例 1:有两个变量 a 和 b ,要求将它们的值互换。例如:a=3,b=4;互换后 a=4,b=3。

- 78 -

分析:为了进行两个变量的值互换,需引入一个辅助变量 c (正如两个杯子里的液体要互换需 要用第三个杯子过渡一样)。其算法可表示如下: S1:a→c(将变量 a 的值送给变量 c ) S2:b→a(将变量 b 的值送给变量 a ) S3:c→b(将变量 c 的值送给变量 b ) 上面用的 S1、S2、S3 表示步骤的次序,在写算法时常用这种形式的标记。S 是 step(步)的首 字母,S1 表示第一步,S2 表示第二步…… 例 2:找出三个数中的最大数。 分析:找出三个数中的最大,我们人手来分就十分简单,一看就知道哪个是最大数,但如果由 电脑来分,就没有那么直接了,电脑只会每次比较两个数的大小,因此,我们用 max 来存最大 的数, 可以将输入的第一个数存地 max 中, 因为这个时候, 只有一个数, 这个数肯定是最大的。 然后输入第二个数,并与 max 的值进行比较:如果大于 max,则用它取代原 max 的值。再输入 第三个数,并与 max 相比较,处理方法与第二个数相同,这时就可以得出三个数中的最大数。 具体算法如下: S1:输入第一个数放在 max 中 S2:输入第二个数放在 x 中 S3:如果 x>max,那么 x→max S4:输入第三个数放在 y 中 S5:如果 y>max,那么 y→max S6:输出 max S7:结束 例 3:求 1+2+3+……+10。 分析:用变量 sum 来存储累加和,初值为零;变量 n 的初值为 1 。重复执行 10 次以下操作: “sum+n→sum;n+1→n”,则 sum 中的值就是 1 到 10 的累加和。具体算法如下: S1:0→sum S2:1→n S3:如果 n<=10,执行以下操作,否则转到 S4 S3.1:sum+n→sum S3.2:n+1→n S3.3:转到 S3 S4:输出 sum 的值 S5:结束 例 4:求两个正整数 m 和 n 的最大公约数。 分析: 一般来说, 求两个正整数的最大公约数, 我们学过的方法是用短除法, 首先用 2 去除 m 和 n ,看能不能除得尽,可以的话就 m 和 n 各自除以 2 ,然后所得的商继续用 2 来试商, 一直试到没有数可以同时整除剩下的商时, 把所有刚才所用的除数相乘就是最大公约数, 这种 方法在电脑上实现起来比较麻烦。我们现在介绍的是另外一种方法:辗转相除法。用 m 去除 以 n 得商 q 与余数 r ,如果 r=0 那么 n 就是 m 和 n 的最大公约数,否则,把 n→m r→n, 然后再用 m 去除以 n , 求出 r , 如果 r=0 那么现在的 n 就是原来的 m 和 n 的最大公约数, 否则继续上面的方法,直到求出 r=0 为止。具体算法如下:

- 79 -

S1:输入两个正整数 m,n。 S2:求 m/n 的余数→r。 S3:如果 r=0,则转 S6 执行,否则执行 S4 S4:n→m,r→n S5:转 S2 S6:输出 n 。 S7:结束。

也可以写成: S1:输入两个正整数 m,n。 S2:重复执行下面操作,直到 r=0 为止 S2.1:求 m/n 的余数→r S2.2:n→m,r→n S3:输出 m 。 S4:结束。

例 5:兔子繁殖问题:假定每一对兔子在出生两个月后每月都产下一对小兔子,在没有死亡的 情况下,由一对新生兔子开始,第 12 个月有多少对兔子? 分析:第一、二个月有一对兔子,第三个月有两对兔子,第四个月有三对兔子。……那么每月 的兔子数就可以形成以下的一个数字序列: 1,1,2,3,5,8,13,21,34…… 通过分析这个数字序列,我们不难得出以下的递推关系:

按照这一递推关系,我们就可以求出每一个月的兔子数。具体算法如下: S1:1→F1 S2:1→F2 S3:3→i S4:重复执行下面操作,直到 i=12 为止 S4.1:Fi-1+Fi-2→Fi S4.2:i+1→i S5:输出 F12 S6:结束

- 80 -


更多相关文档:

青少年信息学竞赛简要介绍

青少年信息学竞赛简要介绍青少年信息学(计算机)奥林匹克竞赛(早期称为青少年计算机程序设计竞赛)是旨在广 大青少年中普及计算机教育,推广计算机应用的一项学科性竞赛活动...

全国青少年信息学奥林匹克联赛大纲

全国青少年信息学奥林匹克联赛大纲_学科竞赛_高中教育_教育专区。全国青少年信息学...联赛命题委员会的主要职责是提供联赛的备选题目,并承担对所提供的题目保密 的...

全国青少年信息学奥林匹克联赛大纲

简称 NOIP)是全国信息学奥林匹克竞赛(NOI)系列活动中的一个 重要组成部分, 旨在...的主要特征、 计算机的主要特征、 数字通信网络的主要特征、数字化) 2. 信息...

全国青少年信息学奥林匹克联赛大纲

全国青少年信息学奥林匹克联赛大纲_学科竞赛_初中教育_教育专区。全国青少年信息学...五、试题的知识范围 (一)初赛内容与要求: 1.计算机和信息社会(信息社会的主要...

青少年信息学奥林匹克竞赛情况简介

青少年信息学奥林匹克竞赛情况简介 信息学奥林匹克竞赛是一项旨在推动计算机普及的...简单的回溯算法 * 简单的递归算法 二、复赛内容与要求: 在初赛的内容上增加...

全国青少年信息学奥林匹克联赛

全国青少年信息学奥林匹克联赛_学科竞赛_高中教育_教育专区。全国青少年信息学奥林...屏示信息 * 自然语言的描述 程序的表示 * PASCAL 或 C 语言 * 简单数据的...

全国青少年信息学奥林匹克联赛大纲

全国青少年信息学奥林匹克联赛大纲_学科竞赛_高中教育_教育专区。全国青少年信息学...计算机和信息社会(信息社会的主要特征、计算机的主要特征、数字通 信网络的主要...

2013年蜀山区青少年信息学竞赛

2013年蜀山区青少年信息学竞赛_解决方案_计划/解决方案_应用文书。2013 年蜀山区...为了让问题简单一些,爸 爸告诉他正确的小木棒表示方式: (1) 这个数可以用一只...

2015年包河区青少年信息学竞赛

2015年包河区青少年信息学竞赛_学科竞赛_小学教育_教育专区。2015 年包河区青少年信息学竞赛小学组试题 2015年包河区青少年信息学竞赛 小学组试题一、题目概况题目名称...
更多相关标签:
全国青少年信息学竞赛 | 青少年信息学竞赛官网 | 青少年信息学竞赛题目 | 青少年信息学竞赛 | 青少年信息学奥林匹克 | 全国青少年信息学联赛 | 2016全国青少年信息学 | 全国青少年信息学奥赛 |
网站地图

文档资料共享网 nexoncn.com copyright ©right 2010-2020。
文档资料共享网内容来自网络,如有侵犯请联系客服。email:zhit325@126.com