haihongyuan.com
海量文库 文档专家
全站搜索:
您现在的位置:首页 > 初中教育 > 学科竞赛学科竞赛

信息学奥赛总讲稿PPT

发布时间:2014-01-30 14:45:18  

Pascal语言程序设计

1

认识Turbo Pascal

2

Pascal的发展历史
? Pascal由瑞士的沃斯(N Wirth)教授于1971
年设计出来的,之所以起名为Pascal,是为 了纪念法国数学家Pascal; ? Pascal语言在诞生后的30多年时间内,先后 出现了多种版本;

3

Pascal的发展历史
? Turbo Pascal是美国Borland(宝兰)公司于
1983年开发的产品,我们所使用的Turbo Pascal 7.0版 是1992年推出的,是一种16位 的软件 ? 目前,信息学竞赛中还用到Free Pascal,这 是一种共享软件,是一种32位的软件
4

Turbo Pascal源程序
? 什么是Turbo Pascal的源程序?
– 机器能够直接认识和运行的程序称为目标程序( 或称机器代码); – 用高级语言编写的程序称为高级语言源程序; 用Turbo Pascal编写的程序称为Turbo Pascal源程 序

5

Turbo Pascal源程序的例子:操 作步骤
1. 启动Turbo Pascal,进入编辑窗口;
2. 输入源程序,进行适当的编辑; 3. 编译源程序 选择Compile(编译)菜单中的Compile(编译)菜单 项(或者直接按Alt+F9),对所输入的源程序进行编 译,将其翻译成机器能够直接识别和执行的机器 语言程序
6

编译程序做哪几件事
? 对源程序进行语法检查,即检查程序语句中是否
存在着错误; ? 如果发现了错误,则发出提示信息; ? 否则,进行编译,生成目标代码(目标程序); ? 这样的目标代码经后续的链接步骤后,即可运行 了。

7

编译时出错的处理
? 在编译源程序时,如果程序中存在着错误,就会
停下来,发出错误警示; ? 这时,用鼠标单击或按键盘上的任意一个键,出 错提示条即消失; ? 这时,再重新进行编译。

? 编译成功、显示有关信息后,按任何键即可返回
编辑窗口。
8

运行程序
? 选择Run(运行)菜单中的Run命令(或者,也
可以按Ctrl+F9),即可运行已编译好的程序 ? 程序的运行结果并不显示在编辑窗口内, 而是显示在Output(输出)窗口中。

9

查看运行结果
1. 选择Debug(调试)菜单中的Output(输出)
命令,可以打开输出窗口,它显示了程序 运行后的输出内容;按F5键可以使输出窗 口最大化;再按一次F5,又可以使输出窗 口还原;

10

查看运行结果
2. 或者,选择Debug菜单中的User Screen(
用户屏幕)命令,可以切换到用户屏幕(即 输出窗口),其中显示了程序的运行结果 注:按Alt+F5可以快速切换到用户屏幕。

11

保存程序
? 选择File(文件)菜单中的Save(保存)命令,
屏幕上显示出Save(保存)对话框; ? 或者,按F2即可保存文件; ? Pascal源程序文件的扩展名是.PAS;

12

换名保存文件
? 对于已经保存过的文件,如果希望改变文
件名再次保存,或者保存到另外一个目录( 文件夹)下,需要选择File(文件)菜单下的 Sav

e As(另存为)命令

13

生成可执行文件
? 选择Compile(编译)菜单下的Destination命
令后,再按Alt+F9对源程序进行一次编译, 就可以在当前目录下产生一个名为xxx.EXE 的可执行文件,直接双击它就可以运行了 ; ? 扩展名为.EXE的文件都是可执行文件。
14

打开文件
? 要打开已有的Pascal源程序文件,可以选择
File(文件)菜单下的Open(打开)命令

15

输入源程序,并进行适当编辑; 编译源程序:Compile→Compile 运行程序:Run →Run 查看运行结果:Debug →Output或 Debug →User Screen 5. 保存程序:File →Save 1. 2. 3. 4.

16

Pascal 语言基础

17

Pascal程序的结构
? 例:已知长方形的长和宽,求长方形的周长和面积。
? 设长方形的长和宽分别为A和B,周长为L,面积为S ,计算长方形周长和面积的公式如下: L = (A + B) * 2 S = A * B ? 源程序见下面,从中可以看出一个Pascal源程序的 基本结构
18

保留字

程序名

参数表

program changfangxing(input, output); {程序首部} var 标识符 程序说明/变量定义 a, b, l, s: integer; (说明、声明)部分 begin 输入语句 程序体 readln(a, b); 赋值语句 l := 2 * (a + b); 程序执行部分( s :=a * b; 语句、指令) writeln(‘l =’, l, 's=', s); end. 输出语句
19

程序首部
? 是程序的开头部分,由保留字program后接程序
名及程序参数表组成,以分号结束 ? 程序名由用户/程序员自己定义 ? 参数表一般为文件变量名,用于该程序与外界的 数据交换,最常用的为input和output

? 在Turbo Pascal中,程序首部的参数表可以省略

20

程序说明部分
? Pascal语言要求,对于将在程序中用到的所
有标号、常量、类型、变量、记录、文件 、过程和函数,都必须在说明部分说明后 ,才能在程序执行部分使用(系统预定义的 除外)

21

程序执行部分
? begin和end之间的一系列语句,语句之间由“;”分隔

? “;”也称为语句结束符
? 一行上可以只写一条语句,也可以写多条语句

? 最后一行的end后加上“.”表示程序的结束

22

完整的Pascal程序框架
program 程序名(程序参数表); label 标号说明; const 常量说明; type 类型说明; var 变量说明; function 函数说明; procedure 过程说明; begin 程序语句; < end.

23

Pascal的基本符号、保留字和标识符
? 1. 2. 3. Pascal程序中涉及以下几类基本符号: 英文字母:大小写均可 数字 特殊符号: +, -, *, /, =, <, >, <>,<=,(,),[,],{,},:=, ., , ;, :, ‘, “

24

Pascal保留字
? Pascal对一些英文单词(或者缩写)规定了确
定的含义,程序员不能随意使用。这些单 词称为“保留字”,如program, begin, end,const,var等。 ? Pascal的保留字共有36个,可以分为6种类 型,以后在程序中逐步介绍。
25

Pas

cal标识符
? 标识符是用来表示常量、变量等名字的符号,
它以英文字母或下划线开头,后接英文字母、 数字、下划线的字符串,Turbo Pascal中允许

的有效标识符长度为63
? 标识符中的英文字母大小写都可以,都是一样



26

Pascal标识符的分类
1. 标准标识符
2. 自定义标识符

27

标准标识符
? 是系统预先定义好的标识符,具有确定的
含义,如input, output, integer, real, sqr, writeln, maxint(即32767)等。 ? 可以分为:标准常量、标准类型、标准文 件、标准函数、标准过程

28

自定义标识符
? 是由程序员自己定义的标识符(如pi,
chfx_mianji, a, b,s等),它们不能与标准 标识符或保留字同名,以免发生错误。 ? 此外,在定义标识符时,最好让标识符有 一定的含义,这样可以增强程序的可读性

29

Pascal自定义标识符合法性判断
min sum a3 x15 5b name

end var Π

30

Pascal的数据类型
? 数据类型不仅确定了该类型数据的表示和取值范
围,还确定了它们所能参加的各种运算 ? 在Pascal中,无论常量还是变量,都必须属于某 种确定的数据类型 ? Pascal提供了丰富的数据类型,它们可以分为三

大类

31

Pascal的数据类型
? 简单类型
? 构造类型

? 指针类型

32

简单类型
? 标准类型
整型(integer)、实型(real)、字符型(char)、 布尔型(boolean)

? 用户自定义类型
枚举型、子界(子域)型

33

标准类型
? 整型(integer)
? 实型(real)

? 字符型(char)
? 布尔型(boolean)

34

整数类型(integer)
? 包括正整数、负整数和零,由正负号和数字组成,
正号可以省略 ? 分为五种:
– 标准整型(integer) – 短整型(shortint)

– 长整型(longint)
– 字节型(byte) – 字型(word)
35

整数类型
? 不同型的整数的取值范围与具体计算机的字长有关
? 例如,在字长为16位(即两个字节)的计算机中, integer类型占两个字节,因而其取值范围为 -32768(minint)~32767(maxint) ? Turbo Pascal还支持另外四种整型,如下表所示:

36

整数类型的运算
? 整数的运算:+, -, *(乘), div(整除), mod(取余)
div: 取两整数相除所得的商,如: 12 div 5 = 2 -8 div 5 = -1 mod: 取两数相除所得的余数,如: 5 mod 3 = 2 19 mod 4 = ?
37

整数类型的运算
? 取余运算结果的符号与被除数相同,与除 数无关,如: -4 mod 3 = -1, -8 mod 3 = ? 8 mod –3 = ?, -8 mod –3 = ? ? 这是因为,在TP中,对mod运算的解释是 这样的: A mod B=A – (A div B)*B
38

整数类型的运算
? *、div、mod运算的优先级高于+、-运算
? 整数运算的结果也是整数,例如:假设x、y均为 整型变量,则3+4、x*y的结果均为整数 ? 当两个整数用 “ / ” 相除时,结果为实数,只能 赋值给实型变量

39

实数类

型(real)
? 实数类型包括正实数(15.2)、负实数(-1.43)和实数零(0.0)

?

实数有两种表示法:
1) 日常表示法(十进制表示法):如15.2,-1.43,30等。 *注意:小数点前后都必须有数字。整数可以当做实数 使用,反之不行 2) 科学计数法:采用“指数+尾数”形式来表示实数
对于字长为16位的计算机,实数的绝对值在 1E-38到1E38之间 40

科学计数法表示的例子
? 2600=2.6×103
用科学计数法表示为:2.6e+3 (或2.6E+3,”+”号 可以省略) 也可以表示为:26e+2等 *注意:指数部分不能为小数;尾数不能省略

41

科学计数法表示的例子
? 0.045=4.5 ×10-2
用科学计数法表示为:4.5e-2

? -0.0086 = -8.6 ×10-3
科学计数法表示为:-8.6e-3

42

实数类型
? 实数类型中,最常用的是标准实型(real),
对于字长为16位的计算机,这种类型实数 的取值范围为1e-38~1e38。 ? 实数的运算:+,-,*(乘),/(除)

43

实数类型
? 整数与实数可以混合运算,但结果为实型
数----系统首先将整型数转换为实型数(如将 30转换为30.0),再进行运算,结果仍为实 数; ? 例如,4 * 0.5 + 1 =3.0

44

字符类型
? 字符类型数据是夹在一对(西文)单引号之间
的一个字符,例如:
‘A’表示字符A ‘3’表示字符3 ‘ ’表示空格字符

? 字符类型用char表示,这种类型是有序的
45

字符串类型
? 当一对单引号之间的字符多于一个时,就
称其为字符串; ? 例如,‘abc’、’china’都是字符串; ? 字符串类型用string表示

46

布尔类型
? 也称为逻辑类型,类型标识符是boolean
? 这种类型的数据只取两种值:一种是true(真),另 一种是false(假) ? 这种类型是有序的,规定True的序号为1,false的 序号为0,因而,false < true

? 问题:QB中的真假值分别是多少?

47

布尔类型(续)
? 用于布尔量的运算称为布尔运算(也称为逻
辑运算),共有三种: not (非) and (与)

or (或)

48

a

not a

true

false

false

true

49

a true
true

b true
false

a and b true
false

false
false

true
false

false
false

50

a
true true

b
true false

a or b
true true

false
false

true
false

true
false

51

布尔类型(续)
? 参与布尔运算的数据必须都是布尔类型,
运算结果也是布尔类型 ? 布尔运算的优先级为:not→and →or

52

常量与变量
? 常量:在程序的运行过程中保持不变的量
,例如:

53

program yuan_cs(input,output); const pi = 3.14; {常量定义语句} var r, d, c, s: real; begin d:= 10.2; r:= d/2; c:= 2*pi*r; s:= pi*sqr(r); {sqr是个求平方的函数} writeln('c=',c); writeln('s=',s); end.
54

常量与变量
? Pascal中有三个标准常量: maxint:系统能表示的最大整数 true: 真 false: 假
? 此外,程序员还可以通过常量定义语句来 定义常量

55

常量定义语句
? const 常量标识符=常量; ? 为什么要用这样的常量定义语句? ? 例:const pi=3.14; a = 10; t = true; 即定义了三个常量“pi?、?a?、?t? ? 已经被定义的常量,可以在程序里使用,但不能 改变其值
56

常量定义语句
? 例:下面的常量定义语句就是错误的: const a = 5; a = 10; 在编译时,会报错“Duplicate identifier (a)? ? 例:下面的常量使用也是错误的: const pi = 3.14; << c = pi * 2 * r; pi = 3.1415;
57

常量定义语句
? 常量标识符的类型与定义式右端常量的类
型相同。 ? 在前面的例子中,pi是实型,a是整型,t是 布尔型

58

变 量
? 变量是在程序执行过程中可以改变的量,例如 program yuan_cs(input,output); const pi=3.14; var r, d, c, s: real; 定义了四个实型变量,其值可以被 多次改变 begin d:= 10.2; r:= d/2; c:= 2*pi*r; s:= pi*sqr(r); writeln('c=',c); writeln('s=',s); 59 end.

变量
? 变量有三个要素:
– 变量名:用于表示变量的标识符 – 变量类型:变量的类型与在变量中存放的数据的类型

相同。例如,整型变量用来存放整数,实型变量用来
存放实数 – 变量值:即存放在变量中的值。在程序的执行过程中 ,变量的值可以被多次改变

60

变量说明语句
? 在Pascal中,变量必须先定义再使用
? 变量的定义也叫做“变量说明”或“变量声明” 。在Pascal中,变量说明语句的格式为: var 变量名:类型 ? 此处的“类型”既可以是标准数据类型,也可以 是用户自定义的类型

61

变量说明语句
? 变量和常量一样,只能属于一种数据类型
? 一个var语句可以用来为多个变量进行说明

,每个说明语句写成一行;

62

变量说明语句
? 例: var x: integer; 说明x是整型变量 a, b,c: real; 说明a、b、c是实型变量

63

变量的说明语句
? 例:下列的变量说明中,哪些是非法的(即 不正确的)?应该如何改? var a, b = integer; x: char; x,y: boolean; cl: ‘a’;

64

变量的说明语句
var a, b: integer; “ :” x: char; y: boolean; cl:char;
“char”

不能用“=”,应改为
变量x定义了两次 ,应删去一个x

类型表示不对,应将“a”改为

65

Pascal中的函数
? 什么是函数?
对于一个或多个原始数据,若按照某一法

则可求得一个结果,称这种功能为函数。
这儿的原始数据称为自变量(或参数),结 果称为因变量(或函数的值)。每个函数都 有名称,称为函数名。
66

Pascal中的函数
? 例:trunc(2.98) = 2
这儿的trunc就是一个(截尾)函数,作用

是将自变量x的小数部分去掉。
? 问题:QB中有无类似的函数?

67

Pascal中的函数
? Pascal中的函数分为两种:
– 标准函数:是Pascal已经定义的、程序员可以 直接在程序中使用

的函数; – 自定义函数:程序员在程序中自行定义的函数

68

Pascal中的标准函数
? 数学函数 ? 转换函数 ? 顺序函数 ? 逻辑函数

见附录四

69

标准函数的例子
abs(-9.3) = 9.3 {abs:求绝对值} sqr(3) = 9 {sqr是求平方的函数} sqrt(25) = 5 {sqrt是求(正)平方根的函数}

70

标准函数的例子
trunc(202.23) = 202 {截尾函数} trunc(-9.5) = -9 round(6.3) = 6 {舍入函数} round(7.52) = round(-3.2) = 8 -3 round(-4.61) = -5
71

标准函数的例子
odd(6) = False {判断奇数函数} odd(13) = chr(48) = ‘0’ ,返回与参数ASCII值对应的字 符} ord(‘A’) = 65 ,返回与参数字符对应的ASCII 值,或取参数的序号} ord(true) = 1, ord(false) = 0
72

标准函数的例子
pred(‘B’) = ‘A’ ,取一个数据函数} succ(‘A’) = ‘B’ ,取后一个数据函数}

73

标准函数的例子
? x的n次方:利用换底公式,可知为exp(n*ln(x)) ,这是因为:

x ? exp(n *ln( x))
n

? exp(ln( x) n ) ?e
ln( x )n n

?x

74

Pascal的运算符
? 运算符:Pascal中的运算符有五类:
– 算术运算符 – 关系运算符

– 逻辑运算符
– 集合运算 – 赋值运算

? 见P25运算符表
75

Pascal的运算符及表达式
? 表达式:在Pascal中,表达式是用运算符把
常量、变量、函数、括号等连接起来后构 成的各种运算式。 ? 单个的常量、变量、函数都可以看成是一 个表达式

76

运算的优先级
? 运算的优先级:当一个表达式中包含多个
运算符时,Pascal语言规定了各运算的先后 次序,称为运算的优先级 ? 优先级高的运算先做;在同一级中,按从 左到右的顺序运算。

77

运算的优先级
? 因为运算符优先级的关系,Pascal语言规定,在
进行逻辑运算时,如果操作数本身是一个布尔表 达式,必须用括号将其括起来,否则会造成逻辑

上与原意不符
? 例如:(a < 5) and (b >= 0) 与

a < 5 and b >= 0 {含义不同,且非法}

78

表达式
? 由不同的运算符连接而成的表达式,可以形成算
术表达式、关系表达式、逻辑表达式等 ? 例:1+2*3 算术表达式,结果为数值 a<b 5<4 3 = (1+2) {此式中不要()可否?} a and b 逻辑表达式,a、b都是逻辑量
79

关系表达式,结果为逻辑值

表达式
23<46 and 72>8 {这个表达式对否?与QB中 的优先级是否一样?} x mod 3=0 and x mod 5=0 {这个表达式对否?} 正确的写法: (23<46) and (72>8) (x mod 3=0) and (x mod 5=0)
80

表达式
? 例:设变量x表示考试成绩,则判断成绩是
否及格,可以写如下关系表达式: >= ? 例:如何表示?变量a既能被7整除,又能 x 60

被11整除?这一条件?
(a mod 7 = 0) and (a mod 11 = 0)
81

表达式
? 如何表达?变量a的取值在90与100之间?
这一条件? (a >= 90) and (a <= 100)

注意,不能写成90<=a<=100

82

运算

的优先级
? 运算符的优先级分为: 括号 函数 4级:not 3级:*,/,div,mod,and 2级:+,-,or 1级:=,<>,>,<,>=,<=,in



83

第四章 程序设计初步

84

本章内容
? 介绍Pascal程序设计中的几种最常用语句, 包括:
– 赋值语句 – 输入语句 – 输出语句

85

简单语句与构造语句
? 在Pascal中,语句分为简单语句和构造语句
两大类 ? 所谓简单语句,又称为基本语句,是指不 能再分解的语句 ? 构造语句是由若干其他语句所组成的语句( 问题:为什么需要复合语句?)
86

赋值语句
? 是为变量提供数据的语句,其格式为:
变量标识符 := 表达式;

? ?:=?为赋值号,其左端必须是合法的
Pascal标识符(变量名),右端可以是常数、

常量、变量、函数,或者通过运算符将它
们连接而成的各种表达式
87

赋值语句
? 语句功能:先计算右端表达式的值,再将
该值赋给左端的变量

88

关于赋值语句的说明
? “:=”不是“=”(亦即,与关系运算符“=”或常
量说明语句中的“=”不同) ? 常量说明语句中只能使用“=”,如: const pi = 3.14; ? 赋值号两边的类型应当相同,或赋值相容。当赋 值号右边的表达式为整型时,它会自动地转为实 型后赋给左边的实型变量
89

有关赋值语句的说明
? 例如: var a: real; a := 10; 则最后a中是10.0 ? 问题: var b: integer; b:=10.0; 则最后b中是? {上机试试}
90

有关赋值语句的说明
? 一个赋值语句只能给一个变量赋值,否则
会编译器会报错。亦即,不能写: a := b: = 10;

91

赋值语句的例子
? 例4-2(P29):分析程序,重点说明其中变量
的赋值及取值的变化。

92

输入语句(read, readln)语句
? 计算机及计算机程序的一个重要作用就是
能够接受来自人们输入的数据 ? 在Pascal中,这一功能是通过输入语句(又 称读语句)来完成的

93

输入语句(read, readln)语句
? 输入语句的格式:
– 格式1:read(变量表); – 格式2:readln[变量表];

? 其中,“变量表”可以是单个变量,也可 以是一串用逗号分隔开的变量

94

输入语句
? 程序运行到输入语句时,系统处于等待状
态,等待用员从键盘上输入数据,将其值 依次赋给变量表中的各个变量 ? readln语句后可以没有变量表,此时,该语 句的作用就是读入一个回车换行符(QB中有 无类似的语句?)
95

输入语句
? 用户从键盘输入的数据必须是常量,且所
输入数据的类型必须与相应变量的类型保 持一致

96

输入语句
? 如果输入的数据个数多于变量表中变量的
个数,则两种格式的read语句的处理是这 样的:
–执行readln后,多余的数据将被忽略; –执行read后,多余的数据要么被忽略,要么被 下

一个read或readln语句所读取
97

输入语句
? 语句read(a1,a2,<,an)等价于
read(a1); read(a2);<;read(an);

? 语句readln(a1,a2,<,an)等价于
read(a1); read(a2);<;read(an);readln;

98

输入语句
? 输入数值型(整型或实型)数据时,数据之间
用空格或回车分隔,最后一定要有一个回 车,表示输入结束 ? 输入字符型数据时,数据间不能用空格或 回车进行分隔,因为计算机默认空格、回 车也是字符
99

例:分析以下输入语句的执行结果
var ch1, ch2, ch3: char;
read(ch1, ch2, ch3); 如果键入mnp再按回车,则执行结果为: ch1=‘m’, ch2=‘n’, ch3=‘p’ 如果键入m?np,则执行结果为: ch1=‘m’, ch2=‘ ’, ch3=‘n’
100

【例4-4 】设i, j, k是字符型变量,现需将 ‘d’, ‘o’, ‘s’分别赋给这三个变量,要求写 出对应于下列语句的所有可能的输入格式 : read(i, j, k); ? 见P31 ? 练习:例4-5, P31,例4-6,P32
101

? 例4-5: readln(a, b, c); readln(i, j, k, l); readln(m, n); 输入数据: 1 2 3 4 5 6 7 8 9 0 10 20 则a、b、c、i、j、k、l、m、n的值各为多少?
102

? 例4-5: read(a, b, c); read(i, j, k, l); read(m, n); 输入数据: 1 2 3 4 5 6 7 8 9 0 10 20 则a、b、c、i、j、k、l、m、n的值各为多少?
103

注意和说明
? 当“变量表”中变量有多个时,要求从键
盘上输入的数据个数不能少于变量的个数 。否则,如果输入的数据项数少于变量的 个数,则系统始终处于等待状态;

104

注意和说明
? 如果输入的数据项数多于变量列表中变量
的个数,这是允许的,但多余的数据对当 前的read语句来说,不起作用

105

注意和说明
? 在同一个read语句的变量列表中,可以包
括整型、实型、字符型变量

106

? 例:设x是整型变量,y是实型变量,ch1和 ch2是字符型变量,并且有以下的输入语句 : read(x,y,ch1,ch2); 那么,如果键入: 50 4.2 ab 则执行结果为: x=50, y=4.2, ch1=‘a’, ch2=‘b’
107

输入语句
? 格式2:readln(变量表) ? 与read语句的功能基本相同,但也存在着 一些区别

108

read语句与readln语句的区别
1. 当输入的数据个数多于变量个数时,两者的处
理不同:
– 执行read后,如果后面不再有输入语句,多余的数据

就被忽略;如果后面还有输入语句,多余的数据会被
下一个read或readln读取 – 执行readln后,多余的数据将被彻底忽略,不能被下 一个read或readln语句所读取

109

read语句与readln语句的区别
2. 标识符read后面必须有变量表,而readln
后面允许没有变量表。如果readln后面没 有变量表,则该语句的作用就是换行读取 数据,即它后面的第一个read或readln语 句需要从下一个数据行中读取数据。

110

输入语句的例子
1) read(a); read(b,c,d,e); read(f,g); 2) readln(a); re

adln(b,c,d,e); readln(f,g);

111

输入语句的例子
如果为这两组语句输入相同的数据: 1 2 3 4 5 6 7 8 9 这两组语句的执行结果是: 1) 的执行结果: a=1 b=2 c=3 d=4 e=5 f=6 g=7
112

输入语句的例子
? 可以看出,当a读入1时,还余下8个数据
。第二个read语句从这些数据中又依次读 入2,3,4,5。第三个read语句的变量f 、g又从余下的四个数据中读入6、7。最 后还剩下两个数据未起作用。

113

输入语句的例子
? (2)的执行结果是: a=1 b=4 c=5 d=6 e=7 f=0 g=0

114

输入语句的例子
? 当a读入1后,还剩下8个数据;
? 第二个readln语句中的变量b, c,d,e并没有从第一 行输入数据中余下的2、3中继续读取,而是换行 到第二行数据的最左端,依次读取b=4、c=5、d=6 。

? 由于这时第二行中的数据已经读完,接着又换行
到第三行读数据,即变量e读入7。
115

输入语句的例子
? 第三个readln语句又需要换行读取数据。这
时,因为由键盘输入的9个数据全部读完, 系统就将变量f、g作为未赋值处理,因而有 f=0, g=0

116

输入语句的例子
readln(x); readln; readln(y,z); 如果输入的数据为: 5.2 9.3 6.1 7.4 8.0 2.8
117

输入语句的例子
? 执行结果为: x = 5.2 y = 8.0 z = 2.8

118

输出(write,writeln)语句
? 功能:将程序的处理结果通过屏幕或打印机显示
出来。 ? 格式1: write(输出项列表); ? 格式2: writeln[输出项列表];

119

输出(write,writeln)语句
? 其中,“输出项列表”是一些用逗号分隔
开的输出项(常量、变量、表达式或字符串) 等。 ? write语句是一项接一项地输出,输出完最 后一项后不换行 ? write语句至少必须输出一项内容
120

输出(write,writeln)语句
? Writeln语句也是一项接一项地输出,但输出完最
后一项后自动换行 ? Writeln语句允许没有输出项,此时该语句不输出 任何内容,只起换行的作用 ? 注意:各输出项的输出效果基本同QB,只是没有

QB中的标准格式与紧凑格式之类的划分

121

输出(write,writeln)语句
? 输出项的类型不同,输出的结果也就不同:
1) 输出项为常数:输出常数 例如,write(18);的输出结果为18

2) 输出项为常量,则输出常量的值
例如,假设已定义了常量pi=3.14,则 write(pi);的输出结果为3.14

122

输出(write,writeln)语句
3) 输出项为变量,则输出变量的值
例如,假设已定义变量x=20,则write(x);的输出 结果为20 4) 输出项为表达式,则先计算表达式的值,再将 其输出

123

输出(write,writeln)语句
例如,假设已定义了
x:=8; y:=7; 则 write(x+y); 的输出结果为15
124

输出(write,writeln)语句
5) 若输出项为字符串,则照原样输出字符串的内
容(不包括单引号)。例如,假设已定义了变量: ch1 := ‘abcde’;

则: write(ch1); 的输出结果为abcde

125

例:编程计算5×7,并输出算式
program chenshi(input,output); const a=5; b=7; var c:integer; begin c:=a*b; write(a,’*’,b,’=’,c); end.

126

?
?

输出结果为:5*7=35
问题:
1) 如果把write语句改写成

write(‘a*b=’,a*b);
输出结果还会是5*7=35吗?

2) 如果想计算41+37+105,并输出加法算式,该如何编
写程序呢?--------上机编写这个程序
127

一个思考题:
? 以下是一段程序:
begin

read(a,b);
writeln(a+b); readln; end.
128

一个思考题:
? 按照一般理解,程序应该在输出结果后停
留在显示屏幕,但实际情况是程序运行后 直接跳回源程序。 ? 要想达到预期的结果,该怎么办?

129

输出语句的输出格式: 输出数据的场宽
? 在输出数据时,可以规定输出数据所占的
宽度(列数),称为“场宽” (或称“域宽”) ,分为标准场宽和自定义场宽。 ? Turbo Pascal对各种数据定义的标准场宽见 教材P33表4-2

130

输出数据的场宽
? 从该表中可以看出,标准场宽往往就是实
际输出值的宽度 ? 如果在write语句中不加场宽说明,系统就 会按标准场宽输出

131

自定义场宽
? 自定义场宽分为单场宽和双场宽两种形式

132

单场宽
? 定义格式:输出项:场宽
? 其中,场宽可以是正整数,也可以是值为正整数 的整型表达式,表示输出项所占的列数。 ? 例:write(‘study’ : 6) 即表示字符串‘study’的场宽是6,在输出时,它的 左边有?个空格

133

单场宽
? 当输出值的长度超过定义的场宽时,自定
义场宽即失效,系统会按实际的位数输出 ? 可定义为具有单场宽的输出项的类型为: 整型、布尔型和字符型,但不允许是实型

134

? 例4-7 设m为整型数1997,ch 为字符‘?’,f为布尔值 true,执行如下输出语句: writeln(m:5); writeln(ch:5); writeln(f:5); writeln(‘ok!’:5);

则屏幕显示为 : ?1997 ? ? ? ?? ?true ? ?ok!
135

? 例:变量a的值为整型数2004,ch的值为字 符?!?,则输出语句: writeln(a:6); writeln(‘happy’:9); writeln(‘new’:10); write(‘year’:13); writeln(ch);
136

双场宽
? 用来定义实型数的输出格式
? 格式:输出项:总场宽:小数位数 ? 总场宽:指输出实型数的总列数,包括符号位、 整数部分、小数点和小数部分 ? 小数位数:指小数部分所占的列宽 ? 注意:总场宽、小数位数应为正数,且要求总场 宽>小数位数
137

双场宽
? 例:
writeln(-110.1194 : 9 : 3) 输出: ?-110.119 writeln(-123.456 : 8 : 2) 输出: ?-123.46 {注意,有舍入进位,书

上错了}
138

双场宽
? 当输出项没有达到总场宽时,左边留空格
;否则,按实际位数输出,但输出的小数 位数一定要符合双场宽

的规定

139

自定义场宽使用时的注意事项
? 自定义场宽的优先级高于标准场宽
? 除实型的双场宽定义外,输出格式一律是左留空 、右对齐 ? 实型的双场宽输出时是向小数点看齐,多余的小 数位数补0

? 例:writeln(-110.11 : 10 : 4)
输出: ?-110.1100
140

自定义场宽使用时的注意事项
? 在数据不突破场宽的限制时,一律按场宽
定义输出; ? 在数据突破了场宽的限制时,是以保证数 据的正确输出为原则的,也就是说:

141

自定义场宽使用时的注意事项
– 在单场宽的情况下,强行自动将场宽扩展到所
需要的数位; – 双场宽时,则强行自动将总场宽扩展到所需的 数位(小数位数场宽的限制仍然照旧)

142

自定义场宽使用时的注意事项
? 当实数的小数场宽小于实际的小数位数时
,则显示时舍去多余的位数。但要注意, 此时内存中该数仍然是原来的精确度(什么 意思?)。 ? 例4-8 写出以下程序的输出结果。(教材P34)

143

复合语句
? 复合语句是由若干条语句所组成的语句序
列, ? 每个语句可以是简单语句,如我们前面学 过的赋值语句、输出语句等,也可以是我 们将要在后面介绍的过程语句或结构型语 句,各语句之间用分号来分隔
144

复合语句
? 并用保留字begin与end将这些语句序列括
起来,构成一条逻辑上的语句,在语法上 充当一条语句。

145

复合语句
? 复合语句的一般形式: begin 语句1; 语句2; << 语句n end;
146

复合语句
? 此处,begin与end起着括号的作用,相当
于用了一个语句括号将若干个语句括了起 来,作为一个语句处理 ? 问题:为什么需要复合语句?哪些地方需要 使用复合语句?

147

综合应用
? 例4-9 已知梯形的上底、下底和高,求梯形 的面积。(教材P36) ? 例4-10 通过键盘输入两个数,交换其值后 输出。 (教材P36)

148

? 例4-10 随机产生一个三位自然数,分离出 它的百位、十位与个位上的数字。 (教材 P36)

149

说明
? random函数:random[范围:word]
– 如果带“范围”参数,则返回一个“0<=x<范围 ”之间的word类型的整数; – 否则,返回一个“0<=x<1?之间的实数值

? randomize过程:用于随机化种子

150

选择结构的程序设计
? if语句
– 格式1:if 条件 then 语句1; – 格式2: if 条件 then 语句1 else 语句2;

? 其中的“语句”可以是单个语句或复合语 句 ? 只在if语句的结束处才需要加分号
151

if语句
? 注意:不象QB中那样,强调“行IF语句”
和“块IF语句”的区别,两种格式都可以写 成多行; ? 第二种格式的if语句在书写时,可以写成如 下形式:

152

? If 条件 then 语句1 else 语句2; 或者: ? If 条件 then 语句1 else

语句2;

153

if语句的书写格式
? if 条件 then 语句1 else 语句2; ? if 条件 then 语句1 else 语句2;

154

if语句的书写格式
? if 条件 then 语句1 else 语句2;

155

逻辑运算及布尔表达式
? 布尔常量:true和false
? 这两个常量可以直接在程序中使用,也可以做如 下的布尔类型的常量定义: const t = true; f = false; 这样,在程序中就可以直接使用 t 和 f 这两个符 号常量了。
156

逻辑运算及布尔表达式
? 在Pascal程序中,只能通过赋值语句给布尔
变量赋值,而不能用read语句读入一个布 尔常量 ? 但是,对布尔型数据,可以利用write或 writeln语句输出其值,例如:

157

var t, f: boolean;
t := true; f := false write(‘t=’, t, ‘f=’:3, f); 输出结果为: t=true f=false
158

关系表达式
? 由一个关系运算符将两个类型相容且有序
的表达式联结起来所形成的式子,称为关 系表达式 ? Pascal中的关系运算符共有六个: <, >, =, < >, <=, >=

159

关系表达式
? 在讲到“集合”的有关内容时,还要引入
一个关系运算符,即in ? 关系表达式的值为布尔值

160

关系表达式
? 对数值型数据的比较,是按照数值的大小
来进行比较的,如13>6的值为true ? 对其他类型数据的比较,是按照其序号来 进行比较的,如‘a’<‘b’的值为true

161

逻辑运算
? 例4-12 若a=true, b=false, x = 7, y = 12, m =
3, n = 35, 求下列布尔表达式的值: a and not(m>n) and (x<y-m) or (a or b)

162

逻辑运算
? 又称为布尔运算,其运算结果只有真或假
两种可能,如比较x>y; ? 逻辑(布尔)常量:true(序号为1)和false(序 号为0),false < true

163

逻辑运算
? false的序号为0,true的序号为1,false <
true,因而,布尔型数据是有序类型的数据 ? 顺序函数ord、pred、succ等均适用于布尔 型数据

164

? 只允许用赋值语句为布尔型变量提供数据,不能 使用read语句为其提供数据,否则会出错 ? 可以利用write或writeln语句输出布尔型数据,例 如: var t, f: boolean; t:= true; f:= false; writeln(‘t=’,t); writeln(‘f=’,f);
165

逻辑运算
? 逻辑运算符:not(非,单目运算符)、and(与,双 目运算符)、or(或,双目运算符) ? 由逻辑运算符连结而成的表达式称为逻辑表达式 ,例如: (a < 0) and (b < 0) (x > 0) or (y > 0) not a not (a < b) ? 逻辑运算的真值表:见P65表5-1
166

? 优先级为:not → and→or ? 运算符的优先级: 括号→函数、not →*、/、div、mod、and →+、-、or →>、=、<、>=、<=、<> ? 同级运算自左至右进行运算 ? 在逻辑表达式中,如果逻辑运算符联结的 是布尔表达式,必须用括号将布尔表达式 括起来,否则会发生逻辑错误
167

? 例4-14
节日期间,某超市购物优惠规定:

所购

物品不超过100元时,按九折付款;如果超
过了100元,超过部分按七折收费,编程完 成超市自动收费的工作。(教材P42)(上 机练习)
168

if语句的嵌套
? then子句中嵌套了if语句 ? else子句中嵌套了if语句

169

then子句中嵌套了if语句
If 条件1 then if 条件2 then 语句21 else 语句22 Else 语句12;
170

then子句中嵌套了if语句
? 由于else后的子句是可以省略的,而在嵌
套时,else是与距它最近的那个尚未与其

他else配对的if<then配对,因此,内层
的else子句是不能省略的,否则将会造成 逻辑错误

171

then子句中嵌套了if语句
? 解决的办法就是写一个空语句或者采用复
合语句,即增加语句括号 ? 另外,在书写程序时,采用缩进格式,也 可以增强程序的可读性

172

else子句中嵌套了if语句
? 在采用这种嵌套形式时,外层的与内层的
相接,若不采用缩进格式,当嵌套层数较 多时,有时会难以在一个程序内写完,给 调试与阅读程序带来困难 ? 因此,通常写与下面的形式:

173

If 条件1 then 语句11 else if 条件2 then 语句21 else 语句22 ;
174

? 在使用嵌套的if语句时,无论多么复杂的嵌
套关系到,只要注意采用适当的缩进格式 ,并使if、then和else相互配对,适当使用 复合语句,就能解决问题。

175

? 例4-16 计算下列函数:
?1 ? y ? ?0 ? ?1 ? ( x ? 0) ( x ? 0) ( x ? 0)

? 分析: 此函数即符号函数(在QB中为SGN()函数),函 数的输入参数为x,输出结果为y。
176

program exp4_16; var x, y: real; begin writeln(‘input x = ’); read(x); if x<0 then y:=-1 else if x > 0 then y:=1 else y:=0; writeln(‘y=’, y) end.
177

if语句
? 例 输入一个整数,判断它是奇数还是偶数
。 ? 分析:奇数和偶数有什么特点?在Pascal中 ,如何来判断一个数的奇偶性? ? 该用if语句的格式1还是格式2来表达?

178

program ji_ou(input, output); var a: integer; begin readln(a); if a mod 2 = 0 then writeln(a,‘是偶数’) else writeln(a,‘是奇数’); end.

179

? 上机练习:
1) 将条件表达式换成“a mod 2 <> 0?后,重写 以上程序; 2) 改用odd()函数来判断输入数的奇偶性,重写 以上程序。

180

? 以下程序能正确判断一个数的奇偶性吗? program ji_ou_a(input, output); var a: integer; begin readln(a); if a mod 2 = 0 then writeln(a,‘-oushu’); writeln(a,‘-jishu’); end.
181

? 从上一个程序的错误中,可以区分出语法
错误与算法错误(亦称为“语义错误”、“ 逻辑错误”)

182

指出下面程序中的错误或不妥
program zuidashu_1(input, output); var a, b, c, max: real; begin readln(a,b,c); if (a > b) and (a > c) then max:= a; if (b > a) and (b > c) then max:= b; if (c > a) and (c > b) then max:= c; writeln(‘max=’,max);

end.
183

? 例 在a > 0的情况下:
如果有b > 0,则显示a与b的和; 否则,显示a与b的差; 否则(a<=0),显示?a <=0?。

184


if a>0 then if b>0 then writeln(‘a+b=’,a+b) else writeln(‘a-b=’,a-b) else writeln(a,‘<=0’);

?语句1?

185

注意:
? 当发生if语句的嵌套时,外层if语句的else部
分可以省略; ? 但是,当外层if语句有else部分时,内层if语 句的else部分不能省略,否则会发生匹配上 的问题;

186

注意:
? 当内层if语句中的else后面不需要有语句12
时,可以表示成空语句(即不书写语句12), 或者,也可以将内层if语句写成复合语句, 即写成如下格式:

187

if 条件1 then begin if 条件2 then 语句11 end else 语句2;

复合语句

188

else后面接if语句
if 条件1 then 语句1 else if 条件2 then 语句21 else 语句22;

?语句2?

189

几点注意
? 无论是哪一种格式的if语句嵌套,只要注意
if、then、else的正确匹配即可 ? 书写程序时,为了增强程序的可读性,应 将嵌套的if语句写成缩进形式

190

分情况(case) 语句
? 当需要从多种条件和情况中加以判断和选
择时,使用if语句会比较麻烦 ? 这时,可以使用Pascal中的分情况(case) 语 句,它是一种多分支选择语句

191

分情况(case) 语句
case 表达式 of 可以是复合语句 常数表1:语句1; 常数表2:语句2; << 常数表n:语句n; [ else 语句n+1[;] ] end[;]
192

? 其中,“表达式”必须是有序类型(整型、
字符型、布尔型或枚举型、子界型),不能 是实型 ? “常数表”一个或几个用逗号分隔的常数 ? 语句1-语句n中,只有一个语句会被执行

193

Case语句的执行流程
1) 首先,对“表达式”求值;
2) 当该表达式的值与某个常数表中的常数相同时 ,即执行该常数表对应的语句; 3) 接着,执行case语句(后面)的下一条语句 4) 如果找不到与之匹配的常数表,则执行else后面 的语句,然后继续执行case语句的下一条语句

194

说明:
? 此语句中的保留字end与保留字case对应
? 表达式的类型为有序型 ? 常数表的类型与表达式的类型一致 ? 各常数表必须彼此不相同,它们的次序是任意的 ,不一定要按从小到大或从大到小的的次序排列( 什么意思?QB中是不是这样?)

195

? 例4-18 输入两个数值(均不为0)及一个算术运算符
,输出其运算结果。 ? 分析: 考虑到算术运算符有四种情况,因此,应根据 输入的运算符分四种情况处理

? 参考程序:见教材P46

196

综合应用
? 例4-19 求一元二次方程ax2+bx+c=0 (a<>0)
的实数根。(教材P46)

197

综合应用
? 例4-20 输入年、月,输出该月的天数。(教
材P47)

198

算法
1) 输入年份(year)和月份(month);
2) 计算所输入月份的天数(days);

1) 利用case语句,根据月份,求出每个月的天数; 2) 对2月份,还要判断闰年问题;
(year mod 4=0) and (year mod 100<>0) or (year mod 400=0)

3) 输出年、月、每月天数信息

199

program day(input,output); var year, month, days: integer; begin read(year, month); case month of 1,3,5,7,8,10,12: days:=31; 4,6,9,11 : days:=30; 2 : if (year mod 4=0) and (year mod 100<>0) or (year mod 400 =0) then days:=29 else days:=28; end; writeln(year,’year’,month,’month:’,’days=’,days); end.
200

循环结构程序设计
? 计数循环(for)语句:
– 递增型for循环 – 递减型for循环

? 条件循环:
– 当型循环 – 直到型循环
201

计数循环(for)语句
? 是一种已知循环次数(如班级中的总人数)的
循环结构 ? 通过计数来控制重复语句的执行次数 ? 分为两种:
– 递增型循环
– 递减型循环
202

递增型for循环
? 格式: for 循环控制变量:=初值 to 终值 do 循环体语句; {可以是复合语句} ? 例: for i:=5 to 10 do write(i); 或写成: for i:=5 to 10 do write(i);
203

功能与执行流程
1. 先把初值赋给循环控制变量;
2. 再将初值与终值进行比较:当初值小于等

于终值时,执行循环体;

204

功能与执行流程
3. 再使循环控制变量在其原值基础上加1,
继续与终值比较。
1) 若仍然小于等于终值,则再次执行循环体; GOTO 3; 2) 否则(即此时循环变量已大于终值),循环结束 ,执行循环语句的下一条语句

205

注意:
? 如果循环体中有多条语句,可以将其设计成复合
语句(即用begin和end括起来) ? 循环变量的初值和终值可以是常量、变量或表达 式,如: n:=5;

for i:=n to n*n do <<;

206

注意:
? 循环变量必须与初值、终值的数据类型相
同,并且必须是有序(整型、字符型、布尔 型等,不能是实型,因为循环控制变量是 按序变化的)

207

注意:
? 在递增型for结构中,循环控制变量按SUCC(x)函
数规律变化;在递减型for结构中,按PRED(x)函 数规律变化。例如:
– 当x为整型值时,后续值为原值加1,前趋值为原值减1
; – x为字符型数据时,其前趋或后继值按ASCII码顺序计 算,如‘k’的前趋是‘j’,后继是‘l’

208

注意:
? 循环体中可以是单个语句,也可以是复合 语句,如: for i:=10 to 30 do begin m:=m+i; writeln(m,’ ‘,i); end;
209

注意:
? 初值与终值在开始重复之前计算,在重复
执行的过程中,其值不受影响; ? 在循环中,一般情况下,不要对循环控制 变量进行赋值操作

210

注意:
? 在递增型for循环中,如果一开始初值就大
于终值,则不执行循环,即循环的次数为0 ; ? 循环控制变量的步长为1或-1

211

问题:
? 循环结束时,循环控制变量的值是多少?
? 该如何来调整循

环控制变量的步长?

212

例题
? 例4-22:计算1+2+3+<+100之和。(见教材
P50) ? 思考题:见P51(上机编程练习)

213

例题
? 例4-23:键入一个自然数,求出这个自然数
的所有约数之和。(见教材P50)(上机练习) ? 例4-24:编程找出四位整数abcd中满足下述 关系的数: (ab + cd)(ab + cd) = abcd

214

递减型for循环
? 指每次执行for语句时,循环变量减1 ? 格式: for 循环控制变量:=初值 downto 终值 do 循环体语句; ? 例:for i:=25 downto 2 do writeln(i); 或写成: for i:=25 downto 2 do writeln(i); ? 问题:该循环一共执行了多少次?输出结果如何 ?
215

? 例6-3 大侦探柯南非常喜欢观察问题和分析 问题,他为取得罪犯能否在现场出现的证 据,亲自实践罪犯可能的行走路线。第一 条路线他用了92min,第二条路线用了 82min。他在每一条路线上用的时间都比上 一条路线少10min,直到第九条路线,他用 了12min。问柯南走完这九条路线共用了多 长时间?
216

问题分析
? 已知:这九条路线的用时分别是92、82、 72、62、52、42、32、22、12分钟。 ? 求:t=12+22+32+<<+92 ? 采用for循环语句:
– 将t作为累加器 – 循环控制变量为i,它从1变到9 – t和i两者之间的关系为: t:=t+10*i+2
217

program e6_3(input,output); var i, t: integer; begin t:=0; for i:=1 to 9 do t:=t+10*i+2; writeln(t); end.
218

? 上机练习:编写计算s=1+3+5+7+<+99的程 序。

219

问题分析与主要思路
for i:=1 to 50 do s: = s+2*i-1; writeln(s)

220

? 例6-4 求水仙花数。所谓水仙花数,即指这 样的一种三位数abc,它满足: a3+b3+c3=abc 例如,153=13+53+33 ,因而153就是一个水 仙花数。

221

问题分析
? 可以利用for循环来解决这个问题
? 由于水仙花数是三位数,因而,循环控制变量可 以从100开始变化,终值是999 ? 对100~999之间的每一个三位数进行检查,看它是 否满足上面的关系式。这种算法称为“穷举法”

? 如何将一个三位数的各位取出来呢?

222

? 看一个三位数的例子345:
345 = 3*100 +4 * 10 + 5
– 345整除100的结果即为百位数字3
– 345 – 3*100 = 45;45整除10的结果即为十位数 字4 – 用原数除10取余数,即得到个位数字5
223

program e6_4(input,output); var i, a, b, c, k: integer; begin for i:=100 to 999 do begin a:=i div 100; {取出百位数a} b:=i div 10 – 10*a; {取出十位数b} c:=i mod 10; {取出个位数c} k:=a *a*a+b*b*b+c*c*c; if k=i then writeln(?水仙花数是”,i); end; End.
224

当型循环(while)语句
? 使用for循环语句编程时,需要预先知道循 环次数
? 对于预先不能确定循环次数的问题,可以 用“当型”(while)语句来解决 ? 格式: while 布尔表达式 do 语句;
225

while语句的执行流程
1. 首先,求“布尔表达式

”的值,当其值为真
(true)时,进入循环执行do后面的语句(称为“ 循环体”);否则,转步骤3;

2. 然后,执行完循环体后,再返回开头(步骤1)求
布尔表达式的值;

3. 不执行循环,执行while语句的下一条语句

226

一个问题:
? 如果首次计算?布尔表达式?时,其值就
不为真,那么循环体还会被执行吗?

227

while语句的用法举例
? 例6-5 求s = 2+6+10+<+98的值。

228

问题分析
? 此问题尽管也可以用for语句来实现,但我
们在此处用while语句来实现,即不是利用 预先确定的循环次数来控制循环,而是利 用一个条件(布尔)表达式来控制循环的结 束,该表达式就是x<=98

229

问题分析
? 采用累加的方法,即定义一个变量s,用它
来存放累加的和 ? 用变量x表示待累加的数据,它的初值为2 ,每次循环后加4

230

program e6_5(input,output); var s, x: integer; begin x:=2; s:=0; while x<=98 do begin s:=s+x; x:=x+4; end; writeln(‘s=’,s); end.
231

有关while语句用法的说明
? 为了使while循环能正常结束(而不致造成死循环)
,布尔表达式中所含变量的值在循环中一定要有 所更改(如上例中的x:=x+4)

? While循环中do后面可以是一个简单语句,也可
以是用begin和end括起来的复合语句

? 如果首次计算布尔表达式时,其值就为假,则循
环体一次也不做
232

【例4-25 】输出1~100之间的奇数
program p4_25(input,output); var x: integer; begin x:=1; while x < 100 do begin write(x: 5); x := x + 2; end end.

233

【例4-26 】输入若干个字符,它的终止字符
是’#‘。计算输入的字符中字母’a’(包 括大小写)出现的次数。

? 参考程序见下页

234

program p4_26; var ch: char; i: integer; begin i := 0; read(ch); while ch <> ‘#’ do begin if (ch=‘a’) or (ch=‘a’) then i := i + 1; read(ch); {能否写成else read(ch)?} end; writeln(‘i=’, i); readln end.

235

【例4-27 】求输入的一个整数的各位数字之 和。

236

分析及问题:
? 如何求出一个整数的各个数位?
? 这个整数的长度确定吗?

? 如果该整数的长度不确定,则该如何来求
取它的各个数位?

237

program p4_27; var x, t, s: integer; begin readln(x); s := 0; while x <> 0 do begin

t := x mod 10; s := s + t; x := x div 10 end; writeln(s); readln; end.

238

【例4-28 】 求两个自然数m、n的最小公倍数。

239

解法分析
? 可以利用以下公式来求m、n的最小公倍数:
[m, n]=(m*n) div (m, n) ? 这样一来,可以将原问题转化求m、n的最大公约 数。之所以做这一转化,是因为我们原来对求两 个数的最大公约数这一问题及解法比较熟悉。

240

求两个数的最大公约数的算法
? 辗转相除 ? 辗转相减 ? 穷举法

241

求两个数的最大公约数:辗转相 除法
repeat r := m mod n;

m := n; n := r; until r = 0;

242

求两个数的最大公约数:辗转相 减法
While m <> n do if m > n then m := m – n else n := n – m;

243

求两个数的最大公约数:穷举法
if m >= n then gcd = n else gcd = m
while (m mod gcd<>0) and (n mod gcd<>0) do gcd := gcd – 1;

244

? 或者,也可以采用穷举法来直接求两个数m
、n的最小公倍数,分析如下

245

解法思路分析
1) 先设一个变量i,让它的值从1开始按自然
数增长 2) 将i与m相乘的积存入变量s中,这样s就是 m的倍数了。由于i是从最小的自然数开始 的,因而,s也就是从最小的值开始的

246

解法思路分析
3) 再用每一个s除以因子n,若能整除,则s
就是m与n的公倍数。第一个能整除n的就 是最小公倍数

247

program p4_28(input,output); var n, m, i, s: longint; begin write(‘请输入两个自然数’); readln(m, n); i := 1; s := m * i ;

248

while s mod n <> 0 do begin i := i + 1; s := m * i; end; writeln(‘m和n的最小公倍数是’,s ); end.
249

? 上机练习:计算1+2+4+8+<+128+256
{用for循环或while循环实现}

250

直到型循环(repeat)语句
repeat 语句1; 语句2; < 语句n; until 布尔表达式;

251

repeat语句的执行流程
1. 首先执行循环体(至少执行一次);
2. 然后,对布尔表达式进行判断:
1) 如果为假,则继续执行循环体; 2) 否则(即“直到布尔表达式成立”时),结束循环,执行 repeat循环语句的下一条语句;

问题:repeat循环与while循环有什么区别?
252

【例4-30 】用repeat语句改写【例4-26 】

253

program p4_26(input,output); var ch: char; i: integer; begin i:=0; read(ch); while ch<>’#’ do begin if (ch=‘a’) or (ch=‘A’) then i:=i+1; read(ch); end; writeln(‘i=‘,i) end.

254

program p4_30(input,output); var ch: char; i: integer; begin i:=0; repeat read(ch); if (ch=‘a’) or (ch=‘A’) then i := i + 1; until ch = ‘#’; writeln(‘i=‘,i) end.
255

多重循环结构
? 前面学习的循环结构称为单重循环
? 如果循环语句中又嵌套了循环语句,称为

多重循环。外层的称为外循环,内层的称
为内循环 ? 根据嵌套的层数,可以有两重循环,三重 循环等
256

【例4-31 】求100~999之间的水仙花数,即满 足abc = a3+b3+c3的数,如153 = 13+53+33 。

257

program p4_31; var a, b, c: integer; begin for a:=1 to 9 do for b:=0 to 9 do for c:=0 to 9 do if a*a*a+b*b*b+c*c*c = a*100+b*10+c then write(a*100+b*10+c); readln end.
258

【例4-32】编程输出如下图形: ########### ######### ####### ##### ### #
259

分析
? 解决字符图形打印问题的要点:
– 图形的特点 – 行数 – 每行的起始位置 – 根据图形的特点而做的其他特殊处理(如上下对 称、左右对称等)
260

分析
? 在该问题中,打印出来的图形行数与每行的“#”
号字符个数之间存在着一定

的关系 ? 可以采用双重循环:
– 外层循环变量(i)控制行数(从1到5变化) – 内层循环变量(j)控制每行“#”号的个数和位置

? 每行是由‘#’和空格组成的

261

每行的组成规律
? 每行前面的空格(即该行的起始位置)是行数
减1 ? 每行中的“#”号数是11 – 2*(i-1)

262

program p4_32(input,output); var i, j, k: integer; begin for i:=6 downto 1 do begin for j := 1 to 6 - i do write(‘ ’, 30 - i); {输出空格}

263

{以下是输出#号的循环} for k := 2*i-1 downto 1 do write(‘#’); ,输出#号后不换行} writeln; {换行} end; readln
end.
264

【例4-33】四个学生上地理课时,回答我国 四在淡水湖的大小时是这样说的。甲说: ?最大洞庭湖,最小洪泽湖,鄱阳湖第三 ?;乙说:?最大洪泽湖,最小洞庭湖, 鄱阳湖第二,太湖第三?;丙说:?最小 洪泽湖,洞庭湖第三?;丁说:?最大鄱 阳湖,最小太湖,洪泽湖第二,洞庭湖第 三?。其中每个人仅答对了一个,请编程 确定各个湖有大小顺序。
265

问题及解法分析
? 如何表示每个湖及每个人说的话?
? 该采用怎样的策略来解决本题?

266

program p4_33; var dong, hong, bo, tai: integer; begin for dong:=1 to 4 do for hong:=1 to 4 do if dong <> hong then for bo:=1 to 4 do if (dong<>hong) and (hong<>bo) then
267

begin tai:=10-dong-hong-bo; if (ord(dong=1)+ord(hong=4)+ord(bo=3)=1) and (ord(hong=1)+ord(dong=4)+ord(bo=2)+ord(tai=3)=1) and (ord(dong=3)+ord(hong=4)=1) and (ord(bo=1)+ord(tai=4)+ord(hong=2)+ord(dong=3)=1) then writeln(‘dong:’, dong,‘hong:’,hong,’bo:’,bo,’tai:’,tai); end; 268 readln

? 上机练习:编程计算 E= 1+1/2!+1/3!+<+1/n!

269

转向(goto)语句
? 格式:goto 语句标号
? 功能:当执行到此goto语句时,直接转到

“语句标号”所标明的那个语句行去执行

270

标号
? 可以是无符号整数,也可以是一个标识符
? 通常加在要转往的语句的前面,格式为:

标号: 语句;

271

转向(goto)语句
? 注意:goto语句中使用的标号必须在程序 说明部分的最前面进行说明,格式如下:

label 标号1, 标号2, <;
? (数字)标号的范围一般是1~9999

272

转向(goto)语句
? goto语句只能从一个语句结构中转出来,
而不能转到一个语句结构中去。 ? 例如,可以在循环语句中,通过goto语句 来跳出循环,但不能从循环语句的外部, 利用goto语句来转到循环语句的内部去 ? 此外,记住应少用或不用goto语句
273

【例】计算下列函数

? x ? 3, x ? 2 ? y?? ? x ? 1, x ? 2 ?
274

program eg(input,output) label 2, one; {说明了两个标号2和one} var x, y: real; begin readln(x); if x<=2 then goto 2 else y:= x – 1; writeln(y); goto one; 2: y:=x+3; write(y); one: end.

275

goto语句的应用
【例4-34】求出3~100

之间的所有质数。
? 参考程序及其修改版本见教材P60

276

综合应用
【例4-35】某班共有50名学生,已知他们的 其中考试的数学成绩,现需要统计100分、 90~99分、80~89分、70~79分、60~69分与 不及格成绩分别有多少人。
? 参考程序见教材P61

277

【例4-36】用5元钱买100只钮扣,其中金属
扣每只5角,有机玻璃扣每只1角,小揿扣1 分钱买3个,编程求出各种钮扣各买了多少 只?

278

问题分析
? 用x、y、z表示金属钮扣、有机玻璃钮扣和小揿扣
的只数。依题意可得如下方程组: x + y + z = 100 ? 可用穷举法来搜索求解。 ? 参考程序见教材P62 (1)

50x + 10y + z / 3 = 500 (2)

279

程序的优化
? 缩小循环控制变量的初值、终值之间的范
围 ? 减少循环的重数 ? 问题:可否如QB中那样,增加步长?

280

【例4-37】用尼考曼彻斯法(Nicomanchas法 ,即辗转相减法)求两个自然数a和b的最大 公约数。
? 参考程序见前面或教材P64

281

第五章 枚举类型和子界类型

282

本章主要内容
? 枚举类型的特点、用途、定义与应用
? 子界类型的定义、运算与应用

283

Pascal中的数据类型
? Pascal中的数据类型:简单类型,构造类型
,指针类型 ? 简单类型又分为:标准数据类型(整型、实 型、字符型、布尔型)和用户自定义类型(枚 举类型、子界类型等)

284

Pascal中的数据类型
? 构造类型分为:数组类型,集合类型,记
录类型,文件类型 ? 上面提到的数据类型中,除了指针是动态 类型外,其他都是静态类型 ? 在这些类型中,除了实型以外的其他简单 类型都是有序类型
285

枚举类型
看下面的两个程序片段:
1) var a: integer; 变量a可以取所有的整数 2) type
新类型 该新类型的取值

weekday=(monday,tuesday,wednesday,thursd ay,friday,saturday,sunday); var b: weekday;
286

枚举类型
? 在上面定义新类型weekday的做法中,将
该类型允许的取值一一列举(即枚举)出来, 因而,weekday即称为枚举类型; ? 变量b即为该枚举类型的变量

287

枚举类型的定义
? 格式:
type 枚举类型标识符=(标识符1,标识符2

,<,标识符n);
? 每个“标识符i?称为枚举元素或枚举常量,

它们构成了这种枚举类型的取值范围(亦称
“值域”)
288

枚举类型的定义
? 一旦定义了新的枚举类型后,就可以象其
他标准类型一样,定义该枚举类型的变量 了 ? 在一个类型定义部分,一次可以定义几个 枚举类型

289

枚举类型的定义
? 也可以将枚举类型的定义与该类型变量的说明合
并在变量说明部分: var b1, b2 : ( monday, tuesday, wednesday, thursday, friday, saturday, sunday); c : ( red, yellow, blue, white);

290

? 枚举类型的引入,增加了程序的可读性,还

可以
节省内存空间 ? 在PC机中,若定义a、b、c、d四个整型变量来分 别表示红、黄、蓝、白四种颜色,需要占用8个字 节

? 若用枚举类型,则只需一个字节,且最多可以表
示256种状态
291

枚举类型数据的特点及应用
? 枚举元素只能是标识符,不能是数据常量或字符
常量。例如,以下的定义是错误的: type days=(‘sun’,’mon’,’tue’,’wed’,’thur’,’fri’,’sat’); month=(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12);

292

枚举类型数据的特点及应用
? 枚举元素是标识符,但不能将这种标识符
视作变量名,亦即,枚举值是不能被赋值 的

293

枚举类型数据的特点及应用
? 同一个枚举元素不能同时出现在两个或两个以上
的枚举类型定义中。例如,以下的定义是错误的 :

type
day1=(monday, tuesday);

day2=(monday, wednesday);

294

枚举类型数据的特点及应用
? 枚举类型是有序的(亦即,其各个取值之间
是有顺序的),序号从0开始。 ? 例如,对于 Type

weekday=(monday,tuesday,wednesday,th
ursday,friday,saturday,sunday);
295

枚举类型数据的特点及应用
有:
ord(monday) = 0, ord(tuesday) = 1 succ(friday) = Saturday pred(saturday) = friday monday < tuesday的值为true, monday > tuesday的值为false
296

枚举类型数据的特点及应用
? 由于枚举类型是一种有序类型,故枚举类
型的变量可以用作循环控制变量。

297

枚举类型的数据特点
? 对枚举类型只能进行赋值运算和关系运算
。例如,对于: var d1, d2 : (sun, mon, tue, wed, thur, fri, sat);

c : (red, yellow, blue, white);

298

以下语句是合法的:
d1 := sun;

d2 := tue;
c := blue;

299

if d1 = d2 then
write(‘the same day’)

else
write(‘different day’);

300

? 以下语句则是错误的: mon := 1; {不能把枚举值当作变量} c := sun; {sun不属于c的值域} readln(d1,d2,c); {不允许用read或readln语句 对枚举变量进行赋值} write(d1,c,blue); {枚举变量或元素都不能用 write或writeln输出} ? 问题:那么,该如何输入输出枚举变量的值呢?
301

枚举类型的应用
? Pascal不允许直接读写枚举值,故经常用
case语句来间接地输入、输出枚举值:
– 输入:先输入枚举值的序号,再通过case语句 ,将枚举值相应地赋值给枚举变量 – 输出:通过case语句判断枚举类型变量的值, 输出相应的字符串

302

【例5-2】有红、橙、黄、绿、蓝五种颜色的
小旗,每次取出三种不同颜色的小旗表示 不同的信号,输出所有信号的方案及方案 总数。

303

program p5_2(input,output); type color=(red,orange,yellow,green,blue); var m,m1,m2,m3: color; s, p: integer; begin s:=0; for m1:=red to blue do for m2:=red to blue do if m1<>m2 then
304

for m3:=red to blue do if (m3<>m1) and (m3<>m2) then begin s:=s+1; write(s,

’:’); for p:=1 to 3 do begin case p of
305

1: m:=m1; 2: m:=m2; 3: m:=m3; end; {end of case p} case m of red: write(‘red’:8); orange:write(‘orange’:8); yellow:write(‘yellow’:8); green:write(‘green’:8);
306

blue:write(‘blue’:8); end; {end of case m} end; {end of for} writeln; end; {end of if} writeln(‘total’, s); end.
307

【例5-1】输入今天是星期几的序号(星期天
的序号为0),输出明天是星期几的英文单 词。

? 参考程序见教材PP69-70

308

子界类型
? 什么是子界类型?
如果要定义变量fs在整数1至100之间取值,可以 写作: type fs = 0 .. 100; 此处,fs是一个子界类型,它的值域为整数1至 100。

309

子界类型
? 问题:可否定义
fs : integer;

310

子界类型的定义
? type 子界类型标识符 = 常量1..常量2
其中,“常量1”称为下界,“常量2”称为

上界,上界必须大于下界

311

子界类型的定义
? 下界和上界可以是整型、字符型、布尔型
、枚举型等顺序类型的两个常量,且必须 是同一类型的数据,该类型称为子界类型 的基类型 ? 子界类型的值域实际上就是其基类型的一 个子集
312

子界类型的定义
? 使用子界类型时,要注意合理选择子界的
大小,否则会使一些本来是合法的数据变 成不合法,或失去检查的意义

313

子界类型变量的定义
type fs = 10 .. 200; zm = ‘a’ .. ’z’; var a1, a2 : fs; ca : zm;

314

子界类型变量的定义
? 此外,也可以如枚举类型一样,将类型定
义与变量定义合并起来进行定义,例如 var a1, a2 : 1 .. 150; ca: ‘a’ .. ’z’;

315

例:定义子界类型
type age=1..100; month=1..12; letter=‘a’..’z’; day=(sun,mon,tue,wed,thu,fri,sat); workday=mon..fri; var a1, a2: age; ch: letter; m: month; d1, d2: workday;
316

? 下面的定义是错误的(Why?):
var k: 3.4 .. 4.78;

这是因为,子界类型的上、下界不能是实
型。

317

子界类型数据的特点及应用
? 基类型上的各种运算都适用于子类型;
亦即,某一子界类型的变量可以当作其 基类型的变量一样来进行运算 ? 例见P73

318

子界类型数据的特点及应用
? 需要注意的是,子界类型的变量能否用
read、write直接进行输入和输出,取决于 该子界类型的基类型(例如,若基类型为枚 举类型,则不能直接用read、write输入和 输出)

319

子界类型数据的特点及应用
? 在同一程序中,具有相同基类型的不同子
类型的数据,可以混合运算。例如: Type atype = 1 .. 20; btype = 50 .. 100;

ctype = -1000 .. 1000;

320

var a: atype;
b: btype;

c: ctype;

321

? 在程序的执行部分,出现下列语句是合法的:
a := 10; b := a + 50; c := a * b; ? 要注意的是,变量a、b、c的值都不能超过各自的 范围,否则编译时会报错

322

子界类型的应


【例】 小明的爷爷记忆力不好,记不住每月 有多少天,于是,小明就编了一个程序来 帮助爷爷。当程序运行时,只要输入年、 月,计算机就能显示该月有几天。小明很 细心,为了减少爷爷在输入过程中的错误 ,使用了子界类型。

323

问题分析:
? 本例中,年(year)的取值范围可以考虑为
1~10000,月(month)的取值范围可以是 1~12,每月天数是28~31。因此,我们可将 它们定义为子界类型。

324

program p7_3(input,output); var year: 1..10000; month: 1..12; days: 28..31; begin read(year, month); case month of 1,3,5,7,8,10,12: days:=31; 4,6,9,11: days:=30; 2: if (year mod 4=0) and (year mod 100<>0) or (year mod 400=0) then days:=29 else days:=28 end; {case} writeln(year,’.’,month,’.’,days); 325 end.

【例5-3】按年、月、日的顺序读入一个日期
,输出该日期是这一年中的第几天。

? 参考程序见教材P74

326

【例5-4】将一个四位的十六进制数转换为十
进制数。

327

问题分析
? 不同进制的转换方法是怎样的?
? 十六进制数转换为十进制数数有什么特别

之外?
? 这种特别之处与子界类型有什么关系?

? 参考程序:见教材P75

328

类型相容及应用
? 当程序中用到的数据类型比较多时,会出现不同
类型之间能否相互转换或相互赋值的问题。例如 :

var a: integer;
b: 10 .. 100;

c: real;
那么,执行下列语句是正确的:
329

类型相容及应用
{整型变量a的值自动转换为} {实型数据后赋给实型变量c} 但是,执行下列语句就会出错: b := a; {假设a的值为200} b := c;

a := b; c := a;

330

类型相容及应用
? 那么,什么情况下,同一数值可以属于两
个不同的类型,什么情况下又不能属于两 个不同的类型呢? ? 这就是类型相容问题。

331

类型相容性
? 满足下列类型相容定义的定义之一,称为
类型相容:
1) 如果类型A和类型B是同一类型,则称类型A 和B是类型相容的。例如:

332

类型相容性
type int1 = 1 .. 50;
int2 = int1; 或者: type int1 = 1 .. 50; int2 = 1 .. 50; 则类型int1与类型int2是类型相容的。
333

类型相容性
2) 如果类型A是类型B的子界,或者类型B是类型A的子 界,或类型A和类型B均为同一顺序类型的子界。例 如:

type int3 = 10 .. 50;
int4 = 0 .. 100; ch1 = ‘a’ .. ‘z’; ch2 = ‘A’ .. ‘Z’;

334

? 类型int3是int4的子界,则类型int3和int4是
类型相容的 ? 类型ch1和ch2同是char类型的子界类型, 因而类型ch1和ch2是类型相容的

335

3) 如果类型A和B是基类型相容的集合类型,则
类型A和B是类型相容的; 4) 如果类型A和B是任意两个字符串类型,则类 型A和B是类型相容的。

336

?

对同一个值来说,可以属于类型相容的不同类
型,但不能同时属于类型不

相容的两个类型, 只有以下两个例外:
1) 在集合类型中,空集可以属于任何集合类型;
2) 在指针类型中,值nil可以属于任何指针类型。

337

赋值相容性
? 赋值相容是对进行赋值操作的两个数据对
象的类型要求 ? 设赋值语句中,?:=?左边的变量类型为T, 右边表达式结果的类型为E,即: <T类型的变量> := <E类型的表达式>

338

?

若类型T和类型E满足下列条件之一,则称它们
是赋值相容的:
1) T和E是相同的类型,且该类型不是文件类型或具有

文件成份的构造类型;
2) T是实型,而E是整型或整型的子界; 3) T和E是类型相容的顺序类型,且E的值不超出T所定 义的值的范围;

339

4) T和E是类型相容的集合类型,且E的值不超出
T所定义的值的范围; 5) T和E是类型相容的字符串类型,且E的长度不 超过T的取值长度; 6) T是字符串类型,E是字符数组类型,且E的长

度不超过T的长度。

340

? 当T和E是顺序类型或都是集合类型时,不
仅要求这两个类型是相容的,还要求E的值 不超出T所定义的取值范围,否则将产生溢 出,这种错误只能在运行程序时进行检查 ,因此,要避免发生这种错误。

341

? 例如:
var a: integer; b: 10 .. 100; c: real; d1: ‘a’ .. ‘z’; d2: char; 那么,程序中执行下面的赋值语句是正确的:

342

a := 80; d2 := ‘t’; a := b; c := b; d1 := d2;

343

? 类型的相容性可以在程序的编译阶段检查
出来,而赋值的相容性在编译阶段是无法 检查出来的,这是因为,在编译阶段,表 达式的值没有被计算出来,只有等到程序 运行后,表达式的值才能确定。

344

应用举例
【例5-5】某医院内科有a、b、c、d、e、f、 g七位大夫,他们在一星期内,每天要值一 次班,排班的要求为:1) a大夫值日比c大 夫晚一天;2) d大夫值班日比e大夫晚二天 ;3) b大夫值班日比g大夫早三天;4) f大夫 值班日在b、c大夫值班日之间,且在星期 四(thu)。请编程打印出每位大夫的值班日 。
345

问题分析
? 逻辑条件的表达
? 如何表达“星期几”? ? 如何打印出每位大夫值班的日子(星期几)? ? 参考程序见教材PP78-79

346

第六章 数 组

347

? 在前面的学习中,变量往往只用于表示单
个数据 ? 在实际应用中,往往需要处理成批的数据 ,如统计一批学生的成绩 ? 这样的批量、类型相同的数据,可以用数 组来表示
348

数组的概念和定义
? 数组由一组固定数目的、相同类型的数据
项,按一定的顺序组合排列而成 ? 亦即,一个数组中可以存放多个数据项; 一个数组中相当于包含了多个变量

349

数组的概念和定义
? 数组中的每个数据叫做数组元素。
? 在Pascal中,数组元素的个

数必须预先确定

? 数组元素利用数组名和数组下标来表示

350

数据: 12, 234, 简单变量: a b 数组元素: x[1] x[2] 对应的下标:i=1 i=2

345 c x[3] i=3

351

? 数组在使用前,也必须先定义,再使用 ? 数组类型的定义格式为: type

数组类型标识符=array[下标类型] of 元素类型
例如: type mu = array[1 .. 10] of integer; {问题: QB中是如何定义数组的?}

352

? ?下标类型”必须是有序类型,如整型、字
符型、布尔型、枚举型、子界类型等

353

? 上例中,下标类型是子界类型
? 每个数组的下标都有上界和下界,下标的

取值在上、下界之间是连续的
? 上例中的下标的下界为1(其实也可以从0开

始),上界为10,共整个数组中共有10个元

354

? 下标可以只有一个,也可以有多个;下标
的个数对应于数组的维数 ? 例如,上例中的数组是一维数组。

355

? type m = array[1..2, 1..3] of integer; 就是一个二维数组,它对应于如下表格:

M[1,1] M[2,1]

M[1,2] M[2,2]

M[1,3] M[2,3]

356

? 定义了数组类型后,必须定义数组类型的
变量,才能使用该数组: var 数组变量名:数组类型名;

357

? 在实际应用中,可以将数组类型定义和数
组变量定义合并在一起,如以上程序中的 数组类型和数组变量定义可以这样来改造 : var x: array[1..1000] of real;

358

数组定义的例子
var a: array[1..n] of char; b: array[10..1] of integer; c: array[integer] of boolean; {会报错: Structure too large} d: array[1.0 .. 3.0] of real; e: array[1 .. 50000] of real; {会报错: Structure too large}
359

数组的初始化
? Pascal允许在定义数组变量的同时,对数组变量赋初值: {var m: array[1..6] of integer=(2,1,5,7,9,6);} const m: array[1..6] of integer=(2,1,5,7,9,6);

? 这相当于定义数组元素:
m[1]:=2; m[2]:=1; m[3]:=5; m[4]:=7; m[5]:=9; m[6]:=6;

360

一维数组
? 一维数组指只有一个下标的数组,适用于
处理一行或一列数据 ? 例如,如果要对全班同学的计算机成绩求 和,可以定义一个一维数组

361

数组定义的例子
1. 30名学生的计算机课成绩
var math: array[1..30] of real;

2. 表示30名学生的及格或不及格情况
var cj:array[1..30] of boolean;

362

数组定义的例子
3. 每天学生出勤情况,按星期一~星期五计算
type day = (mon, tue, wed, thur, fri); cq = array[day] of integer; var m: cq;

363

数组定义的例子
? 在以上定义的数组中,m[mon], m[tue],
m[wed], m[thur], m[fri]这五个元素分别代 表星期一~星期五的出勤人数

364

注意:
? 在数组定义中,下标范围中不能有变量,
例如: var x: array[1 .. n] of char; 是错误的。

365

注意:
? 下标的下界、上界必须从小到大排列,例
如: var y: array[12 .. 2] of integer; 是错误的。

366


注意:
? 下标的范围不能太大,以免计算机的空间
分配不够,如: var z: array[integer] of real; 因为下标是integer,它包含的数据太多,

所以是错误的。

367

注意:
? 下标类型不能是实型,如:
var k: array[1.0 .. 10.0] of real;

是错误的。

368

注意:
? 在表示某一数组元素时,元素的下标可以是表达
式,该表达式必须与数组类型说明中的类型一致 ,如:

var x: array[1..20] of integer;
i: integer;

i := 3;
x[i+1] := 5;
369

一维数组的基本操作
? 数组的赋值、输入、输出
? 数组元素的移动

? 数组元素的查找、插入、删除

370

将数组作为一个整体进行操作
? 将数组作为一个整体进行操作出现在两种
情况下:
– 数组之间的相互赋值;{问题:QB中有无这样的 用法?} – 数组作为过程或函数的参数。

? 下面介绍第一种情况。
371

对数组的操作--赋值
? 两个同类型的数组之间可以(整体)相互赋值
。例如,设有数组a、b定义如下: var a, b: array[1..20] of integer;

372

对数组的操作--赋值
? 如果a已经赋值,则可以通过:
b := a;

来将数组a中所有元素的值都赋给数组b

373

对数组的操作--赋值
? 另外,输入/输出字符串变量也可以进行整
体操作,有关内容将在后面介绍。 ? 除此之外,对数组的基本操作都是以数组 元素为基本操作对象,通过简单循环来进 行的。

374

对数组的操作--输入和输出
? 一般情况下,采用循环来输入或输出数组
中的元素 ? 注意:数组无法整体输入或输出

375

对数组的操作--输入和输出
【例】输入100个数据,同时输出这些数据。

376

问题分析
? 输入数据可以用read或readln语句来完成
? 现在,利用循环来输入数组元素

377

program e6_3(input,output); var m:array[1..100] of real; i: integer; begin for i:=1 to 100 do begin read(m[i]); write(m[i]); end; end.
378

【例6-3】计算并输出

s?

?x
i ?1

10

i

yi

其中, xi的值为1、3、5<17、19,yi的值为

21、22、23<29、30。

379

问题分析
? 可以用两个整型数组来分别存放所有的xi和yi
? xi即第i个奇数,即2i+1 ? yi即20+i ? 对i进行1~10的循环,就能解决原问题。 ? 参考程序见教材P85

380

数组元素的移动
【例6-4】将a数组中第一个元素移到数组的 最后,将其余数据依次往前平移一个位置 ,如图6-1所示。
? 参考程序见PP85-86

381

数组元素的查找、插入、删除
【例6-5】对于数组a,输入一个测试数据x,
如果x存在于数组a中,则把元素x删除;否 则,将x插入在相应的位置上。要求数组仍 然有序(假设数组元素按递增顺序排列)。

382

问题分析
? 数组中的数据是如何来的?
? 如何在数组中查找?(顺序查找?二分查找?) ? 找到后如

何删除? ? 找不到的话如何插入? ? 参考程序见教材PP86-87

383

【例6-6】从键盘输入若干个数,将它们按照 从小到大的顺序输出。 要求:用选择排序和冒泡排序算法。 参考程序:见教材PP88-89

384

冒泡排序
1. 从A(1)~A(9),把相邻的两个数两两进行比较:
即A(1)和A(2)比,A(2)和A(3)比,A(3)和A(4)比 ,<<,A(9)和A(10)比;

2. 在每两个数的比较过程中,若前一个数比后一
个数大,则对调两个数;

3. 在比较完一轮后,若曾进行了对调 ,对调则从
(1)开始重复,否则排序结束。
385

program bubblesort;
const n = 10

var a: array[1..n] of integer;
begin write(‘排序前:’); for i := 1 to n read(a[i]); repeat f := 0;
386

for i := 1 to n-1 if a[i] > a[i+1] then begin t := a[i]; a[i] := a[j]; a[j] := t; f := 1 end; until f = 0 write(‘排序后:’); for i:= 1 to 10 write(a[i]); writeln; end.
387

一维数组应用举例
【例6-7】将一个十进制整数转化为二进制数


388

问题及算法分析
? 假设输入的整数为长整型,而二进制数的每个数
位用一个整型数组来存放(每个元素存放一个二进 位),那么,该数组应定义为多长?

? 十进制整数如何转化成二进制整数?
? 参考程序见PP89-90

? 问题:如何将十进制小数(实数)转换为二进制数?

389

【例6-8】圆盘找数:如图6-2所示,找出4个
相邻的数,使其相加之和最大和最小,给 出它们的位置。

390

问题及解法分析
? 本题是什么意思?该如何下手解决?
? 如果是简单地要求数组中最大元素或最小

元素,该如何做?
? 现在是要求找4个数,使其和最大或最小,

又该如何做?

391

问题及解法分析
? 如何找出连续的4个数?如何取遍所有可能的
连续4个数? ? 循环数组的问题? ? 参考程序见PP90-91

392

【例6-9】投票问题:竞选时,要求选民在A
、B、C、D四个候选人中选择(人数不限)。 如果选择了ABCD以外的人员,则视为废票 。统计时,输入?#?结束。请按候选人得 票数从大到小的顺序,输出候选人及其得 票情况。
393

问题分析
? 本题是什么意思?
? 选票上的内容是什么? ? 选票如何输入? ? 四个人的选票数如何记录、如何排序? ? 在对选票数排序时,相应的候选人的名字应如何 处理? ? 参考程序见教材P92
394

多维数组
? 在前面,我们介绍了数组类型定义的两种 形式: type 类型标识符=array[下标类型] of 基类型; type 类型标识符=array[下标类型1,下标类型 2,<,下标类型n] of 元素类型
395

多维数组
? 在第一种定义形式中,当数组元素的基类
型为数组类型时,即构成了多维数组,因 此经常可以见到这样的定义方式: type 类型标识符=array[下标类型1] of array[下标类型2] of 基类型;

396

多维

数组
? 可以这样理解:所有其他形式的数组都是在一维
数组的基础上衍生出来的,当组成一维数组的各 个元素本身又均为数组时,该数组即多维数组。

? 不过,在定义多维数组时,常采用第二种形式
? 最常用的多维数组是二维数组

397

二维数组
? 对于如下的表格中的数据,用一维数组来 保存就不合适了:

398

二维数组的定义
? 对于这样的表格数据,当需要引用某一行
、某一列中的数据项时,要用到两个下标 ,一个是行下标,另一个是列下标。这时 ,就要用到二维数组了,例如: type m = array[1..3, 1..4] of real; var s: m;
399

? 也可以直接定义二维数组变量:
var s: array[1..3, 1..4] of integer;

400

A[1,1]

A[1,2]

A[1,3]

A[1,4]

A[2,1]

A[2,2]

A[2,3]

A[2,4]

A[3,1]

A[3,2]

A[3,3]

A[3,4]

401

多维数组的应用
【例6-10】输入50名学生5门功课的成绩,输
出各人各科成绩及总分。

? 参考程序:教材P94

402

多维数组的应用
【例6-11】打印杨辉三角形的前10行。杨辉
三角形形如图6-3所示。

403

问题分析
? 这是一个数字图形打印问题
? 这类问题的要点/难点是什么?

? 杨辉三角形的规律是怎样的?
? 见图6-3,图6-4

404

多维数组的应用
【例6-12】大部分元素是0的矩阵称为稀疏矩
阵。假设稀疏矩阵中有k个非零元素,则可 以把稀疏矩阵用k*3的矩阵简单地表示,其 中第一列是行号,第二列是列号,第三列 是该行、该列下的非零元素的值。例如:

405

0 2 0 0

0 0 1 0

0 0 0 0

5 0 0 0

1 4 5
简记为

2 1 2

3 2 1

406

试编程读入一个稀疏矩阵,转换成简记形式
并输出。

407

问题分析
? 在本题中,要解决的主要问题是什么?
? 主要问题:查找非零元素,并记忆其位置 ? 将原矩阵存于数组a中,将转换后的矩阵存于数组 b中 ? 参考程序见教材PP96-97

408

【例6-13】奇数魔方阵:把整数1到n2(n为奇
数)排成一个n*n的方阵,使方阵中的每一行 、每一列以及对角线上的数之和都相同。 如图6-5(P97)就是一个五阶魔方阵。

409

15
16 22 3

8
14 20 21

1
7 13 19

24
5 6 12

17
23 4 10

9

2

25

18

11

410

问题分析
? 当n为奇数时,魔方阵可以按下列方法构成:
1) 把1填在第一行的正中间,然后依次填入数2到n2 ;

2) 如果数k填在第i行第j列的格子中,那么数k+1应填在
它的左上方,即第i-1行、第j-1列的位置中。但是, 如果左上方无格子,即如果i-1为0,则填在第n行第

j-1列的格子中;若j-1列为0,则填在第i-1行第n列的
格子中;若i-1和j-1均为0,则填在第n行第n列的格 子中。
411

问题分析
3) 如果按(2)的方法找到的格子中已填过数了,
那么数k+1改填在第k个数的正下方,即填在 第i+1行、第j列的那个格子中。


? 参考程序:教材P98

412

字符数组与字符串
? 紧缩数组 ? 字符数组与字符串

413

紧缩数组
? 为了充分利用存储空间,避免浪费空间,
Pascal引进了紧缩数组。 ? 紧缩数组的定义:在数组类型定义中的 array前面,加上关键字packed

414

紧缩数组
? 例如,数组a的定义为:
var a: array[1..10000] of char; 占用10000个字长,而改用紧缩方式: var a: packed array[1..10000] of char; 在16位微机中,就只占用5000个字长,而在32位 微机中,只占用2500个字长。

415

紧缩数组
? 在程序中,紧缩数组与非紧缩数组的用法
是相同的 ? 在紧缩数组中,特别值得重视的是字符数 组

416

字符数组与字符串
? 在实际应用中,大量用到字符串,如图书名、姓
名、地址等 ? 字符串可以用字符数组来表示 ? 在计算机系统中,字符数组的每个元素需占用一 个存储单元(字长)。

? 在字长为32位的计算机中,一个存储单元由32个
二进位所构成
417

字符数组与字符串
? 存储一个字符实际上只需8个二进位,这样就会造
成24个二进位的浪费 ? 如果数组元素是是布尔型的话,则存储空间的浪 费就更大了,因为每一个布尔值在存储时,只占 用一个二进位

? 为了减少存储空间的浪费,引入紧缩(字符)数组
的概念
418

紧缩字符数组
? 所谓紧缩字符数组,就是使数组中的字符
元素紧密地存储在存储单元中,从而可以 充分利用存储空间。 ? 问题:什么是“紧缩存储”?

419

紧缩字符数组
? 紧缩字符数组的定义如下:
var 数组名:packed array[下标类型] of 元素类型;

? 例: var b:packed array[1..8] of char;

420

紧缩字符数组
? 在上例中,b 数组中包含8个字符元素,在字长为
32位的计算机中,如果不作紧缩数组处理,需要 占用8个存储单元,会浪费24×8=192个二进位

? 将b数组定义为紧缩字符数组后,8个字符元素占
用8 ×8=64个二进位,只需占用2个存储单元,从

而大大节省了存储空间

421

紧缩字符数组
? 紧缩字符数组与非紧缩字符数组只是在存
储方式上有所不同,在使用方式上是相同 的

422

字符串
? 我们把存储在字符数组中的一串字符叫做
字符串 ? 字符串有常量形式和变量形式。例如, write(‘input a number’); 中括号内的内容就是字符串常量

423

字符串
? 紧缩字符数组中存入的字符串不但可以节约存储
空间,还能对字符串进行整体读写、比较和赋值 ? 例如,定义紧缩字符数组如下: var q, w: packed array[1..5] of char; 则在程序中可以直接执行整体读语句: readln(q);

424

字符串
? 如果输入字符串:try 则数组q中各元素值如下:
q[1] ‘t’ q[2] ‘r’ q[3] ‘y’ q[4] q[5]

425

字符


? 由于输入的字符数少于数组说明中规定的
长度,则元素q[4]、q[5]没有赋值,字符串 ‘try’后面会自动补空格 ? 如果输入的字符数多于数组说明中规定的 长度,则后面多余的字符就自动舍掉

426

字符串变量
? 字符串变量是紧缩型的一维字符数组,可以直接
用串类型标识符string[n]来表示字符串变量 ? 此处,n必须是一个确定的值,表示字符串的最大 长度,n的取值在1~255之间。 ? 在Turbo Pascal中,n可以省略,默认为255

427

字符串变量
? 定义字符串类型的格式为: type 字符串类型名=string[最大长度]; ? 字义字符串变量的格式为: var 字符串变量名:字符串类型名; ? 例如: type t1 = string[10]; var s: t1;
428

字符串变量
? 也可以直接定义字符串变量,其格式为 var 字符串变量名:string[最大长度]; 或: var 字符串变量名:string; ? 例: var x: string[7]; var y: string; {y是长度为255的字符串类型变量}

429

字符串变量
? 因为字符串变量是紧缩型的一维字符数组
,所以如下两个字符串变量的定义是等价 的: var x: packed array[1..5] of char; var x: string[5];

430

字符串的特性
? 由于字符串类型是数组类型的特殊情况,
因而字符串变量也可以像数组变量一样使 用,但也要注意其特性:

431

字符串的特性
? 对字符串可以整体输入和输出,如read(x)
、write(y) ? 允许对串变量进行赋值,如: x:=‘abc’;y:=x; ? 问题:对普通数组变量能否这样直接赋值?

432

字符串的特性
? 可以对字符串进行连接运算(运算符为“+”),如
‘ho’+’me’的结果是‘home’ ? 字符串之间可以利用关系运算符,进行关系运算 。 ? 比较的方法是:对两个字符串,从左到右,按

ASCII码逐个字符地进行比较。例如:‘abcsw’ <
‘abewkl’
433

TP中的标准字符串函数和过程
1) 字符串测长函数
– – – 格式:length(s); 功能:求字符串s的长度,返回结果为整型 示例:length(‘abcde’)返回的结果为5

434

TP中的标准字符串函数和过程
2) 取子串函数
– – 格式:copy(s,n,l) 功能:在s串中的第n位开始,截取长度为l的 字符串,结果为字符串类型

435

TP中的标准字符串函数和过程
? 示例:设x:=‘abc12345gh’,则copy(x,6,4)的
结果是‘345g’ ? 注意:
–如果n大于s的长度,则返回一个空串; –如果l大于从n开始余下的串,则仅返回到s的 尾部为止
436

TP中的标准字符串函数和过程
3) 查找子串位置函数
– – – 格式:pos(b,s) 功能:求子串b在(母串)S中的起始位置,结果 为整型。若未找到,则返回0 示例:设x:=‘is’;y:=‘This is a pen.’,则pos(x,y) 的结果为3

437

TP中的标准字符串函数和过程
4) 插入过程

– – 格式:insert(s1,s2,i) 功能:将s1插入到s2中第i个字符的位置。若结果超出

s2的最大长度,则超出的部分将被截掉
示例:设s为‘12345’,则执行insert(‘ab’,s,3)后,s 为’12ab345’

438

TP中的标准字符串函数和过程
5) 删除过程
– – – 格式:delete(s,i,n) 功能:删除s中第i个位置开始的n个字符。 示例:设s为‘abcdefg’,则执行delete(s,2,4) 后,s为’afg’

439

TP中的标准字符串函数和过程
6) 数值转换为字符串过程
– – – 格式:str(v,s) 功能:将数值v转换为字符串,存放在字符串 变量s中 示例:设v:=56,则执行str(v,s)后,字符串s为 ’56’

440

TP中的标准字符串函数和过程
7) 字符串转换为数值过程
– – – 格式:val(s,v,c) 功能:将字符串s转换为数值,变量c记录检测出错的

第一个字符的位置。当未出错时,c为0。
示例:设s为‘865’,则执行val(s,v,n)后,变量v的 值为865

441

TP中的标准字符串函数和过程
? 有关字符串的其他函数和过程参见附录
? 下面介绍一些字符数组和字符串的应用实



442

【例6-14】输入两串字母,并按字典顺序将
其输出。(字符串的长度不定,假设输入以 ‘#’字符作为结束。)

443

问题分析
? 定义两个字符数组,长度可以略大一些
? 字符串的输入以‘#’作为结束

? 参考程序见教材PP100-101

444

【例6-15】输入一行字符,其中包含若干个
单词,相邻的两个单词用空格隔开,编程 统计单词的个数。

445

问题分析
? 寻找并统计一下空格的个数,即可统计出单词的
个数 ? 问题是,整个字符串如何存储? ? 可以存储在一个字符串中,然后,对该字符串进 行扫描

? 参考程序见教材P102

446

【例6-16】输入两个整数x、y,输出它们的
和。(0<=x, y <=10100)

447

问题分析
? 对x、y可以进行通常的整数运算吗?
? 若不行的话,原因是什么? ? 应该如何解决?——用字符数组来存储大整数的各 个数位,这也就是高精度计算的思想 ? 本题给我们的启示:要注意题目中有关输入数据 的说明 ? 参考程序:P103
448

字符串的应用实例
? 例6-8 输入两个字符串,比较它们的大小, 然后按大的在前、小的在后的顺序输出。
? 问题分析:定义两个字符串变量s1、s2, 然后根据ASCII码进行比较,按照降序输出 。

449

program e6_8(input,output); var s1, s2: string; begin readln(s1); readln(s2); if s1 > s2 then begin write(s1); write(s2); end else begin write(s2);write(s1); end; end.
450

? 例6-9 英语老师给学生留作业,要求学生们 写一篇不超过500个英语字符的日记。现在 要求编程统计一下在这篇日记中,数字1、 2、3出现的次数。

451

问题分析
? 把日记的内容存入紧缩数组中,

最后输入
一个“!”来结束输入工作,然后对a中的 每一个元素进行检查,分别累计1、2、3出 现的次数。

452

program e6_9(input,output); var a: packed array[1..500] of char; n: char; j, len,one, two, thr: integer; begin read(n); len:=0;one:=0;two:=0;thr:=0; while n <> ‘!’ do begin len:=len+1; a[len]:=n; read(n); end;
453

for j:= 1 to len do begin if a*j+=‘1’ then one:=one+1; if a*j+=‘2’ then two:=two+1; if a*j+=‘3’ then thr:=thr+1; end; writeln(‘1的个数:’, one); writeln(‘2的个数:’, two); writeln(‘3的个数:’, thr); end.
454

? 思考:要在输入的一段英文中,查找某个
字母出现的次数如何编程?(例如,查找字 母k,不区分大小写)

455

【例6-10】输入25个英文单词,要将它们按
字典顺序排序(即排成从小到大的顺序)后 输出。

456

问题分析
? 每一个单词可以作为一个字符串,所以把
单词定义成字符串类型(紧缩字符数组类型 )。通常我们所见的英文单词字母个数都在 20个以内,因此,表示单词的字符串类型 长度定为20。

457

问题分析
? 然后,再定义一个包含25个元素的数组,元素类
型为字符串类型,表示如下: one two three <<

458

问题分析
? 共有25行20列,可以看作是一个二维数组
,只是每一行作为一个字符串,即一个单 词。

459

program e6_10(input,output); type zfch=string[20]; var m: array[1..25] of zfch; n: zfch; i, j: integer; begin for i:=1 to 25 do readln(m[i]);

460

for i:=1 to 24 do for j:=i+1 to 25 do if m[i]>m[j] then begin n:=m[i]; m[i]:=m[j]; m[j]:=n; end; for i:=1 to 25 do writeln(m[i]); end.
461

? 思考:输入全班同学姓名后,再按字典顺 序排序输出。 ? 注意:
1) 此处的姓名为汉字,而汉字在字典中是按汉 语拼音的字母顺序进行排序的;
2) 一个汉字相当于两个字母,因此在定义字符 串类型的长度时要考虑好

462

第七章 函数与过程

463

结构化程序设计
? 结构化程序设计思想有两个基本要点:
1) 自顶向下,逐步求精的设计方法; 2) 程序的模块化。

? 在Pascal中,过程与函数就是实现结构化 程序设计的主要手段之一。

464

? 要解决一个相对较大的、较为复杂的问题
,可以将其化为一系列较小的、较为简单 的问题来加以解决,这就是所谓的“结构 化程序设计”的思想

465

? 一个较大的程序可以划分为一系列较小的
模块(或称为子程序)来实现 ? 在Pascal语言中,这一系列的子问题可以用 函数或过程来实现

466

子程序的概念
? 在Pascal中,子程序一般是以函数和过程的形式
来呈现的。 ? 引入子程序之后,可以方便地把较为复杂的问题 分解成若干较小但易于处理的子问题 ? 更重要的是,可以使程序的结构清晰、层次分明

,增强了程序

的可读性

467

子程序的概念
? 程序是从主程序开始执行的,通过主程序去调用
子程序,子程序是不能单独执行的。 ? 在一个程序中,主程序只能有一个,但子程序可 以根据需要有多个,以完成不同的功能。 ? 主程序与子程序的一般关系见图7-1

468

函数
? 我们前面学过了一些Pascal语言提供的标准
函数,它们使用起来非常方便,但不能满 足我们所有的、特定的需要 ? 在这种情况下,程序员可以自定义函数。 亦即,可以根据自己的特殊需要,自己定 义一个新的函数。
469

新函数的定义格式
function 函数名(形式参数表):函数类型 var 变量说明部分 begin 函数体 end;

470

【例7-1 】输入两个数,求出其中较小的数。

471

问题分析
? 求两个数中较小的数这一任务,无法直接
用Pascal中的标准函数来解决。因此,可 将它定义为一个函数。程序如下:

472

function min(x, y: integer) : integer; begin if x <= y then min := x else min := y; end;

473

? 以上这种用户自定义函数由以下几部分构 成:
1) 2) 3) 4) 函数首部 变量说明部分 函数体 函数处理结果的返回

474

函数的调用
? 函数定义好了以后,就可以像标准函数一 样被调用了。调用格式为:
函数名(实在参数表)

475

program p7_1(input,output); var a, b, c: integer; function min(x, y: integer): integer; begin if x<=y then min:=x else min:=y; end; begin readln(a, b); c:=min(a,b); writeln(c); end.
476

有关函数调用的说明
? 函数调用必须出现在表达式中 ? 函数的调用过程是这样的:
1) 将主程序中的每个实在参数的值传递给函数中 对应的形式参数; 2) 然后,由函数完成处理; 3) 处理结果存放到函数名中送回主程序。

477

有关函数调用的说明
? 例如,对于上面例子中的c:=min(a,b),函数
调用的过程是这样的:
1) 它首先将a的值(如36)传给x,将b的值(如78) 传给y; 2) 函数处理后,将a、b中较小的数(如36)赋给 min,由min带回主程序中,再赋给变量c

478

有关函数调用的说明
? 实在参数与形式参数必须一一对应,参数之间用
逗号分隔开 ? 实在参数可以是表达式,在调用时,首先计算表 达式的值,再将它们赋给相应的形式参数 ? 函数可以没有形式参数;如果没有形参,那么在

调用函数时,也不能有实在参数及括号

479

有关函数调用的说明
? 自定义函数只能在定义它的程序中使用,
而且要将它写在程序的说明部分

480

【例7-2 】小明在读课外书时看到这样一个题
:设p=(a+b)!÷(a!+b!),当a、b分别为2 和3、4和5、7和8、5和6时,求p的值。

481

问题分析
? a!表示a的阶乘,即a!=a×(a-1) ×< ×2 ×1
? 要求p的值,需要先计算a!、b!及(a+b)!的值,为 此,需要先定

义一个计算n!的函数。 ? 然后,通过在主程序中调用该函数,问题就可以 解决了

482

function f(n:integer) : real; var i: integer; t: real; begin t:=1; for i:=1 to n do t:=t*i; f:=t; end;
483

program p7_2(input,output); var a,b: integer; p: real; function f(n:integer):real; var i: integer; t: real; begin t:=1;
484

for i:=1 to n do t:=t*i; f:=t; end; begin readln(a,b); p:=f(a+b)/(f(a)+f(b)) writeln(‘p=’,p:8:0); end.
485

? 思考:在什么情况下,程序中最适合使用
函数?

486

过程
? 函数实际上就是一段程序,相对于调用函数的主
程序而言,函数可以称为子程序,并且,这种子 程序在每次调用后,都必须返回值

? 如果需要设计子程序,但又不需要它返回值,该
怎么办呢?

? 这时,可以借助于过程。过程就是一种不返回值
的子程序
487

过程
? 在Pascal中,过程分为:
– 标准过程 – 用户自定义过程

488

标准过程
? 给某个语句序列组成的子程序赋予一个标
识符,程序中凡是需要出现这个语句序列 的地方,就可以独立地写上该标识符。 ? 像这样完成一个操作的子程序称这过程。

489

标准过程
? 前面用过的语句read/readln、
write/writeln实际上都是过程(语句)。 ? 由于它们都是Pascal语言系统预先说明的, 故称为标准过程。 ? Pascal的标准过程见附录。

490

用户自定义过程的定义
procedure 过程名[(形式参数表)]; var 变量说明部分 begin 过程体 end;

491

【例7-3】定义过程fa,求n!。

492

版本一:
procedure fa(n: integer); var k: integer; begin t := 1; {t是全局变量} for k := 2 to n do t := t * k; end;
493

版本二:
Var a, b: integer; procedure fa(n: integer; var t: real); var k: integer; begin t := 1; {t是变量参数} for k := 2 to n do t := t * k; end; Begin a := 3; fa(a, b); writeln(b); readln; End.

494

? 在以下这一行过程首部中:
procedure fa(n:integer;var t:real); N称为值形参(简称为值参),t 称为变量形参(简称 为变参) ? 与函数不同的是,在过程的体中,不能给过程名 赋值

495

【例7-4】定义交换两个变量值的过程。

? 问题:过程首部(尤其是参数)该如何设计?

应设计成值参,还是设计成变参?

496

Var a, b: integer; procedure swap(var m, n: integer); var zhong: integer; begin zhong := m; m := n; n := zhong; end; Begin a := 1; b: =2; writeln(a, b); swap(a, b); writeln(a, b); End. 497

【例7-5】定义一个求三个数中最大数的过程 。

498

Var a, b, c, d, e: integer; procedure max(x,y: integer; var z: integer); begin if x>z then z:=x; if z < y then z:=y; end; Begin a:=1;b:=3;c:=2; max(a, b, c); writeln(c); readln; End.

499

【例7-6】定义一个打印表头的过程head。

500

procedure head; {无形式参数} var k: integer; begin for k:=1 to 10 do write(‘*’); write(‘biaotou’); for k:=

1 to 10 do write(‘*’); end;
501

过程的调用
? 函数的调用不能作为单独的语句出现,而
过程的调用则必须是一个单独的语句 ? 过程调用语句的格式: 过程名(实在参数表);

502

【例7-7】求3!+4!+5!

503

program p7_7(input,output); var x, s: real; procedure fa(n:integer;var t:real); var k:integer; begin t:=1; for k:= 1 to n do t:=t*k; end;
504

begin s:=0; fa(3,x); s:=s+x; fa(4,x); s:=s+x; fa(5,x); s:=s+x; writeln(s:8:2); end.
505

有关过程调用的说明
? 实在参数与形式参数必须一一对应,参数
之间用逗号分隔。如fa(3,x)中,参数3对应 于过程中的形参,n对应于形参t ? 实在参数可以是常量、变量或表达式,如 fa(5+2,x)与fa(7,x)的效果是一样的

506

有关过程调用的说明
? 调用过程时,值形参只给过程提供数据,
但不能带回结果 ? 变量形参既可以给过程提供数据,也用于 将结果带回调用程序(或称主调程序)

507

有关过程调用的说明
? 也可以这样说,值形参是过程的输入参数,而变
量形参既是输入参数,也是输出参数 ? 例如,对fa(3,x),调用时将3赋给n,将x的值(此 时为0)赋给t,过程执行完后,再将t的值赋给x, 由x带回到主程序中

? 过程调用及返回的示意图见教材P125

508

有关过程调用的说明
? 使用过程时需要特别注意的一个问题就是
参数的传递问题,尤其是变量参数的传递 。

509

【例】比较下面的程序与程序p7_7的不同,
写出程序的执行结果。

510

var x,s: real; procedure fa(n: integer; var t: real); var k:integer; begin for k:= 1 to n do t:=t * k; end;
511

begin s:=0; x:=1; fa(3,x); s:=s + x; fa(4,x); s:=s + x; fa(5,x); s:=s + x; writeln(s:8:2); end.
512

【例7-8】编写过程来求如P112图所示的五边 形面积。 参考程序见P112。

513

【例7-9】幼儿园大班做游戏,由老师随便说
出三个字母,然后由小朋友按字母表顺序 排列这三个字母。编程帮助小朋友完成这 一任务。

514

问题分析
? 在给字母排序时,可能要交换两个变量的
值,这可以用例7-4中的过程来完成,程序 如下:

515

program p7_9(input,output); var a1,b1,c1: char; procedure swap(var m, n: char); var zhong: char; begin zhong:=m; m:=n; n:=zhong; end;

516

begin read(a1,b1,c1); if a1>b1 then swap(a1,b1); if a1>c1 then swap(a1,c1); if b1>c1 then swap(b1,c1); writeln(a1,b1,c1); end.
517

过程与函数的主要区别
1) 过程一般会被设计成求若干个运算结果,
或完成一系列的数据处理、或与计算无关 的各种操作,而函数往往只是为了经过加 工求得一个函数值; 2) 过程无类型,不能给过程名赋值;函数有 类型,最终要将函数值赋给函数名;
518

过程与函数的主要区别
3) 调用方式不同。函数的调用出现在表达式中,
而过程调用是由

独立的过程调用语句来完成的 ;

4) 返回值的方法不同。函数值是通过函数名传回
主调程序的,而过程则是通过变参/实参或全局

变量将运算结果带回主调程序。

519

局部变量与全程变量
? Pascal程序中使用的所有变量都必须先定义
(或称说明)再使用 ? 主程序中有变量说明语句,过程和函数中 也有变量说明语句

520

局部变量与全程变量
? 在主程序中说明的变量称为全程变量(或称
全局变量),如例7-7中的x、s等。 ? 在过程/函数中说明的变量称为局部变量, 如例7-9中的zhong

521

变量的作用域
? 变量在程序中的使用范围称为变量的作用域
? 在程序中,局部变量和全程变量的作用域是不同 的:
–局部变量的作用域是它所在的过程或函数 –因为形式参数也只在它所属的过程或函数中有效,所

以也属于局部变量

? 全程变量的作用域分两种情况,下面通过例7-10 说明
522

【例7-10】通过程序运行结果,体会全程变
量的作用域。 1) 全程变量在过程中改变值时,新的值回到 主程序后有效。

523

program p7_10_1(input,output); var m: integer; procedure test1; begin m:=100; {m为全程变量} end; begin m:=5; writeln(‘Before’, m); test1; writeln(‘After’, m); end.

524

2) 全程变量和局部变量同名时,全程变量的
作用域是包含同名局部变量的过程或函数 以外的程序部分。

525

program p7_10_2(input,output); var m:integer; procedure test1; var m:integer; begin m:=100; end; begin m:=5; writeln(‘before’,m ); test1; writeln(‘after’,m); end.

526

? 利用全局变量的性质,可以对例7-7的程序修改如 下: program p7_7_2(input,output); var t: integer; s: real; procedure fa(n:integer); {不再使用变量形参} var k:integer; begin t:=1; for k:=1 to n do t:=t * k; end; 527

begin s:=0; fa(3); s:=s + t; fa(4); s:=s + t; fa(5); s:=s + t; writeln(s:8:2); end.
528

一些说明
? 引入局部变量的好处是既可以节省内存空
间,又给结构化程序设计带便利。 ? 在程序中,为了使各模块间的影响尽可能 地小,常常使用局部变量。 ? 当模块间需要某种联系时,可以采用全局 变量或形式参数。
529

【例7-15】(数组参数)设计一个过程,将数组 中的元素从小到大排列。 ? 思考:如何设计该过程的参数,使得既能 得到输入数组,又能将排过序的数组传回 主调程序? ? 参考程序:见教材P119
530

关于形参数组的说明
? 当形参为数组时,必须用类型名对形参数 组的类型预先加以定义,不能写成:

procedure sort(var p:array[1..10] of
integer);

? 另外,定义函数时,要注意函数的结果类
型不能是数组类型,因为函数的功能只是 求得一个值。
531

【例7-16】编写过程,将一个实数拆分成整
数部分n和小

数部分p。 ? 思考:如何设计过程的参数,才能既能输 入一个实数,又能将整数部分和小数部分 返回主调程序。 ? 参考程序:见教材P120
532

值参和变参区别小结
? 传值:为值参分配存储单元,将实参的值
赋给值参,过程体内对值参的操作不影响 实参。一旦过程体执行完毕,系统将收回 值参所占用的存储单元,值参的值也就不 复存在了。

533

值参和变参区别小结
? 传地址:将实参的地址传给对应的变参,
即变参所占用的存储单元中存放的是实参 的地址,因此对变参的操作就是对实参的 操作。一旦过程体执行完毕,系统将收回 变参所占用的存储单元,但运算结果已保 留在对应的实参中。
534

值参和变参区别小结
? 由此可以看出:过程定义中的形参种类不
同,决定了实参的单、双向传递 ? 值参实现的是单向传递,仅把过程外部的 值传递给过程,故可以称之为输入参数, 它所对应的实参可以是常量、变量或表达 式
535

值参和变参区别小结
? 变参实现的是双向传递,除了将过程外部
的值传递给过程外,更重要的是它能将过 程中经过加工处理的形参值带出来,故又 称之为输出参数,其对应的实参必须为变 量

536

嵌套与递归
【例7-11】 子程序的嵌套: program p7_11(input,output); var n: integer; procedure sub; procedure tu1; begin writeln(‘##########’); end; {tu1}
537

procedure tu2; begin writeln(‘**********’); end; {tu2} begin tu1; writeln(‘welcome’:7); tu2; end. {sub} begin sub; end.
538

? 上面的程序中,过程sub中又定义了过程
tu1和tu2,这就是过程的嵌套。函数的嵌套 也是类似的。 ? 注意:定义嵌套过程或函数时,内、外层 子程序不能相互交叉,内层必须完全嵌套 在外层中
539

调用原则
? 外层程序可以调用与它相邻的内层程序,
反之不行。 ? 此外,也不能隔层调用。例如,主程序可 以调用sub,sub可以调用tu1和tu2,但tu1 和tu2都不能调用sub,主程序也不能直接 调用tu1和tu2
540

调用原则
? 同层子程序处于后面的可以直接调用前面
的,如tu2可以调用tu1。如果tu1想调用调 用tu2,必须作出如下处理:

541

procedure tu2; {新增的行,使tu2的首部提前} forward; {向前引用} procedure tu1; begin tu2; writeln(‘##########’); end; {tu1} procedure tu2; begin writeln(‘**********’); end; {tu2}
542

【例7-12】

的计算公式为:
Cm
n

Cm

是数学中的组合运算符号, n

Cm

n

=m!/(n!×(m-n)!),
C9

利用公式分别计算

和 3

C8

5



543

program p7_12(input,output); function fac(x:integer):integer; var i: integer; begin fac:=1; for i:=1 to x do fac:=fac*i; end;
544

function c(a,b:integer):real; begin c:=fac(a)/fac(b)*fac(a-b) end; begin {主程序} writeln(‘c(9,3)=

’,c(9,3)); writeln(‘c(8,5)=’,c(8,5)); end.
545

【例7-18】求组合数 3 5的和。 C6 ? C9 已知
C
m n

n! ? m !(n ? m)!

,在本题中定义一个具有嵌套结构的函数, 外层函数cnm用于求C,内层函数fac用于求 k!的值。 ? 参考程序见教材PP122-123
546

说明
? 在本程序中,函数cnm和fac被定义为实型
,是为了避免整数运算产生溢出 ? 本程序中各函数间的调用关系见教材P123

547

递归
? 一个函数或过程直接或间接地调用其自身
,就是递归 ? 在解决某些程序设计问题时,递归是一种 非常有用的方法,它可以使得某些看起来 不容易解决的问题变得容易解决,写出的 程序较为简洁、自然
548

【例7-13】递归计算n!。

549

问题分析
? n!可以由下列公式计算:

?1 n! ? ? ? n(n ? 1)!

n =0 n>0

550

问题分析
? 因为(n-1)!乘n等于n!,所以求n!的问题可以
转化为求(n-1)!的问题,同理又可以转化为 求(n-2)!的问题,<<,最后归结为求0!的 问题,而0!已定义为1。这时,再由0!一 步步返回上去,求出1!、2!、<<直到 求出n!。
551

program p7_13(input,output); var n:integer; y:real; function fac(n:integer):real; begin if n=0 then fac:=1 else fac:=n*fac(n-1); end;
552

begin readln(n); y:=fac(n); writeln(n,’!=’,y:10:0); end.

553

? 上面递归程序的递归求解过程见教材P132图示
? 递归结构的程序具有结构清晰、容易阅读和理解 的特点。 ? 但在处理递归问题的过程中,需要保留每次递归 调用时的参数和局部变量,这样就需要占用大量

的存储空间和耗费更多的时间,因此程序的运行
效率比较低。
554

【例7-14】输入一串字符(以‘*’结束),按
相反的顺序输出。

555

program p7_14(input,output); procedure nixu; var c: char; begin read(c); if c<>’*’ then nixu; write(c); end; begin nixu; end.
556

【例7-21】用递归方法求两个数m和n的最大 公约数。(m>0,n>0)

557

问题分析
? 求两个数的最大公约数,可以用循环搜索
方法,找到能被两个数同时整除且是最大 的约数的方法;也可以用展转相除法,这 里采用递归程序设计方法。

558

求两个数的最大公约数:辗转相 除法
r = m mod n 当 r<>0 重复做
1) m=n 2) n= r 3) r= m mod n

559

求两个数的最大公约数:辗转相 除法
? 该算法符合递归条件:
1) 求m与n的最大公约数等价于求n与余数r的最 大公约数,即将原问题的求解转化为子问题 的求解,其求解方法与原问题相同; 2) m与n的值不断更新,使问题求解的范围愈来 愈小;

560

3) 在不断求解两个数的公约数的过程中,范围 变小,直到满足结束条件m mod n =0 即余数 为零,则求出最大公约数,其值是最终存放 在n中的数据。显然这个问题可以用递归来实 现。可以归

纳出如下递归公式:

561

求两个数的最大公约数:辗转相 除法的源程序
program p7_21(input,output); var m,n,g:integer ; function gcd(m,n:integer):integer; var r: integer; begin r:=m mod n;

562

求两个数的最大公约数:辗转相 除法的源程序
if r=0 then gcd :=n else gcd:=gcd(n, r); { 递归调用,此时n,r} {的值都发生了变化 } end; {of function} begin { 主程序 } read (m,n); g := gcd( m,n); writeln (‘m=’,m ,’n=’,n ,’gcd=’,g ); end.
563

练习:
? 画出程序中函数递归调用的过程,并用栈
表示出参数m,n的变化。

564

递归程序设计练习:
1. 用递归方法计算1+2+3+<<+n的值
2. 从键盘输入n个数,用递归方法求最大数

及最大数在数列中的位置
3. 从键盘输入一串字符,以“!”结束,以

逆序方式输出

565

递归程序设计练习:
4. 练习册中的递归函数计算如:

计算ack(1,2)和ack(2,2)的值 。

566

过程与函数的综合应用
【例7-24】从键盘读取A,B数组的元素,A, B数组均已从小到大排好序(无相同元素) ,现将A,B合并为数组C,同样要求数组C 也是从小到大排好序(有相同元素时只保 留一个)。程序中n表示数组A,B的长度, i,j,k分别表示数组A,B,C的取数或存 数的指针。

567

program excp3; const n=8; m=2*n; type arr1=array [1..n] of integer; arr2=array [1..m] of integer; var a,b : arr1; c : arr2; i,j,k :integer; procedure copy(x: arr1; var y: arr2; var i, j: integer); begin i := i + 1; y[i] := x[j]; j := j + 1; end; 568

begin for i:=1 to n do read(a[i] );readln; for i:=1 to n do read( b[i] );readln; i:=1;j:=1; k:=0 ; while (i<=m) and (j<=n) do if a[i]<b[j] then copy (a,c,k,i) else if b[j]<a[i] then copy (b,c,k,j) else begin copy(a,c,k,i); j:=j+1 ; end;
569

while i<= m do copy(a,c,k,i); while j<=n do copy(b,c,k,j); writeln for i:=1 to k do write (c[i]:4); writeln; end.

570

问题:
? 在过程、函数设计中,何时该用变参,何
时该用值参,能否仅用全程变量,而不用 变参?

571

【例7-25】 有n只猴子选大王,先从头到尾1 至3报数,报到3的猴子退出,报至尾后, 再尾到头1至3报数,报到3的猴子退出<< 依此类推,当剩下两只猴子时,报1的猴子 为大王。问:若想当大王,应站在什么位 臵?

572

问题分析
? 以10只猴子为例,则猴子退出的编号顺序为:3 6
9 7 2 5 4 10,当剩下8号和1号时,8号猴子报1 ,因而为大王。

? 该如何来设计存储这n只猴子及其是否出列状态的
数据结构呢?
– 可以定义一个一维数组h,用于存放猴子是否出列的信
息,如h[3]=0即表示3号猴子已经出列,h[7]=1即表示7 号猴子还在圈中
573

问题分析
? 报数及改变猴子是否出列状态的过程中,
有哪些关键问题要加以

注意和处理呢?
– 报数的方向 – 在当前的这一轮报数中,还剩下几只猴子要参 加报数(或者说,如何控制当前这一轮循环的结 束?)

574

过程与函数的深入应用
【例1】验证哥德巴赫猜想:将6—100的偶数分解为 两个素数的和。 其输出形式为: 6=3+3 8=3+5 10=3+7 12=5+7 <<
575

问题分析:
1) 本问题解决的模式:x=t1+t2,由此得出需要产 生两个数t1与t2,只要确定了t1,则便得到t2
2) t1可以从3开始逐渐递增,t2=x-t1

3) 需要判断t1、t2是否为素数,因此两次调用判断 素数的程序,由此得出设计一个函数,其功能 是判断一个数是否为素数 4) 函数中的参数和函数的值的类型的设计、整个 程序的设计
576

program liti1; var x,t1,t2 :integer ; function prime ( n : integer ) : boolean ; var i: integer ; begin prime:=true ; for i:= 2 to (n div 2) do if n mod i=0 then prime:=false; end;
577

begin x:=6 ; while x<200 do begin t1:=1 ; repeat t1:=t1+2 ; t2:=x - t1 ; until prime(t1) and prime(t2) ; write(x,?=?,t1,?+?,t2); x:=x+2 ; end; end.
578

练习:
? 验证:将7-100之间的奇数分解为三个素数
的和(提示:难点在于如何拆分三个数)。

579

【例2】用递归方法求n个数中的最大数。

580

问题分析
? 求n个数的最大数,可以理解先求n-1个数
的最大数<<,直到求两个数的最大数, 得到两个数的最大数后,递归返回可以求 得3个数、<<、n-1个数的最大数,直到求 得n个数的最大数。

581

问题分析
? 请同学们设计分析过程或函数的参数设置
,希望能输出最大数的位置。下面给出过 程的解决方案:

582

program liti2 ; var x, n, k: integer ; procedure maxn( var x:integer; i:integer); var y :integer ; begin if i>n then exit else begin read(y); if x < y then begin x:=y; k:=i;end; maxn(x, i+1); end; end;
583

begin read(n,x); k:=1;

maxn(x, k+1);
writeln(?max=?,x, ? ? , ?k=?,k);

end.
584

【例3】用递归方法,将一个十进制数n转换
成t(设t<=9)进制的数。

585

问题分析
1)输入n、t;
2)方法:除以t反向取余数

586

? 方法1:用循环加数组结构 ? 方法2:
1) 2) 3) 4) 用n除以t取余数,将余数结果赋值给k 再用n除以t取整数,其结果赋值给n 如果n不为0,则以n为实参继续调用过程 输出k的值

587

? 由于递归程序调用特点,先进后出,所以
输出结果正好为逆序输出 ? 该问题在设计中,如果仍然用数组存放余 数的话,就不能体现递归算法的优点和特 点了,参考算法如下:

588

procedure transform( n: integer); var k: integer;

begin
k:=n mod t ;

n:=n div t ;
if n <> 0 then transform(n) ;

write(k:1);
end;
589

主程序: (1) 输入n, t (2) transform( n)

590

? 通过以上例题的分析与综合运用,同学们
应该能够掌握递归程序设计的方法,并且 能够

理解递归调用的过程、参数变化、变 量的变化等,为后面学习回溯算法打下坚 实基础

591

? 递归程序设计的缺点:递归调用嵌套层次
不能过深,否则会栈溢出。 ? 解决方案:将递归算法改为非递归算法

592

第八章 集合和记录

593

集合的概念
? 在数学中,把具有某些共同特征的元素构
成的一个整体称为集合 ? 在Pascal中,一个集合就是由同一种有序类 型的一组数据元素所组成的,这一有序类 型称为该集合的基类型

594

集合的表示
? 集合一般用一对方括号表示:
[red,black,white,blue,green,yellow] ? 其中, red、black、white、blue、green、 yellow称为集合的元素,各元素间用逗号隔开 ? 在一个集合中,可以没有任何元素,这样的集合

称为“空集合”,用[]表示

595

有关集合的几点说明
? 集合的值与方括号内元素出现的次序无关,如[1
,2,3,4]与[1,2,4,3]是两个相等的集合 ? 在集合中,同一元素的重复出现对集合的值没有 影响,如[1,2,3,1,1,2]与[1,2,3]也是两个相等的集合 ? 问题:集合与数组有什么区别吗?

596

有关集合的几点说明
? 在集合中,如果元素的值是连续的,则可
以用子界类型来表示。例如,对于 [1,2,3,4,5,8,9,10,15,21,22,23,24] 这个集合,可以表示成

[1..5, 8..10, 15, 21..24]

597

有关集合的几点说明
? 集合的基类型可以是任何顺序类型,包括
整型、字符型、枚举型、子界型,但不能 是实型或其他构造类型 ? 每个元素均可以用基类型所允许的表达式 来表示,如[1+10,4*2,3..6]

598

集合类型的定义及集合变量的说 明
? 集合也是一种用户自定义的数据类型,与
枚举和子界类型一样,其定义如下: type 标识符 = set of 基类型;

599

集合类型的定义及集合变量的说 明
? 例: type num1 = set of 1..10; num2 = set of integer; c1 = set of ‘A’..’Z’; c2 = set of char; weekday = (sun,mon,tue,wed,thur,fri,sat); colors = (red,black,white,blue,green,yellow); fruits = (orange,banana,apple);
600

集合类型的定义及集合变量的说 明
c3 = set of weekday; c4 = set of colors; c5 = set of fruits;

601

集合类型的定义及集合变量的说 明
? 有了以上的集合类型定义后,就可以定义
集合类型的变量了,如: var n: num1; ch1: c1;

602

集合类型的定义及集合变量的说 明
? 也可以把集合类型的定义和集合类型的变量定义
合并到一起,如: var n: set of 1..10; ch: set of ‘A’..’Z’; ? 当一个集合变量允许包含有n个元素时,不考虑有 重复元素的情况,则所构成的集合有2n种可能

603

? 例如:type numset = set of 1..3;
var n: numset; 则集合n的值有8种可能,分别为:

[],
[1],[2],[3], [1,2],[1,3],[2,3], [1,2,3]
604

集合的赋值

? 对集合变量的赋值只能通过赋值语句来完成,而 不能通过输入语句(read或readln)来进行(与枚举 类型变量相似) ? 例如,假设在程序说明部分已包含了以下一行:
var ch1, ch2: set of ‘A’..’Z’; 那么,在程序的执行部分,只能通过赋值语句对 ch1、ch2赋值,如:
605

集合的赋值
ch1:=[] ch2:=*‘A’..’D’+; 而不能用read(ch1, ch2);

606

? 另外,还要注意,赋值号右边必须用
*‘A’..’D’+,而不能写成 ch2 := ‘A’..’D’; 这是因为赋值号的左边是集合型变量,根

据赋值相容原理,赋值号右边也必须是一
个集合(或集合表达式)
607

集合之间的并、交、差运算
? 假设有两个集合A=[1,3,4,5],B=[4,5,6,7],则A和B
可以进行求并集(+)、交集(*)、差集(-)三种集合运 算:

A + B = [1,3,4,5,6,7]
A * B = [4,5]

A – B = [1,3]

608

集合之间的关系运算
? 两个集合之间可以进行不等、相等、包含或被包 含的关系运算,运算的结果为布尔值 ? 假设有A=[1,3,4,5],B=[1,3,4],则上述四种关系运 算的含义如下: A=B false A <> B true A <= B(包含于) false A >= B(包含) true
609

in运算
? 在程序设计过程中,经常要检查一个元素
是否在指定的集合中,从而对这个集合做 进一步的操作 ? ?属于集合”运算符in是用来判断元素与集 合的关系的,运算结果也是布尔型

610

in运算
? 例如,假设集合a=[1..5],x为integer,要求 判断x是否在集合a中,若在,则删除a中的 这个元素;若不在,则把x这个元素添加到 集合a中。 ? 程序片段如下: if x in a then a:=a – [x] else a:=a + [x];
611

in运算
? 集合变量的输出也不能直接用write或writeln语句 ,往往也是通过in运算来实现的(这一点也与枚举 类型变量类似) ? 例如,集合a=[1,3,5,7,9,11,13,15,17,19],x为 integer,要求输出20之内的奇数,程序段如下:
for x:=1 to 20 do

if x in a then write(x:3);

612

集合的综合应用
【例8-1】调用随机函数产生10个互不相同的
随机整数(0≤x ≤ 40),放入集合中并一 起输出(5个一行)。

613

program p8_1(input,output); var a: set of 0..40; i, m, n: integer; begin a:=[]; n:=0; randomize; repeat m:=random(41); if not(m in a) then begin a:=a+[m]; n:=n+1; end; until n = 10;

614

n:=0; for i:=0 to 40 do if i in a then begin write(i:4); n:=n+1; if (n mod 5)=0 then writeln end; End.
615

? 输出的一个样例: 2 6 19 21 25 24 30 32 38 40

616

【例8-2】从键盘输入一系列字符,编程分别
统计出其中的数字字符、字母字符和其他 字符的个数,输入???时表示程序结束。 ? 问题:判断属于各种字符的方法有哪些?

617

program p8_2(input, output); var ch: char; letter: set of char; digit: set of ‘0’..’9’; k, m, n: integer; begin letter:=*‘a’..’z’,’a’..’z’

+; digit:=*‘0’..’9’+; k:=0; n:=0; m:=0;
618

repeat read(ch); if ch in letter then k:=k+1 else if ch in digit then n:=n+1 else m:=m+1; until ch=‘?’ writeln(‘letter=‘,k:6,’digit=’,n:6,’other=’,m-1:6); {空格也算其他字符,但应减去最后一个“?”} end.
619

? 输入一个样例:abc&ddd$12345#? 输出样例的结果:letter=6 digit=5 other=4

620

【例8-3】用筛法求n以内的所有素数(包括n
,输出时5个一行)。

621

问题分析
? 筛法是一种高效地求素数的方法,它是由希腊著
名数学家埃拉托色尼(Eratosthense)首先提出的。 ? 具体算法如下: 假设用集合变量sieve表示筛子,用集合变量 primes存放结果(n以内的所有素数)。

622

1) 初始化:将所有候选数放入筛中,即
sieve:=[2..n],同时置primes:=[]; 2) 找出筛中的最小数next,next必定为素数; {为 什么?} 3) 将next存入primes中,同时将它的所有倍数从

sieve中筛去;
4) 重复(2)~(3),直到筛为空时为止(sieve=[])
623

program p8_3(input,output); const n=100; var sieve, primes: set of 1..n; next, j: integer; begin sieve:=[2..n]; primes:=[]; next:=2;
624

repeat while not(next in sieve) do next:=next + 1; primes:=primes+[next]; j:=next; while j<=n do begin sieve:=sieve – [j]; j:=j+next; end; until sieve = [];
625

j:=0; for next :=2 to n do if (next in primes) then begin write(next:4); j:=j+1; if (j mod 5=0) then writeln; end; writeln; end.
626

【例8-4】口袋中有红、黄、蓝、白、黑5种
颜色的5只小球,每次从口袋中取出3只球 ,问:最多有几种不同颜色的组合?

627

问题分析
? 应如何设计算法?
? 应如何记录(注意,是问“记录”,不是打

印)各种组合的具体颜色值?
? 应如何输出各种组合中的颜色值?

628

program p8_4(input,output); const m = 30; type color = (red,yellow,blue,white,black); colset=set of color; arrset=array[1..m] of colset; {每个元素为一 个集合} var p, n: integer; a: arrset; i, j, k, pri: color; b: colset; yes: boolean;
629

begin for p:=1 to m do a[p]:=[]; n:=0; for i:=red to black do for j:=red to black do if i<>j then

630

for k:=red to black do if (k<>i) and (k<>j) then begin b:=[i]+[j]+[k]; yes:=true; for p:=1 to m do if b=a[p] then yes:=false; if yes then begin n:=n+1;a[n]:=b;end; end;
631

for p:=1 to n do begin for i:=red to black do if i in a[p] then case i of red: write(‘red’:20); yellow: write(‘yellow’:20); blue: write(‘blue’:20); white: write(‘white’:20); black: write(‘black’:20) end; writeln; end; writeln(‘total num is :’, n);

632

【例8-5】 编程把一个任意十进制数转换成成 二进制数,要求利用集合表示二进制数.如 18的二进制数为10010,则集合的值为[2,5] ,即倒数第2位和倒数第5位上是1,其余各 位是0。
? 输入样例:18 输出样例:(10010)2
633

问题分析
? 将十进制正整数ten转换

成二进制数,只要
把ten不停地除以2求余数,每除一次,则 num:=num+1。若求得的余数为1,则将此时 的num存入集合中,最后按要求一起输出。

634

program p8_5(input,output); var ten, t, num, i: integer; two: set of 1..32; begin write(‘input an integer:’); readln(ten); t:=ten; two:=[]; num:=0;

635

while t <> 0 do begin num:=num+1; if t mod 2 = 1 then two:=two+[num]; t:=t div 2; end;

636

if ten=0 then writeln(ten,’=(0)2’) else begin write(ten,’=(‘); for i:=num downto 1 do if i in two then write(‘1’) else write(‘0’); writeln(‘)2’); end; readln; end.

637

? 输入样例:1000 输出样例:1000=(1111101000)2

638

问题
? 数组与集合有哪些区别?各自适用于哪些应
用问题? (可从两者的特点、支持的运算等方面来展 开讨论)

639

记录
? 记录的概念
? 记录类型的定义及记录变量的说明

640

记录的概念
? 数组可以用来组织成批的数据,但数组中的所有
元素都必须是同一类型的数据 ? 在现实生活和问题中,会遇到另外一种情况,即 一批数据是由性质各不相同的多种成份所组成的 ? 例如,要处理100名学生的档案信息,而每个学生

的档案数据包含以下几个数据项:

641

记录的概念
? 学号:string 年龄:integer 是否团员:boolean 电话号码:string 数学成绩:real 英语成绩:real 政治成绩:real 姓名:string 性别:char 家庭住址:string 语文成绩:real

642

记录的概念
? 在这样的数据中,每个成份是完全不同的数据类
型,很难用数组或其他数据结构来表示和存储 ? 这种数据可以用“记录”数据类型来表示 ? 记录是由一系列称为域(又叫成员、字段)的数据 成份所组成,其中每个域都可以有不同的类型

643

记录类型的定义及记录变量的说 明
type 类型标识符 = record 域名1:类型; 域名2:类型; << 域名n:类型; end;

644

type studata=record num : string[6]; name:string[10]; age : integer; sex : char; ty: : boolean; addr : string[30]; tel : string[11]; chinese: real; maths: real; english: real; politics: real; end;

645

关于记录类型定义的说明
? 在一个记录类型中,不能有相同的域名
? 在记录中,各个域的类型可以是简单类型,也可 以是数组等其他构造类型 ? 定义过记录类型后,即可以定义记录类型的变量 了

? 也可以将记录类型的定义与记录型变量的定义放
在一起,例如:
646

var d: record year: 1980..1999; month: 1..12; day: 1..31; end;

647

记录成员的引用
? 在使用记录时,需要注意以下两点:
1) 对记录的操作,除了可以进行整体赋值外, 只能对记录成员逐个引用; 2) 记录的每个成员只能参加其基类型所允许的 运算操作

648

? 假设有以下说明:
var a, b: student; 若记录a中每个成

员都已有确定的值,那么在程序 的执行部分就可以执行如下语句: b := a ; 它表示将记录a的每个成员的值赋给记录b中各同 名成员(这一点与数组类似)。
649

? 对记录成员的引用方式有两种:
– 直接引用:记录名.域名 – 开域引用:

? 对域变量的赋值可以通过read语句,也可以通过
赋值语句,如:

read(d.year, d.month, d.day);
d.year:=1980; d.month:=10; d.day:=25;
650

? 对于域类型又是数组的,引用形式具体为:
记录名.数组名[i] ? 例如,要读入一位学生四门课的成绩,可以写成 : for i = 1 to 4 do read(studata.s[i]);

651

? 在程序中对记录进行处理时,经常需要引
用同一记录中的不同域,如果每次都要用 “记录名.域名”的形式,非常麻烦。

652

? 为此,TP中专门提供了一条with语句,以
简化对记录的引用,称为“开域引用”, with语句又称为“开域语句” ? with语句的格式为: with 记录名 do 语句;

653

? 例如以下的程序段: write(‘input year:’); readln(d.year); write(‘input month:’); readln(d.month); write(‘input day:’); readln(d.day); 可以改写成:
654

with d do begin write(‘input year’); read(year); write(‘input month’); read(month); write(‘day’); read(day); end;
655

关于开域语句的几点说明
1. TP规定,在with<do后面的语句中,不能改变
已开域的记录。 假设有以下开域语句: with x do 语句 y; 在执行时,不允许语句y影响已开域的记录x,所 以,下面语句是不合法的:

656

with a[i] do
begin << i := i + 1; end; 这是因为,i:=i+1改变了a[i],所以造成不能正常 运行。
657

2. 关于记录的嵌套:在一个记录类型中,也
可以引用另一个记录类型,但记录的嵌套 层次是有限的。例如,下列记录说明是合 法的:

658

var x : record i: integer; y: record j: 0..5; k: real; end; m: real; end;
659

此时,若使用开域语句输入数据,可以写成: with x do with x, y do begin read(i,j,k,m); read(i); with y do read(j,k); read(m); end;
660

记录数组
? 所谓记录数组,是指一个数组中的元素类型(基类
型)又是一个记录类型,如: var students: array[1..100] of studata; ? 记录数组的引用形式为: 数组名[i].域名 ? 例如,第10位同学的年龄可以表示为: students[10].age
661

变体记录
? 在前面介绍的记录中,每个记录的域个数和类型
都是固定不变的。 ? 在实际问题中,仅有这样的数据类型是不够的。 例如,在学生档案中的登记中,对男同学要求只 登记身高,而对女同学则要求只登记体重,那么

这样的数据要想定义成记录该怎么办呢?
? 这时,要用到“变体记录”
662

变体记录
type stu=record score: array[1..6] of 0..100; age: integer; case sex: char of ‘m’: (weight: 70...15

0); ‘f’: (height: real); end;
663

综合应用
【例8-6】输入20位同学的数据记录(包括学 号、姓名、年龄、成绩五个域),按成绩从 高到低排序输出。
【参考程序】见教材P148

664

综合应用
【例8-8】应用记录数据类型,编写一个程序
完成复数的加、减、乘、除运算。

【例8-9】任给三条直线的方程,求它们所围

成的三角形的面积。

665

第九章 文



666

文件
? 在前面接触过的
program xx(input,output);

中的input和output就是Turbo Pascal的标
准文件,分别对应着计算机的标准输入设

备(键盘)和标准输出设备(显示器)。

667

文件
? 在TP中,这两个文件可以直接使用,甚至
可以省略不写 ? 这两个文件是与外设打交道的,因而将其 称为“外设文件”

668

文件
? 在程序设计中,常常需要通过键盘输入一些数据
,当数据量比较大时很麻烦,也很容易出错;同 时,在程序运行后也往往后产生大量的输出数据

? 能不能有一种方法,让程序自动地从某个地方读
取数据运行,再将程序的运行结果保存到指定的

地方呢?

669

文件
? TP中的“文件”类型即可满足这些要求。
? 此处的“文件”是指存储在外存(如磁盘)上

的、可由计算机识别的一系列数据成份组
成的整体,也就是平时所说的“文件” ? 在TP中,文件被定义为同一类型的元素组 成的顺序集合;
670

文件
? 文件所含元素的个数称为文件的长度。长
度为0的文件(即不含任何元素的文件)称为 空文件

671

文件与数组的比较
? 从定义上看,文件与数组很相似,但两者 是不同的:
– 数组的长度是固定的,而文件的长度不固定, 而且可以很长; – 数组可以通过下标对任一数组元素进行访问, 而文件一般必须从前往后逐个访问,直到找到 或找完为止; – 数组可以整体赋值,而文件却不可以。
672

文件的特点
? 顺序性 ? 永久性 ? 容量大

673

文件的特点
? 顺序性
– 文件是由同一类型的元素组成的,它们是按一 定的顺序排列和存放的。一般情况下,读取文 件中的数据或输出文件中的内容,都必须从文 件头到文件尾顺序访问。 – 在TP中定义的每个文件类型变量,都自动附带 一个文件指针,通过文件指针来指向文件中的 某个元素,并对该元素进行操作。

674

文件的特点
? 永久性
– 前面讲过的所有数据类型(数据、记录、集合等 )都是在程序运行期间在内存空间中临时开辟和 存储的,都不具备永久性 – 文件是存储在外存上的,可以永久地保存起来 。数据以文件形式存放后,还可以被其他程序 调用,成为共享数据。

675

文件的特点
? 容量大
– 由于内存容量有限,所以,我们在定义和

使用 数组等数据类型时,数据的存储容量往往受到 很大的限制; – 文件是存储在外存上的,因而容量可以很大

676

? 由于文件有上述特点,文件类型的变量就成为了
一种特殊的变量 ? 文件类型的变量可以在程序执行前存在,也可以 在程序执行后存在,而且它的值可以比程序本身 还大。

? 对文件的操作只能通过文件指针,对文件的元素
进行操作。
677

文件的分类
? 按不同的原则,可以将文件分成不同的种 类:
– 按文件的结构分:
? 文

文件是按行排列 的,行与行之间用行结束标记隔开,最后有一个

文件结束标记。
? 对这种文件而言,对字符的处理一般是以行为单

位进行读、写操作的。由于每行的长度不一样,
因而要采用顺序文件的处理办法
686

表示可以开始读取文件了 但是,不能向文件中写数据。



注意,文件名filevar同样必须存在,且文件中必须有
满足程序运行要求的输入数据

698

? read过程的调用格式如下:
read(filevar,var1,var2,<,varn);
–它的作用是从文件filevar中读取若干个数据,分别赋给 变量var1,var2,<,varn。当然,这里的变量类型必须和 文件中元素的类型一致 –每读取一个数据,文件指针就向下移动一个位臵

699

? readln过程的调用格式如下:
readln(filevar,var1,var2,<,varn);

它的作用是执行read过程,然后跳到文件的
下一行。

700

5. 对文件的输入、输出操作必须以行为单位进行
,读写完毕要用close命令关闭文件。 Close过程的作用是关闭一个文件,无论是向磁 盘写文件,还是人磁盘文件中读取数据,读、 写完毕后,都要用close关闭文件,以保证文件

的完整性和可靠性,否则将可能引起文件处理
错误。
701

close过程的调用格式如下:
close(filevar);

702

与文

放在text 类 型的文件file1中,再从此文件中读取所有数 据进行排序,把排好序的数存放在text类型 的文件file2中,最后把file2中的文件在显示 器上输出。

711

算法分析
1) 利用一个过程来产生随机数;每产生一个随机 数,就将其写入一个文件中; 2) 再利用一个过程,将该文件中的数据读出,每 读出一个数据,就放入一个数组中; 3) 再对该数组中的数据进行排序; 4) 利用一个过程/循环,将数据中的每个元素写入 到另一个文件中去; 5) 最后,再利用一个过程,将第二个文件中的数 据一一读出,并写到屏幕上去
712

第十章 指针

713

静态存储与动态存储
? 在Pascal程序中,变量必须先定义后使用
? 变量一经定义,在编译时系统就会为变量

分配内存空间。这种分配称为静态分配,
因为各变量对应的内存空间在程序运行之 前就已经确定了

714

静态存储与动态存储
? 在实际应用中,经常遇到事先无法确定有
多少数据要存储的情况,此时就不能采用 静态存储。为此,Pascal中引入了动态存储 分配机制,以满足应用程序的需求

715

静态存储与动态存储
? 所谓动态存储分配,是指事先不确定数据
存储,在程序运行的过程中,再根据实际 需要,动态地申请所需存储空间,用完后 再及时将空间归还给系统。 ? 内存被划分成一系列的单元,每个单元都 有一个编号,即单元的地址。
716

静态存储与动态存储
? 存储单元中存放的是具体的各种类型的数据,即
存储单元的内容。 ? 在计算机中,单元的地址其实也是一个整数,只 不过比较特殊,用来表示单元的地址而已。因此 ,地址也可以被看作是一种特殊的“内容”,存

储到另一个存储单元中去(与抽屉~钥匙/抽屉号码
的关系类比)
717

静态存储与动态存储
? 两者之间的关系见教材P169的图10-1、10-2
。在这两个图中,a中的数据是(指向)b的地 址,因而将其称为指针。 ? 相应地,存储了指针的变量称为指针变量( 如a),指针箭头所指向的变量(如b)存储的 数据类型称为指针变量的基类型
718

动态存储分配的特点
? 可以在程序运行时,根据需要随用随要
? 每次所申请的存储单元在内存中可以不连

续,它们通过指针建立起相互之间的联系
(How?)

719

指针变量的定义
? 为了表示指针变量和它所指向的变量之间
的联系,在Pascal语言中,使用了“^”符 号来表示指向。有两种说明这种指向关系 的方法

720

指针变量的定义
? 方法一:首先进行指针类型标识符的定义,其次
再进行指针变量的定义,如: type 指针类型标识符 = ^基类型标识符; var 指针变量名: 指针类型标识符; 例见教材P170 ? 注意,此

处的基类型可以是除文件类型以外的任 何类型。
721

指针变量的定义
? 方法二:直接在var区中定义,即:
var 指针变量名: ^基类型标识符;

? 因此,上例的说明也可以写为:
var p1, p2: ^integer;

722

指针与动态存储分配
? 指针是用来实现动态存储分配(how?),指
针变量的值是内存中某一个存储单元的地 址,该地址单元中的值类型是指针变量的 基类型,可以是除文件以外的所有其他类 型

723

指针与动态存储分配
? 动态存储分配是在程序运行过程中实现的
,因此,在运行前,指针变量中到底存储 哪一个地址并不确定,要到程序运行进, 进行过动态存储分配后动态赋值

724

指针变量的基本使用方法
? 动态存储申请:在程序运行时,根据需要,可以
在程序中向系统提出存储申请,由系统分配一个 存储单元,然后获得该单元的确切地址,并将其

写入到指针变量中
? 当不再需要某一存储单元时,就必须将该存储单

元空间归还给系统,称为释放

725

申请存储单元的过程
? 申请存储单元的过程:
new(指针变量); 例如:new(h); ? 说明:执行这一过程后,系统就会分配一个存放 数据的存储单元,并将该单元的地址赋给指针变 量h。存储单元的大小由h的基类型决定(如图10-3 所示)
726

? 又如: new(h); h^ := 123; new(h);

h^ := 234;
具体的实现过程见教材 P171 图10-4 ? 由上可知,对同一个指针变量,可以调用多次new过程,但每一次调 用后,指针变量h的值是不一样的,也就是说指向的是不同的内存单 元

727

释放存储单元的过程
? 释放存储单元的过程:
dispose(指针变量); 例如:dispose(h); 执行这条语句后,系统收回指针变量h所指向的 内存单元,此时指针变量h所指的内存单元的值 不可用,即指针h变成无确定指向。

728

指针变量的赋值和操作
? 利用new过程可以申请新的存储单元,真正实现
动态存储分配,并将一个地址值赋给某个指针变 量(p)

? 我们并不关心这个地址值,真正关心的是该指针
变量所指向的单元的内容(p^)

? 对p和p^都可以进行赋值,前者赋的是地址,后
者赋的是数据内容
729

指针变量的赋值和操作
? 假设p1和p2都是指针变量,其基类型为整
型,则: p1 := p2; 表示将变量p2的值(即某一存储单元的地地

址)赋给p1,这样p1和p2都同时指向原来由
p2所指向的单元(见教材P172图10-5)
730

指针变量的赋值和操作
? 语句
p1^:=p2^; 的意思是将变量p2所指向的单元中的值赋给p1所 指的单元,这样p1和p2所指向的单元虽然不同, 但两个单元中的数据内容变成一样的了,都是原

来p2所指向的单元中的值(见教材P172图10-6)

731

指针变量的赋值和操作
?

有时候,并不需要某一指针变量(如p1)指向
其他存储单元,这时,可以将NIL赋给该指 针变量,如 p1 := NIL; 表示使p1为空。任何类型的指针变量都可 以被赋值为NIL。
732

线性链表
? 线性链表的概念 ? 线性链表的建立 ? 线性链表的遍历与输出 ? 线性链表的查找 ? 线性链表结点的插入 ? 线性链表结点的删除

733

线性链表的概念
? 先看一看下面的说明: type pointer = ^node; node=record data : integer; next : pointer; end; var p, q: pointer;
734

线性链表的概念
? 在上述的定义中,指针变量有两个,p和q,其基
类型为node,node是一个自定义记录类型,有两 个域:
–一个域名为data,类型为整型;
–另一个域名为next,类型为pointer型,意思是可以存 放另一个node类型存储单元的地址。这里对类型的说 明使用了递归的方法。

735

线性链表的概念
? 假设在程序中出现: new(p); new(q); p^.data := 120; p^.next := q; 则效果如P173上图10-7所示。

736

线性链表的概念
? 通过上述方法,可以利用指针,将两个独
立的存储单元链接起来 ? 当将多个单元链接起来时,就形成了一个 “链”,链中的每一个单元都称为一个结 点

737

线性链表的概念
? 一般地,把若干个结点按照一定的顺序,通过其
指针域链接在一起所形成的链,称为线性链表, 其结构如P173图10-8所示。

? 其中第一个结点称为表头,最后一个称为表尾;
指向表头的指针称为头(head)指针,表尾结点的

指针域为空(NIL)

738

head
1462 1462 *** 1358 1358 *** 1645 1645 *** 2143 2143 *** NIL

739

线性链表的概念
? 图10-8中的链表是一种单(向)链表,其特点
是除第一个结点和最后一个结点外,每一 个结点都有一个直接前趋结点和一个直接 后继结点 ? 相邻结点的地址是互不连续的,它们靠指 针域互相连接起来
740

线性链表的概念
? 链表的主要作用是作为一种动态数据结构,链接
一系列的数据(思考:哪些应用场景中有这样的数 据结构需求?)

? 其主要操作有链表的建立、链表的遍历、对链表
中结点数据的访问、向链表中插入一个结点、从

链表中删除一个结点等,这些操作都是从指针域
入手的
741

线性链表的建立
? 一个线性链表的建立分为三个步骤:
1) 申请新结点; 2) 在结点的数据域填入相应的数据,在指针域 中填入NIL; 3) 将结点链接到表中的某一位臵处。

742

线性链表的建立
【例10-1 】输入一个正整数序列,遇到负数
时停止,并建立一个按输入顺序排列的线 性链表。

743

问题分析
? 就这个问题而言,所需的数据类型说明为 : type pointer = ^node; node = record data : integer; next : pointer; end;
744

变量说明
var p, q, head : p

ointer;
{p用于存放新申请的结点的地址,q用于存 放目前已建立链表的尾结点的地址} x : integer;

745

算法
1) 从空表开始,头指针置为NIL; 2) 读入一个数; 3) while 读入的数为正数 do begin
if 要填数据的结点为头结点 then begin 申请新结点;
746

填新结点的数据域,指针域置为NIL; 将头、尾指针设置成都指向新结点; end else begin 申请新结点; 将读入的数据送入新结点的数据域,指针域 置为NIL; 将新结点链接到已有的表的表尾; 尾指针后移一个结点,调整尾指针,使其指 向新的表尾(为连接下一个新结点做准备); end;
747

读下一个数; end; ? 参考程序片段如下:

748

head:=nil; read(x); while x >=0 do begin if head = nil then begin new(p); p^.data:=x; p^.next:=nil; q:=p; head:=p end; else begin new(p);p^.data:=x;p^.next:=nil; q^.next:=p;q:=p; end; read(x); end; {of while}
749

也可以这样做:
head:=nil; read(x); new(p); p^.data:=x; p^.next:=nil; head := p; q := p; read(x); while x >=0 do begin new(p); p^.data := x; p^.next := nil; q^.next := p; q := p; read(x); end; {of while}

750

线性链表的遍历与输出
? 一个线性链表的遍历与输出过程就是从表头结 点开始,按链接的顺序依次访问至表尾的过程 ,可如下表示:
1) 设临时工作变量指针p指向链表的头结点(头结点的地 址不能丢失和改变,否则会丢失整个链表); 2) While p<>NIL do begin 输出p所指向的结点(当前结点)的数据值; p移向后一个结点; end;
751

参考程序片段
p:=head; while p <> nil do begin write(p^.data:8); p:=p^.next; end;

752

线性链表的查找
? 所谓线性链表的查找,是指在表中找出符合条 件的结点,过程如下:
1) 设指针变量p(临时工作变量)指向链表的头结点; 2) while (未找到) and (未到表尾) do if 找到 then 退出循环 else p移向下一个结点; 3) if 到了表尾 then 输出?未找到? else (找到)对p所指结点进行相应的处理。

753

? 为了能表示出是否找到了所需的结点,在
程序段中用到了一个布尔型的变量found, 若找到了,found的值就置为true,否则, 就置为false。

754

参考程序片段
write(‘输入要查找的数据’); readln(x); p:=head; found:=false; while (p<>nil) and not(found) do if x=p^.data then found:=true else p:=p^.next; if found then < else writeln(‘not found’);
755

线性链表结点的插入
? 由于线性链表结点的物理地址的非连续性,对于
结点的插入,事实上就是改变线性链表中某结点 的后继指针的值。

? 根据插入位置的不同,我们分三种不同的情况进
行分析:表头插入、表中插入和表尾插入。

? 参见P177图10-10和图10-11

756

表头插入
1) 2) 3) 4) 申请一个新结点newpoint; 将输入的数据赋给newpoint的数据域; 将head的值赋给newpoint

的指针域; 将newpoint结点的地址赋给head

757

参考程序片段
new(newpoint); readln(x); newpoint^.data:=x; newpoint^.next:=head; head:=newpoint;

这两条语句的顺 序能颠倒吗?

758

表中插入
1) 申请一个新结点newpoint;
2) 将数据赋给newpoint的数据域; 3) 将新结点newpoint的指针域赋值为插入点之前 的一个结点(用p表示)的指针域; 4) 将newpoint的地址赋给插入点之前结点(用p表 示)的指针域。

759

参考程序片段
new(newpoint); readln(x); newpoint^.data:=x; newpoint^.next:=p^.next; p^.next:=newpoint;

760

表尾插入
1) 申请一个新结点newpoint;
2) 将数值赋给newpoint的数据域,将NIL赋

给newpoint的指针域;
3) 将newpoint的地址赋给已原链表尾结点(

用q表示)的指针域。

761

参考程序片段
new(newpoint); readln(x); newpoint^.data:=x; newpoint^.next:=nil; q^.next:=newpoint;

762

【例10-2】输入一个正整数序列,遇负数时 停止,并按输入顺序反向输出。

763

问题分析
? 由于对线性链表进行数据访问时,只能从
表头结点开始,根据问题要求可知,在线 性链表建立时,必须采用插入到表头的方 法进行建立。 ? 解决本问题所用到的数据结构与上例中的 相同。
764

算法描述
1) 将表头指针置为NIL; 2) 输入一个数; 3) While 读入的数为正整数 do begin 申请一个新结点; 将读入的数送入新结点的数据域; 将原表头指针赋给新结点的指针域; 将新结点的地址赋给表头指针; 读入下一个值; end; 4) 顺序输出各结点的数据值。

765

参考程序(见教材PP178-179)
program p10_1; type pointer = ^node; node = record data : integer; next : pointer; end; var p, head : pointer; x : integer;
766

begin head := nil; readln(x); while x >= 0 do begin new(p); p^.data := x; p^.next :=head; head :=p; readln(x) end;
767

p := head; while p <> nil do begin write(p^.data : 8); p := p^.next; end; writeln; end.
768

线性链表结点的删除
? 线性链表结点的删除包括以下几步:
1) 把要删除的结点地址赋给一个临时变量; 2) 把要删除的结点的指针域赋给要删除的结点的前一结 点的指针域; 3) 将要删除的结点删除,释放存储单元。

?

在利用程序来删除结点时,需要用到两个指针 变量:变量q表示要删除的结点的前一结点的地 址,变量p表示要删除的结点的地址。

769

? P179图10-13、10-14、10-15、10-16示出了 删除表头、表中和表尾结点的不同情况

770

删除表头结点的参考程序片段
p := head; ‘这句话能否不要? head := head^.next; dispose(p);

771

删除表中结点的参考程序片段
q^.next := p^.next; dispose(p);

772

删除表尾结点的参考程序片段
q^.next := p^.next; dispose(p); 或者,也可以: q^.next := NIL; dispose(p);

773

? 通过以上的说明可以看出,链表上所有操

作的关键在于如何改变结点指针域的值 ? 掌握线性链表的访问基本方法是,从头结 点开始,沿线性链表方向进行操作。

774

? 在这一过程中,一般会用到两个指针型变
量:一个用于指向刚查过的结点地址,另 一个用于指向下一个待查的结点地址。 ? 结束访问的条件有两个:一个是结点地址 为NIL,另一个是找到了相应的结点。

775

? 最容易出现的错误是,当p为NIL时取
p^.data,因为当p为NIL时,p^.data的值 是无定义的。

776

线性链表的应用
? 求线性链表的长度
? 线性链表的排序

? 线性链表的归并算法
? 循环链表

777

求线性链表长度的运算
? 所谓线性链表的长度,是指从表头结点到
表尾结点之间的结点个数,也就是从表头 结点开始,沿链表方向顺序访问各结点时 ,统计被访问的结点的个数。

778

【例10-3】编写一段程序,统计某个整数链
表(以head为头指针)中整数的个数。

779

问题分析
? 从表头结点开始,沿链表的方向查找,每
找到一个结点,就进行计数统计,直到结 点地址为空(NIL)时为止。

780

参考程序片段
p:=head; n:=0; while p <> nil do begin n:=n+1; p:=p^.next; end; writeln(‘length=‘, n);
781

线性链表的排序
【例10-4】 用插入排序法建立一个升序链表


782

问题分析
? 为了建立一个有序链表,可以将读入的第一个数
作为表头结点,对后面读入的数使用插入的方法 ,找到合适的地方进行插入操作。

? 由于插入一个结点的过程是按数据域的大小顺序
进行插入的,因此,得到的链表就是有序链表。

783

算法描述
1) 将头指针置为NIL; 2) 读入一个数; 3) while 读入的数>=0 do begin 申请一个新结点; 将读入的数赋给新结点的数据域,将 NIL 赋 给新结点的指针域; {沿链表方向找到要插入结点的位臵}

784

将p设为表头指针;g为NIL {g是p指针所指结点的前一个结点} while (读入的数 > 结点数据域) and (p <> NIL) do begin g设置为p; p指针沿链表方向后移一个结点 end; if g = NIL then {第一个结点} begin
785

头指针置为新结点; g置为新结点 end else if p = NIL then {到了表尾} 在表尾插入新结点 else if 插入点在表头 then 在表头插入 else 在表中插入 读入下一个数 end;
786

4) 顺序输出结点的数据域。
? 参考程序见教材

787

问题:
? 写成如下形式行不行? new(q); q^.data := x; q^.next:=nil; while (p^.data<x) and (p<>nil) do p := p^.next; q^.next := p^.next;

788

?
?

不行,因为当找到应插入x的位置时,p指针跑 到x的后面去了 改进:
1. 用两个指针g、p一前一后跟着; 2. 判断条件改为: while p^.next^.data<x do 这样即可 1. 先不做new操作, 而是用两个指针q、p一前一后跟 着,找到合

适位置后,再做new(p),再插入数据x ( 想一想,这样为何是可行的?)
789

线性链表的归并算法
? 线性链表的归并主要用于归并排序,是指
将两个或两个以上的有序线性表合并成一 个新的有序线性表。下面来看一个个例子 。

790

【例 10-5 】 将以下两个有序线性表进行归并 : 线性表(1)是:{34,56,68,79,90,100} 线性表(2)是:{12,25,48,74,85} 归并后的线性表为:{12,25,34,48,56, 68,74,79,85,90,100}

791

问题分析
? 线性表中的结点是按数据域由小到大排序的,
? 根据两个线性表中结点数据域的大小进行归并运 算是这样的:
–哪个表中的数据小就归并哪一个;
–当两个线性表中有一个已归并完毕时,另一个线性表 的剩余部分全部复制到所建立的新的线性表中。

–如果在处理时出现同样值的话,两个表中的数据选取 顺序任意。

792

算法描述
1) 建立线性表1,以输入-1作为建立链表的结束; 2) 建立线性表2,以输入-1作为建立链表的结束; 3) {一边进行比较,一边建立线性表3} while (链表1未到尾) and (链表2未到尾) do begin if 链表1表头结束的数据小于链表2表头结点 的数据 then begin 链表3申请一个新结点; 将链表1中当前结点的数据域值复制到链表3 的新结点的数据域中; 793

将链表3新结点的指针域置为NIL; 链表3新结点从尾部插入链表3; 链表1指针前移一个结点; {为下一个结点 做准备} 链表3尾指针调整为指向新结点 end else begin
794

链表3申请一个新结点; 将链表2的当前结点数据域复制到链表3 新结点的数 据域中; 链表3新结点指针域置为NIL; 链表3新结点从尾部插入链表3; 链表2指针前移一个结点;{为下一个结点做准备} 链表3尾指针调整为新结点 end end;
795

4) if 链表1找完而链表2未找完 then 链表 2 中的剩余结点数据域的值全部复 制到链表3中; if 链表1未找完而链表2已找完 then 将链表1中的剩余结点的数据域的值全 部复制到链表3中; 5) 输出链表3。
796

? 参考程序见教材PP184-186。
? 当然,按以上的算法进行编程虽然比较容易理解 ,但这并不是最好的算法,因为在构建链表3时申 请了新结点。 ? 如果表1有n1个结点,表2有n2个结点,表3就申请

了n1+n2个结点,这样就有2*(n1+n2)个内存单元
被占用了。
797

? 只要想一想,我们就可以发现,如果将链
表1作为链表3的原型,使用插入结点的方 法,将链表2的结点插入到链表1中,就可 以实现对算法的优化,不仅可以节约存储 空间,还可以缩减程序的规模。具体实现 可以让请大家自己思考。
798

? 在平时的编程中,对线性表的归并操作,
不一定非得用到指针结构不可,可以利用 数

组来实现,其中数组的下标相当于某结 点的“地址”,数组元素的值表示的是结 点的值。

799

循环链表
【例10-6】 循环链表的应用:有n只猴子,按 顺时针方向围成一圈选大王。具体方法是 从1号猴子开始报数1,2,<,数到m号时 ,该猴子退出到圈外,再如此报数,直到 圈内只剩下一只猴子时,此猴子便是大王 。由键盘输入n、m,打印出走出圈外的猴 子序号。

800

问题分析
? 因为这n只猴子是围成一圈的,故对于第n只猴子
来说,它的后一只猴子应该是第1只猴子,这就形 成了一个环。

? 如果将猴子的编号作为结点中的数据域,将指向
的下一只猴子的地址作为结点中的指针域,就可

以形成一个循环链表。

801

算法分析
1) 建立初始化循环链表;
2) 从某个结点开始数数,每当数到是m的整数倍时 ,删除该结点,并输出猴子的编号; 3) 重复(2)的过程,直到只有一只猴子时为止。 ? 参考程序见教材

802

二叉树
? 二叉树是计算机中常用的另外一种动态数据结构(
如下图所示),每个结点最多有两个后继结点,一 左一右,分别称为左子女和右子女。

? 因此,二叉树的结点类型应该是一种包括三个域
的记录类型:一个数据域,两个指针域,分别称

为左指针和右指针,用它们指向左子女结点和右
子女结点。
803

二叉树的结点类型说明
type tree = ^node; node = record data : integer; lchild, rchild : tree; end; var bt: tree; {指向树根的指针}
804

a

b

c

d h

e

f

g

805

? 以上给出的是二叉树(指向子女的)链接
存储方式,它有一种变形,即在结点中再 增加一个parent指针域,它指向结点的父结 点。这种存储结构既便于查找子女结点, 也便于查找父结点。

806

? 在二叉树中插入或者删除结点要复杂一些
,但基本方法和线性链表中是相似的。事 实上,二叉树是由多个线性链表合成的, 在上图中,可以找出如下几个线性链表:

807

? a→b→d、a→b→d→h、a→b→e、a→c→f、
a→c→g ? 所以,在二叉树中插入或者删除结点,本质上仍 然是线性链表中结点的插入或者删除,只是看待 问题的角度不同。例如,对于以链表形式存储的

二叉树,其插入结点的基本算法如下:

808

procedure insert(var bt: tree; n: integer); begin if bt = nil then {空树,插入的结点即成为根结 点} begin new(bt); bt^.data := n; bt^.lchild:=nil; bt^.rchild:=nil; end else if n<bt^.data then insert(bt^.lchild, n) {<, 左} else if n>bt^.data then insert(bt^.rchild, n); {>, 右} 809 end;

有关指针的深入应用
【例】编程输入一组不同的整数(约定这些
数都必须大于等于0,当输入负数时表示结 束),用二叉排序树排序后,按从小到大 的顺序

输出。

810

问题分析
? 二叉排序树具有这样的性质,即任何结点的值都
大于它左子树中结点的值,小于右子树中结点的 值。

? 采用二叉排序树对一组输入数据进行排序后,再
对树做中序遍历,即可生成输入数的一个按从小

到大顺序输出的有序序列了。

811

问题分析
? 对于本题而言,可以首先生成一个结点(用于存
放下一个待排序的数据),再根据数据的大小, 决定这个结点是应当插在当前结点的左子树中,

还是应当插在右子树中。如此重复处理,直到输
入一个负数时为止。

? 参考程序见附件

812

一些标准函数与过程(略)

813

第十二章 常用算法初步

814

? 递推、递归算法 ? 穷举算法 ? 回溯算法

815

12.6 递推与递归算法深入
? 递推程序设计
– 根据题意(根据数学知识),找出递推式,从已知条件出 发,逐步推出解来 – 分为顺推和逆推两种

– 另外,在解题时,往往把递推问题表现为迭代形式, 用循环来处理(Why?)
– 所谓迭代,是指在程序中用同一个变量来存放每一次 推算出来的值,每一次循环都执行同一个语句,给同 一个变量赋以新的值,即用一个新值来代替旧值,这 种方法称为迭代
816

【例12-20】 有2×n的一个长方形方格,用一个1×2的骨牌 铺满方格。例如,当n=3时,为2×3方格。此时用 一个1×2的骨牌铺满方格,共有3种铺法(图见 P245)。 请编写一个程序,试对给出的任意一个n(n>0) ,输出铺法总数。 【问题分析】 能否想到?推公式?(即递推)? 如何推出递推式?
817

? ? ? ?

N=1时,f=1 N=2时,f=2 N=3时,f=3 N=4时:
– 若最后一格是竖着放的,则左边的三个原来已知,为 f=3; – 若最后两格是横着放的,则左边的两个原来已知,为 f=2。

? N=5时,依此类推。 ? 因此,可知递推式为Fn=Fn-1+Fn-2
818

program p12_20; var x, y, z: longint; i, n: integer; Begin write(‘Input n:’); read(n); x:=0; y:=1;
819

for i:=1 to n do begin z:=y+x; write(‘x*’,i:2,’+=’,z); x:=y; y:=z; end; end.
820

? 例12-21 用迭代方法求 的值。X由 3 y ? x 键盘输入。利用下列迭代公式计算:
2 x ? yn ? 2 3 3 yn

yn ?1

初始值为y0=x,误差要求

? ? 10?4
821

问题分析
? 本题的主要任务在于迭代,而不主要在于递推 ? 迭代法即反复代入法 ? 在上式中,将yn代入公式的右端,可以计算出yn+1 ,然后,将yn+1作为新的yn代入右端,又将计算出 新的yn+1 ? 如此重复,直到 | yn+1 - yn | <ε时为止 ? 初始值y0=x意味着第一次迭代中代入公式右端的 yn取值为x
822

program p12_21; const e=0.0001; var x, y0, y1, y2: real; begin write(‘input x:’); read(x); writeln; y1:=x; y2:=x; repeat y1:=y2; y2:=2/3*y1+x/(3*y1*y1); unti

l abs(y2-y1) < e; writeln(y2); end.

823

递归算法的深入与递归转化为非 递归
【例12-22】给定n (n≥1),用递归的方法计 算1+2+3+4+<+(n-1)+n。

824

问题分析
? 本题可以用递归方法求解,原因是它符合 递归的三个条件:
1) 本题是累加问题: 当前和 = 前一次和 + 当前项 而前一次和的计算方法与其相同,只是数据 不同(或问题/数据的规模缩小了)而已: s(n)=s(n-1)+n 2) 给定n,所以是有限次的递归调用; 3) 结束条件是当n=1时,s=1。
825

program p12_22; var s, t: integer; function fac(n: integer): integer; begin if n=1 then fac:=1 else fac:=fac(n-1)+n; end; begin read(t); s:=fac(t); writeln(‘s=‘, s); end.
826

? 本程序的递归调用过程见P248图示;
? 递归调用过程的实质就是不断地调用子过程或子 函数的过程。 ? 每递归调用一次,所有子程序的变量(局部变量、 变参等)、地址在计算机内部都会用特殊的管理方

法——栈(先进后出)来管理

827

? 一旦递归调用结束,计算机便开始根据栈
中存储的地址返回各子程序变量的值,并 进行相应操作。

828

【例12-23】设有n个数已经按从大到小顺序
排列,现在从键盘上输入x,判断它是否在 这n个数中。如果存在,则输出?yes?,否 则输出“no?。

829

问题分析
? 该问题属于数据的查找问题
? 数据查找有多种方法,通常的方法是:顺

序查找和折半查找
? 当n个数已排好序时,用折半查找方法其速

度大大加快

830

折半查找算法
1. 设有n个数存放在a数组中,待查找数为x,用f
指向数据的高端,r指向低端,mid指向中间 2. 若x=a[mid],则输出“yes?; 3. 若x<a[mid],则到数据后半段查找:r不变, f=mid+1,计算新的mid值,并进行新的一段查

找;

831

折半查找算法
4. 若x>a[mid],则到数组前半段查找:f不变
,r=mid-1,计算新的mid值,并进行新的 一段查找。 若f>r都没有查找,则输出“no?.

832

? 该算法符合递归程序设计的基本特点,因
而可以采用递归方法来编程实现。 ? 源程序见教材P249

833

【例12-24】Hanoi(河内/汉诺)塔问题
有n个圆盘,依半径大小(半径都不相同),自 下而上套在A柱上,每次只允许移动最上面一个盘 子到另外的柱子上去(除A柱外,还有B柱和C柱, 开始时,这两个柱子上无盘子),但绝不允许发生 柱子上出现大盘子在上,小盘子在下的情况,现 要求设计将A住柱子上n个盘子搬移到C柱子上的方 法。
834

问题分析
? 经简单推理可知,移动盘子的一般规律为 :
1) 先将n-1个盘子从A柱称到B柱上,C柱为中 间柱; 2) 将第n个盘子从A柱移到C柱上; 3) 再将n-1个盘子从B柱移到C柱上,A柱为中 间柱。
835

program hanoi_tower; var n: integer; procedure hanoi(n:intege

r; x, y, z:char); begin if n=1 then writeln(x,’->’,n,’->’,z) else begin hanoi(n-1, x, z, y); writeln(x,’->’,n,’->’,z); hanoi(n-1, y,x, z); end; end;

836

begin {main program} write(‘input n:’); read(n); hanoi(n,’a’,’b’,’c’) end.

837

【例12-25】用递归的方法求费波那契数列中
的第n个数:
?0 ? f n ? ?1 ?f ? n ?1 ? f n ? 2 n=0 n=1 n>1
838

program p12_25; var m, p: integer; function fib(n:integer):integer; begin if n=0 then fib:=0 else if n=1 then fib:=1 else fib:=fib(n-1)+fib(n-2); end;
839

begin {main program} readln(m); p:=fib(m); writeln(‘fib(’,m,’)=’,p) end.

840

【例12-26】用递推方法求费波那契数列中的
第n个数。

841

program p12_26; var n, m: integer; f: aray[0..20] of integer; begin f[0]:=0; f[1]:=1; readln(n); for m:=2 to n do f[m]:=f[m-1]+f[m-2]; writeln(‘f*’,n,’+=’,f*n+) end.
842

穷举法
? 是一种基于计算机的特点而进行解题的思 维方法 ? 一般是在一时找不出更好的解题途径(如从 数学上找不到求解的公式或规则)时,可以 根据问题中的部分条件(约束条件),将所有 可能解的情况列举出来,然后再一一验证 是否符合整个问题的求解要求,从而得到 问题的解。
843

穷举法
? 穷举算法的特点是算法简单,但运行时所
花费的时间量大。 ? 有些问题所列举出来的情况数目会大得惊 人。 ? 因此,应尽可能将明显不符合条件的情况 排除在外,以尽快取得问题的解
844

穷举算法的模式
1) 确定问题解的可能搜索的范围:用循环或
循环嵌套结构实现; 2) 写出符合问题解的条件; 3) 能使程序优化的语句,以便缩小搜索范围

,减少程序的运行时间。

845

用穷举法解题的例子
【例】九头鸟(传说中的一种怪鸟,它有九个
头、两只脚)、鸡和兔子关在一个笼子里。 数数它们的头正好是100,数数它们的脚数 也正好是100。请编程计算其中九头鸟、鸡 和兔子各有多少只?

846

问题及方法分析
? 基本题意与已知条件: 设九头鸟有M只,鸡有N只,兔子有L只,则 有: 9M +N+L=100 (1) 2M+2N+4L=100 (2) 题目的要求就是要找出符合条件的M、N和L 。该如何入手来解决这个问题呢?
847

方法1
? 由于M、N和L的变化范围都是1~100,因此,可
以采用穷举法的思想与做法,让M、N和L分别从 1变化到N(利用多重循环来实现),看看它们的每

一组取值是否能满足上面两个等式的要求。
? 如果满足要求,则将M、N、L的值打印出来;否

则,继续搜索。

848

program jiutouniao; var m, n, l, t: integer; begin t: = 0; ‘记录共有多少组满足条件的数据 for m:=1 to 100 do ‘体现穷举的做法 for n:= 1 to 100 do for l:= 1 to 100 do if (9*m+n+l=100) and (2*m+2*n+4*l=100) then begin write(m,n,l); t=t+1; end; write(‘总共有:’,t,

’种情况‘ ) end.
849

方法2
? 仍然采用穷举法,只是先做一些预先的分析,从
而可以达到一定的优化效果。由题意可知:
– 如果100个头都是九头鸟的话,那九头鸟最多有

INT(100/9)=11只;
– 如果100只脚都是鸡的话,则最多有50只鸡 – 同理,兔子最多有25只

850

program jiutouniao; var m, n, l, t: integer; begin t: = 0; for m:=1 to 11 do for n:= 1 to 50 do for l:= 1 to 25 do if (9*m+n+l=100) and (2*m+2*n+4*l=100) then begin write(m,n,l); t=t+1; end; write(t ) end.
851

? 在上面的方法2里,采用的是缩短循环变量
的初值和终值的方法,来减少循环次数, 以减少程序的运行时间。 ? 那么,能不能对方法2做进一步的优化呢?

852

方法3
? 由方法2可知,鸡的循环变量范围最大,最值
得进一步优化/缩小。 ? 根据等式(1),将N和M和L来表示,得: N=100-9M-L (3) 这样一来,就又可以做进一步的优化了:将原 来的三重循环降低到了两重循环(减少了一个循 环变量)。
853

方法3
? 但是,(3)式根据M和L计算出来的N值可能
会出现负数,这是不允许的。 ? 所以,在循环体中判断(2)式是否成立时, 还要加上N>0这一条件。

854

program jiutouniao; var m, n, l, t: integer; begin t: = 0; for m:=1 to 11 do for l:= 1 to 25 do begin N:=100-9*M-L if N>0 AND 2*M+2*N+4*L=100 then begin write(m,n,l); t=t+1; end; write(t ) end.
855

方法4:进一步的优化
? 将式(1)×2再减去(2),这样就消去N得: 16M – 2L = 100 整理上式可得: L = 8M – 50 (4) 这样就将两重循环又进一步简化成了一重 循环。

856

方法4:进一步的优化
? 但是,(4)式由M计算出来的L也可能会出现负数
,这是不允许的,故在循环体中的语句是: IF L>0 AND N>0 THEN PRINT M,N,L:T=T+1 ? 表达式(4)应写在表达式(3)的前面,即必须先求出 L,才能求N。

857

program jiutouniao; var m, n, l, t: integer; begin t: = 0; for m:=1 to 11 do begin L = 8*M –50 N:=100-9*M-L IF L>0 AND N>0 then begin write(m,n,l); t=t+1; end; write(t ) end.
858

? 上面的四种方法都能给出正确的结果,但
所需循环次数分别是100*100*100、 11*50*25、11*25、11次,通过一系列优化 措施,以及将不必要的循环去掉,从而将 程序的效率不断地提高

859

提高穷举法效率的方法
1. 步长值不变的情况下,减少循环变量的初 值和终值的差距;
2. 在初值、终值不变的情况下,增大步长值 ; 3. 减少循环嵌套的层数。 具体使用时,应根据题目的条件,灵活运 用。
860

【例】一个正整数,当分别被5、7、9除,余
数分别为1、2、3,求满足此条件的最小 数。

861

问题分析
1. 设要求的这个正整数为X。由题意可知: X MOD 5 = 1 X MOD 7 = 2 X MOD 9 = 3 2. 由于不知道整数的范围,可以让X从1开始 搜索,直到满足以上

三个条件时为止。

862

var x: integer; begin x := 1 repeat x := x + 1; loop until (x mod 5=1) and (x mod 7=2) and (x mod 9=3); write(x); end.
863

? 在5、7、9这三个数中,9最大,而且X
MOD 9=3,所以,X至少是3,符合X MOD 9=3的下一个数是X+9 ? 这样,可以通过增加步长来减少循环次数 。

864

var x: integer; begin x := 3 repeat x := x + 9; until (x mod 5=1) and (x mod 7=2); write(x); end.
865

【例】已知:N,M为非负整数,现有
X=2^N*3^M,试编程找出第K个小的 2^N*3^M。

866

问题分析
? 根据题意,可以先列出前几个数:
K=1,N=0,M=0: 2^N*3^M=1 K=2,N=1,M=0: 2^N*3^M=2 K=3,N=0,M=1: 2^N*3^M=3 K=4,N=1,M=1: 2^N*3^M=6 <<

867

问题分析
? 那么,第K个符合条件(N、M为非负整数)
的数X是多少呢?可以用穷举法来实现 ? 如何穷举?如何才能保证得出的数是第K小 的?

868

问题分析
? 具体思想是这样的:
– 从1开始取一个数,让这个数不断地加1,并且看此数是否 正好能分解成?2^N*3^M?的形式,若不是,则看下一

个数;若是,则记录下来,再取下一个数考察,一直
处理到第k个数为止。 – 分别用三个数组A[]、B[]和C[]来存放符合条件的数, 以及此时的N、M值;

869

var a: array[1..100] of integer; b: array[1..100] of integer; c: array[1..100] of integer; k: integer; begin i:=0; x:=0; while i < k do begin x :=x+1; y:=x; n:=0; m:=0;
870

repeat if y / 2=y div 2 then begin y:=y div 2; n:=n+1; end; until y / 2 <> y div 2; repeat if y / 3 = y div 3 then begin y:=y div 3; m:=m+1; end; until y div 3 <> y / 3;

871

if y = 1 then begin i:=i+1; a[x]:=x; b[i]:=n; c[i]:=m; end; end;
872

for i:=1 to k write(‘k=‘,i,’2^’,b*i+,’*3^’,c*i+,’=‘,a*i+); end.

873

另一种解法
? 也可以采用比较直观、朴素的穷举思路,
即对N、M进行穷举(分别从1变到K),再将 得到的(至多)K2个数进行排序,取前K个即 可 ? 应如何评价这种方法?可以进一步优化吗?值 得我们进一步推广吗?
874

? 【例】给出一个自然数N(1≤N ≤ 15,且N为奇数 ),要求找出N个连续正整数,使得前(N+1)/2个正 整数的平方和等于后(N-1)/2个正整数的平方和。 规定:连续的正整数中最小的数不大于100。( 思考:为什么要做这一规定?) 例如:当N=5时,满足条件的5个正整数为 10,11,12,13,14,且: 102+112+122=132+142

875

问题分析
? 对本题该如何下手?如何套用“穷举法”解题的
几个套路步骤?有哪些东西是可以穷举的(N的取值 、第一个数的取值等)

? 在没有任何思路时,可以先手工具体地走一走这
个问题,手工列举出一些具体的数据,把问题具

体地搞清楚了,思路也就相对比较容易出来了

876

问题分析
? 例如,可以对N的取值、(当N取定后)N个连续整
数的可能取值情况(这N个

数最小可能从几开始取 起?最大可能取到几?等等),都具体地列举一下,

观察一下其中的特点和规律 (这一过程非常重要,
是最终理解问题、找出问题的本质和规律、得出

解题思路、将问题与我们所学过的算法相结合的
一个重要阶段)
877

问题分析
? 就本题而言,有无什么规律可循?或者,还
是只能一一列举? ? 首先分析题目,尽可能找出已知条件:根 据题意,N的取值只可能是 1,3,5,7,9,11,13,15这8个奇数,下面分别对它 们加以讨论:
878

问题分析
? 当N=1时,因为(1+1)/2=1,(1-1)/2=0,一个正整数
的平方和不可能为0,所以N=1不符合; ? 当N=3时,因为(3+1)/2=2,(3-1)/2=1,即讨论前面两 个连续正整数,以及后面一个正整数的平方和的 问题;连续的3个正整数可能是1、2、3,或2、3

、4,或3、4、5(满足条件),或4、5、6<<

879

问题分析
? 当N=5时,连续的5个正整数可能是12345,23456 ,<,10、11、12、13、14(满足条件)<<,用 类似的方法可知答案只有一个 ? 由上述分析可知,只要根据问题中的条件,将可
能的解列举出来,进行一一验证是否符合问题的 求解要求即可(至此,与穷举法挂上了钩) ? 思考:应如何进行穷举呢?当确定了N的某个取值 后,这N个数的取值范围是怎样的?
880

问题分析
? 当N为某一值时,可能有一个答案,也可能
不存在符合条件的值

881

问题分析
? 变量说明: N:输入的自然数 A:数组,用于存放符合条件的N个整数,如果 N=1,则输出“无解”,结束; X:累加器,用于存放前(N+1)/2个数的平方和 Y:累加器,用于存放后(N-1)/2个数的平方和 C:累加器,用于从1开始递增枚举 I:循环变量
882

算法
S(0):先判断是否满足条件“N为奇数,且
1≤N ≤ 15?; S(1):符合条件后,建立一个有N个元素的数 组A(N),其中各元素的初值均为0; S(2):将C清0;{C表示这连续N个数的第一个 数,从1开始考虑}
883

算法
S(3):将连续的N个整数按序放到A数组中;{
这N个数为C,C+1,<,C+N-1} S(4):求前(N+1)/2个数组元素的平方和,放 入X中; S(5):求后(N-1)/2个数组元素的平方和,放 入Y中;
884

算法
S(6):如果X=Y则找到解,输出结果并结束;
S(7):若没有找到解,则将X、Y清0,将穷举变量C 增加1; S(8):将A数组中各元素的值皆增加1; S(9):如果C=100,则结束循环; S(10):结束。

885

var a: array[1..15] of integer; n, c, i, x, y: integer; begin repeat write(‘请输入奇数n(1-15):’); readln(n); until (n>=1) and (n<=15) and (n mod 2=1); if n = 1 then begin write(‘无解’); halt end; c := 0;
886

repeat for i:=1 to n do a[i]:=a[i]+i; for i:=1 to (n+1)/2 do x := x +a[i]*a[i]; for i:=(n+1)/2+1 to n do y:=y+a[i]*a[i];

887

if x = y then begin for i:=1 to n d

o write(a[i]); writeln; exit {找到符合条件的数后,结束穷举} end; x:=0; y:=0; c:=c+1; for i:=1 to n do a[i]:=c; until c=100; end.
888

【例】警察局抓了A,B,C,D四名偷窃嫌 疑犯,其中有一个是小偷。审问中:
A说:“我不是小偷。” B说:“C是小偷。” C说:“小偷肯定是D。? D说:“C在冤枉人。” 现在已经知道四个人中有三个人说的是真话,一 人说的是假话,问到底谁是小偷。
889

问题分析
? 这个题目是逻辑推理题,常用的方法是用
穷举法,把各种可能的组合都列举出来, 然后根据题目的条件,排除不合乎要求的 组合或选择需要的组合。

890

方法一
? 用A,B,C,D四个变量存放A,B,C,D 四个人是不是小偷的信息:0表示这个变量 代表的人不是小偷;1表示是小偷。例如, A=0说明A不是小偷。 ? 以A,B,C,D四个变量作为循环变量构造 四重循环,每重循环都从0到1,这样就可 以把谁是小偷的各种情况都列举出来。

891

? 题目给出的其他条件用有关的表达式可以 表示为: 四个人中有一名小偷:A+B+C+D=1 A说的话:A<>1 B说的话:C=1 C说的话:D=1 D说的话:D<>1
892

? 四句话中只有三句真话:A,B,C,D四句 话的逻辑值加起来等于-3。即: (A<>1)+(C=1)+(D=1)+(D<>1)=-3

893

for a: = 0 to 1 do for b := 0 to 1 do for c := 0 to 1 do for d: = 0 to 1 do if (a+b+c+d=1) and (ord(a<>1)+ord(c=1)+ord(d=1)+ord(d<>1)=3 ) then begin if a = 1 then write(‘a是小偷’); if b = 1 then write(‘b是小偷’); if c = 1 then write(‘c是小偷’); if d = 1 then write(‘d是小偷’) end;
894

方法二
? 把A,B,C,D四个人进行编号,号码分别为1, 2,3,4 ? 用变量x存放小偷的编号。x的值从1取到4,这样 就假设了他们中的某人是小偷的所有情况 ? 四个人所说的话就可以分别写成:
– – – – A说的话:x<>1 B说的话:x=3 C说的话:x=4 D说的话:x<>4或not(x=4)

895

? x的值使这四个逻辑式的值相加等于-3时, 它就是小偷的编号了。

896

for x := 1 to 4 do if ord(x<>1)+ord(x=3)+ord(x=4)+ord(x<>4)=3 then write(chr (64+x),’是小偷‘);

897

? 在利用穷举法解题时,应尽可能将明显不
可能的情况排除在外,以减少穷举可能解 的个数。

898

? 【例12-1】古希腊人认为因子的和等于它本 身的数是一个完全数(自身因子除外),例 如28=1+2+4+7+14,因而28是一个完全数。 编写一个程序,求出2~1000以内的所有完 全数。

899

问题分析
? 本题是一个搜索问题,搜索范围是2~1000,搜索
的是该范围内的完全数; ? 完全数必须满足的条件:因子的和等于该数据本 身; ? 问题的关键:将该数的因子一一找出来,并求出

因子的和。分解因子的方法比较简单,采用循环
完成分解因子和求因

子的和。
900

问题分析
? 寻找因子的方法、在什么范围内寻找因子(
在什么范围内穷举)? for b:=1 to a-1 do if a mod b=0 then s:=s + b

? 源程序见P205

901

【例12-2】一根29cm长的尺子,只允许在上
面刻7个刻度,要能用它量出1~29cm的各种 长度。试问这根尺的刻度应该怎样选择?

902

问题分析
? 求组合数的公式:
Cm ?
n

m! n !* ( m ? n )!

?

m( m ? 1) ? ( m ? n ? 1) n!

? 从1~29cm中选择7个刻度的所有可能情况数 是:
C29 ?
7

29 * 28 * 27 * 26 * 25 * 24 * 23 7!
903

=1560780

问题分析
? 对于每一组刻度的选择,都要判断是否能将
1~29cm的各种刻度度量出来,例如选择的刻度 为a1,a2,a3,a4,a5,a6,a7,则能度量的刻度为:

a1, 29 - a1
a2, a2 - a1, 29 - a2

2
3

a3, a3 - a1, a3 - a2, 29 - a3
<<

4

a7, a7 - a1, a7 - a2, <, 29 - a7

8

904

问题分析
? 共可量出2+3+4+5+6+7+8=35种刻度,事实上有许
多刻度是重复的,不一定能覆盖1~29(见P206) ? 如果找出了刻度a1,a2,a3,a4,a5,a6,a7,那么我们就 可以利用其对称性29-a1,29-a2,29-a3,29-a4,29a5,29-a6,29-a7,来求出另一组解,所以求解过程中

可以仅考虑a1<a2<a3<a4<a5<a6<a7的情况

905

问题分析
? (根据题意,逐步细致地分析如何穷举各种
解)显然,要使1,28两种刻度能量出来,则 在7个刻度中就必须有1或28; 这样,可以 设a1=1(或a1=28)。

906

问题分析
? 本题就变成了只要在2~27中选择六个刻度
的问题了。其刻度选择的数目为:
C26 ? 230230
6

907

问题分析
? 这样,解的范围就从百万变成了十万的数 量级了,大大减少了运行的次数。
? 如何验证每一组解? 看看由这7个刻度所组成的各种组合能否 构成从1到29的连续刻度。

908

问题分析
? 为了判定7个刻度是否能度量出1~29的所有
长度,可以利用集合,也可以利用0~1数组 进行判断。 ? 书上的参考程序采用了0~1数组的方法。 ? 参考程序见PP207~208

909

【例12-3】
邮局发行一套票面有四种不同值的邮票,

如果每封信所贴邮票张数不超过三枚,存
在整数r,使得用不超过三枚的邮票,可以 贴出连续的整数1、2、3<、r来,找出这 四种面值数,使得r最大。
910

问题分析
? 几个问题:
– – – 本问题要我们求什么? 已知什么? 应沿用怎样的思路来导出满足题意的解?

911

问题分析
? 本题的算法与例12-2有相同之处,上面例题是知
道总长,搜索7个刻度位置 ? 本题是知道每封信邮票数的范围(<=3),邮票有四 种类型,编程找出能使面值最大的邮票 ? 实际上,两个问题也有着相似性,求的都是“面

值/刻度”。

912

问题分析
1) 面值不同的四种邮票,每封信所贴邮票不超过3张 ;(问题:能否重复使用同一面值的邮票?) 2) 用这四

种邮票贴出连续的整数,并且使r值最大; 3) 用穷举法,找出所有符合条件的解(问题:如何根 据穷举法的几个要点来进行穷举?);
4) 本题用集合的方法统计邮票的面值,提高判重的 速度(程序优化)。

913

问题分析
? 设四种邮票的面值分别为a、b、c、d,根据题意 ,可设: a<b<c<d 并且有a=1。 ? 用循环结构来进行穷尽搜索:
– 在可以贴在信封上的三张邮票中,(四种面值的)邮票的 张数是可变的,可以穷举; – 四种面值也是可以变的,因而对四种面值也可以穷举 – 这样,就可以间接地穷举出各种面值总额来

914

问题分析
? 四种面值的可取值范围要受到一定的限制
,如一定要有一种面值为1的邮票,第二种 面值最小可以是2,但最大不能超过4(Why? 如何才能在审题时发现这一限制?),等等 ? 源程序见教材P208

915

【例12-4】编一个程序,对给定的自然数n, 找出满足下述关系的最小s: s = pn+qn = rn + tn 其中p、q和r、t互不相同。有解时输出解 ,否则给出无解信息。

916

问题:
? 本题到底是什么意思?题目提出的要求是什
么(要求的解是什么?是求符合公式的s吗?为 了求出s,还应该求出什么?) ? 直观上看/从数学的角度来看,该如何下手 来解决本题?

917

问题:
? 与我们前面解过的问题有无什么相似之处?
能否利用转换法的思想,将此题(或此题的 解题思路)转换为以前掌握过的方法?

918

算法分析
? 本问题要求的是最小的的s,即p,q,r,
t的一组取值,它使得s最小; ? p,q,r,t的取值范围为: [0,trunc(exp(ln(maxint)/n))] (Why?)

919

算法分析
? 本题是否可以采取穷举法来求解?(或者说
,本题是否有着明显的可用穷举法求解的 特征?) ? 要求的解是什么?解空间是怎样的?应如何穷 举?对解的验证规则是什么?如何优化?

920

算法分析
? 对给定的n,利用穷举法,使p,q,r,t在
[0,trunc(exp(ln(maxint)/n))]穷尽变化, 对每次p、q、r、t的一个组合,验证pn+qn = rn + tn ,且p<>q,p<>r,p<>t,q<>r, q<>t,r<>t,将满足这些条件的p,q,r,t 选出,并找出其中的最小值。
921

算法分析
? 但是,这样搜索的时间太长。
? 为了改善搜索的效率,可以适当改变表达式和存 储方式,用pn- rn =tn- qn (或pn-tn = rn - qn )的方法 和用二维数组存放差的结果,行、列下标分别表 示p,q,r,t的值。

? n=3时, a3- b3 的列表见P210

922

算法分析
? 关键:三角矩阵的生成
? 如何以较少的工作量来生成该三角矩阵

? 一旦生成三角矩阵后,就可以通过在矩阵
中查找来寻找可行解了

923

不同进制数的转换及应用
? 在计算机领域中,所谓不同进制数的转换
,主要指的是将十进

制数与二进制、八进 制、十六进制数之间的互相转换

924

数制转换的基本方法
? 十进制数(y)转换成任意进制数(n)的方法: 将十进制数除以n进制,再反序取余数 ? 将任意进制数转换成十进制数:按“权” 展开 ? 二进制、八进制、十六进制数之间的转换 :
– 利用3位进制表示1位八进制数 – 利用4位进制表示1位十六进制数
925

十进制数(y)转换成任意进制数 (n)
t:=0; repeat t:=t+1; a[t]:=y mod x; y := y div n; until y=0;

926

十进制数(y)转换成任意进制数 (n)
? 输出时,按从a[t]到a[1]的顺序输出各余数 即可

927

任意进制数转换成十进制数
? (1101)2=1*23+1*22+0*21+1*20=13 ? (165)8=1*82+6*81+5*80=117

928

? 例12-5 将十进制数转换成任意进制的数(设 n<10)。

929

program p12_5; var a: array[1..50] of integer; n, x, y, i: integer; begin write(‘input number x, y:’); read(x,y); t:=y; writeln; i:=0; repeat i:=i+1; a[i]:=y mod x; y:=y div x; until y = 0;

930

for n:=i downto 1 do write(a[n]); writeln; end.

931

? 如果超过了十进制,可以用字符A、B、C 、D、E、F表示10~15的数,将余数再转换 为字符类型进行处理。

932

【例12-6】将任意进制整数转换成十进制数
? 程序见教材P214

933

将十进制小数转换成其他进制的 小数
? 将小数乘以待转换的进制数,再正向取整 ? 例见P215

934

数的进制的应用
【例12-7】用三进制数求解数学问题
用质量为1g、3g、9g、27g和81g的砝码 称物体的重量,最大可以称121g。如果砝 码允许放在天平的两边,编程输出称不同 物体时砝码应该怎样安排?例如m=14时, m+9+3+1=27或m=27-9-3-1,即天平的一端 放m=14g的物体和9g、3g、1g的砝码,另一 端放27g的砝码。
935

问题分析
1. 被称物体的质量计算的数学原理:
设被称物体m放在天平左边,根据天平平衡原理 ,左边的质量应等于天平右边的质量。

936

问题分析
2. 问题的关键在于算法中如何体现砝码放在
天平左边、右边或没有参加称量:
可以用-1、1、0表示砝码放在了天平的左、右和 没有参加称量。除了这三个数外,不再有其 他数了,因而称为三进制数。每个砝码都有

这样的三种状态。

937

问题分析
3. 被称物体质量计算:
m=a*81+b*27+c*9+d*3+e 这里a、b、c、d、e分别表示81、27、9、3、1克 的砝码是放在天平的左边、右边或是没用。 其程序表示见教材P216。

938

【例12-8】走路问题
小明每天上学要从街口A到街口B,求

他从A到B的向前路(不后退)一共有多少种
走法?应该怎样走?(如P216图示)

939

问题分析
1. 我们可以利用二进制数来表示从A到B的走法: 设向右走记为0,向下走记为1
2. 用m表示行数,即横向街道数;n表示列数,即 纵向街道数 3. 从A到B一共走10步

,即步数的和为10,我们用x 、i、j、k、a这五重循环分别记下每走一步的情 况(用1或0表示) ? 程序见教材P217
940

【例12-9】
将2n个0和2n个1排成一圈,从任意一个位臵开 始,每次按逆时针的方向,以长度为n+1的单位计 数二进制数。要求给出一种排法,用上面的方法 产生出2n+1个不相同的二进制数。如当n=2时,有 22个0和22个1排列如图12-2所示。 如果从a位臵开始,逆时针方向取三个数000, 然后再从b位臵上开始取三个数001,接着取010, <<,可以得到8个不同的二进制数。
941

问题分析
1. 若要产生n位二进制数,则有2n-1个0和2n-1个1, 由这些0、1组成n位的二进制数,所以用数组记 录2n-1个0和2n-1个1的排列方法。 2. 若要产生三位二进制数,即n=3时,有: a*1+=0,a*2+=0,<,a*8+=1,表示为: a1a2a3=0,a2a3a4=1,a3a4a5=2,<,a7a8a1=4,数组 需要多定义两位。为此,一般情况多定义n-1位 。

942

问题分析
3. 所产生的不同二进制数的判断方法:将产 生的二进制数转换成十进制数,其范围是 0~2n-1的整数,判断所产生的二进制数是 否在此范围内。 4. 从后向前产生数据t。t=ai-1*2n-1+t/2,若t在 s中可以接受,否则不可以接受,另换一 个值。 程序见教材P218。
943

高精度计算
? 利用计算机进行计算时,有时会遇到这样
的问题:有些计算要求精度高,希望计算 的数的位数可达几十位甚至几百位,虽然 计算机的计算精度也算较高了,但因为受 到硬件的限制,往往达不到实际问题所要 求的精度。
944

高精度计算
? 我们可以利用程序设计的方法去实现这样
的高精度计算。 ? 下面介绍常用的几种高精度计算方法

945

高精度计算
高精度计算中需要处理好以下几个问题: 1) 数据的接收方法和存储方法; 2) 计算结果位数的确定 3) 进位、借位处理 4) 商和余数的求法

946

数据的接收方法和存储
? 当输入的数很长时,可以采用字符串方式
输入,这样可输入数字很长的数,利用字 符串函数和操作运算符,将每一位数取出 ,存入数组中。另一种方法是直接用循环 加数组方法输入数据。

947

计算结果位数的确定
? 利用对数函数:
l = trunc(ln(x)/ln(10)) + 1

再定义数组a[l]

948

进位、借位处理
? 加法进位:
a[i]:=a[i]+b[i]

若a[i]>10,则:
a[i]:=a[i]-10

a[i+1]:=a[i+1]+1
949

进位、借位处理
? 减法借位:
若a[i]<b[i],则:

a[i+1]:=a[i+1]-1
a[i]:=a[i]+10

a[i]:=a[i]-b[i]
950

进位、借位处理
? 乘法进位:
y:=a[i]×b[i]+c

c:=y div 10
a[i]:=y – c × 10 或a[i]=y mod 10

951

商和余数的求法
? 视被除数和除数的位数情况进行处理。

952

【例12-10】高精度加法运算
? 问题分析
1) 采用字符串输入的方法:str1, str2, 用字符串截取 的方

法取出每一位;

2) 将每一位数分别存放到a、b两数组中;
3) 从低位到高位依次将各位数相加,对需要进位的采用 进位处理方法; 4) 从高位到低位输出。

953

? 程序见P220。
? 有关高精度减法运算,只需处理好借位问

题,其基本方法同加法运算。

954

【例12-11】高精度乘法运算
? 问题分析
1)采用字符串接收数据,这一点同例12-10; 2)位数的确定:设被乘数为a,乘数为b,它们的位数分

别为L1和L2,故积的位数最长为L1+L2;
3)进位处理:乘法进位、加法进位同前

? 参考程序:见P222

955

【例12-12】(高精度)求n!的精确值( 解法一)
const y = 100; var i, j, n, c, k : integer; a: array[1..y] of integer; begin for i := 1 to y do a[i] = 0; a[1] := 1;
readln(‘n =‘, n); for i := 1 to n do begin c=0 for j := 1 to y do begin x := i *a[j] + c; c := x div 10; a[j] := x mod 10; end;

956

【例12-12】(高精度)求n!的精确值
k: = y; while a[k] = 0 do k := k – 1; write(i, ‘!=); for j := k downto 1 do write(a[j]); writeln; end end.
957

【例12-12】(高精度)求n!的精确 值(解法二)
? 问题分析
N!=1*2*3*<*n,我们用高精度算法来求出每一位数,其 算法如下:

1)确定位数:n!=n*(n-1)*(n-2)*<*3*2*1,根据数学知
识可知:n!的位数是: L=trunc(1/ln10(lnn+ln(n-1)+<+ln3+ln2+ln1))+1

958

然后,每位数占一个数组单元,这里我们稍加改进, 每个单元存放四位数,内存可节省1/4 (为什么这样 做?改用字符数组行不行?) ; 2) 进位处理:进位的条件是存储单元中的数是否大于 9999; 3) 输出处理:将各单元中的数顺序输出,但若该单元不 是最高位且不足四位数,则需要在前面补0,凑成四 位数

?

参考程序:见PP222-223

959

【例12-13】计算a/b的精确值,设A、B是一
般整数(是计算机可接受的整数),需要计 算它们的除法运算的精确结果。

960

问题分析
? 由数学知识可知,除法运算中被除、除数、商、
余数之间的关系是: 新的被除数 = 余数 * 10 商 = trunc(被除数/除数) 余数 = 被除数 mod 除数 ? 有了以上关系,就可以设计出一个高精度除法程 序,见教材PP224-225
961

回溯算法
? 搜索法与问题求解 ? 回溯法是搜索算法中的一种控制策略

962

回溯算法的基本思想
? 在搜索过程中,如果当前步骤中求解/搜索失败,
为了摆脱当前失败状态,需要返回搜索步骤中的 上一点,去寻求新的路径,以求得答案。

? 要返回上一步,则前进中的某些状态必须保存,
才能使得退回到某一状态后,可以继续向前执行

下去

963

回溯算法的基本思想
? 要保存状态,可以采用“栈”(也称堆栈)。
栈又可以采用数组等结构来实现

964

回溯算法的特点
? 搜索策略:符合递归算法,问题

的解决可以转化
为子问题,其子问题的解法与原问题相同,只是 数据增大或减少;

? 控制策略:为了避免不必要的穷举搜索,对在搜
索过程中所遇到的失败,采取从失败点回到上一

点,进行重新搜索,以寻找新的求解路径

965

回溯算法的特点
? 数据结构:用数组保存搜索过程中的状态
、路径

966

回溯算法的特点
? 假设回溯算法是要找出问题的所有答案(x1
,x2,<,xn),对于每个答案,都有一个 由根结点(开始位置)到终点(所要到达的结 点)的路径(设为T)。另外,假定存在一些规 则(设为B),则回溯算法的一般形式为:

967

回溯算法的一般形式
procedure backtrack(n); k ←1 while k>0 do begin if 还有未检验过的x(k)且x(k)是其中的一个可能 解,且满足规则b then if 存在由根结点经过x(k)的一条到达答案结点 的路径 then 输出x(1),x(2),<,x(k)路径 end if
968

k←k+1 else k←k-1 end if end; end;

969

一些典型的回溯算法问题
【例12-27】有2n个人排队购一件价格为0.5元的商
品,其中一半人拿一张1元的人民币,另一半人拿 一张0.5元的人民币。要使售货员在售货中,不发

生找钱困难,问这2n个人应该如何排队?找出所有
排队的方案。(售货员一开始就没有准备零钱)

970

问题分析
? 根据题意可以看出,要使售货员在售货过
程中不发生找钱困难,则在排队时,在任 何情况下,持0.5元的、排在前面的人数应 多于持1元的人数。

971

问题分析
? 该问题可以用二进制数表示:用0表示持0.5
元的人,用1表示持1元的人,那么,2n个 人排队问题就可转化为2n个0、1的排列问 题。 ? 这里我们用数组b[1..2n]来表示2n个人的持 币情况
972

问题分析
? 设k是b数组的下标,b[k]=0或b[k]=1。
? 另用数组d[],其元素d[0]、d[1]记录0与1的

个数,且必须满足:d[1]<=d[0]<n (用两个
普通的变量做计数器也可以)

973

算法:回溯搜索
a) 先将b*1+,b*2+,<,b*2n+置为-1,从第一个
元素开始搜索,每个元素先取0,再取1, 即b[k]+1→b[k],试探新的值,若符合规 则,则增加一个新元素; b) 若k<2n,则k+1→ k,试探下一个元素。 若k=2n,则输出b*1+,b*2+,<,b*2n+。
974

算法:回溯搜索
c) 若b[k]的值不符合要求,则将b[k]再加上1
,试探新的值。若b[k]=2,表示第k个元 素的所有值都已搜索过了,均不符合条件 ,只能返回上一个元素b[k-1],即发生回 溯。

975

算法:回溯搜索
d) 返回到上一个元素,即执行k:=k-1,并修改d[0] 、d[1] e) 直到求出所有的解。
? 程序清单见PP256-257。

976

? 由本例中对回溯算法的描述,可知回溯算
法中经常用数组(如b数组)作为一个栈,记 录访问过的点,并用数组下标(如k)作为栈 指针,表示搜索的进程(

路径)。

977

? 栈的后进先出特点,恰好符合回溯的后产
生的点先回溯这一特点。所以,回溯算法 中经常用数组这样的数据结构来存储操作 过程。 ? 针对本题的特殊性,还可以有其他更简便 的解法,请同学们自行设计完成。
978

【例12-28】骑士游历问 题 在n*n的国际象棋 棋盘上,在某一位臵处 放臵一个马,然后用象 棋中?马走日字?的规 则,要求这个马能不重 复地走完所有的n*n个 格子。试编程解决这个 问题。

3

2

4 骑士 5
6
图12-3

1 8
7

979

问题分析
? 本题是典型的回溯算法问题。设骑士在某
一位置(设该位置为(x, y)),这时,按跳马的 规则,下一步可以跳到如图12-3(n=5的情况 )所示的8个位置之一。

980

问题分析
? 我们将重点考虑前进的方向:如果某一步
可继续走下去,就试探着走下去,并且考 虑下一步的走法;若走不能则返回,考虑 另选一个位置 ? 算法的伪代码见教材PP259-260

981

问题分析
? 马走的路径可以用二维数组表示:横向和
纵向,其走的方向有8种可能,用数组记录 下某点所对应的8个方向的坐标

982

算法中用到的数据结构
? 算法中用到的数据结构如下: const n=8; nsq=64; type index = 1..n; var i, j: index; g: boolean; b: array[1..n, 1..n] of integer;

983

算法中用到的数据结构
? 我们约定:
?0 当棋格(i,j)未被占据 b[i, j ] ? ? ?k 当棋格(i,j)在第k次移动中被占据

984

算法中用到的数据结构
? 用数组b记录移动的情况,当可以走通时,
置b[i1,j1]:=i,否则(即走不通)的话,需删除 以前记录,即置b[i1,j1]:=0

985

算法中用到的数据结构
? 用k表示当前进行的方向,选下一个位置就
是改变下标值:设当前下标为 (x,y)→(u1,v1),其关系是u1=x-1,v1=y+2, 其他几个跳马位置的坐标关系可依此类推 ,用坐标增量来表示移动情况 ? 参考程序见教材PP260-261
986

【例】求解迷宫问题
一个迷宫包含有m行×n列个小方格,每 个方格用0表示可通行,用1表示墙壁,即 不可通行。迷宫中通常有一个入口和一个 出口,入口点的坐标为(1,1),出口点 的坐标为(m,n),当然入口点和出口点均 为0,即均可通行。

987

问题描述
? 从迷宫中的某一个坐标位置向东、南、西
、北任一方向移动一步(即一个方格)时 ,若前面的小方格为0,则可前进一步,否 则通行受阻,不能前进,应按顺时针方向 ,改变为沿下一个前进方向再行试探移动 。
988

问题描述
? 求解迷宫是从入口点出发,寻找一条通向
出口点的路径,并打印出这条路径,即经 过的每个小方格的坐标

989

? 如图5(a)、(b)是一个6×8的迷宫,
? 入口点坐标为(1,1),出口点坐标为(6,8) ?

其中的一条路径为(1,1),(1,2),(2,2 ),(2,3),(3,3),(3,4),(3,5) ,(3,6),(4,6),(4,7),(5,7),

(6,7),(6,8)。

990

1
1 2 3

2

3

4

5

6

7

8

4
5 6

图5 迷宫阵列图

991

1 1 2 3 4 5 6 0 1 0 1 0 1

2 0 0 0 1 0 0

3 1 0 0 0 0 1

4 1 1 0 1 0 0

5 0 1 0 1 0 0

6 1 0 0 0 1 0

7 0 0 1 0 0 0

8 1 0 1 0 1 0

图5 迷宫阵列图

992

? 在一个迷宫中,中间的每个方格位置都有
四个可选择的移动方向,而在四个顶点处 ,只有两个方向,并且每个顶点的两个方 向均有差别,每条边线上除顶点之外的每 个位置只有三个方向,并且也都有差别。

993

? 为了在求解迷宫问题的算法中,避免判断
边界条件和进行不同处理的麻烦,使每一 个方格都能够度着按四个方向移动,可在 迷宫的周围镶上边框,在边框的每个方格 里填上1,作为墙壁,如图5(c)所示。

994

? 这样,需要用一个[1..m+2,1..n+2]大小的
二维整型数组(假定用maze表示数组名) 来存储迷宫数据。

995

0 0 1

1 1

2 1

3 1

4 1

5 1

6 1

7 1

8 1

9 1

1
2 3 4 5 6

1
1 1 1 1 1

0
1 0 1 0 1

0
0 0 1 0 0

1
0 0 0 0 1

1
1 0 1 0 0

0
1 0 1 0 0

1
0 0 0 1 0

0
0 1 0 0 0

1
0 1 0 1 0

1
1 1 1 1 1

7

1

1

1

1

1

1

1

1

1

1

图5 迷宫阵列图

996

? 当从迷宫中的一个位置(称它为当前位置)前进到
下一个位置时,下一个位置相对于当前位置的位 移量随着前进方向的不同而不同

? 东、南、西、北(即右、下、左、上)各方向的
位移量依次为(0,1)、(1,0)、(0,-1)、

(-1,0)。

997

? 假定用一个4×2的整型数组move来存储位
移量数据,则move数组的内容如下:

998

行位移 1

列位移 2

1
2 3

0
1 0

1
0 -1

←东 ←南 ←西 ←北

4

-1

0

999

? 其中,第一行到第四行依次存储了向东、
南、西、北每个方向移动一步的行、列位 移量。 ? 例如,move[2,1]和move[2,2]分别表示从 当前位置向南移动一步的行位移量和列位 移量,其值分别为1和0。
1000

? 在求解迷宫问题时,还需要使用一个与存
储迷宫数据的 maze 数组同样大小的辅助数 组,假定用标识符 mark 表示,用它来标识 迷宫中对应位置是否被访问过。 ? 该数组中每个元素的初始值都为0,表示迷 宫中的所有位置均没有被访问过。
1001

? 每访问迷宫中一个可通行的位置时,都使
mark数组中对应元素置1,表示该位置已经 被访问过了,以后不会再访问到,这样才 能够探索新的路径,避免重走已经知道走 不通的老路。

1002

? 为了寻找从入口点到出口点的一条通路,首先从
入口点出发,按照东、南、西、北各方向的次序 试探前进

? 若向东可通行,同时没有被访问过,则向东前进
一个

方格;否则,表明向东没有通向出口的路径

,接着应向南方向试着前进。若向南可通行且没
有被访问过,应向南前进一步,否则依次向西和 向北试探。
1003

? 若试探完当前位置上的所有方向后,都无
法到达终点,则应退回一步(发生回溯), 从到达该当前位置的下一个方向试探着前 进。 ? 例如,若到达该当前位置的方向为东,则 下一个方向为南。
1004

? 因此,每前进一步,都要记录其上一步的
坐标位置和前进到此的方向,以便发生回 退时之用——这正好可以用栈来解决:

1005

? 每前进一步时:
1) 都要把当前位臵和前进一步的方向进栈 2) 接着,使向前一步的位臵成为当前位臵

? 当从当前位置无法继续前进时:
1) 就做一次退栈操作 2) 再从上一次位臵的下一个方向试探着前进
1006

? 若当前位置是出口点时,则表明找到了一条从入
口点到出口点的路径,应结束算法的执行。此时 ,路径上的每个方格的坐标(除出口坐标外)均

被记录在栈中。
? 若做退栈操作时栈为空,表明连入口点也被退栈

了,并且其所有方向都已访问过,没有通向出口
点的路径,此时应结束算法,打印出无通路信息 。
1007

? 下面给出求解迷宫问题的递归算法,其中m和n为
全局整型常量,分别表示迷宫的行数和列数,它 们也是出口点的坐标。

? Maze和mark分别为具有[1..m+2,1..n+2]大小的全
局整型数组,分别用来保存迷宫数据和访问标记



1008

{ 从迷宫中坐标点 (x,y) 的位臵寻找通向终点 (m,n) 的路径,若找到则返回 1 ,否则返回 0 , (x,y)的初始值通常为(1,1)} function seekpath(x, y: integer): integer; var i, g, h: integer; {i 作为循环变量,代表从当前位臵移到下一个 位臵的方向,g和h表示下一个位臵的坐标} begin if (x=m) and (y=n) then
1009

begin seekpath := 1; {递归边界条件:到达出口 点,返回1,结束递归} exit; end; {of if} for i:=1 to 4 do {依次按每一个方向寻找通向终点的路径} begin g:=x + move[i,1]; {求出下一位置的行坐标} h:=y + move[i,2]; {求出下一位置的列坐标}
1010

if (maze[g,h]=0) and (mark[g,h]=0) then {若下 一位置可通行且没有被试探过,则从(g,h)位置 起寻找路径——这是一种深度优先的搜索策略 } begin mark[g,h]:=1; {表明该位置已被访问过} if seekpath(g,h)=1 then begin write(g,h); seekpath:=1;{注意:递归过程中入栈和弹 栈全部由系统自动完成} exit; end end {of if} end; {of for} 1011

if (x=1) and (y=1) then {当入口点的所有方向 都已访问完后,表明不存在通向终点的路径, 应打印出没有路径的信息} begin writeln(“No path.”); seekpath:=0; exit; end; {of if} end; {of function seekpath}
1012

问题
? 在上述的递归算法中,回溯是

如何体现的、是在 何时做的?
? 在这种带回溯的算法中,弹栈操作并不一定是在 最终到了递归边界或递归上升阶段时才发生,在 中间就有可能发生 ? 中间发生的递归上升是真正的回溯,而当成功地 搜索出一条通路后发生的一连串递归上升,则属 于递归本身的特性
1013

迷宫算法的另一种非递归版本
xpos:=1; ypos:=1;p:=1;i:=0; x[p]:=xpos; y[p]:=ypos; repeat i := i + 1; if i<=4 then begin xpos:=x[p]+move[i,1]; ypos:=y[p]+move[i,2]; if maze[xpos,ypos]=0 then begin

1014

p:=p+1; s[p]:=i; x[p]:=xpos; y[p]:=ypos; mark[xpos,ypos]:=1; i:=0 end end else begin i:=s[p]; p:=p – 1 ; end; until (p=0) or (xpos=m) and (ypos=n);
1015

if p=0 then writeln(‘无通路’) else for i:=1 to p do write(x*i+,’,’,y*i+,’→’) ;

1016

【例12-29】四色问题
设有如图12-4所示的地图,每个区域

代表一个省,区域中的数字表示省的编号
。现要求给每个省涂上红、蓝、黄、白四 种颜色之一,同时使相邻的省份以不同的 颜色区分。
1017

问题分析
? 本题是图论中的一个搜索问题,我们可以
这样来简化该问题:将每个省看作是一个 点,将省之间的联系看作为一条边,这样 就得到图12-5所示的图形。

1018

问题分析
? 从图12-5可知各省之间的相邻关系,可以用
矩阵(即二维数组)来表示它: R[x,y]=1, 表示省x与省y相邻 R[x,y]=0, 表示省x与省y不相邻

1019

问题分析
? 由图12-5可得P263矩阵
? 对所有的省和四种颜色进行编号 ? 从编号为1的省份开始,按四种颜色顺序填色。当 第一个省颜色与相邻省不同时,就可以确定第一 个省的颜色。然后,再依次对第二、第三、<进

行处理,直到所有省份的颜色都涂上为止。

1020

问题分析
? 问题的关键在于填色过程中,如果即将填
的颜色与相邻省的颜色相同(如何找当前省 的相邻省?如何确定其颜色与相邻省份的颜 色不同? ),而且四种颜色都试探过,均不 能满足要求,则需要回溯到上一个点(即前 一个省),修改上一个省的颜色,重新试探 下一个省的颜色。
1021

问题分析
? 因此,从直观上看,本题就可以采用回溯
方法来求解。其基本算法如下:

1022

procedure 着色过程mapcolor; begin

初始化并对第一个省着色:s[1]:=1; x:=2; y:=1; {s[]数组记录每个省的颜色; n:省份总数;x:当 前着色的省的编号;选择颜色;y:表示当前所选 颜色的编号 }
while x<=n do {选择颜色}

begin
k:=1; {开始检查相邻区域的颜色} while k < x and (如果k与x相邻 and s[k]与x 的当前所选颜色不冲突) do k:=k+1; 1023

if k < x {即当前为x所选的颜色与相邻区域有冲突}then 试探下一种颜色:y:=y+1 else 本区域涂色,准备接着处理下一区域; if 试探不成功{即y> 4} then begin x := x - 1 {返回上

一个点,即回溯} 修正y颜色的值 end; end; {of while} end; {of mapcolor}
1024

算法说明
? 在上面的算法中:
– s数组表示某区域所涂的颜色

– r数组表示省之间的关联,用0、1表示

1025

? 因此,可用以下判断来检查(比当前结点编
号低的 )相邻区域是否涂色或涂的颜色是否 相同: s[k] * r[x,k] <> x的当前所选颜色 ? 程序清单见PP264-265

1026

【例12-30】 在n*n的棋盘上(1≤n≤10)中填入1,2,3 ,<<,n*n,共有n*n个数,使得任意两 个相邻数的和为素数。例如:当n=2时,有 :
1
4

2
3
1027

? 当n=4时,一种可以填写的方案如下表所示 。这里我们约定:左上角的格子里必须填 数字1。程序要求: 1)输入n; 2)若输出有多个解,则输出第一行、第一 列之和为最小的排列方案;若无解,则输 出?NO!?
1028

1
16

2
15

11
8

12
5

13
6

4
7

9
10

14
3

1029

问题分析
? 该问题就是要找出一种或多种满足条件的
“放置布局”,此处的条件、如何放、如 何找又不易用数学模型来表达,因此,可 以看出,是一个较为明显的“找”(或称 尝试,即“搜索”)解决方案的问题,只 能慢慢地找或尝试(回溯)或搜索
1030

问题分析
? 基本的搜索及回溯过程是比较直观的(应如
何搜索?)

1031

问题分析
? 但是,如果一边填数、一边求和及判断素
数的话,则程序运行的速度将大大地减慢 (因为每新填入一个数,都要对已填好的 每一对数进行计算,看是否两两的和都是 素数,这样的计算量很大/越来越大,而且 是实时计算的)
1032

问题分析
? 因此,基于这一考虑,我们可以采用数组
结构,将2~n*n之间的所有素数存放在一个 数组中,目的是不进行现场计算,而是与 该数组中的素数进行比较(这样一来,代 价节省在何处?)。

1033

问题分析
? 由于问题中指出n<=10,所以,最大的相邻
两个数的和是99+100<200。因而,我们只 需将2~200之间的素数存放在数组中即可( 或将该区间内的所有素数放入一个集合,用 集合操作in来判断当前相邻数的和是否在 该素数集合中)。
1034

问题分析
? 按行、列填入数据,并求相邻两个数的和
,将其与素数数组比较(如何比较?)
–若是素数,则当前格子里可以填数(该填入哪 个数?),继续填数 –若当前格中没有数可以填入,则要回溯到上一 格,重新填写该格里的数据,再进行判断

1035

算法中用到的数据结构
? 用一个布尔数组h表示1~n*n之间的数是否
用过,false表示尚未用过,true表示用过了 ? 用一个二维数组a存放棋盘格子中填数的情 况(即每一个格子里放了什么数字),其中 a[1,1]=1

1036

算法中用到的数据结构
? 用一个数组下标指针,来表

明递归调用的
层次和回溯的层次

1037

procedure 填数过程; begin 初始化工作; 对第一格填数:a[1,1]:=1; while k<=n*n do {还有空格没有填数} begin if (第k个数未用过) and (与相邻数的和是素数 ) then
1038

将数据填入格子内,且设置为已填过此数; 准备试探下一个空格; if 当前数据不能填 then 试探下一个数据; if 试探不成功 then {回溯或退栈,返回前一个 格子} begin dep:=dep – 1 重新填数 end; end; {of while loop} end; {of procedure ?填数过程”}

1039

? 源程序见PP266-267

1040

适合用回溯法求解的问题
? 问题的解包含一个过程(或由一系列状态连接而 成),此过程需要若干个步骤才能完成,每一个 步骤又分为若干种可能 ? 同时,为了完成任务,还必须遵守一些规则,但 这些规则无法用数学公式表示
对于这一类问题,一般采用搜索的方法来解决, 回溯法就是搜索算法中的一控制策略,它能解决 许多搜索中的问题。
1041

实现时的要点
? 数据结构:用栈(数组)来存放前进中的一系列 状态 ? 可以用递归实现:搜索策略符合递归算法的特点 ,即原问题的解决可以化为对一系列子问题的解 决,子问题的解决算法与原问题相同,只是数据 增大或减少 ? 控制策略:为了避免不必要的穷举搜索,对在搜 索过程中所遇到的失败,采取从失败点返回到上 一点,进行重新搜索,求得新的求解路径
1042

回溯法可以解决的经典问题
? 自然数的排列 ? n皇后问题
? 迷宫问题 ? 数的拆分 ? 0/1背包问题 ? 旅行商问题 ? 货船装货问题 ? 图形覆盖正方形等
1043

? 在应用回溯法求所有路径的算法框架时, 应考虑如下几个重要因素:
1) 2) 3) 4) 5) 定义状态 边界条件 搜索范围 约束条件和最优性要求 参与递归运算的参数

1044

排序查找算法
? 排序算法:
我们在前面学过的排序算法有选择排序、冒泡排 序等,它们的时间复杂性为O(n2),稳定性比较好 ,但速度比较慢 ? 另外的一些排序算法:

插入排序、希尔(Shell)排序、快速排序、归并(合
并)排序
1045

插入排序
? 其思想与打牌时,当手中的一手牌已排好 序,又摸起一张新的牌插入这一手牌中时 差不多 ? 算法的基本思想:
1) 设n个数据已经按照顺序排列好(假定已按从 小到大的顺序排序,并存放在数组a中) 2) 输入一个数据x,将其按有序顺序,放入适当 的位置上,从而使整个数据序列仍然保持有 序顺序;
1046

a) 将x与n个数比较,寻找应当插入x的位置: i:=1; while x>a[i] do i:=i+1; b) j:=i; c) 将a数组中从j位置开始的元素向后移动: for k:=n+1 downto 1 do a[k]:=a[k-1]; d) a[j]:=x;

3) 输出已经插入完毕的有序数列。 例见P225。
1047

? 算

法(最坏情况下)的复杂性:O(n2)
? 适用于:原先的数据已经过了排序、又插 入了一个新数据项的情况

1048

Shell排序
? 此算法是Shell于1959年提出的,又称缩小
增量排序算法,其基本思想是:
1) 发现当n不大时,插入排序的性能是不错的。 因此,将大量的插入排序划分为小组的、少 量数据的插入排序;

1049

Shell排序
2) 设法先取小于n的一个增量d1,将第1、1+d1、
1+2d1<个元素作为第一组,将第2、2+d1、 2+2d1<个元素作为第二组,将d1 、 d1 +d1、

d1 +2d1<个元素作为第d1组,并在各组之内
运用插入排序。

3) 然后,再取d2<d1,重复进行上述过程,直到
增量di=1时为止。
1050

? 进行Shell排序时要考虑的问题:增量的个
数、大小应如何选取? 无明确的规则,只能凭经验。 ? 该算法是一种不稳定的排序算法,其时间

复杂性为O(n1.3)。

1051

? 思考:与插入排序相比,Shell排序的性能
为什么能有一定的改善? ? 程序见P226

1052

快速排序
? 是冒泡排序算法的改进,它是目前所有常
用排序方法中最快的一种(为什么?) ? 在冒泡排序中,数据的比较和交换是在相 邻单元中进行的,每次的交换只能上移或 下移一个单元,因而总的比较次数多

1053

快速排序
? 在快速排序中,数据的比较和交换是从两
端向中间进行的,一次就可以交换定位两 个单元中的数据,因而总的比较次数和交 换次数比较少

1054

快速排序算法
1) 设有n个数存放在数组s中;
2) 在s[1..n]中任取一个元素作为比较的基准

点(亦称为支点)元素,例如取t=s[1],其目
的是定出t应在排序结果中的位置k,并将 排序的元素交换成: s[1...k-1] <= s[k] <= s[k+1..n]
1055

快速排序算法
3) 利用分治策略,可以进一步对s[1...k-1]和
s[k+1..n]中的两组数据进行快速排序,直 到分组对象只有一个数据时为止。 例见P230。

1056

快速排序算法
? 从输出数据可以看出,对于比较坏的初始
数据(如第一组输入数据),快速排序在交换 数据的次数方面已给出了相当好的结果, 时间复杂性是O(nlog2n),因此速度是比较 快的,但同时,它也是一种不稳定的排序 方法。
1057

归并排序
? 所谓归并排序,就是指将两个或两个以上
的有序的数列(或有序表),合并成一个仍然 有效的数列(有序表)。 ? 这样的排序方法常用于将多个有序的数据 文件归并成一个有序的数据文件。

1058

归并排序算法的基本思想
1. 假设已经有两个有序数列,分别存放在两
个数组s和r中,并设i、j分别为指向数组 第一个单元的下标;设s有n个元素,r有m 个元素;再另设一个数组a,且k指向该数 组的第一个单元;

1059

归并排序算法的基本思想
2. 对s和r中的当前

元素进行比较,将较小者
放入结果数组a中,不断重复这个过程, 直到某个数组已经结束时停止; 3. 将尚有数据的数组中余下的元素依次放入 结果数组a中。 程序片段见P232。
1060

例12-16 有两个多项式:
y1=3x5-3x4+7x2-5x-2 y2=7x8+4x6-2x5+3x4-6x3+2x-9 编一个程序,求两个多项式的和。

1061

问题分析
1) 多项式加法问题, 就是多项式同类项合并问题
,也就是两个有序表的归并排序问题; 2) 问题的关键是如何表示两个多项式,这里可以 借助于于记录型数组来表示(或二维数组),数组 的每个单元表示一个项,它有两个域:系数和

指数;

1062

问题分析
3) 利用归并排序算法,进行多项式加法运算
。注意当其中某一项的和为0时的处理。 ? 程序见P233

1063

排列
? 在现实生活中,常常会遇到这样的问题,
就是要把一些事物排在一起,构成一列, 计算有多少种排法,这就是排列问题。在 排的过程中,不仅与参加排列的事物有关 ,而且与各事物所在的先后顺序有关。

1064

? 例:某客轮航行于天津、青岛、大连三个 城市之间,问:应准备多少种不同的船票 ? ? 分析:船票的种类不仅与所选的两个城市 有关,还与这两个城市的起点、终点顺序 有关。因此,需要在三个城市中每次取出 两个,按照起点、终点的顺序排列,共有 3*2=6种
1065

? 一般地,将从n个不同元素中取出m个 (m≤n)元素的所有排列的个数,叫做从n个 不同元素中取出m个元素的排列数,记做
?
m n 对上面的例子而言,有:

P

P ? 3? 2 ? 6
2 3
1066

? 一般地,有:

P ? n(n ? 1)(n ? 2)? (n ? m ? 1)
m n

1067

? 例:幼儿园里6名小朋友去坐3把不同的椅 子,有多少种坐法?
? 分析:可以将3把椅子看作是3个位臵,而6 名小朋友作为6个不同的元素,问题就可以 转化为从6个元素中取3个,排在3个不同位 臵上的排列问题。

P ? 6 ? 5 ? 4 ? 120
3 6
1068

? 在涉及排列的编程问题中,问题的一般形
式是这样的:任给n个不同的元素排成一列 ,问有多少种不同的排列。不仅要给出排 列的数目,而且要能列举出所有不同的排 列序列。

1069

【例12-27】有4人照相,按照他们排列位臵
的不同照相,问有多少种排列方法?

1070

? 通过数学方法可以计算出排列总数
? 要输出每种排列,可以用穷举法。但是,

当n较大时,要穷举出n个元素的排列就会
比较困难

1071

? 观察:
– 各个位置上数的变化快慢规律 – 最初的排列、最终的排列 – 上一个排列和下一个排列之间的内存关系/变化 规律

1072

产生/输出排列的算法
1) 初始状态为1 2 < n; 2) 对最大的活动元素沿箭头方向交换位置, 产生一个新排列;

3) 交换后要变更当前活动元素大的元素的箭 头方向; 4) 重复(2)、(3),直到没有活动元素时为止 。 ? 图见教材P236,, 参考程序见P239
1073

组合
? 日常生活中,有很多“分组”问题,如在 体育比赛中把参赛队分为几个组等,即我 们要讨论的组合问题。 ? 我们着重要研究有多少种分组的方法
? 例:某客轮航行于天津、青岛、大连三个 城市之间,那么,船票共有几种价格(往返 票价相同)?
1074

? 分析:如果把问题中的对象(即三个城市) 看作元素,那么,上面的问题就是从3个元 素中取出两个,组成一组的问题。我们把 这样的一组叫做一个组合,把所有的组合 的个数叫做组合数。上面的问题就是要求 组合数。

1075

? 生成组合的程序:见教材PP241~242

1076

一些重要的排列组合公式(略)

1077

全排列的通用程序
readln(n); t:=0; s:=1; for i:=1 to n do a[i]:=i; {产生一种初始排列格局} for i:=1 to n do s=s*i; {s = n!,用于控制循环的次数} repeat {循环产生n!种不同的排列} t := t + 1; {t用于记录排列的数目} for i := 1 to n do write(a[i]); writeln;
1078

全排列的通用程序片段
for i := 1 to n-1 do if a[i] < a[i+1] then m:=i; {找到一个?顺?序的对 子} for j := m+1 to n do if a[m] < a[j] then h:=j; x:=a[m]; a[m]:=a[h]; a[h]:=x; {交换后即产生了一种新的排列}
1079

全排列的通用程序片段
for r:=m+1 to (n+m+1) div 2 do begin x:=a[r]; a[r]:=a[n+m+1-r]; a[n+m+1-r]:=x end; {of for} until t=>s write( t);
1080

组合的通用程序片段
read(n,r); s:=0; for i:=0 to r do b[i]:=0; while b[0]=0 do begin s:=s+1; for i:=1 to r do write(b[i]); j:=r;
1081

组合的通用程序片段
while b[i]=n-r+j do j:=j-1; b[j]:=b[j]+1; for i:=j+1 to r do b[i]:=b[i-1]+1; end; {of while} writeln(s);

1082

? 例:信封问题 某人非常粗心,他准备同时给n个人发信, 却把每封信都装在错误的信封里。请帮他 打印出发生这样的错误的各种情况以及总 数。

1083

问题分析
? 根据题意可知,题目要求的是所有未将第i
封信装入第i个信封的方案 ? 将n个信封编号为1,2,<,n,并假设它们已经 按顺序排列好。现在要求的是所有i不在第i 个位置上的方案

1084

问题分析
? 不管是哪一种方案,都是n个编号的一个排
列,因此,所有方案都在从n个元素中任取 n个元素的排列之中(即n的全排列) ? 可以用Ai(即A1,A2,<,An)表示第i封信,用 i表示第i个信封

1085

【例12-19】任何一个大于1的自然数n,总可
以拆分成若干个小于n的自然数之和。

1086

问题分析
? 本题需要注意,任给自然数n,能否给出所
有不同的拆分。 ? 还有,要注意10=3+7与10=7+3是同一种拆 分。 ? 要点:如何求出所有的拆分。

1087

问题分析
? 下面以n=7为例来说明拆分过程

: 第一步:将n拆分为两项之和: 7=1+6 7=2+5 7=3+4 拆分的特点是第2个加数总是大于第一个加 数,因此,第一个加数从1变化到n div 2。
1088

? 第二步:只要第2个加数仍大于1,就可以按第 一步重复拆分,例如: 7=1+6 7=1+1+5 7=1+2+4 7=1+3+3 其中7=1+1+5又可以继续拆分为: 7=1+1+1+4 7=1+1+2+3 << 最后获得P243的结果。
1089

关于算法及数据结构的说明
? 采用数组a[0..100](假设操作中输入的n≤100),a[k]
中记录已完成的一种拆分。 ? 例如: 7=1+6表示为a[0]=7,a[1]=1,a[2]=6,k=2。 ? 继续拆分从a[k](此时即为a[2])开始。A[k]能否继 续拆分取决于a[k] div 2是否大于等于a[k-1];

1090

关于算法及数据结构的说明
? 递归过程有两个参数:nx表示要拆分的数
值大小,kx表示nx存储在数组元素a[kx]中 ,即a[kx]=nx ? 程序清单见PP243-244

1091


网站首页网站地图 站长统计
All rights reserved Powered by 海文库
copyright ©right 2010-2011。
文档资料库内容来自网络,如有侵犯请联系客服。zhit326@126.com