当前位置:首页 >> 其它课程 >>

Pascal选修


第 一 讲

程序设计基础

十进制与二进制
进制 十进制 数字符号
0,1,2,3,4,5,6,7,8,9

基数
10

运算规则 逢十进一

二进制

0,1

2

逢二进一

/>
十进制
1+1= 十进制 0 1 2 3 4 5 二进制 0 1 10 11 100 101 2

二进制
10 十进制 6 7 8 9 10 11 二进制 110 111 1000 1001 1010 1011

启发 二进制理论

莱布尼茨(G.Leibnitz,1646-1716)德国数学家 1与0,一切数字的神奇渊源。这是造物的秘 密美妙的典范,因为,一切无非都来自上帝。

现代计算机科学

十进制与二进制相互转换
二进制整数转十进制整数的方法:(加权系数展开法) (219)10=2×102+1×101+9×100

系数

权值

(11010)2=1×24+1×23+0×22+1×21+0×20=26

十进制整数转二进制整数的方法:(除二取余逆序法)
2 13 2 6 2 3 2 1 0 1 0 1 1

(13)10=(1101)2

课堂练习
将下列二进制数转换为十进制数: (101101)2= (45)10

(111111)2= (63)10

将下列十进制数转换为二进制数: (32)10= (100000)2 (127)10= (1111111)2

计算机系统的组成
软件系统 硬件系统 硬件系统 目前的计算机硬件系统多采用美籍匈牙利数学家冯.诺依曼提出的“存储程 序和程序控制”模型,它由运算器、控制器、存储器、输入设备和输出设备五部 分组成 外存储器 信息 输入设备 (存)数据 内存储器 (存)数据 (取)指令 信息 输出设备 控制器 (取)数据 运算器

操作系统(如:Windows)

系统软件
编程软件(如:FreePascal) 软件系统

应用软件

软件就是程序、数据和相关文档资料的集合。

程序是软件的核心

程 序

什么是程序
程序就是用于完成某项具体工作的指令的序列。
渡河指令: 1、人、羊过河 2、人返回 3、人、狼过河(人、菜过河) 4、人、羊返回 【人羊菜狼过河问题】

5、人、菜过河(人、狼过河)
6、人返回 7、人、羊过河 计算机程序就是用计算机语言编写的程序

计算机程序设计语言是一种什么语言呢?
计算机语言就是计算机能够识别的语言.
计算机语言的分类
1、机器语言 例如:51+53 机器语言表示:10110000 00110011 10110010 00110101 00000000 11000010

2、汇编语言 例如:51+53 汇编语言表示: mov AL , 33H mov DL , 35H add DL , AL

3、高级语言 例如:51+53 高级语言表示: 51+53

Basic、Pascal、C、C++、Java都是常用的高级语言 注意:无论是用高级语言还是汇编语言编写的程序都要经过编译器的编译或 解释,将其转换为机器语言之后,计算机才能执行。

Pascal 是什么
Pascal是一种计算机程序设计语言,它是由瑞士
的沃斯(N Wirth)教授于1971年设计出来的,之所以

起名为Pascal,是为了纪念法国数学家Pascal;它也
是学习计算机编程最好的入门语言之一。

例1:编写一个计算任意三角形面积的程序。

分析问题

利用三角形面积公式 三角形面积=底边长度×底边上的高÷2 求面积 1)将底边长度输入计算机 2)将底边高输入计算机 3)计算 底边长度×底边上的高÷2 的值 4)输出计算值

设 计 算 法

编 写 程 序

例1:编写一个计算任意三角形面积的程序。

程序名 程序首部 说明 部分 程序体 执行 部分

program sjx; var

a,b,s:real;
begin readln(a,b); s:=a*b/2; writeln(‘s=‘,s) end.

算法
算法就是解决问题的方法和步骤

算法的特征
可行性 确定性 有穷性

图形符号
开始 结束

名称 起止框 输入、输出框 处理框

输入
输出 条件

判断框 流线 连接圆

算法的描述
自然语言描述法
流程图描述法

例1:编写一个计算任意三角形面积的程序。

开始

program sjx;
输入a,b

var a,b,s:real; begin readln(a,b); s:=a*b/2;

算 法

s=a*b/2

输出s

writeln(‘s=‘,s)
end.

结束

算法的三种基本结构

顺序结构

分支结构

循环结构

条件 成 立

不成立

不成立 条件 成 立 循环体

编写 FreePascal 程序的过程

上机练习
1、上机调试计算三角形面积的程序 输入: 3 4 输出: s=6.000000000000000E+000 思考题: 1、将程序改成计算梯形面积的程序 2、将程序改成计算圆面积的程序

推荐书籍

第 二 讲 Pascal基本语法

例2:编写一个计算任意圆周长的程序。

分析问题

利用圆周长公式 圆周长=2×∏×R 求圆周长

设 计 算 法

1)将圆半径 R 输入计算机 2)计算 2×∏×R 的值 3)输出计算值 var t,r:real; program yzc; const pi=3.1415926;

编 写 程 序

begin readln(r); t:=2*pi*r; writeln(‘t=‘,t:0:6)

end.

Pascal中的字符 保留字
Pascal语言中有固定意义的一批英文单词或简写,共有36个,如:

program,var等。
program yzc; const pi=3.1415926; var t,r:real;

begin
readln(r); t:=2*pi*r; writeln(‘t=‘,t:0:6) end.

标识符
标识符是用来说明程序、常量、变量、过程、函数、文件和类型等 名称的符号(它必须以英文字母或下划线开头,后接英文字母、数字、

下划线的字符串,标识符中的英文字母大小写都可以,都是一样的)

标准标识符
是系统预先定义好的标识符,具有 确定的含义,可以分为:标准常量、标 准类型、标准文件、标准函数、标准过

program yzc;
const pi=3.1415926; var

程5大类。

t,r:real;
begin readln(r); t:=2*pi*r;

自定义标识符
是由程序员自己定义的标识符,它

们不能与标准标识符或保留字同名,以
免发生错误。

writeln(‘t=‘,t:0:6)
end.

例3:判断下面的自定义标志符是否正确。

Start Begin Pi 3th ∏ F&j 没有以英文字母开头 不是英文字母数字或下划线 与保留字同名

使用了非法符号&

Name_of_school

Pascal中的数据
Pascal中的数据是指计算机能够识别的数值及字符,数据有三个要素:数据类 型、数据范围、能参与的运算。

Pascal 中的常用数据类型

整型
名称 字节型 短整型 整型 字型 长整型
64位长整

类型标识符
byte shortint integer word longint int 64

取值范围
0~255 -128~+127 -32768~+32767 0~65536 -2147483648~+2147483647 9223372036854775808~+9223372036854775 807



可用运算:+、-、*、/、div(整除)、mod(取余)、关系运算 div: 取两整数相除所得的商
5 div 2= 2 5 div (-2)= -2 (-5) div 2= -2 (-5) div (-2)= 2 Div:同号为正,异号为负

mod: 取两数相除所得的余数
5 mod 2= 1 5 mod (-2)= 1 (-5) mod 2= -1 (-5) mod (-2)= -1 mod:符号与被除数相同

注意:整数类型的数据在进行“+ - * div mod”运算时结果一定是整数,而
在进行“/”运算时结果一定是实数,并且时常采用“尾数+指数”这种科学记数法 的形式进行输出。 尾数 指数

2/2=1.00000000000000E+000
25/2=1.25000000000000E+001

实型
名称 实数型 单精度型 双精度型 扩展型 十进制型 类型标识 符
real single double extende d comp

取值范围 -1.7×1038..-2.9×10-39 和 2.9×10-39..1.7×1038

可用运算:+、-、*、/、关系运算
注意:实数类型的数据进行所有运算时结果都是实数。 1.5+1.5=3.00000000000000E+000 1.5*2=3.00000000000000E+000

布尔型(boolean)
取值范围:只有两种值 true 和 false
可用运算:and(与) or(或) not(非) xor(异或) 逻辑运算规则
A true true false false B true false true false not A false false true true A and B true false false false A or B true true true false A xor B false true true false

例4:如何表示语文成绩x和数学成绩y都大于90分。

(x>90) and (y>90)

字符型
类型标识符:char
取值范围:ASCII码字符集

可用运算:> <

= >=(大于等于) <=(小于等于) <>(不等于)

’a’ > ’b’ ’a’ = ’b’ ’a’ < ’b’

false

false
true

在Pascal中字符型数据必须用一对单引号括起来

Pascal中的数据表示方式 常量
常量即程序中其值不能改变的量。可分为普通常量和符号常量两种。符号常 量在使用前要先在程序说明部分声明。 符号常量声明格式 const 标识符=常量值; (注意:字符串常量必须用’ ’括起来) (常量数据的类型由常量值确定不需要声明)

program yzc;

const
pi=3.1415926; var t,r:real; begin readln(r); t:=2*pi*r;

writeln(‘t=‘,t:0:6)
end.

例4:判断下面的符号常量定义有哪些错误。

const m=100; n,p=50; s=100 or 55; t:=true; m=20;
1)

m定义了两次,应去掉1个

2)
3) 4)

若n,p都是50,应写成n=50;p=50;
S不能表示100又表示55,值必须唯一 t:=true不符合语法,应写成 t=true

变量
变量即程序中其值可以改变的量,主要用于存储数据。变 量在使用前要先在程序说明部分声明,变量的值主要通过赋值 语句获得。
program yzc; const pi=3.1415926; var t,r:real;
(变量名要用一个合法的标识符来表示) 变量声明格式: Var 标识符列表:类型名;

begin readln(r); t:=2*pi*r; writeln(‘t=‘,t)

end.

例5:判断下面的变量声明中哪些是非法的。

var x1=integer; x2,x3:real; ch1:’a’; x2:boolean;
x1=integer 不符合语法格式,应写成下 x1:integer

1)

2)
3)

ch1 的变量类型不符合要求
x2 定义了两次,应去掉一个

Pascal中的函数
什么是函数? 对于一个或多个原始数据,若按照某一法则可求得一个结果,称这种 功能为函数。这儿的原始数据称为参数,结果称为函数的返回值。每 个函数都有名称,称为函数名。 Pascal中有两种函数: 标准函数:是Pascal已经定义的、程序员可以直接在程序中使用的函数

自定义函数:程序员在程序中自行定义的函数
注意:函数都有返回值

函数调用格式:函数名(参数1,参数2,…)

常用标准函数
函数
abs(x) sqr(x) sqrt(x) trunc(x)

含义 求x的绝对值 求x的平方 求x的平方根 求x的整数部分

参数类型 整型或实型 整型或实型 整型或实型 实型

返回值类型 与x相同 与x相同 实型 整型

举例
abs(-3)=3 sqr(5)=25 sqrt(100)=10.0 trunc(1.99)=1

frac(x)
int(x) round(x) random( x)

求x的小数部分
求x的整数部分

实型
实型

实型
实型 整型 整型

frac(1.34)=0.3 4
int(1.99)=1.0 round(1.5)=2 random(10)为0 到9之间的一个随机

求最接近x的整数 实型 产生0到x-1之间 整型 的随机数



Pascal中的运算符
种类 算数运算 关系运算 布尔运算 集合运算 赋值运算 运算符 + - * / div mod < <= > >= = <> in and or not xor + - * :=

优先级 小括号( )
同级运算从左到右 不同级运算从高到低 括号内运算优先



函数
+(正号) -(负号) not * + < / <= div or > mod xor >= = <> in and


Pascal中的表达式
在程序中,由运算对象(常量,变量,函数)、运算符 和括号按一定次序组成的有意义的式子称为表达式,它等价 于数学中的代数式。
注意: 1)乘号*不能省略,例如a*b不能写成ab

2) 不允许连续出现两个运算符,例如a/(-b)不能写成a/-b
3) 表达式中只能用小括号(),且必须成对出现 4)代数式转换成表达式,必要时要添加括号,以保证运算顺序的正确

例6:将下列代数式转换为pascal表达式。

(1/2)*a*b*c

a+b/(c+d)

1/sqr(n)*sqr(m/2) 或 1/(n*n)*m/2*m/2

y+sqrt(y*y+1)

上机练习
1、输入圆的半径,计算它的周长和面积

2、输入x的值,分别输出x2,x3,x4,x2+x3+x4的值

3、从键盘输入一个年份,并判断是否是闰年。 判定公历闰年遵循的一般规律为: 四年一闰,百年不闰,四百年再闰.
program runnian; var year:integer;

begin
write('please input year:'); readln(year); if__________________________________then

writeln(year,' is a leap year!')
else writeln(year,' is a non-leap year!'); end.

第 三 讲 顺序结构语句

顺序结构

赋 值 语 句(:=) 格 式 变量标识符:=表达式;
功 能
Program yzc; Const pi=3.1415926;

先计算右端表达式的值,然后将 该值赋给变量。
表达式计算结果

Var
t,r:real; Begin readln(r); t:=2*pi*r; writeln(‘t=‘,t:0:6) End.

变量

举例
运行下面的程序,屏幕上的输出结果是什么?
program p3_1; var a,b:integer; begin
a 1 1 3 3 2 输出: a=2 b=1 2 2 1 1 b

a:=1;
b:=2; a:=a+b; b:=a-b; a:=a-b; writeln(‘a=‘,a,’ b=‘,b) end.

注 意
1)“ := ”为赋值号,其左边为合法的变量标识符,右 边可以是常数、常量,变量,函数,或者通过运算符将他们 连接而成的表达式。例如:a:=b+1; 例如:b+1:=a 这种写法是错误的。 2)在Pascal中“ = ”号是关系运算符,用于判断符号 两边是否相等,或用于声明符号常量; 例如:const pi=3.1415 3)赋值语句一次只能给一个变量赋值;例如:a:=3 例如:语句 a:=b:=3 编译时会出错。

程序举例
下面程序的输出结果是什么?
program p3_2; var a,b,t:integer; begin

a:=3;
b:=4; t:=a; a:=b; b:=t; writeln(‘a=‘,a,’ b=‘,b) end.
输出: a=4 b=3

三变量交换法

赋值语句的常用用法 1)交换:t:=a; a:=b; b:=t;

2)计数:a:=a+1; b:=b-1;
(也可以用计数过程 inc(a) 和 dec(b))

3)积累运算:a:=a+x; b:=b*x;

输出语句(write,writeln)
功能:将程序的处理结果,传递给外界(屏幕,文件或打印机) 格式: 格式1:write(输出项列表); 格式2:writeln[(输出项列表)];

Program yzc; Const

pi=3.1415926;
注 意 Var t,r:real;

1)输出项可以是变量、常量或表达式,各 Begin 输出项之间用,号隔开。 readln(r); 2)write与writeln的区别在于write输出 t:=2*pi*r; 所有输出项后不换行,而writeln要换行。 writeln(‘t=‘,t:0:6) 3)write语句必须有输出项,writeln可以 End. 没有输出项。

举例 下面程序的运行的结果是什么?如果将write语句改为 writeln语句结果会有什么变化?
program p3_3; var

a,b,c,d:integer;
begin a:=3; b:=128; c:=36; d:=8; write(a,’+’,b,’=’,a+b,’ write(c,’-’,d,’=’,c-d) end. ’);

输出: 3+128=131 36-8=28

用writeln输出:
3+128=131 36-8=28

用场宽控制输出语句的输出格式
输出语句在输出数据时,数据所占列数称作“场宽”,场宽分为标准场 宽,自定义场宽两种。 1)输出语句不加冒号时使用标准场宽输出,标准场宽除实型外,都以 数据的实际长度为标准场宽,实型数据标准场宽为17。例如:
write(‘hello’) 的输出结果为:hello write(-123.4) 的输出结果为:-1.234000000000000E+002

17位
-1.234000000000000e+002=-1.234×102 var a:real; begin a:=123.4; writeln(a);

1.2340000000000E+002 15位

2)输出语句加冒号时使用自定义场宽输出,自定义场宽又分为单场宽 和双场宽两种。双场宽只适用于实型数据。
program p3_4; const a=’hello’; var b:real; begin b:=3.1415; writeln(a:8); writeln(a:4); writeln(b:0:6); writeln(b:6:2); end.

输出:

规 则 1)场宽大于输出项宽度时,左留空,右对齐 2)场宽小于输出项宽度时,按实际输出项宽度输出 3)在双场宽中如果小数位场宽大于实际小数位,末位补0,如果小数位场宽小 于实际小数位,则对多余位数进行四舍五入,但数据精度不变。

举例
下面程序的运行的结果是什么?
program p3_4; Const s=’Let us begin’; pi=3.14 var a,b:real; begin writeln(s:20); a:=2*pi;

writeln( ’a=’ , a :4:1);
writeln( ’a=’ , a: 2:2); writeln( ’a=’ , a: 0:2); end.

输 入 语 句(read,readln)
格 式 格式1:read(变量表); 格式2:readln[(变量表)]; Program yzc; Const pi=3.1415926;

Var
功 能 t,r:real; Begin readln(r); t:=2*pi*r; writeln(‘t=‘,t:0:6)

从外界读入数据给变量。当程序 运行到输入语句时,程序处于等待状 态,等待用户从键盘输入数据,然后 将数据依次赋值给变量表中的各个变 量。

End.

注 意
1)变量表可以是单个变量,也可以是多个用逗号隔开的变量。这些变 量必须在说明部分说明,可以直接输入的变量类型有:整型、实型、字符 型和字符串型。

read(a) ; read(b) ; read(c) ; readln(a) ;

read(a,b,c);

readln(a,b,c);

readln(b) ;
readln(c) ;

2)read与readln的区别在于在处理一行中的多余数据时, read将一行中的多余数据留给下一条输入语句,而readln则忽 略这行中的多余数据。
program p3_5; var a,b,c,d:integer;

输入: 1 2 3 4 输入: 1 2 3 4

begin
read(a,b); read(c,d); end.

writeln(‘a=‘,a,’ b=‘,b,’ c=‘,c,’ d=‘,d)

将read语句全部改为readln语句结果有什么不同?

3)Readln语句可以没有变量表,此时该语句的作用就 是等待读入一个回车换行符。可用于暂停程序
Program yzc;

Const
pi=3.1415926; Var t,r:real;

Begin
readln(r); t:=2*pi*r;

writeln(‘t=‘,t:0:6)
readln; End.

4)在输入数值型数据时,数据之间用空格或回车分隔, 最后一定要有一个回车,表示输入结束;而在输入字符型数据 时,数据间不能用空格或回车进行分隔,因为计算机默认空格 、回车也是字符。
program p3_5; var a,b,c,d:char; begin read(a,b,c,d);

输入样例1:g i r l 输入样例2:girl

writeln(‘a=‘,a);
writeln(’b=‘,b); writeln(’c=‘,c);

writeln(’d=‘,d)
end.

顺序结构程序设计实例
【数字分离问题】 小明刚学会1位数字的加法运算,小明妈妈想考核小明的运算能力,于 是每次给一个四位整数,让小明求各位数字和。小明妈妈让你帮她写一个 程序,能随机产生一个四位整数,同时给出各位数字和。这样她能一边做 自己的事,一边考核小明。 输入:随机产生一个四位整数 输出:产生的整数和各位数字和 1)随机产生一个四位数存放在num变量中 算 法

2)将num变量中的数各位数字拆分出来存放在a,b,c,d四个变量中
3)求各位数字之和S

4)输出num和s

program p3_6; var num,a,b,c,d,s:integer; begin randomize; num:=1000+random(9000);
//随机产生一个四位数

a:=num mod 10;
b:=num div 10 mod 10; c:=num div 100 mod 10;

d:=num div 1000;
s:=a+b+c+d; writeln(num); writeln('s=',s); readln end.

【时间戳问题】 某国家安全局获得了一份珍贵的材料,上面记载了一个即将进行的恐 怖活动的一切。不过,国家安全局人员却没法直接得到实施的时间!材料 上的时间使用的是Linux时间戳,即从1970年1月1日0时0分0秒开始到该时 刻总共过了多少秒。现在希望你帮助完成此事,给你一个时间戳,你要写 个程序计算出恐怖活动在那一天实施。(这里为了简单起见,规定一年12 个月,每个月30天) 输入:输入一个整数n(0≤n≤21474836),表示从1970年1月1日0时 0分0秒开始到该时刻过了n秒 输出:一行三个整数y,m,d,表示恐怖活动在y年m月d日实施 1)输入n的值 算 法 2)y=n div 31104000+1970 3)m=n mod 31104000 div 2592000+1 4)d=n mod 31104000 mod 2592000 div 86400+1

program p3_7; const years=31104000; months=2592000; days=86400;
输入: 1304324570
输出: 2011/12/7

var
n:longint; y,m,d:integer; begin readln(n); y:=n div years+1970; m:=n mod years div months+1;

d:=n mod years mod months div days+1;
writeln(y,'/',m,'/',d); readln

end.

【分糖果问题】 某幼儿园里有5个小朋友,编号为1,2,3,4,5,他们按自己的编号 围坐在一张圆桌旁。他们身上都有若干糖果,现在他们做一个分糖果游戏 。从1号小朋友开始,将他的糖果平均分成3分(如果有多余的,则他将多 余的糖果吃掉),自己留一份,其余2份分给他相邻的两个小朋友。接着2 号,3号,4号,5号小朋友也这样做。问一轮后每个小朋友手上分别有多少 糖果? 1)输入5个小朋友糖果的初值a,b,c,d,e 算 法

2)第一次 a=a div 3
3)第二次 b=b div 3 4)第三次 c=c div 3 5)第四次 d=d div 3

b=b+a
c=c+b d=d+c e=e+d

e=e+a
a=a+b b=b+c c=c+d

6)第五次 e=e div 3
7)输出a,b,c,d,e

a=a+e

d=d+e

program p3_7;
var a,b,c,d,e:integer; begin readln(a,b,c,d,e); a:=a div 3;b:=b+a;e:=e+a; b:=b div 3;c:=c+b;a:=a+b;

c:=c div 3;d:=d+c;b:=b+c;
d:=d div 3;e:=e+d;c:=c+d; e:=e div 3;a:=a+e;d:=d+e;

writeln(a,' ',b,' ',c,' ',d ,' ', e);
readln end.

上机练习
program ss; var a,b:integer; begin a:=3;b:=128; _____________

1、给程序添加四条输出语句, 输出a+b的竖式表达式? 输出样例: 3 + 128 -----131

_____________
_____________ _____________ end.

2、编写一个能将任意的3位数整数的个位、十位、百位加起 来的程序? 输入样例: 693 输出样例: 6+9+3=18

3、输入一个时间的秒数,分别将其换算为下述时间单位输出: ×小时 ×天 ×星期 输入样例:

604800
输出样例: 604800s=168h=7d=1w

4、笑笑有一些糖果。第一天,他吃了总数的一半多一颗; 第二天,他又吃了剩下糖果的总数的一半多一颗;第三天, 他又吃了剩下糖果的总数的一半多一颗。结果发现,剩下的 糖果数量恰好是他的幸运数字。你能算出笑笑原来一共有多 少糖果吗?
输入样例: 12 输出样例: 110

第 四 讲 选择结构语句
分支结构

条件 成 立

不成立

【判断奇偶数】
从键盘输入一个正整数,判断并输出它是奇数还是偶数。
begin readln(x)
program p4_1; var x:integer; begin readln(x); if x mod 2=1 then writeln('jishu') else writeln('oushu'); end.

x mod 2=1

false

true
writeln(’jishu’)

writeln(’oushu’)

end

if 语句
格 式1: if 条件表达式 then 语句1 else 语句2; 常用写法
布尔表达式 false

if 条件表达式 then 语句1 else 语句2; 格 式2:

true 语句1 语句2

布尔表达式

false

if 条件表达式 then 语句;

true 语句1

布尔表达式
布尔表达式是指值为布尔型(即:true 或 false)的表达式,它可 以是布尔型常量、变量以及关系表达式和逻辑表达式等。例如:
100>99 2*3<>1*6 ’a’>’b’ x mod 2=1 (x>=60) and (x<=90) (year mod 4=0) and (year mod 100<>0) or (year mod 400=0) true false fasle

例2:变量a的值为100,变量b的值为20,请写出以下表达式的结果。
a<>b true false false false false true false true

a<=(b+20) (a>=100) and (b>20)

(a=b) and (b>10) (a=b) or (b<10) (a<200) or (b=20)

not((a>200) or (b=20)) not((a>200) and (b=20))

【判别三角形】 从键盘输入三根小木棒的长度,判断能否用它搭出一个三角形。
begin
program p4_2; var a,b,c:integer; begin readln(a,b,c); if (a+b>c) and (a+c>b) and (c+b>a) then writeln(’OK’); end.

输入a,b,c

false

两边之和>第三边
true

输出‘OK‘

end

【数字排序】 从键盘输入a,b两个整数,并且按从小到大的顺序输出
program p4_3; var a,b,t:integer; begin readln(a,b); if a<b then writeln(a,b) else writeln(b,a); end.

begin

输入a,b
false a<b true 输出a,b 输出b,a

end

方法二
program p4_4; var a,b,t:integer; begin readln(a,b); if a>b then begin t:=a; a:=b; b:=t; end; writeln(a,b); end. 当then或else后面跟多条语句时要 使用begin和end将多条语句括起来,且 每条语句后都要用;号结束。

begin 输入a,b false

a>b true
交换a,b

输出a,b
end

简单语句和复合语句
在Pascal中,语句分为简单语句和复合语句两大类;所谓简单语句, 又称为基本语句,是指不能再分解的语句;而复合语句是由若干其他语句 所组成的语句,这些语句一般要通过begin和end进行复合。

简单语句
write('please input year:'); if

复合语句
a>b then begin c:=a; a:=b; b:=c;

end;

【三数排序】 从键盘输入a,b,c三个整数,并且按从小到大的顺序输出.
1)输入a,b,c 2)如果a<b<c,则输出a,b,c; 3)如果a<c<b,则输出a,c,b; 4)如果b<a<c,则输出b,a,c;
program p4_5; var a,b,c:integer; begin readln(a,b,c); if (a<b) and (b<c) writeln(a,b,c); if (a<c) and (c<b) writeln(a,c,b); if (b<a) and (a<c) writeln(b,a,c); if (b<c) and (c<a) writeln(b,c,a); if (c<a) and (a<b) writeln(c,a,b); if (c<b) and (b<a) writeln(c,b,a); end.

then then

then
then then then

5)如果b<c<a,则输出b,c,a;
6)如果c<a<b,则输出c,a,b; 7)如果c<b<a,则输出c,b,a;

方法二
begin 输入a,b,c a>b false program p4_5; var a,b,c,t:integer; begin readln(a,b,c); if a>b then begin t:=a; a:=b; b:=t; end; if a>c then begin t:=a; a:=c; c:=t; end; if b>c then begin t:=b; b:=c; c:=t; end; writeln(a,b,c) end.

true

交换a,b a>c false

true

交换a,c b>c false

true

交换b,c 输出a,b,c end

方法三

begin 输入a,b,c

true true

a<b
b<c

false false a<c true false 输出c,a,b false a<c true 输出b,a,c false 输出b,c,a

c<b

输出a,b,c

true 输出c,b,a

输出a,c,b

end

条件嵌套

program p4_5; var a,b,c:integer; begin readln(a,b,c); if a<b then if b<c then writeln(a,b,c) else if a<c then writeln(a,c,b) else writeln(c,a,b) else if c<b then writeln(c,b,a) else if a<c then writeln(b,a,c) else writeln(b,c,a); end.

条 件 嵌 套

case 语句
格式: case 表达式 of 例如: case a of 常量表1:语句1; 常量表2:语句2; 常量表3:语句3;

可以是复合语句

……
常量表n:语句n; [else 语句n+1]

1,3,5 : writeln(’Odd’); 2,4,6 : writeln(’Even’); else end; writeln(’Out of range’);

end;

【输出计算式】 输入两个整数和一个算术运算符后,输出其运算结果 输入: program p4_6; 3 9 var + a,b:integer; 输出: op:char; 3+9=12 begin
算法 readln(a,b); readln(op); 1)输入两个数; case op of 2)输入运算符; '+':writeln(a,'+',b,'=',a+b); '-':writeln(a,'-',b,'=',a-b); 3)根据运算符进行判断: '*':writeln(a,'*',b,'=',a*b); 如果运算符为“+”,则输出两数的和 '/':if b<>0 then 如果运算符为“-”,则输出两数的差 writeln(a,'/',b,'=',a/b:0:2) 如果运算符为“*”,则输出两数的积 else writeln('chu shu wei 0!'); 如果运算符为“/”,需要判断除数是 否为0,不为0则输出商,否则输出错误信 else writeln('yun suan fu cuo wu!'); 息 end; end. 如果运算符为其它符号也输出错误信息

【等级评价】 现在学生档案中经常采用等级评价,于是李老师想将百分制成绩转化为等级。李老师的成 绩单上的成绩都是整数,他约定等级与百分制的对应关系如下: A:90~100; B:80~89; C:60~79; D:0~59; 请编程将任意输入的分数转化为等级。 输入:93 输出:A program p4_7; var 算法 x:integer; 1)输入分数X; begin readln(x); 2)根据x div 10的结果进行判断: case x div 10 of 值为9,10,则输出A; 9,10 : writeln(‘A'); 8 : writeln(‘B'); 值为8,则输出B; 6,7 : writeln(‘C'); 值为6,7,则输出C; 0,1,2,3,4,5 : writeln(‘D'); 值为0,1,2,3,4,5,则输出D; else writeln(‘fen shu cuo wu!'); 其它值则输出错误信息 end; end.

【数表读数】 最近柯南被卷进阿笠博士发明的一个无聊游戏中,阿笠博士画了一个9×9的靶型数表,每 一个格子内都标有一个1到5之间的整数作为该格子的价值,而且,价值的分布很有规律,如下 图所示。现在博士要考柯南某行某列格子的价值是多少。于是柯南想请你帮他编个程序回答博 士的问题。
算法
1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 1

1)输入行号i和列号j 2)第1行和第9行全是1 3)第2行和第8行,除第1列和第9列为1,其余全 是2 4)第3行和第7行,除第1列和第9列为1,第2列 和第8列为2,其余全是3 5)第4行和第6行,除第1列和第9列为1,第2列 和第8列为2,第3列和第7列为3,其余全是4 6)第5行,1、9列为1,2、8列为2,3、7列为 3,4、6列为4,第5列为5。

1 2 3 3 3 3 3 2 1
1 2 3 4 4 4 3 2 1 1 2 3 4 5 4 3 2 1 1 2 3 4 4 4 3 2 1 1 2 3 3 3 3 3 2 1 1 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1

program p4_8; var i,j:integer; begin readln(i,j); case i of 1,9:writeln(1); 2,8:if (j=1) or (j=9) then writeln(1) else writeln(2); 3,7:case j of 1,9:writeln(1); 2,8:writeln(2); else writeln(3); end; 4,6:case j of 1,9:writeln(1); 2,8:writeln(2); 3,7:writeln(3); else writeln(4); end; else case j of 1,9:writeln(1); 2,8:writeln(2); 3,7:writeln(3); 4,6:writeln(4); else writeln(5); end; end; end.

1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 1 1 2 3 3 3 3 3 2 1 1 2 3 4 4 4 3 2 1 1 2 3 4 5 4 3 2 1 1 2 3 4 4 4 3 2 1 1 2 3 3 3 3 3 2 1 1 2 2 2 2 2 2 2 1

1 1 1 1 1 1 1 1 1

方法2
1)由于这个数表中的数值是关于第5行和第5列以及中心点对称的
因此有: [i,j]的值=[10-i,j]的值=[i,10-j]的值=[10-i,10-j]的值 因此,表中的任意一个点都可以映射到左上角的区域内,即当i>5 或j>5时就用10-i或10-j将其转化为左上角的点,我们只要知道左上 角区域内每个点的值,就知道了表中所有点的值了,这样问题的规模 就缩小为原来的1/4了。

1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 1 1 2 3 3 3 3 3 2 1 1 2 3 4 4 4 3 2 1 1 2 3 4 5 4 3 2 1 1 2 3 4 4 4 3 2 1 1 2 3 3 3 3 3 2 1 1 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1

2)在左上角第1行和第1列都是1,因此: i=1 or j=1 时,[i,j]一定为1; 3)如果不在第1行和第1列,则: 只要 i=2 or j=2 时,[i,j]一定为2; 4)如果不在第1,2行和第1,2列,则: 只要 i=3 or j=3 时,[i,j]一定为3; 5)如果不在第1,2,3行和第1,2,3列,则: 只要 i=4 or j=4 时,[i,j]一定为4; 6)如果不在第1,2,3,4行和第1,2,3,4列,则:

只要 i=5 or j=5 时,[i,j]一定为5;

program p4_8; var i,j:integer; begin readln(i,j); if i>5 then i:=10-i; 将点映射到左上角 if j>5 then j:=10-j; if (i=1) or (j=1) then writeln(1) else if (i=2) or (j=2) then writeln(2) else if (i=3) or (j=3) then writeln(3) else if (i=4) or (j=4) then writeln(4) else writeln(5); end.

1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 1

1 2 3 3 3 3 3 2 1
1 2 3 4 4 4 3 2 1 1 2 3 4 5 4 3 2 1 1 2 3 4 4 4 3 2 1 1 2 3 3 3 3 3 2 1 1 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1

算法还能优化吗?

[i,j]的值(左上角区域)就是 i与j的最小值
program p4_8; var i,j:integer; begin readln(i,j); if i>5 then i:=10-i; if j>5 then j:=10-j; if i<j then writeln(i) else writeln(j); end.

上机练习
【超市打折】 超市为了促销,进行打折销售。优惠条件为:超过50元,打9.5折,超过100元,打9折 ;超过200元,打8折;超过300元,打7折;当购物s元时,实际付费是多少呢? 输入格式:一个实数,表示应付费 输出格式:一个实数,表示实际付费 输入样例:120 输出样例:108.00 输入样例:220.5 输出样例:176.40
【天数计算】 输入年、月,输出该月的天数。 输入格式:2个整数,表示年和月 输出格式:1个整数,表示天数 输入样例:2000 2 输出样例:29 输入样例:2011 3 输出样例:31

【判断直角三角形】 从键盘输入三角形的三边长度,然后根据三边长度判断该三角形是否为直角三角形。 输入格式:3个整数,表示三边长度 输出格式:1个字符串,表示是否为直角三角形 输入样例:3 4 5 输出样例:Right Triangle! 输入样例:-3 4 5 输出样例:No Triangle! 输入样例:4 4 5 输出样例:Triangle!

【数字排序】 从键盘输入4个整数,并且按从大到小的顺序输出. 输入格式:4个整数,表示要排序的数 输出格式:4个整数,表示排序后的数 输入样例:3 4 5 6 输出样例:6 5 4 3 输入样例:27 48 32 3 输出样例:48 32 27 3 【车牌号码】 一起交通事故后,有人记住了肇事车辆的车牌后四位数字:前两位数字相同,后两位数字也相同。还 有一个数学家发现这四位数是一个完全平方数。现在,交警要根据这两条线索判断其他目击者提供的号码 是否有价值。 输入格式:一个四位整数 输出格式:一个字符串,Yes或No 输入样例:7744 输出样例:Yes 输入样例:3322 输出样例:No 【买笔问题】 小林有x(x≥12)元钱,准备全部购买笔。店里有8元、7元、6元、5元、4元一支的四种笔。请编程 ,在8元一支的笔必须购买一支的前提下,使购买的笔数量最多,而钱又恰好用完,输出此时购买的各种 笔的数量。 输入格式:一个整数,表示总钱数 输出格式:共5行,每行表示一种笔的价格和数量 输入样例:69 输出样例: 8 yuan:1 7 yuan:0 6 yuan:0 5 yuan:1 4 yuan:14 max:16

第 五 讲 循环结构语句

【打印星号】
在屏幕上输出100个星号,每行输出10个。
begin

输出一行10个*

输出一行10个*
输出一行10个* 输出一行10个* 输出一行10个* 输出一行10个* 输出一行10个* 输出一行10个* 输出一行10个* 输出一行10个*
end

program p5_1; begin writeln(‘**********’); writeln(‘**********’); writeln(‘**********’); writeln(‘**********’); writeln(‘**********’); writeln(‘**********’); writeln(‘**********’); writeln(‘**********’); writeln(‘**********’); writeln(‘**********’); end.

【方法2】让输出10个*号的语句重复执行10次
begin i=1 i<=10 true false

输出一行10个* i=i+1

program p5_1; var i:integer; begin for i:=1 to 10 do writeln(‘**********’); end.

end

false 循环条件 true 循环体语句

计数循环(for)语句
计数循环是一种已知循环次数的循环,根据计数的方式分为递增型循环和递减型循环

递增型for循环 格式: for 循环控制变量:=初值 to 终值 do 循环体语句;

递减型for循环 格式: for 循环控制变量:=初值 downto 终值 do 循环体语句;

执行过程 先将初值赋值给循环控制变量;然后与 终值进行比较,如果小于或等于终值时执行 循环体语句;然后使循环控制变量自己加1; 然后再重复上述过程直到大于终值时退出循 环。

执行过程 先将初值赋值给循环控制变量;然后与 终值进行比较,如果大于或等于终值时执行 循环体语句;然后使循环控制变量自己减1; 再重复上述过程直到小于终值时退出循环。

For i:=5 to 10 do write(i); 也可以写成:for i:=5 to 10 do write(i); For i:=10 downto write(i); 5 do

运行结果为:5678910

运行结果为:1098765

也可以写成:for i:=10 downto 5 do write(i); For i:=10 to write(i); 5 do 运行结果为:无

如果递增型循环中初值一开始就大于终值,则循环体语句一次也不执行,递 减型循环中初值一开始就小于终值,则循环体语句也不执行。 For i:=‘a’ to ‘k’ do write(i);

运行结果为:abcdefghijk

初值和终值的类型必须相同,且必须为顺序类型(如整型、字符型等)。

注意事项
1)循环体中可以有多条语句,但必须用begin和end括起来组成复合语句。 例如:在屏幕上输出100个星号,每行输出10个。 program p5_1; var i:integer; begin for i:=1 to 100 do begin write(‘*’); if i mod 10=0 then writeln; end; end. 2)循环变量的初值和终值可以是常量、变量或表达式。 例如: n:=10; for i:=2*n to n*n do …

程序举例 1、计算1+2+3+…+100的结果。
【问题分析】
可以把运算式分解为100步加法运算 1) 1 + 2 = 3 2) 3 + 3 = 6 3) 6 + 4 = 10 … s i program p5-2; var s,i:integer; begin s:=1; for i:=2 to 100 do s:=s+i; writeln(‘s=‘,s) end. program p5-2; var s,i:integer; begin s:=0; for i:=1 to 100 do s:=s+i; writeln(‘s=‘,s) end.

s

s=s+i

程序举例 1、计算1+22+32+…+1002的结果。
Program p5-3; Var s,i:integer; begin s:=0; for i:=1 to 100 do s:=s+i*i; writeln(‘s=‘,s) end.

【问题分析】 可以把运算式分解为100步加法运算 1) 0 2) 1 3) 5 + 12 = 1 + 22 = 5 + 32 = 14 …… s i*i s

4) 14 + 42 = 30

s=s+i*i

3、计算12+ 32 + 52 +…+ 992
【问题分析】
可以把运算式分解为50步加法运算 1) 0 2) 1 3) 10 4) 35 s + + + + …… s (2*i-1)*(2*i-1) 12 = 1 32 = 10 52 = 35 72 = 84

Program p5-4; Var s,i:integer; begin s:=0; for i:=1 to 50 do s:=s+(2*i-1)*(2*i-1); writeln(‘s=‘,s) end.

(1≤i≤50)

s=s+(2*i-1)*(2*i-1)

对比三段程序中循环变量的作用 program p5-2; var s,i:integer; begin s:=0; Program p5-4; for i:=1 to 100 do Var s:=s+i; s,i:integer; writeln(‘s=‘,s) begin s:=0; end. for i:=1 to 50 do 1)用循环变量控制循环次数和数列本身值 s:=s+(2*i-1)*(2*i-1); Program p5-3; writeln(‘s=‘,s) Var end. s,i:integer; begin 3)用循环变量控制循环次数和数列项数 s:=0; for i:=1 to 100 do s:=s+i*i; writeln(‘s=‘,s) end.
2)用循环变量控制循环次数和数列局部值

程序举例
【麦子问题】 相传古印度宰相达依尔是国际象棋的发明人,有一次,国王因为他的贡献要奖 励他,问他想要什么。达依尔说:“只要在国际象棋棋盘上(共64格)摆上这么些 麦子就行了:第一格一粒,第二格两粒,…后面一格的麦子总是前一格麦子数的两 倍,摆满整个棋盘,我就感恩不尽了。”国王一想,这还不容易。你知道需要多少 麦子吗?(假设1吨麦子=108粒麦子) 输入格式:一个整数,表示棋盘上的格子数 输出格式:一个实数,保留2位小数。表示麦子的吨数

输入样例:30
输出样例:10.74

【问题分析】 总麦子数为:1+21+22+23+…+2n-1 可以把运算式分解为n-1步加法运算式 1) 1 + 21

20 * 2
21 * 2 22 * 2 n

输入样例:40 输出样例:10995.12

2) 3 + 22
3) 7 + 23 …… s n

s=s+n

n=n*2

program gw; var s,n:int64; i,m:integer; begin readln(m); s:=1;n:=1; for i:=2 to m do begin n:=n*2; s:=s+n; end; writeln(s/100000000:0:2); end.

program gw; var s,n:int64; i,m:integer; begin readln(m); s:=0;n:=1; for i:=1 to m do begin s:=s+n; n:=n*2; end; writeln(s/100000000:0:2); end.

【素数问题】 从键盘输入一个正整数n(1<n<2000000000),如果是素数输出“yes”否则输出“no”
【问题分析】 如果n不能被整数i(2≤i≤n-1)整除则i为素数,否则为非素数。 Program p5_6; Var n,i:longint; f:boolean; begin readln(n); f:=true; for i:=2 to n-1 do if n mod i=0 then f:=false;

if f then writeln(‘Yes’) else writeln(‘No’)
end.

【问题优化】
由于约数总是成对出现的(i是n的约数,n div i也是n的约数)如:100的约数有 2和50,4和25,5和20,10和10等,所以循环的终值可以优化成“trunc(sqrt(n))”

Program p5_6;

Var
n,i:longint; f:boolean; begin readln(n); f:=true; for i:=2 to trunc(sqrt(n)) do if n mod i=0 then f:=false; if f then writeln(‘Yes’) else writeln(‘No’) end.

上机练习
1、编程计算1-1/2+1/3-1/4+...-1/100 输入样例:无 输出样例:0.688172

2、在屏幕上输出100个星号,每行输出10个。并将其构成平行四边形,如图所示: ********** ********** ********** ********** ********** ********** ********** ********** ********** **********

上机练习
3、输出费波那契数列的前n项(n<30),该数列的规则为前两项数字之和等于 第三项。例如:该数列的前10项为:0 1 1 2 3 5 8 13 21 34。输出时每行 输出8个数, 输入格式:一个整数,表示n 输出格式:n个整数,表示斐波那契数列,每行输出8个整数 输入样例:10 输出样例: 0 1 1 2 3 5 8 13 21 34

上机练习
4、编写程序找出所有的水仙花数,所谓水仙花数即满足下列条件的数。 abc = a3+b3+c3 例如:153=13+53+33因此153就是水仙花数。 输入样例:无 输出样例:153 370 371 407 5、猴子摘了一堆枣子,每天吃掉当天枣子数的一半,而且每次忍不住多吃 一个,这样吃完第十天时只剩下n个枣子了,请你编程计算猴子最初共摘了 多少个枣子。 输入格式:1个整数,表示第10天吃完后剩下的枣子数 输出格式:1个整数,表示第1天没吃之前枣子的个数

输入样例:1 输出样例:1534

上机练习
6、编程输入一个自然数x(x<=10000),求这个自然数的所有约数(包括1和X本身)之和 。 例如: 输入样例:10 输出样例:18 7、生活中,我们经常乘坐出租车。出租车的计费是一个很有趣的问题。比如在某市,出 租车起价费是3公里之内8元,超过3公里后,15.1公里之内,每550米计费1元;而超过 15.1公里之后,每370米计费1元。这样,乘坐出租车行驶的里程越远,花费就越多。例 如30公里时,就需要付费70元。但是有经验的老手告诉我们,实际上没有必要花那么多 钱,如果中途下车再打一辆车(相当于在中途结一次账),就能够少花一些钱。请验证 老手的话,求出在行驶多少米时结一次账是最便宜的(如有多解取最少的米数),并输 出在此情况下所需支付的钱数 输入格式:1个整数,表示总里程(单位:米) 输出格式:共一行,2个整数,中间用空格隔开,第1个整数表示中途结账地点距离起点 的路程,第2个整数表示最少付费值。 输入样例:30000 输出样例:14531 58

【折纸问题】 假如一张纸的厚度为0.06mm,且面积足够大的纸,将它不断地对折,问对折多 少次后的厚度可达到珠穆朗玛峰的高度(8848米)。 【算法分析】 1)输入纸的初始厚度h=0.00006米 2)记录纸的初始对折次数n=0 3)将纸对折,每折一次,纸的厚度变为原来的2倍,记录纸的新厚度h=2*h 4)纸每对折一次,对折次数加1,即n=n+1 5)判断纸的新厚度是否超过珠峰高度,如果超过,输出对折次数n,否则,重复 步骤3),4),5)

Program p5_7;
Var n:integer; h:real;
begin h=0.00006; n=0; h=h*2 n=n+1 false

begin
h:=0.00006; n:=0; repeat 循 环 体 h:=h*2; n:=n+1; until h>8848; writeln('n=',n); end. 循环条件 writeln('h=',h:0:2);

h>8848 true

输出h,n
end

Program p5_7;
Var n:integer; h:real;
begin h=0.00006; n=0; h<=8848 true h=h*2 n=n+1 false

begin
h:=0.00006; n:=0; while h<=8848 do begin 循 环 体 h:=h*2; n:=n+1; end; writeln('h=',h:0:2); writeln('n=',n); end. 输出h,n
end

循环条件

直到型循环(repeat-until)语句
格 式 repeat 循环体语句; until 条件表达式; 执行过程 先进入循环执行循环体语句,然后 计算条件式的值,当值为true时退出循 环,值为false时再次执行循环体。

注意:不管条件表达式是否为true直到型循环至少执行一次循环体语句 。
例如: i:=1; repeat i:=i+1; until i>0; writeln(i) 例如: i:=1; repeat i:=i+1; until i<0; writeln(i)

输出:2

死循环

对于预先不知道循环次数的程序可以使用until语句

对于预先不知道循环次数的程序也可以使用while语句

当型循环(while)语句
格 式 while 条件表达式 do 循环体语句; 执行过程 先计算条件表达式的值,当值为 true时,进入循环执行循环体语句,然 后再次计算条件式的值,直到值为 false时停止循环。

注意:如果条件表达式一开始就为false,则一次也不循环。
例如: i:=10; while i<0 do i:=i+1; writeln(i); 例如: i:=10; while i>0 do i:=i+1; writeln(i);

死循环

输出:10

循环结构小结
false 循环条件 true 循环体语句

while语句 当型循环 for语句

循环体语句

直到型循环
false 循环条件

repeat语句

true

程序举例
【字母统计问题】 输入若干字符,直到遇到‘#’号时停止,计算输入的字符中字母 ‘a’出现的次数。 输入:abcdaa#ab
【算法分析】

输出:3

1)用一个变量s做计数器,s的初值为0
2)输入一个字符,并存入变量c 3)如果c是‘A’或’a’,计数器s加1 4)如果c等于‘#’号,则输出s的值,否则重复步骤2)3)4)

program p5_8;
var s:integer; c:char;

program p5_8; var s:integer;

c:char;
begin s:=0; read(c); while c<>’#’ do begin if (c=‘a’) or (c=‘A’) then inc(s); read(c); end; writeln(‘s=‘,s)

begin
s:=0; repeat read(c); if (c=‘a’) or (c=‘A’) then inc(s); until c=‘#’; writeln(‘s=‘,s) end.

end.

程序举例
【最大公约数】 任意输入两个整数m,n求他们的最大公约数。
【问题分析】 由于m和n的最大公约数一定在1到x(x为m,n中较小的数)之间,因此可以通过循 环穷举x到1之间的每一个数,找到第一个能够整除m和n的数,这个数就是最大 公约数。 program p5_9; var m,n,x:integer; begin readln(m,n); if m>n then x:=n else x:=m; while (m mod x<>0) or (n mod x<>0) do x:=x-1; writeln(x) end.

【算法优化】 辗转相除法又名欧几里德算法(Euclidean algorithm)乃求 两个正整数之最大公因子的算法。欧几里德认为如果m mod n=0那 么n就是最大公约数,否则m,n的最大公约数等于n和r(r=m mod n) 的最大公约数。 program p5_9; var m,n,c:integer; begin read(m,n); repeat r:=m mod n; if r<>0 then begin m:=n; n:=r; end; until r=0; writeln('gys=',n); end.

上机练习
1、输入若干字符,直到遇到‘#’号时停止,计算输入的小写字母的个数。 输入格式:一行字符 输出格式:一个数字,表示小写字母的个数 输入样例:abCDEFghi#abC 输出样例:5 2、任意输入一个正整数n(0<n<1000000000)求其各位数之和。 输入格式:一个正整数,表示n 输出格式:一个正整数,表示各位数之和 输入样例:135 输出样例:9 输入样例:1234 输出样例:10 3、任意输入两个正整数m,n求他们的最小公倍数。 输入格式:2个正整数,表示m和n 输出格式:1个正整数,表示最小公倍数 输入样例:3 5 输出样例:15 输入样例:4 6 输出样例:12

循 环 嵌 套 如果循环语句中又嵌套了循环语句,称为循环嵌套。外层 的称为外循环,内层的称为内循环。根据嵌套的层数,可以 有两重循环,三重循环等
例如 : 例如 :

For 循环变量1=初值 to 终值 do begin ……; For 循环变量2=初值 to 终值 do …….; end

While 条件 do begin ……; For 循环变量=初值 to 终值 do …….; end

总循环次数=外循环次数*内循环次数

程序举例 1、编写程序找出所有的水仙花数,所谓水仙花数即满足下 列条件的数。 a3+b3+c3=abc 例如:153=13+53+33 【问题分析】
利用三个变量穷举个位,十位,百位

program p5_10; 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=100*a+10*b+c then 环 一 writeln(100*a+10*b+c); 二 end.

程序举例 2、输出2到100之间的所有素数。
program p5_11; 【问题分析】 var n,i:integer; 1)利用外循环穷举2到100之间的整数 yes:boolean; begin 2)利用内循环判断穷举的每一个数是否 for n:=2 to 100 do 为素数 begin yes:=true; for i:=2 to trunc(sqrt(n)) do if n mod i=0 then 外 内 begin 循 循 yes:=false; 环 环 break end; if yes then write(n:4); end; End.

程 序 举 例
3、编写程序输出N行如下图形。 输入样例:5 输出样例: 【问题分析】 可以用两重循环来实现,外循环控制输出多少行,内 循环控制每行输出多少个#号。 # ### ##### ####### #########

外 循 环 控 制 行 数

program p5_11; var i,j,n:integer; begin readln(n); for i:=1 to n do begin write('’:n-i); 用空字符的场宽控制每行符号输出的起始位置 for j:=1 to 2*i-1 do write('#'); writeln; 内循环控制每行‘#’出现的次数 end 输出完一行后换行 end.

思 考
######### ####### ##### ### # # ## ### #### ##### # ## ### ## # # ### ##### ####### ######### ####### ##### ### #

解决图形输出问题的要点: 1、行数 2、每行字符个数以及与行数之间的对应关系

3、每行的起始位置
4、图形特点

循环的综合应用
1、编程求1000的阶乘(1000!)尾部有多少个连续的0
【问题分析】 求1000!中有多少个0实际上就是统计1000!中有多少个因子10,又由于10=5*2 ,因此问题可转化为统计有多少个5*2,那就要统计有多少个5和多少个2,显然5的

个数比2少,因此只要统计因子5的个数就可以了。因此程序实现时,实际统计的是
数列5,10,15,20,25,?1000中因子5的个数。

外循环用于构造 5,10,15…1000数列

program p5_12; var n,s,i:integer; begin s:=0; for i:=1 to 200 do begin n:=i*5; while n mod 5=0 begin s:=s+1; n:=n div 5; end end; writeln(s) end.

do
内循环统计 因子5的个数

循环的综合应用
2、四个学生上地理课时,回答我国四大淡水湖大小时这样说。甲说: “最大洞庭湖,最小洪泽湖,鄱阳湖第三”;乙说:“最大洪泽湖,最小 洞庭湖,鄱阳湖第二,太湖第三”;丙说:“最小洪泽湖,洞庭湖第三” ;丁说:“最大鄱阳湖,最小太湖,洪泽湖第二,洞庭湖第三”。其中每 个学生仅答对一个,请编程确定湖的大小。

问题分析 1、通过循环穷举所有的可能性。

2、判断那种可能性能满足每个学生仅答对一个的条件。满 足条件的可能性就是我们需要的解。

program hpwt; 补充知识 var ord(true)=1 d,h,p,t:integer; ord(false)=0 begin for d:=1 to 4 do for h:=1 to 4 do if d<>h then for p:=1 to 4 do if (d<>p) and (h<>p) then begin t:=10-d-h-p; if (ord(d=1)+ord(h=4)+ord(p=3)=1) and (ord(h=1)+ord(d=4)+ord(p=2)+ord(t=3)=1) and (ord(h=4)+ord(d=3)=1) and (ord(p=1)+ord(t=4)+ord(h=2)+ord(d=3)=1) then writeln('d=':3,d,'h=':3,h,'p=':3,p,'t=':3,t); end; end.

上机练习 1、百钱买百鸡问题:鸡翁一值钱五,鸡母一值钱三,鸡雏三 值钱一,百钱买百鸡,问:鸡翁,鸡母,鸡雏各几何?(其中 允许某种鸡的数量为0只) 输入样例:无 输出样例: jw jm jc 0 25 75 4 18 78 8 11 81 12 4 84

上机练习 2、编程画出n(n一定为奇数)行以下形状的图形: 输入样例:9 输出样例:
# ### ##### ####### ######### ####### ##### ### #

上机练习
3、有a,b,c,d,e五本书要分给张、王、刘、赵、钱五位同学看,每人只能 选一本,事先让每个人把自己喜爱的书填于下表,请编程找出让每个人都 满意的方案 ,输出所有可能的方案。 输入样例:无 输出样例: c a b d e d a c b e d b c a e d e c a b a b √ √ √ √ √ √ √ √ c d e √

张 王 刘 赵 钱






上机练习
4、数学上的“完全数”是指真因子之和等于它本身的自然数,如6=1+2+3 ,所以6是一个完全数。编程输出n(n<=100000)以内(包括n在内)的所 有完全数。 输入格式:一个正整数,表示n 输出格式:若干个正整数,表示n以内的所有完全数,每个数用空格隔开 输入样例:100 输出样例:1 6 28

第 六 讲 枚举类型和子界类型

数据类型
标准类型

整型(Integer) 实型(Real) 字符型(Char) 布尔型(Boolean) 枚举型 自定义类型 子界型 数组类型 集合类型 注意 1、简单类型中除了real以外 都是顺序类型; 2、所有数据类型除了指针以 外都是静态数据类型;

简单类型

构造类型 记录类型 文件类型 指针类型

枚举类型
例 如
type color=(red,orange,yellow); var i:color;

color是我们自定义的新类型,括号中是它允许的取值,这种将取值一 一列举出来的数据类型称为枚举类型。变量i是枚举类型的变量。
声明格式1

type 枚举类型标识符=(标识符1,标识符2,…,标识符n); var 因 此 变量名:枚举类型标识符; 上面枚举类型变量i也可以这样声明 声明格式2 var var i:(red,orange,yellow); 变量名:(标识符1,标识符2,…,标识符n);

枚举类型特点
1、枚举类型可以增加程序的可读性,还可以节省内存空间。但枚举类 型最多只能有256个元素。

2、枚举元素只能是标志符,不能是数据常量或是字符常量。
例如: var x:(1,2,3,4,5);

y:(‘a’,’b’,’c’);
z:(‘red’,’green’,’blue’); 这些声明都是错误的

3、同一枚举元素不能同时出现在两个以上的枚举类型定义中。

例如:
Var x:(monday,tuesday); y:(monday,wednesday); 这样的声明是错误的 4、枚举类型只能进行赋值运算和关系运算
例如,对于:
Var x,y:(red,green,blue); x:=red;y:=x; 如果: Read(x); write(x); 或 write(blue)是非法的。

注 意 枚举类型常用case语句进 行输入输出。

5、枚举类型也是顺序类型,元素的序号从0开始。 例如,对于: type color=(red,green,blue,black); 有: ord(red)=0 succ(red)=green green>red ord(green)=1 pred(green)=red

程序举例
有红,橙,黄,绿,蓝五种颜色的小旗,每次取出三种不同颜色的小 旗表示不同的信号,请你编程输出所有信号的方案及方案总数
program p6_1; Var m,m1,m2,m3:integer; s, p: integer; begin s:=0; for m1:=1 to 5 do for m2:=1 to 5 do if m1<>m2 then for m3:=1 to 5 do if (m3<>m1) and (m3<>m2) then begin s:=s+1; write(s,’:’); for p:=1 to 3 do begin case p of 1: m:=m1; 2: m:=m2; 3: m:=m3; end; case m of 1: write(‘red’:8); 2:write(‘orange’:8); 3:write(‘yellow’:8); 4:write(‘green’:8); 5:write(‘blue’:8); end; end; writeln; end; writeln(‘total’, s); end.

用 于 输 出 每 一 种 方 案

子界类型
例 如 type fs=0..100; var i:fs; fs也是我们自定义的新类型,等于号后面是它允许的取值范围, 这种用上下界的方式定义数据的类型称为子界类型。变量i是子界类 型的变量。
声明格式1 type 子界类型标识符=下界常量..上界常量; 因 此 var 变量名:子界类型标识符; 上面子界类型变量i也可以这样声明 声明格式2 Var var i:0..100; 变量名:下界常量..上界常量;

子 界 类 型 特 点
1、子界类型的上界必须大于下界 2、子界类型的基类型必须是顺序类型 例如:var i:1.2..3.3; 这样定义是错误的

3、适合其基类型的运算,也同样适合该子界类型

4、具有相同基类型不同子界类型的变量可以混合运算,但要注意,计 算后变量的值不能超过其子界范围 例如: a:1..10; b:1..50; c:1..100;

类 型 相 容 问 题
当程序中用到的数据类型比较多时,会出现不同类型之间能否相互转 换或相互赋值的问题,我们把这类问题称之为类型相容性问题。 例如: Var a:integer; b:1..100; c:real; Begin a:=b; c:=a; b:=a; b:=c End.
1)类型相同的变量在赋值时相容。 2)取值范围小的数据类型容于取值范围大 的类型,反之不容。

类型相容可以执行 类型相容可以执行 执行时结果可能溢出 编译时会出错

阅读程序
program ex1; 输入: var ch:char; 3 t:1..15; s,qz:longint; 3bc n,i:1..7; 输出: 956 begin s:=0;qz:=1; readln(n); for i:=2 to n do qz:=qz*16; for i:=1 to n do begin 将一个n位的16进制数转化为十进制数 read(ch); case ch of '0'..'9':t:=ord(ch)-ord('0'); 'a'..'f':t:=ord(ch)-ord('a')+10; 'A'..'F':t:=ord(ch)-ord('A')+10; end; s:=s+t*qz; qz:=qz div 16; end; writeln(s) end.

上机练习
按年、月、日的顺序读入一个日期,输出该日期是这一年中的第几天。 输入格式: 1行三个整数,分别表示年、月、日

输出格式:
1行一个整数,表示一年中的第几天 输入样例: 2002 2 5 输出样例: 36

第 七 讲 数 组

数 组 的 概 念 数组既由一组固定数目的,相同类型的数据项,排列 而成的数据,每个数据项称为一个数组元素。
数组元素



组:

10

234

34

37

46

28

简单变量:

a

b
x[2]

c
x[3]

d
x[4]

e
x[5]

f
x[6]

数组变量: x[1]

数 组 变 量 的 声 明
格 式1 type 类型名=array[下标类型] of 元素类型; var 变量名:类型名; 举 例 type number=array[1..6] of integer; var a:number;

格 式2 var 变量名: array[下标类型] of 元素类型;
举 例 var a: array[1..6] of integer;

注 意
1、下标类型必须是整型、字符型、布尔型等顺序类型,一般用子界类 型表示。

例如:
a:array[1..10] of integer; of integer;

b:array[‘a’..’z’]

2、下标可以是1个,也可以是多个,下标类型的个数对应着数组的维 数。 例如: a:array[1..100] of integer; {一维数组} b:array[1..10,1..10] of integer; {二维数组}

3、Pascal允许在定义数组变量时,为数组变量赋初值。 例如: Var a:array[1..6] of integer=(2,4,6,8,10); Const b: array[1..6] of integer=(2,4,6,8,10);

4、在定义数组变量时,下标不能是变量,且上界必须大于下界。 例如:

a:array[1..n] of integer;
b:array[10..1] of integer; 以上都是错误的

一维数组变量的基本操作
1、赋值 一般情况下数组通过循环语句对元素进行赋值,但在两种情况下数 组可以整体赋值,(1)两个同类型的数组之间相互赋值(2)数组作为过程 或函数的参数。 例如: var a,b:array[1..10] of integer; i:integer; begin {通过循环语句对每一个元素赋值} for i:=1 to 10 do a[i]:=2*i; {数组整体赋值} b:=a; end.

2、输入,输出 数组一般无法整体输入输出,必须通过循环语句逐个输入或输出数 组中的元素。 var a:array[1..10] of integer; begin for i:=1 to 10 do read(a[i]); for i:=1 to 10 do write(a[i]); end.

{输入} {输出}

上 机 练 习
任意输入n(n<100)个整数,并按输入顺序的逆序输出。 输入格式:共2行,第1行一个正整数表示n,第二行由若干个整数组成,中间用 空格隔开,表示要输入的n个整数 输出格式:共1行,由若干个整数组成,中间用空格隔开,表示按输入顺序的逆 序输出的整数序列 输入样例: 10

8 13 26 -38 9 10 15 27 45 9
输出样例: 9 45 27 15 10 9 -38 26 13 8

3、查找(查找操作就是在数组元素中搜索我们所需要的数据,并输出搜索结果
) 如果数组无序一般采用顺序查找

如果数组有序可以采用折半查找
[n]

[1] [2] [3] [4] [5] [6] [7] [8] …

j st

j=(st+en) div 2

en

read(x); j:=1; while (j<=n) and (x<>a[j]) do j:=j+1; if j<=n then writeln(j); 顺序查找

read(x); st:=1;en:=n; repeat j:=(st+en) div 2; if x<a[j] then en:=j-1; if x>a[j] then st:=j+1; until (x=a[j]) or (st>en); if st<=en then writeln(j); 折半查找

4、移动
在移动某一数组元素时,要先在数组中留出至少一个元素空间,然后再移动,要 将k号元素向后移动一个位置,就要从数组的最后一个元素j号元素开始,依次向后移 动一个位置,直到k位置。 将k号元素向后移动一个位置 [1] [2] [3] [4] [5] [6] [7] … [n-1] [n] j

k for i:=j down k do a[i+1]:=a[i];

[1] [2] [3] [4] [5] [6] [7] … [n-1] [n]

5、插入
在数组中插入数据时,要先从最后一个元素j号元素开始逐个向后移动,直

到插入位置。然后再将要插入的数据插入数组。 k
[1] [2] [3] [4] [5]

j
… [n] [n+1]

将x插入k号位置 for i:=j downto k do a[i+1]:=a[i]; a[k]:=x; x

6、删除 在数组中删除元素时,只要将删除位置以后的数据向前移动就可以了。 删除k号位置上的元素 [1] [2] [3] [4] [5] [6] [7] … [n-1] [n] k

for i:=k+1 to j do a[i-1]:=a[i];

j

上 机 练 习 任意输入n(n<100)个从小到大排列的整数和一个测试数据x,如果x存在于

这n个整数中,则把x从这个整数序列中删除;如果x不在这n个整数中,则将x插
入到整数序列的相应位置上(即插入后整数序列扔保持从小到大的顺序不变) 输入格式:共3行,第一行为一个整数,表示n。第二行为n个从小到大排列的整

数,表示整数序列。第三行为一个整数,表示测试数据x。
输出格式:共1行,表示插入或删除后的结果。

输入样例: 5 2 4 6 8 10 3 输出样例: 2 3 4 6 8 10

输入样例: 5 2 4 6 8 10 1 输出样例: 1 2 4 6 8 10

输入样例: 5 2 4 6 8 10 11 输出样例: 2 4 6 8 10 11

输入样例: 5 2 4 6 8 10 4 输出样例: 2 6 8 10

应用举例
用筛法求素数。

方 法 描 述
1、将2到n的数放入筛中。
2、找出筛中最小的数(必为素数);

3、将该素数的所有倍数(2倍,3倍…)从筛中筛去;
4、重复2,3步直到筛空;

初始状态:2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
第一次筛选:2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 第二次筛选:2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 第三次筛选:2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 第四次筛选:2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 第五次筛选:2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 第六次筛选:2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 第七次筛选:2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 第八次筛选:2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

定义一个布尔型的数组a作为筛子,数组元素a[i]表示i是否为素数,由于布 尔型变量默认值为false,因此如果a[i]是素数则不变,如果不是素数就将a[i] 值设为true。 [2] [3] [4] [5] [6] [7] [8] [9] … a F F F F F F F F F [n] F

思考:这个程序可以进行优化吗?

定义一个布尔型的数组a作为筛子,数组元素a[i]表示i是否为素数,由于布 尔型变量默认值为false,因此如果a[i]是素数则不变,如果不是素数就将a[i] 值设为true。 [2] [3] [4] [5] [6] [7] [8] [9] … a F F F F F F F F F [n] F

优 化 算 法

数组排序问题 输入n(n<=1000000)个整数,将它们按由小到大的顺序输出。
方法一:插入排序 和我们打牌时抓 牌的情景一样,每抓 一张牌,就把这张牌 放到该放的位置上, 每读入一个数据就把 该数据插入到相应位 置,并把它后面的所 有元素向后移一位。

2

5

3

8

7

3

9

0

1

4

6

将2放入序列
将5放入序列 将3放入序列 将8放入序列 将7放入序列 将3放入序列 将9放入序列 将0放入序列 将1放入序列 将4放入序列 将6放入序列

2
2 2 2 2 2 2 0 0 0 0 5 3 3 3 3 3 2 1 1 1 5 5 5 3 3 3 2 2 2 8 7 5 5 3 3 3 3 8 7 7 5 3 3 3 8 8 7 5 4 4 9 8 7 5 5 9 8 7 6 9 8 7 9 8 9

x j 初始状态 i j
[1] [2] [3] [4] [5] …… [n]

x
[5] …… [n]

[1] [2] [3] [4]

x j j

后插状态
i
[5] …… [n]

[1] [2] [3] [4]

前插状态
i

方法二:选择排序 第一次从数列中选择一个最小的数与放在第一个位置上的数交换,则第一个位置上的数变为 最小,这样n个数的排序就转化为n-1个数的排序,第二次从2~n的数列中再选一个最小的数与 第二个位置上的数交换,那么经过这样n-1次选择,数列就有序了。

2 将0放入序列 将1放入序列 将2放入序列 将3放入序列 0 0 0 0

5 5 1 1 1

3 3 3 2 2

8 8 8 8 3

7 7 7 7 7

3 3 3 3 8

9 9 9 9 9

0 2 2 3 3

1 1 5 5 5

4 4 4 4 4

6 6 6 6 6

将3放入序列
将4放入序列

0
0

1
1

2
2

3
3

3
3

8
4

9
9

7
7

5
5

4
8

6
6

将5放入序列
将6放入序列

0
0

1
1

2
2

3
3

3
3

4
4

5
5

7
6

9
9

8
8

6
7

将7放入序列

0

1

2

3

3

4

5

6

7

8

9

i
[1] [2]

j
[3] [4] [5] … [n-1] [n]

min

方法三:冒泡排序(又名:交换排序) 从第1个数开始,依次比较相邻的两个数据是否为逆序对。若逆序就交换两个数,即第 1个和第2个比,第2个和第3个比,若逆序就交换位置,直到第n-1个和第n个比较。比较 完后,再从第1个数开始,直到第n-2个和第n-1个比较,如此往复,直到不再发生数据交 换为止。

2
第1次交换 第 一 趟 排 序 第2次交换 2 2

5
3 3

3
5 5

8
8 7

7
7 8

3
3 3

9
9 9

0
0 0

1
1 1

4
4 4

6
6 6

第3次交换
第4次交换 第5次交换 第6次交换 第7次交换 第2趟排序 第3趟排序 第4趟排序 第5趟排序 第6趟排序 第7趟排序

2
2 2 2 2 2 2 2 2 2 0

3
3 3 3 3 3 3 3 3 0 1

5
5 5 5 5 5 3 3 0 1 2

7
7 7 7 7 3 5 0 1 3 3

3
3 3 3 3 7 0 1 3 3 3

8
8 8 8 8 0 1 4 4 4 4

9
0 0 0 0 1 4 5 5 5 5

0
9 1 1 1 4 6 6 6 6 6

1
1 9 4 4 6 7 7 7 7 7

4
4 4 9 6 8 8 8 8 8 8

6
6 6 6 9 9 9 9 9 9 9

思考:这个程序可以如何优化?

i
[1] [2] [3] [4] [5] … [n-1] [n]

j j+1

上 机 练 习
【数学黑洞问题】
任意一个四位数,只要它们各个位上的数字是不全相同的,就有这样的规律: 1)将组成该四位数的四个数字由大到小排序,形成由这四个数字构成的最大的四位数; 2)将组成该四位数的四个数字由小到大排列,形成由这四个数字构成的最小的四位数(

如果四个数中含有0,则得到的数不足四位);
3)求上述两个数的差,得到一个新的四位数(高位零保留) 重复以上过程,不出7步必然得到6174,这个数被称为卡布列克数,请编写一个程序,计 算一个四位数经过上述运算,最后得到卡布列克数所需的步数。 输入格式: 一行一个4位正整数,表示开始的4位数 输出格式: 过程如下: 1000 – 1 = 999 9990 – 999 = 8991 9981 – 1899 = 8082 8820 – 288 = 8532 8532 – 2358 = 6174

一行1个整数,表示步数
输入样例: 1000 输出样例:

5

【约瑟夫问题】 n个人围成一圈,从第一个人开始报数,数到k的人出圈,再由下一个人重新开 始报数,数到k的人出圈,直到最后一人。请你编程依次输出出圈人的编号。n的值 预先设定,k的值由键盘输入。比如:n=8,k=6时依次出圈的编号为:6、4、3、5、 8、7、2、1。
输入格式:
一行两个正整数,分别表示n和k 输出格式: 一行n个整数,表示出圈的顺序

输入样例:
8 6 输出样例: 6 4 3 5 8 7 2 1

【圆盘找数】 如图所示,将n个数围成一圈,从这n个整数中分别找出k个相邻且相加之和 最大和最小的哪k个数,并输出这个最大数和最小数。

5 20 1 18 4 16 6 10 15 2 17 3 14 7 13 8 11 19 9 12
数据范围: 1≤k≤n≤1000,0<ai<1000 样 例

输入样例:
20 4 5 20 1 18 4 16 6 10 15 2 17 3 14 7 13 8 11 19 9 12 输出样例: max:51 min:33

【杨辉三角】 输出杨辉三角的前n行
输入格式: 一行1个正整数,表示n 输出格式: 共n行,第i行有i个整数 数据范围: 0<n<30 输入样例: 5 输出样例:

1 1 1 1 1 1 2 3 4 1 3 6 1 4 1

1
1 1 1 2 1 1 3 3 1 1 4 6 4 1

【蛇形方阵】 编程输出N阶蛇形方阵。如N=5时,方阵如下: 1 3 4 10 11 2 5 9 12 19 6 8 13 18 20 7 15 14 16 17 22 21 23 24 25

字符数组和字符串
字符型数组

如果一个数组的基类型为char我们称它为字符型数组。 Var
a:array[1..1000] of char;

应用举例
任意输入两个英语单词,按字典顺序比较其大小。
【问题分析】 1、定义两个字符型数组用于存储单词

2、由于不知道单词的长度,必须人为设定一个结束标记如‘#’,然后通过循环语句将单词字母依次存入数组 。
3、按照数组下标逐个比较单词中的字符,根据比较结果判断单词的大小。 4、比较结果有4种情况

1)两个单词长度相等,字符完全相同,则两单词相等。
2)两个单词长度不等,一个单词是另一个单词的前缀,则长度大的单词大 3)两个单词长度不等,从第一个字符开始逐个比较,当遇到第一个不相等的字符时,字符大的单词大。

program zfcbj; var str1,str2:array[1..100] of char; ch:char; len1,len2,i:integer; begin len1:=0; read(ch); while ch<>'#' do begin inc(len1); str1[len1]:=ch; read(ch) end; len2:=0;read(ch); while ch<>'#' do begin inc(len2); str2[len2]:=ch; read(ch) end; i:=1; while (i<=len1) and (i<=len2) and (str1[i]=str2[i]) do inc(i); if (i>len1) and (i>len2) then write('str1=str2'); if (i>len1) and (i<=len2) then write('str1<str2'); if (i<=len1) and (i>len2) then write('str1>str2'); if (i<=len1) and (i<=len2) then if str1[i]>str2[i] then write('str1>str2') else write('str1<str2') end.

字符数组和字符串
字符串类型(string)
我们把存储在字符数组中的一串字符叫做字符串,字符串类型就等于 一个长度为255的紧缩型字符数组。例如下面的变量a和b是等价的。 Var a:string; b:packed array[1..255] of char; 可用运算:+(连接运算)、关系运算

应用举例
任意输入两个英语单词,按字典顺序比较其大小。 program zfcbj; var str1,str2:string; begin readln(str1); readln(str2); if str1>str2 then writeln(str1,'>',str2) else if str1<str2 then writeln(str1,'<',str2) else writeln(str1,'=',str2); end.

字符串类型的特点
1、字符串型变量可以直接进行输入和输出或赋值; 例如: Var a:string; Begin read(a); write(a); end. 2、字符串变量中的某一个字符可以用数组的方式进行调用,但要注意字 符串型变量的最大长度为255。 例如: Var a:string; Begin a:=‘hello’; write(a[1]); end.

与字符串相关的常用标准函数
函数名
length(str) pos(str1,str2)

参数 str为字符串 str1,str2都是字符串 字符串str的长度

返回值

如果前字符串str1在后字符串str2中存在则 返回它第一次出现的位置,否则返回0

copy(str,pos,nu m)

str为字符串,pos和num为整数。

str字符串中从pos位置开始,num数量的字符 串。

与字符串相关的常用标准过程
过程名 str(val,str) val(str,val,code) insert(str1,str2,pos) delete(str,pos,num) 参数 val为数值型数据str为字符串 str为字符串val为数值型数据 code为0或1 Str1,str2为字符串,pos为整数 Str为字符串,pos和num为整数 功能 将变量val中的数值转化为字符串并存储 到str变量中 将变量str中的字符串转化为数值并存储 到val变量中,如果成功code为0否则为1 将str1插入到str2的pos位置 删除str中从pos开始的num个字符

上机练习
输入一行字符(总长度<255),其中包含若干个单词,相邻的两个 单词用若干个空格隔开,编程统计单词的个数。
【问题分析】 1、将所有字符存入一个字符串变量。 2、依次扫描字符串中的每个字符,遇到空格跳过,遇到非空格计数器加1,然后再 跳过连续的非空格,如此循环直到最后。
o n e t w o

上机练习
设有n个正整数(n≤20),将他们连接成一排,组成一个最大的多位 整数,输入时第一数为n,后面为n个正整数。例如

样例
输入: 3 3 8 7 输出: 873 输入: 3 13 8 输出: 8713 7 输入: 2 83 831 输出: 83831

上机练习
单词接龙游戏: 游戏规则:输入两个单词,判断是否可以首尾拼接,第二个单词首部 和第一个单词尾部有相同的字符串才能拼接,如果可以拼接,输出 “yes”,否则输出“no”。

样例
输入: hello open 输出: yes 输入: hello hell 输出: no 输入: hello love 输出: yes

第 八 讲

文 件

文 件 的 概 念
文件是指存储在外存(如磁盘)上的,由同一类型的元素组成的顺序集 合,文件所包含的元素的个数称为文件的长度,长度为0的文件(即不含任 何元素的文件)称为空文件。

文 件 和 数 组 的 比 较
? ?

数组的长度是固定的,而文件的长度不固定,而且可以很长;

数组可以通过下标对任一数组元素进行访问,而文件一般必须从前往后 逐个访问,直到找到或找完为止;
?

数组可以整体赋值,而文件却不可以;

文 件 的 优 点
1、文件可以永久保存,文件中的数据不会因程序的结束而消失。 2、文件中的数据可以被多个应用程序共享; 3、文件中的数据可以多次重复使用;

4、文件的容量理论上没有限制;

数据类型
标准类型

整型(Integer) 实型(Real) 字符型(Char) 布尔型(Boolean) 枚举型 自定义类型 子界型 数组类型 集合类型

简单类型

构造类型 记录类型 文件类型 指针类型

文件操作
1)利用assign( )过程让实际文件与程序中的文件变量建立连接; 方法: assign(input,’路径\文件名’); assign(output ,’路径\文件名’); 2)利用reset( ),rewrite( )等过程和文件变量打开文件; 方法: reset(input); rewrite(output);

3)利用输入输出语句对文件进行读写操作;
read( );readln( );write( );writeln( )

4)利用close( )过程和文件变量关闭文件;
close(input); close(output);

程序举例
读取n个整数,计算它们的和,并把结果输出 【输入文件】 共两行,第一行包含一个正整数n(n<100),第二行包含n个用空格隔开的整数。 【输出文件】 仅一行,表示n个整数的和。 【输入样式】 连接输入文件 连接输出文件 打开输入文件 打开输出文件 assign(input,'ex1.in'); assign(output,'ex1.out'); reset(input); rewrite(output); readln(n); s:=0; for i:=1 to n do begin read(x); inc(s,x); end; writeln(s); 关闭输入文件 关闭输出文件 close(input); close(output);

5
1 2 3 4 5

【输出样式】 15 【输入文件】ex1.in 【输出文件】ex1.out

程序举例
读取n个整数,计算它们的和,并把结果输出 【输入文件】 就一行包含n个用空格隔开的整数。 【输出文件】 仅一行,表示n个整数的和。 【输入样式】 assign(input,'ex1.in'); assign(output,'ex1.out'); reset(input); rewrite(output); s:=0; while not eof do begin read(x); inc(s,x); end; writeln(s); close(input); close(output);

1 2 3 4 5
【输出样式】 15 【输入文件】ex1.in 【输出文件】ex1.out

利用while循环 和eof函数判断 是否结束

程序举例
读取若干单词,计算单词的总数,并把结果输出
【输入文件】 共若干行,每行包含1个单词。 【输出文件】 program wjqh; var w:string; s:integer; begin assign(input,'ex1.in'); assign(output,'ex1.out'); reset(input); rewrite(output); s:=0; while not eof do 判断文件是否结束 begin read(w); 用于读入一 readln(w); inc(s); 行字符作为 inc(s); readln; 字符串 end; 利用readln直接吸收回车符 writeln(s); close(input); close(output) end.

仅一行,表示单词的个数。
【输入样式】 One Two

three
【输出样式】 3 【输入文件】ex2.in 【输出文件】ex2.out

标 准 文 件 变 量 input 和 output
在Pascal中有两个事先定义好的文件变量input和output,默认情
况下input连接的文件是键盘,output连接的文件是显示器。因此默认 情况下对input和output进行读写时,实际上就是对键盘和显示器进行

读写。由于read,readln,write,writeln语句默认是就是对input和
output进行读写的,因此默认read和readln是从键盘读取,write和 writeln是向显示器写入。 所以当我们利用assign( )过程改变input和output的连接文件时 ,read,readln,write,writeln读取写入方向也会改变。

文件处理中的标准过程和函数

标准函数
函数名
eoln(FileVar)

参数 FileVar为文件变量(可省略)

返回值 行结束返回true否则返回false

eof(FileVar)

FileVar为文件变量(可省略)

文件结束返回true否则返回false

标准过程
过程名
assign(FileVar,FileName) close(FileVar) reset(FileVar)

参数 FileVar为文件变量,FileName为实际文件名 FileVar为文件变量 FileVar为文件变量 关闭文件

功 能 将文件变量和实际文件进行连接 打开一个已有文件

rewrite(FileVar)
append(FileVar)

FileVar为文件变量
FileVar为文件变量

打开一个新文件
在一个已有文件后追加

上机练习
输入n个整数(n<1000000),每个数不大于10000,并对这n个数按从小到大的顺序 排序。 【输入格式】 共2行,第1行一个整数,表示n,第二行n个整数,中间用空格分隔。 【输出格式】

仅一行,包含n个排好序的整数。
【输入样例】 5

10

9

7

3

6

5

【输出样例】 3 5 6 7 9 10

【源文件】px.pas 【输入文件】px.in 【输出文件】px.out

第 九 讲 过程和函数

结构化程序设计思想
所谓结构化程序设计思想,就是在解决问题时如果无法一步到位,先将 问题分解为若干个小问题,如果这些小问题仍无法解决,再进行分解,直到 每一个问题都能轻松解决为止,在编写程序时也将一个大程序分解为主程序 和若干子程序,每个子程序用来解决一个小问题,最后将这些子程序通过主 程序组合起来,共同解决一个大问题。 结 构 化 思 想 基 本 要 点

1)程序由顺序、分支、循环三 种基本结构组成
2)自顶向下,逐步求精 3)模块化
子程序 子程序

主程序

子程序

子程序

子程序

在Pascal中过程与函数是实现结 构化程序设计的主要手段

结构模型

问题一
求:3!+5!+6!

program jc; var s:longint;
function jc(n:integer):longint; var i,x:longint; begin x:=1; for i:=1 to n do x:=x*i; jc:=x end; begin s:=jc(3)+jc(5)+jc(6); writeln(s) end.

program jc; 自定义 var 一个求 i,x,s:longint; 阶乘的 begin 函数jc s:=0; x:=1; 求3! for i:=1 to 3 do x:=x*i; s:=s+x; x:=1; 求5! for i:=1 to 5 do x:=x*i; s:=s+x; x:=1; 求6! for i:=1 to 6 do x:=x*i; s:=s+x; writeln(s); end.

一、函数 函数分为标准函数和自定义函数两种,自定义函数格式如下:

Function 函数名[(形式参数表)]:函数类型; [函数的说明部分] Begin 语句1; ……. 函数名:=表达式; End;
将函数值传给函数名 执 行 部 分 函 数 体

函数首部

函数使用要点
1、自定义函数必须在主程序的声明部分进行声明后才能使用,而且只能在定义它的程序中使用。

2、函数可以没有形式参数,如果没有这部分可以省略。
3、在函数首部中,函数名是一个由用户自定义的标识符,不能与保留字或已用标识符同名。 4、形式参数简称形参,相当于函数中定义了某些变量。形参表的一般格式如下: [var] 变量名表:类型标识符;? 5、形参的类型说明只能使用类型标识符。例如,在形参中使用数组时,必须事先定义一个数组 类型标识符。 Type arr=array[1..10] of integer; Function f(x:arr):integer; … 6、形参表由若干个以分号隔开的参数组成。例如: function f(a:integer;b,c:real):integer;

7、函数的说明部分可以定义函数内部需要用到的变量,或者是属于这个函数自身的函数或过程。

8、函数类型表示函数返回值的类型,所有的函数,最后都要返回函数值,这个操作可以通过 以下两种方式实现: 1)函数名:=表达式;

功能:函数结束时,函数值将被返回到调用它的语句中
2)exit(表达式) 功能:跳出函数,以表达式的值作为函数值 9、函数必须在定义之后调用,其调用格式为: 函数名[(实际参数表)] 10、实际参数简称实参。实参的个数必须与函数定义中形参的个数一致,实参的类型与形参的 类型应当一一对应。 11、函数只有在被调用时才被执行,但要注意函数只能在表达式或输出项中才能被调用,不能 单独使用。 12、函数调用的过程如下: 1)将主程序中的每个实在参数的值传递给函数中对应的形式参数; 2)由函数程序完成处理; 3)处理结果存放到函数名中返回调用函数的程序;

函数名

program jc; var s:longint;

形参表

子程序

主程序

function jc(n:integer):longint; var i,x:longint; begin x:=1; for i:=1 to n do x:=x*i; jc:=x end; 实参表 begin s:=jc(3)+jc(5)+jc(6); writeln(s) end.

函数类型(即返回值类型)

应用举例
1、计算组合数C(m,n)的值(m<=10,m>=n)

【输入格式】 共一行,两个整数,分别表示m和n的值 【输出格式】 共一行,一个整数,表示C(m,n)的结果 【输入样例】 3 2 【输出样例】 3

m! C(m ,n)? (m ? n)!n!

【问题分析】

由于在求组合数时需要求三次阶乘,所以我们可以编写一个求n!的函数f(n) ,这样组合数就可以写成f(m) div (f(m-n)*f(n)),这样我们只要输入m和n的 值并把他们代入表达式就可以求出c(m,n)了。

program zhs; var m,n:integer; c:longint; function f(n:integer):longint; var i:integer; s:longint; begin s:=1; for i:=1 to n do s:=s*i; f:=s; end;

定义一个求 阶乘的函数 f(n)

子程序

求组和数

begin readln(m,n); c:=f(m) div (f(m-n)*f(n)); writeln(c); end.

主程序

2、求2~n(2<n≤1000000)中有多少个素数。
【输入格式】一个正整数,表示n 【输出格式】一个正整数,表示素数的个数

【输入样例】100
【输出样例】25 【问题分析】 1)设计一个判断x是否为素数的函数,如果为素数返回true,否则返回false 2)通过循环,利用该函数对2~n的数进行判断,如果是素数,计数器加1。 3)输出计数结果。

定义一个 检测x是 否为素数 的函数 check(x )

主程序

program ssgs; var s,n,i:longint; function check(x:integer):boolean; var i:longint; begin check:=true; for i:=2 to trunc(sqrt(x)) do if x mod i=0 then 如果x可以被i除尽,则 begin 返回false exit(false); end; end; begin readln(n); s:=1; for i:=3 to n do if check(i) then inc(s); writeln(s); end.

上机练习
【数字分离】 定义函数digit(n,k)分离出整数n从右边数的第k个数字,如: digit(31859,3)=8 digit(2076,5)=0。 【输入格式】 共一行,2个整数,分别表示n和k 【输出格式】 共一行,1个整数,表示n从右边数的第k个数字 【输入样例】 31859 3 【输出样例】 8 【源文件】szfl.pas 【输入文件】szfl.in 【输出文件】szfl.out 【数据范围】 0≤ n ≤ 109

上机练习
【数值计算】 设有3个函数: f(x)=3x2+x-6 g(x)=4x2-9x h(x)=x3-7x2+2x-9 对于给定的长整型数据x,求f(g(h(x))) mod 6799的值。 (如果结果小于0则加上6799,结果大于0不变) 【输入格式】 共一行,1个整数,表示x 【输出格式】 共一行,1个整数,表示结果 【输入样例】

5
【输出样例】 4237 【源文件】szjs.pas

【输入文件】szjs.in
【输出文件】szjs.out 【数据范围】 -103 ≤ x ≤ 103

上机练习
【质因数分解】 已知正整数n是两个不同的素数的乘积,试求出较大的那个素数 【输入格式】 共一行,1个整数,表示n 【输出格式】 共一行,1个整数,表示较大的那个素数 【输入样例】 21 【输出样例】 7 【源文件】prime.pas 【输入文件】prime.in 【输出文件】prime.out 【数据范围】 对于60%的数据,6 ≤ n ≤ 1000 对于100%的数据,6 ≤ n ≤ 2*109

二、过程 概念:在程序中如果有一段程序将被重复使用,我们可以赋予这段程 序一个标识符,以后在需要使用这段程序的地方,只要用标识符就可以代 替这段程序,从而增加程序的可读性。这种被赋予标识符的子程序称为过 程。 过程也分为标准过程和自定义过程两种,例如:read,write都是标准 过程,自定义过程格式如下:

Procedure 过程名 [(形参表)];
[过程说明部分] Begin
执 语句1; 行 部 ……. 分 过 程 体

过程首部

End;

过程使用要点
1、过程首部以关键字procedure开头,过程名是用户自定义的标识符,只用来标识一个过程,不能代表任何 数据,因此不能说明过程的类型。 2、形参表的一般格式为: [var] 变量名表:类型标识符;…

3、形参表缺省时,称为无参过程。
4、过程体与程序、函数体的写法类似。与函数体不同的是:函数体的执行部分至少有一个语句给函数名赋值, 而过程体的执行部分不能给过程名赋值。 5、过程通过一条独立的过程调用语句来实现调用,格式如下: 过程名[(实际参数表)];

6、实参的个数必须与形参一一对应。
7、对应于值形参的实参可以是表达式,对应于变量形参的实参只能是变量。例如: procedure key(x,y:real;var k:integer); … begin


key(1.5,1,4); key(1.5,1,n); … end.

错误 正确

8、过程调用的步骤为:
1)将实参的值或变量的“地址”传送给对应的形参; 2)执行过程体,返回调用程序。

程序举例
【翻牌问题】 有n(2≤n≤10000)张扑克牌,使他们全部正面朝上。从第二张牌开始,把凡是2的倍 数位置上的牌翻成正面朝下,接着从第3张牌开始,把凡是3的倍数位置上的牌正面朝上的 翻成正面朝下,正面朝下的翻成正面朝上,接着从第4张牌开始,把凡是4的倍数位置上的 牌按此规律翻转。以此类推,直到第n张牌。统计最后有几张牌正面朝上,并打印出他们的 位置。 【输入格式】 共一行,一个整数,表示n张牌。 【输出格式】 共一行;前面若干个整数,表示正面朝上的牌的编号,最后一个整数表示共有多少张牌正 面朝上。 【输入样例】 10 【输出样例】 1 4 9 3

【问题分析】 根据题目我们可以用一个布尔 型数组p[i]模拟扑克牌,用not p[i]模拟翻牌的动作,编写一个翻 牌的过程fp(x),x表示要翻几的倍 数。这样通过一个循环就可以把2 ~n的牌都翻一遍。最后检查数组 中那些牌是朝上的,将其下标i输 出就可以了。

program pkp; var p:array[1..10000] of boolean; i,n,s:integer;

过程名

procedure fp(x:integer); var 形参表 i:integer; begin i:=1; while i*x<=n do begin 过程体 p[i*x]:=not p[i*x]; inc(i); end; end;

begin readln(n); for i:=2 to n do fp(i); 调用翻牌过程 s:=0; for i:=1 to n do if p[i]=false then begin 输出正面朝上的牌 write(i,' '); inc(s); end; 输出总数 writeln(s); end.

【绘制圣诞树】 诞节要到了,不少商家在宣传板上绘制了圣诞树的图案,如图所示。一棵 圣诞树由A和B两部分组成:A部分是由n(n≥)个呈三角形的字符矩阵构成的 ,每个字符矩阵由三个参数ai、bi、ci唯一确定。ai表示字符矩阵第一行字符的 个数;bi表示字符矩阵从第二行开始每一行与它上面那行的字符数之差均为bi; ci则表示字符矩阵的行数。B部分是一个x行y列的长方形,由x和y这两个参数 唯一确定。 因为圣诞树是中轴对称的,所以根据所有的参数构成的圣诞树是唯一确定 的。简单来讲,我们所说的一棵圣诞树就是像图那样的*矩阵,每一行的字符 是指若干个连在一起的*。 【输入格式】 输入数据分若干行。第一行是一个整数n,表示A部分中字符矩阵的个数。 以下n行,每行有三个正整数ai、bi、ci(ai为奇数,bi为偶数)。输入数据的 最后一行,有两个正整数x、y(y是奇数),表示B部分的行数和列数。 【输出格式】 对于输入数据给定的圣诞参数,输出与之对应的圣诞树矩阵。 【说明】 (1)输入数据保证圣诞树不会超出一页纸的范围。 (2)要求圣诞树是轴对称的,并且字符矩阵的第一列至少有一个非空格字符 ,即圣诞树尽量“顶格写”。在以上要求下,输出的圣诞树矩阵一定是唯一的 (不考虑每行行末的空格)。 【输入样例】 3 143 543 544 25 【输出样例】

程序举例

* ***** ********* ***** ********* ************* ***** ********* ************* ***************** ***** *****

【问题分析】

* ***** 由于题目已经提示我们,圣诞树是由A和B两部分构成。因 ********* 此我们绘制图形时也分为两部分来考虑。而A和B的绘制都有考 ***** 虑图形的对称轴。因此整个问题分解为三个子问题: ********* 1)输入图形数据,并确定对称轴(用于确定每行前的空格数 ************* ) ***** 2)绘制A部分。 ********* 3)绘制B部分。 ************* ***************** 分析子问题1:设A部分图形中每个小三角最后一行有k ***** 个*,那么每个小三角对称轴所在列数m=(k+1)div 2,A部分图形中最大的m就是整个图形的对称轴(每行 *****
前的空格数=图形对称轴-每行对称轴)

分析子问题2:由于A部分有n段树,每一段树的图形是类 似的,所以我们可以设计一个过程sj(a,b,c)通过循环绘 制每一段树。
分析子问题3:B部分比较容易,可以通过循环绘制一个x行y列的矩阵,也可以把 它看成子问题2中的一个特殊矩阵即:a=y,b=0,c=x的矩阵,这样就可以把子问 题3归入子问题2了。

绘制A部 分每段树 的过程

读入每段树 的a,b,c值并 存入数组, 同时计算最 大的中轴所 在的列

绘制B部 分图形

program sds; var a,b,c:array[1..100] of integer; n,x,y,i,j,t,m,k:integer; procedure sj(a,b,c:integer); var i,j,t:integer; begin for i:=1 to c do begin 计算每行*的个数 t:=a+(i-1)*b; 输出没行前的空格 write('':m-(t+1) div 2); for j:=1 to t do write('*'); writeln; end; end; begin readln(n); m为中轴所在的列 m:=0; for i:=1 to n do begin 求每个小三角最后一行的*号数 readln(a[i],b[i],c[i]); k:=a[i]+(c[i]-1)*b[i]; t:=(k+1) div 2; 求每个小三角的对称轴 if m<t then m:=t; 求最大的对称轴 end; 读入矩形的行数x和列数y readln(x,y); 调用过程绘制A for i:=1 to n do sj(a[i],b[i],c[i]); 部分图形 for i:=1 to x do begin write('':m-(y+1) div 2); for j:=1 to y do write('*'); writeln; end; end.

绘制B部分图形

program sds; var a,b,c:array[1..100] of integer; n,x,y,i,j,t,m:integer; procedure sj(a,b,c:integer); var i,j,t:integer; begin for i:=1 to c do begin t:=a+(i-1)*b; write('':m-(t+1) div 2); for j:=1 to t do write('*'); writeln; end; end; begin readln(n); m:=0; for i:=1 to n do begin readln(a[i],b[i],c[i]); t:=(a[i]+(c[i]-1)*b[i]+1) div 2; if m<t then m:=t; end; readln(x,y); for i:=1 to n do sj(a[i],b[i],c[i]); sj(y,0,x); end.

上 机 练 习
1、给定n*n的整数矩阵,输出其转置矩阵(2≤n≤100)
1 5 2 6 3 7 4 8 1 2 5 6 7 8 9 10 11 12 13 14 15 16

9 10 11 12 3 【输入格式】 13 14 15 16 4 共n+1行 第一行,1个整数,表示n 后n行,每行n个整数,表示n*n的矩阵 【输出格式】 共n行,每行n个整数,表示转置后的矩阵 【输入样例】 3 1 2 3 4 5 6 7 8 9 【输出样例】 1 4 7 2 5 8 3 6 9 【源文件】jzzz.pas 【输入文件】jzzz.in 【输出文件】jzzz.out

2、将正整数n(0≤n≤10000)转化为二进制数。
【输入格式】 共一行,1个整数,表示正整数n 【输出格式】 共1行,若干个整数,表示转化后的二进制数 【输入样例】 9 【输出样例】 1001 【源文件】bin.pas 【输入文件】bin.in 【输出文件】bin.out

数值形参与变量形参
数值形参: 数值形参是指形式参数表中前面没有var标识的参数。它仅为过程和函数的执 行提供初值,而不影响实参的值。在调用过程或函数时,数值形参所对应的实参必 须是表达式,并且实参必须和形参赋值相容。 program ex1; var a:integer; procedure addl(x:integer); begin x:=x+10; writeln('x=',x); end; begin a:=0; addl(a); writeln('a=',a); end. x 0 x:=x+10 x 10

a 0

输出结果: x=10 a=0

变量形参:
变量形参是形参表中前面有var标识的参数。变量形参的值可以被带出子程序。 变量形参要求它所对应的实参是和它同一类型的变量。 program ex1; var a:integer; procedure addl(var x:integer); begin x:=x+10; writeln('x=',x); end; begin a:=0; addl(a); writeln('a=',a); end. 输出结果: x=10 a=10 x x:=x+10 x

a 0

a 10

变量及其作用域
全局变量和局部变量 在主程序中声明的变量将在整个程序发生作用,因此,称为全程变量,而在子 程序中声明的变量仅在子程序中发生作用,因此,称为局部变量。变量在程序中的 作用范围称为变量的作用域。

变量作用域 1)局部变量的作用域仅限于它所在的子程序

2)当全程变量和局部变量不同名时,全程变量的作用域为整个程序
3)当全程变量和局部变量同名时,全程变量的作用域不包含局部变量的作用域 4)形参也属于局部变量

program ex2; var x:integer;
procedure sub; var x:integer; begin x:=20; end; begin x:=10; sub; writeln('x=',x); end.
输出: x=10

program ex2; var x:integer;
procedure sub; begin x:=20; end; begin x:=10; sub; writeln('x=',x); end.

输出: x=20

程序举例
Program ex3; Var x,y:integer; Procedure swap(a,b:integer); Var t:integer; Begin t:=a;a:=b;b:=t;; End; Begin x:=10;y:=20; swap(x,y); writeln(‘x=‘,x,’y=‘:6,y); End. Program ex3; Var x,y:integer; Procedure swap(var a,b:integer); Var t:integer; Begin t:=a;a:=b;b:=t;; End; Begin x:=10;y:=20; swap(x,y); writeln(‘x=‘,x,’y=‘:6,y); End.

输出: x=10

y=20

输出: x=20

y=10

Program ex3; Var x,y:integer; Procedure swap(x,y:integer); Var t:integer; Begin t:=x;x:=y;y:=t;; End; Begin x:=10;y:=20; swap(x,y); writeln(‘x=‘,x,’y=‘:6,y); End.

Program ex3; Var x,y:integer; Procedure swap; Var t:integer; Begin t:=x;x:=y;y:=t;; End; Begin x:=10;y:=20; swap;
writeln(‘x=‘,x,’y=‘:6,y); End.

输出: x=10

y=20

输出: x=20

y=10

函数与过程的嵌套
函数和过程的内部可以定义和调用函数和过程,这就是函数或过程的嵌套, 不过要注意的是,函数和过程都必须先定义,后调用。 举例:打印n行如右图的三角形 * * * *

* * program ex4; program ex4; var var * * n:integer; n,i,j:integer; procedure sj(n:integer); begin var readln(n); i:integer; for i:=1 to n do procedure drawline(i:integer); begin for j:=1 to i do write('*'); var j:integer; writeln; begin end; for j:=1 to i do write('*'); end. writeln;
end; begin for i:=1 to n do drawline(i); end; begin readln(n); sj(n); end.

*

*

还可以这样写: program ex4; var n:integer; procedure drawline(i:integer); var j:integer; begin for j:=1 to i do write('*'); writeln; end; procedure sj(n:integer); var i:integer; begin for i:=1 to n do drawline(i); end; begin readln(n); sj(n); end.

program ex4; var n:integer; procedure sj(n:integer); var i:integer; begin for i:=1 to n do drawline(i); end; procedure drawline(i:integer); var j:integer; begin for j:=1 to i do write('*'); writeln; end; begin readln(n); sj(n); end. 这样写不可以

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

程序举例
编程计算n!

n!=1*2*3*…*(n-1)*n
readln(n); s:=1; for i:=1 to n do s:=s*i; writeln(n,’!=’,s) 常 规 做 法

程序举例
编程计算n! n!=1*2*3*…*(n-1)*n
递归函数: f(n)=
1

(n=1) (n>1)

递归终止条件 递归方程

n*f(n-1)

Program jc; 递 归 程 序 Var n:integer; Function f(m:integer):real; Begin if m=1 then f:=1 else f:=m*f(m-1); End; Begin readln(n); writeln(n,’!=’,f(n)) End.

程序举例
编程计算n! n!=1*2*3*…*(n-1)*n 递归调用过程
5!=f(5) 5*f(4) 4*f(3)

3*f(2)
2*f(1) 1

注意:递归程序在运行过程中需要保留每次递归调用时的参数和局部
变量,这样就需要占用大量的存储空间和耗费更多的时间,因此程序的运 行效率比较低。

程序举例
求m,n的最大公约数。
递归函数:
gcd(m,n)= gcd(n,(m mod n)) (m mod n<>0)

n

(m mod n=0)

m n gcd

m mod n

试试看能不能写出递归程序

程序举例
楼梯有n(n<=20)级台阶,上楼可以一步上1级,也可以一步上2级,请
你计算共有多少不同的走法。
第1步 第2步 … 第x步 1 2 … … 1 2 2 … … 1 1 2 … … … … … … … … … … 1 2 f(3) f(2) f(2) f(1) f(4) f(3)

f(5)

如果设f(n)为n级台阶的走法总和,那么: 当第x步只走1级台阶时,共有f(n-1)种走法; 当第x步走2级台阶时,共有f(n-2)种走法; 因此综合这两种情况得:f(n)=f(n-1)+f(n-2) 这样就缩小了问题的规模 递归函数: 1

f(2)

f(1)

(n=1) (n=2)

f(n)

2

f(n-1)+f(n-2)

(n>2)

program tj; var n:integer; function f(x:integer):integer; begin if x=1 then f:=1 else if x=2 then f:=2 else f:=f(x-1)+f(x-2); end; begin readln(n); writeln(f(n)); end.

程序举例
【汉诺塔问题】
设有n个大小不等的中空圆盘,按从小到大的顺序叠套在立柱A上,另外还 有两根立柱B和C。现要求把全部圆盘从A柱移到C柱,移动过程中可借助B 柱。移动要求如下: 1)一次只允许移动一个盘子; 2)任何时候任何柱子上不允许把大盘放在小盘上边; 3)可使用任何一根立柱暂存圆盘;

请你编程输出每一步移动方案。

A

B

C

A A->C

B

C

A A->B

B

C

A C->B

B

C

A

B

C

A->C A B->A B C

A B->C

B

C

A A->C

B

C

A

B

C

目标: 将n个盘子从A盘移动到C盘,借助B盘。 移动策略: 1)先将n-1个盘子从A盘移动到B盘,借助C盘。 2)将第n个盘子从A盘移动到C盘 3)再将n-1个盘子从B盘移动到C盘,借助A盘。

A

B

C

A

B

C

A

B

C

目标: 将n个盘子从A盘移动到C盘,借助B盘。 移动策略: 1)先将n-1个盘子从A盘移动到B盘,借助C盘。 2)将第n个盘子从A盘移动到C盘 3)再将n-1个盘子从B盘移动到C盘,借助A盘。 这样问题的规模就缩小到n-1了 因此我们可以设计一个过程p(n,x,y,z)表示将n个盘子从x柱移动到y柱的过程 ,其中z柱为过渡柱,以3个盘子为例,过程如下: P(3,’A’,’C’,’B’) P(2,’A’,’B’,’C’) P(1,’A’,’C’,’B’) A->B A->C P(2,’B’,’C’,’A’) B->C P(1,’A’,’C’,’B’)

P(1,’C’,’B’,’A’) P(1,’B’,’A’,’C’)

A->C

C->B

B->A

A->C

递归函数:
p(n,x,y,z)

p(n-1,x,z,y) 输出x->y
p(n-1,z,y,x)

program hnt; var total:integer; procedure move(n:integer;x,y,z:char); begin if n=1 then writeln(x,'->',y) else begin move(n-1,x,z,y); writeln(x,'->',y); move(n-1,z,y,x) end end; begin readln(total); move(total,'A',‘C',‘B') end.

上机练习
已知:f(x,n)= 的值。 输入样例:4.5 10 输出样例:3.676
n ? (n ? 1) ? (n ? 2) ? ... ? 1 ? x

计算x=4.2,n=10以及x=2.5,n=15时f

上机练习
【折半查找问题】有n个已经排好顺序的整数存储在数组a中,现在从

键盘输入一个数x,请判断它是否在这n个数中,如果存在输出“find”否
则输出“no find”。 请你用递归算法编写search( )过程,将程序补充完整。
program zbcz; const n=10; var x,i:integer; a:array[1..100] of integer; 在此处编写search( )过程 begin for i:=1 to n do a[i]:=2*i; readln(x); search(x,1,n); end.

递归算法的应用
【组合问题】找出从自然数1,2,3…,n(n≤15)中任取r个数的所有组合。 例如:n=5,r=3的所有组合为: 1)1 2 3 6)1 4 5 2)1 2 4 7)2 3 4 2 )1 2 5 8 )2 3 5 4)1 3 4 9)2 4 5 5)1 3 5 10)3 4 5

输入格式:共一行,两个整数分别表示n和r 输出格式:若干行,每行r个整数,表示所有可能的组合数 输入样例:3 输出样例: 12 13 2

23
常规解法:

1)我们可以采用翻牌模拟法
2)由于组合中不能有相同元素,我们可以先将数组初始化为0到r,即组合的第一种状态; 3)设定一个翻牌指针j,让指针从第r个元素(j:=r)开始翻牌(a[j]:=a[j]+1),每翻 一次就得到一种组合方案。当指针指向的元素翻到最大值时,就将指针前移一格,继续翻牌

,同时将已经翻到最大值得牌,重新初始化,然后重复以上步骤,直到a[0]=1。

readln(n,r); for i:=0 to r do a[i]:=i; while a[0]<>1 do begin for i:=1 to r do write(a[i]); writeln; j:=r; while a[j]=n-r+j do j:=j-1; a[j]:=a[j]+1; for i:=j+1 to r do a[i]:=a[i-1]+1; end; 将翻到最大值的牌重新初始化

初始化数组为组合的第一种状态

当翻到最大值时,移动翻牌指针

递归解法: 1)我们也可以顺推产生组合的过程; 2)第一个数a[1]有1到n-r+1种选择; 3)为了不产生重复,第二个数a[2]有a[1]+1到n-r+2种选择, 即第i个数a[i]有a[i-1]+1到n-r+i种选择

4)以此类推直到第r个数,这就产生了递归的过程。

procedure find(i:integer); var j:integer; begin if i>r then 如果已 begin 经产生 for j:=1 to r do write(a[j]:3); 了r个数 writeln; ,则输 end 出组合 else 结果 第i个数有a[i-1]+1到n-r+i种取值 for j:=a[i-1]+1 to n-r+i do begin a[i]:=j; 把新产生的数j放入数组,i表示第几个数 find(i+1); 查找下一个数 end; end; begin readln(n,r); a[0]:=0; 将0号元素初值设为0 find(1); end.

【合理排列】由m个A,n个B组成若干个排列。从某个排列的位置1开始数,数到任意位 置时都能保证A的个数不少于B的个数,则称该排列为合理排列。例如:当m=2,n=2时 A A B B(合理) A B A B(合理) A B B A(不合理) B B A A(不合理) 合理排列数有2种 输入格式:只有一行两个整数m,n(1≤n≤m≤12)(用空格分隔) 输出格式:一个整数(所有的合理排列数) 输入样例:3 2 输出样例:5 问题分析:

1)我们可以顺推模拟排队的情况;
2)从第1个开始,第1个只能是A,第2个可以是A也可以是B; 3)我们可以用两个计数器i和j分别记录当前位置前A和B的个数; 4)如果i<m并且i>=j那么放A,即i+1; 5)如果j<n并且i>j那么放B,即j+1; 5)以此向后推,直到i=m并且j=n为止,这就产生了一种新排列,总数计数器s加1。

program pailie; var m,n:integer; s:longint; procedure pl(i,j:integer); begin if (i=m) and (j=n) then 如果生成一个排列计数器s加1 s:=s+1 else begin 增加一个A if (i<m) and (i>=j) then pl(i+1,j); if (j<n) and (i>j) then pl(i,j+1); 增加一个B end; end; begin readln(m,n); pl(1,0); writeln(s); end.

优化算法
program pailie; var m,n:integer; s:longint; procedure pl(i,j:integer); begin if (i=m) or (j=n) then s:=s+1 else begin if (i<m) then pl(i+1,j); if (j<n) and (i>j) then pl(i,j+1); end; end; begin readln(m,n); pl(1,0); writeln(s); end.

上机练习
例5、把自然数N(N<=100)分解为若干个自然数之和,有几种情况。 如N=5时,有7种情况

5=1+1+1+1+1
5=1+1+1+2 5=1+1+3 5=1+2+2 5=1+4 5=2+3 5=5

【输入格式】 共1行1个整数,表示n
【输出格式】 共1行,1个整数,共多少种情况。 【输入样例】5 【输出样例】7

【源文件】fenjie.pas

【输入文件】fenjie.in

【输出文件】fenjie.out

上机练习
【简单的背包问题】设有一个背包,可以放入的重量为s。现有n件物品,重量分别为
w1,w2?wi?,wn,(1≤i≤n)均为正整数,从n件物品中挑选若干件,使得放入背包的重 量之和正好为s。找到一组解即可。 【输入格式】

共1行n+2个整数,第1个数表示可放入重量s,第2个数表示n件物品,后面n个数表示w1,w2?wn
【输出格式】 共1行,1个字符串“Yes”或“No” 【输入样例】20 5 1 3 5 7 9 【输出样例】Yes 【源文件】beibao.pas 【输入文件】beibao.in 【输出文件】beibao.out

第 十 讲 集合与记录

数据类型
标准类型

整型(Integer) 实型(Real) 字符型(Char) 布尔型(Boolean) 枚举型 自定义类型 子界型 数组类型 集合类型

简单类型

构造类型 记录类型 文件类型 指针类型

集 合类型
集合就是由同一种有序类型数据组成的数据集合体。集合中的每个数 据称为集合的“元素”,一个集合中的元素不得超过255个。 集合在Pascal中的表示 常量方式:[元素1,元素2,?,元素n] 例如:[1,2,4,7] 特点: 1)集合的值与方括号内元素出现的次序无关。如:[1,2,3]和[1,3,2] [1] []

2)集合中同一元素重复出现对集合值没有影响。如:[1,1,2,3]和[1,2,3]
3)集合中如果元素的值是连续的,可以用子界来表示。 如:[1,2,3,4]和[1..4]

4)集合的基类型可以是任何顺序类型。
5)每个元素都可用基类型所允许的表达式来表示。如:[1+10,2*3,4]

变量方式 方法一
Type 类型名=set of 基类型; Var 变量名:类型标识符; 例如: Type num1=set of 1..10; Var a:num1;

方法二
Var 变量名:set of 基类型;

例如: Var a:set of 1..10;

与集合有关的运算 1、赋值运算(:=) 例如: Var ch1,ch2:set of ‘a’..’z’; Begin ch1:=[];ch2:=[‘a’..’d’]; ch1:=ch2; End. 2、并集运算(+)

B A A

B A

B

A+B

3、交集运算(*)

B A A A*B

B

4、差集运算(-)

B A A A-B

B B

A

5、关系运算

运算符
= <>

名称
相等 不相等

表示形式
A=B A<>B

定义
测试两个集合是否相等 测试两个集合是否不相等

<=
>=

包含于
包含

A<=B
A>=B

测试集合A中的元素是否都包含于集合B 中
测试集合A是否包含集合B中的所有元素

6、in 运算(判断in左边的数据是否在右边的集合中)

集合的应用
例1:从键盘上输入若干个大写字母,以“.”号结束,按字母表顺序输出其 中出现了哪些字母。例如:输入DDCBCDDAABBCCCDD.则输出ABCD。 问题分析:我们可以逐个将读入的字符存储到一个集合中,由于集合会忽略重复 的元素,所以最后集合中出现的所有元素就是字母出现的所有种类。
program zm; var zf:set of 'A'..'Z'; ch:char; begin read(ch); while ch<>'.' do begin zf:=zf+[ch]; read(ch) end; for ch:='A' to 'Z' do if ch in zf then write(ch); writeln end.

输出集合中的每一个元素

与枚举类型一样,在Pascal中不允许直接使用read/readln语句和 write/writeln语句对集合进行输入/输出,只能间接进行读写操作。

例2:一共有t个人,用1~t编号。现在一共有n场party.每场有m个人参加。 问t个人中每一场都参加的是哪些人?
输入格式: 第一行三个数t,n,m(t<=100,n<=10,m<=10) 之后n行,每行m个数,表示每场参加的人员编号 输出格式: 1行,升序输出所有每场都参加的人员编号。 输入样例: 6 3 3 4 2 3 2 3 4 3 4 5 问题分析:如果把每场的参加者看成一个集合,那么每 一场都参加的人实际上就是这些集合的交集

输出样列:
3 4

var bh:set of 1..100; now:set of 1..100; t,n,m,i,j,num:integer; begin read(t,n,m); 将bh集合初始化为所有编号的全集 bh:=[1..t]; for i:=1 to n do begin now:=[]; for j:=1 to m do begin read(num); 将每场派对的参加者编号存入now集合 now:=now+[num]; end; bh:=bh*now 每场派对参加者集合的累积交集,为我们最后所求答案 end; for i:=1 to t do if i in bh then write(i,' '); end.

例3:用筛选法输出2~n(n<=250)之间的所有素数 问题分析:建立一个2~n的集合,依次把集合中最小的数的所有倍数去除,剩下 的就是素数
var p:set of 2..250; i,j:integer; begin p:=[2..250]; for i:=2 to 250 do if i in p then begin j:=2*i; while j<=250 do begin p:=p-[j]; j:=j+i; end; end; for i:=2 to 250 do if i in p then write(i,' '); end.

上机练习
有两个集合A和B分别放入K1和K2个小于200的正整数,按以下要求分别求值。 1)求在集合A中,同时也在集合B中的所有整数。 2)求在集合A中,但不在集合B中的所有整数。 3)既不在集合A中,也不在集合B中的200以内的所有整数。 输入格式: 第一行2个整数k1,k2 第二行为集合A中的k1个整数 第三行为集合B中的k2个整数 输出格式: 第一行为若干个整数(问题1的解)或’NULL’(问题1无解) 第二行为若干个整数(问题2的解)或’NULL’(问题2无解) 第三行为若干个整数(问题3的解)或’NULL’(问题3无解) 输入样例: 2 3 20 35 33 35 40 输出样例: 35 20 1..19 21..32 34 36 41 42..200

输入一段文章(文章字符数在10000以内),统计文章中小写元音字母(a,e,i,o,u) 和小写辅音字母(除了元音以外的字母)出现的次数。 输入格式:

若干行单词组成的文章
输出格式: 一行2个整数分别表示元音的次数和辅音的次数 输入样例: Welcome to you! 输出样例: 6 5

学生档案问题

姓名 羊嘉智 施若男
方法一: Var

性别 男 女

出生年月
1999/1/ 1
1999/1/ 2

家庭住址 南京 北京

联系电话
123 456

电子邮件 无 无

入学成绩
496 550

name,sex,birthday,address,mail:array[1..100] of string; phone:array[1..100] of longint; result:array[1..100] of integer;

记录类型
记录就是由一系列不同类型数据构成的数据集合体。 记 录 型 变 量 的 定 义 方 式

方式一
Type 类型标识符=record 域名1:类型; 域名2:类型; …… 域名n:类型;

举例
Type student=record name:string[10]; sex:char; birthday:string; address:string phone:longint; mail:string; result:integer; End; Var a:student;

End;
Var 变量名:类型标识符;

方式二 Var

举例 var a:record name:string[10]; sex:char; birthday:string; address:string phone:longint; mail:string; result:integer; End;

变量名:record
域名1:类型; 域名2:类型;

……
域名n:类型; End;

注意:
1)定义时同一记录中不能有相同域名; 2)各个域的数据类型可以是简单类型,也可以是构造类型;

记录成员的引用
1、整体引用(主要用于赋值) 例如: var a,b:student; begin a:=b; end.

2、引用域成员 方法一:记录名.域名
例如: a.name:=‘gexin’ a.sex:=‘b’ read(a.name); write(a.sex) 方法二:使用开域语句 with 记录名 do

例如: with a do begin name:=‘gexin’; sex:=‘b’; result:=560; read(address); end;

记录数组
记录数组定义方法:在定义数组时将数组的基类型定义为记录类型即可。 例如: Type student=record name:string[10]; sex:char; birthday:string; address:string phone:longint; mail:string; result:integer; End; Var a:array[1..10] of student; i:integer; Begin for i:=1 to 10 do with a[i] do begin readln(name);readln(name);readln(sex);readln(birthday); readln(address);readln(mail);readln(phone);readln(result); end; End.

变体记录 在前面介绍的记录中,每个记录的域个数和类型都是固 定不变的,在实际问题中,仅有这样的数据类型是不够的。例 如,在学生档案中的登记中,对男同学要求只登记身高,而

对女同学则要求只登记体重,那么这样的数据要想定义成记
录该怎么办呢?这时,要用到“变体记录”
type stu=record score: array[1..6] of 0..100; age: integer; case sex: char of ‘m’: (weight: 70...150); ‘f’: (height: real); end;

应 用 举 例
1、输入20位学生的数据记录(包含学号、姓名、性别、成绩四个域),按成绩从高 到低排序输出。
program p7_3; const n=20; type student=record num:integer; s_name:string[15]; sex:char; score:real; end; var stu:array[1..n] of student; t:student; i,j:integer; begin for i:=1 to n do with stu[i] do begin readln(num);readln(s_name);readln(sex);readln(score); end; for i:=1 to n-1 do begin max:=i for j:=i+1 to n do if stu[i].score<stu[j].score then max:=j; t:=stu[i];stu[i]:=stu[max];stu[max]:=t; end; for i:=1 to n do begin with stu[i] do write(num:8,s_name:8,sex:2,score:8:1); writeln; end; end.

第十二讲

算法

算 法 评 价
对算法优劣的评定称为“算法评价”,算法评价的目的在于从不同的算法中选出一种较为 合适的算法,一般对算法的评价主要包括四个方面: 1)算法的正确性 算法的正确性是指在合理的数据输入下,能在有限的运行时间内得到正确的结果。

2)算法的简单性 算法的简单性是指算法有利于阅读,这样也使得程序的编写、修改和调试较容易,但算法简 单并不意味着效率最高,效率比简单性更重要。

3)算法的时间复杂性 通常我们把算法中包含简单操作的次数称作算法的时间复杂性。它是一个算法运行时间的相 对量度,一般用数量级的形式给出。 4)算法的空间复杂性 空间复杂性通常是指程序运行过程中占用存储空间的大小,包括程序中的所有变量和递归时 所使用的堆栈空间两部分。一般也用数量级的形式给出。

算法的时间复杂度

如果撇开计算机硬件、软件的因素,我们可以认为一个特定算法的时间复杂度, 只依赖于问题的规模n,因此我们用一个与n相关的函数f(n)来表示时间复杂度,记作 T(n)=O(f(n)),他表示随着问题规模n的增大,算法执行时间的增长率和f(n)的增长 率相同。
常见的时间复杂度有: O(1) O(n) O(n2) 常量阶 线性阶 平方阶 对数阶

O(nlog2n)

O(2n) 指数阶
大小关系为: O(1) < O(log2n) < O(n)< O(nlog2n) < O(n2) < O(n3) < O(2n) 算法的时间复杂度

空间复杂度也用与问题规模n相关的函数f(n)来表示,记作 S(n)=O(f(n))

例1:编程计算:y = anxn + an-1xn-1 + ? + a1x1 + a0
y=a[0]; For k:=1 to n do Begin s:=a[k]; for j:=1 to k do s:=s*x; y:=y+s; End; 空间复杂性 存储空间为数组a的空间,规模为n(数量级为n)记做 O(n)

时间复杂性 1)乘法运算=1+2+…+n=n(n+1)/2 次 2)加法运算=n 次。 共:n(n+1)/2+n 次(数量级n2) 记做 O(n2)

Writeln(‘y=‘,y);

例1:编程计算:y = anxn + an-1xn-1 + ? + a1x1 + a0
b[0]:=1; For k:=1 to n do b[k]:=b[k-1]*x;

y:=a[0];
For k:=1 to n do y:=y+a[k]*b[k]; Writeln(‘y=‘,y);

时间复杂性

1)第一个循环乘法运算=n 次
2)第二个循环乘法运算=n 次。 共:2n 次(数量级n) 记做 O(n)

空间复杂性 存储空间为数组a,b的存储空间,规模为2n(数量级为n)记做 O(n)

例1:编程计算:y = anxn + an-1xn-1 + ? + a1x1 + a0
将表达式改写为 y =(…((anx + an-1) x + an-2 )… + a1 )*x + a0 y:=a[n]; For k:=n-1 downto 0 do y:=y*x+a[k]; Writeln(‘y=‘,y);

时间复杂性 就一个循环=n 次 共:n 次(数量级n) 记做 O(n) 空间复杂性

存储空间为数组a存储空间,规模为n(数量级为n)记做 O(n)

第十三讲

穷举法

穷举法是基于计算机特点进行解题的思维方法,即根据问题的约束条 件将所有可能的解都列举出来,然后一一验证是否符合题目要求,从而得 到问题的解。(这种方法一般在我们没有更好的解决方法时使用) 一般模式为:
1 )列出问题解的可能范围,一般用循环或循 环嵌套结构实现 2)探究,挖掘出问题解的约束条件 3 )根据约束条件优化算法,尽可能地缩小穷 举范围,较少穷举次数,降低算法的时间复杂 度和空间复杂度

【完全数问题】 古希腊人称因子的和等于它本身的数是完全数,例如28的因子是1,2,4,7, 14,而28=1+2+4+7+14,所以28是一个完全数,编程输出2~1000内的所有完全数。
问题分析: 从2到1000逐个穷举,判断每个数是否符合完全数的条件,即把每一个数的所有因子找 出来,并求出他们的和,看是否等于这个数本身 program wqs; program wqs; var var n,i,s:integer; n,i,s:integer; begin begin for n:=2 to 1000 do for n:=2 to 1000 do begin begin s:=0; s:=0; for i:=1 to trunc(sqrt(n)) do for i:=1 to n-1 do if n mod i=0 then s:=s+i+(n div i); if n mod i=0 then s:=s+i; if s=2*n then write(n,' ') if s=n then write(n,' ') end; end; end. end.

【一元三次方程的解】 设有一元三次方程 ax3+bx2+cx+d=0 ,给出该方程中各项系数 a,b,c,d (均为实 数),并假设该方程一定存在三个不同的实数解(范围在-100~100之间),且解与 解之差的绝对值大于等于1。请编程由小到大输出这三个解,精确到小数点后2位。 输入样例:1 -5 -4 20 输出样例:-2.00 2.00 5.00
问题分析: 这个方程要想直接求解不可能,只能换个角度想,在-100~100之间找三个满足方程的实 数。但是实数不是顺序类型,无法直接穷举,只能利用题目给出的限制条件:解只要精确到 小数点后两位,所以我们只需将循环变量扩大100倍即可顺利穷举了,最后再将结果缩小100 倍输出。

readln(a,b,c,d); for i:=-10000 to 10000 do begin x:=i/100; if abs(a*x*x*x+b*x*x+c*x+d)<0.000001 then write(x:0:2,' '); end;

优 化
readln(a,b,c,d);
i:=-10000; while i<=10000 do begin x:=i/100; if abs(a*x*x*x+b*x*x+c*x+d)<0.000001 then begin write(x:0:2,' '); i:=i+100; end;

i:=i+1;
end;

【四皇后问题】 在4×4的棋盘上安置4个皇后,要求任意两个皇后不在同一行,同一列,同一条 对角线上,输出所有可能的皇后放置方案。(输出皇后所在的列即可) 输出样例: 2 4 1 3 3 1 4 2
问题分析: 由于4个皇后在4×4的棋盘上不同行,不同列,所以肯定每行都有一个皇后。因此只要穷 举每个皇后的列位置是否合法(即不在同列,同一条对角线)就可以了。

begin for i1:=1 to 4 do for i2:=1 to 4 do for i3:=1 to 4 do for i4:=1 to 4 do begin s[1]:=i1; s[2]:=i2; if check then print; end end.

s[3]:=i3;

s[4]:=i4;

主程序 穷举每 一个皇 后在不 同列的 所有可 能性

function check:boolean; var i,j:integer; begin check:=true; for i:=1 to 3 do for j:=i+1 to 4 do if (s[i]=s[j]) or (s[i]-i=s[j]-j) or (s[i]+i=s[j]+j) then begin check:=false; exit; 判断是否同列,同对角线 end; end; procedure print; var i:integer; begin for i:=1 to 4 do write(s[i]:2); writeln end;

输出可行方案

【阿姆斯特朗数】 编程找出三位到七位数中的所有阿姆斯特朗数。阿姆斯特朗数也叫水仙花数, 它的定义如下:一个n位自然数的各位数字的n次方之和等于它本身。 输出样例: 153 370 371 407 1634 8208 9474 54748 92727 93084 548834 1741725 4210818 9800817 9926315

问题分析: 由于这种数没有规律,所以只能采取穷举法。但如果对任意一个数k,都去求它的各位的 若干次方,再求和判断是否等于k,效率比较低。我们注意到每个位只可能是0~9,而且只会 计算3~7次方,因此可以采用“以空间换时间”的策略,使用一个二维表存放所有数字的各 次幂,再用一个一维数组存放各位数字,然后让这个数组中的数字从100变化到9999999,从 而找出所有的阿姆斯特朗数。

program amstl; const maxlen=7; var i,j,highest:integer; currentnumber,s:longint; power:array[0..9,0..maxlen] of longint; num:array[1..maxlen+1] of integer; begin for i:=0 to 9 do begin 建立0~9所有数 power[i,0]:=1; 字的次方表 for j:=1 to maxlen do power[i,j]:=power[i,j-1]*i; end; for i:=1 to maxlen+1 do num[i]:=0; 将num初始化为 num[3]:=1; highest:=3; 0010000 currentnumber:=100; 将各位数的次方 repeat 加起来,并检查 s:=0; for i:=1 to highest do s:=s+power[num[i],highest]; 和原数是否相等 if currentnumber=s then write(currentnumber,' '); ,如果相等就输 i:=1; 出 num[i]:=num[i]+1; 改变num while num[i]=10 do 的值并检 begin 查是否符 num[i]:=0; 改变num和currentnumber的值 合条件 num[i+1]:=num[i+1]+1; i:=i+1; end; if i>highest then highest:=i; currentnumber:=currentnumber+1; until highest>maxlen end.

【方格填数】 在如图1所示的8个格子中放入1~8八个数字,使得相邻的和对角线的数字之差 不为1,编程输出所有放法。图2便是一种方法。

b1 b2 b3 b4 b5 b6 b7 b8
问题分析:

5 3

2 8

1 7
图2

6 4

图1

8个数字放到8个格子里共有8!=40320种方法。我们可以对这些方案逐一检测,输出符合 条件的解。但如果对这么多种方案逐一检测效率较低,最好能排除一些不可能的情况, 仔细观察你会注意到b3和b6两个格子,与它们“相邻”的格子有6个,也就是说,这两个 格子中的数,必须和6个数不连续,仅可以和一个数是连续的,这样的数只有2个,即1和8。 这样b1,b3,b6,b8这4个格子中数的放法仅有两种可能:2、8、1、7和7、1、8、2。而 b2,b4,b5,b7四个格子中的数仅需在3~6四个数中选择。经过上述优化,可行解仅有2×4! =48个,大大减少了计算量

b1 b2 b3 b4 b5 b6 b7 b8
图1
问题分析:

2 5 3

8 1 7
图2

6 4

经过上述优化,可能的解仅有2×4!=48个,而这48种可能解中,b1,b3,b6,b8是肯定符合要求 的,因此每种解也只需检查(b1,b2),(b1,b4),(b2,b5),(b4,b7),(b5,b8),(b7,b8)这6 对数之差是否等于1就可以了。

procedure try; var b2,b4,b5:integer; begin for b2:=3 to 6 do for b4:=3 to 6 do if b2<>b4 then for b5:=3 to 6 do if (b5<>b2) and (b5<>b4) then begin b[2]:=b2; b[4]:=b4; b[5]:=b5; b[7]:=18-b[2]-b[4]-b[5]; if (abs(b[1]-b[2])<>1) and (abs(b[1]-b[4])<>1) and (abs(b[2]-b[5])<>1) and (abs(b[4]-b[7])<>1) and (abs(b[5]-b[8])<>1) and (abs(b[7]-b[8])<>1) then begin writeln(' ',b[1]:2); writeln(b[2]:2,b[3]:2,b[4]:2); writeln(b[5]:2,b[6]:2,b[7]:2); writeln(' ',b[8]:2); writeln; end; end; end; begin b[1]:=2;b[3]:=8;b[6]:=1;b[8]:=7; try; b[1]:=7;b[3]:=1;b[6]:=8;b[8]:=2; try; readln; end.

上 机 练 习
【三角形个数】 输入一根木棒的长度,将该木棒分成三段,每段的长度为正整数;输出 由这三段小木棒组成的不一样边长的三角形个数。如输入10,则输出2,能 组成的两个三角形边长分别为2,4,4和3,3,4。 源文件:sjx.pas 输入文件:sjx.in 输出文件:sjx.out 输入格式:1个整数,代表木棒长度 输出格式:1个整数,代表三角形个数 输入样例:100 输出样例:208

【孪生素数】 在素数大家庭中,大小之差不超过2的两个素数称为一对“孪生素数”, 如2和3 ,3 和5 ,17 和19 等。请你编程统计出不大于自然数 n(0<n<=231)的素 数中,孪生素数的对数。 源文件lsss.pas 输入文件:lsss.in 输出文件:lsss.out 输入格式:1个整数,代表n 输出格式:1个整数,代表孪生素数的对数 输入样例:20 输出样例:5

【巧妙填数】 将1~9这9个数字填入一个3行3列的表格中。每一行的三个数字组成一个三位数。如果要使第二行的三 位数是第一行的两倍,第三行的三位数是第一行的三倍,应怎样填数?输出所有方案。 源文件qmts.pas 输出文件:qmts.out

输出格式:若干行,3行一组,每行1个3位整数
输出样例: 192 384 576 219 438 657 273 546 819 327 654 981

【邮票问题】 邮局发行一套票面有4种不同面值的邮票,如果每封信上贴邮票的张数不允 许超过3枚,存在整数r,使得不超过三枚的邮票可以贴出1、2、3..r的各种 面值来,请你找出使r值最大的邮票面值组合方式。 源文件ypwt.pas 输出文件:ypwt.out 输出格式:1行,共5个整数用空格分隔,分别表示4种邮票面值和最大r

输出样例:1 4 7 8 24

第十四讲

贪心法

贪心算法是指从问题的初始状态出发,通过若干次的贪心选择而得出 最优解或较优解的一种解题方法。但是,贪心算法总是作出在当前看来是 最优的选择,也就是说贪心算法并不是从整体上加以考虑,它所作出的选 择只是在某种意义上的局部最优解。并不一定是整个题目的最优解。
例如:在一个m×n的方格中,每一格都有一个权值,现在让你从左下角走到右 上角,每次移动只能向上或向右,试找出一条权值之和最大的路径, 3 1 4 2 6 1 0

如果用贪心法求解,所得路径为:1,3,4,6 实际解为:1,2,10,6 使用贪心法的关键在于找到贪心的标准以保证得到问题的最优解 。

【购买贺年卡】 新年快到了,笑笑打算给他的好朋友们发贺年卡,而且他已经选好了自己要购 买的贺卡的样式。俗话说得好,货比三家,笑笑来到商店,看了各个商铺这种贺卡 的价钱。不仅如此,笑笑还记住了每个商铺的存货量。已知笑笑打算购买m张贺卡, 问他最少花多少钱。 【输入格式】 第一行两个整数m和n。其中m表示要购买的贺卡的数量,n 表示商铺的个数。 以下n行,每行两个整数,分别表示该商铺这种贺卡的单价和存货量。 【输出格式】 仅一个数,表示笑笑花的最少钱数。 【输入样例】 10 4 4 3 6 2 8 10 3 6 【输出样例】 36 【数据规模】 0<m,n<=1000 可以保证最后结果在长整型范围内,商铺的总存货量不少于m。

问题分析:

将贺卡单价由低到高排序,然后从便宜的买起,如果当前商家的贺卡数量大于需要购买的 数量,则一次买足,否则买进商家的所有贺卡,并从所需数量中减去购买量,然后重复以上操 作,直到达到规定数量。

通过插 入排序 将存有 贺卡单 价和数 量的二 维数组 按单价 有低到 高排序

var i,j,m,n,jg,sl,ans:longint; data:array[1..1000,0..1] of longint; begin 读入要购买的贺卡数和商家数 readln(m,n); for i:=1 to n do begin readln(jg,sl); j:=i; while (j-1>0) and (jg<data[j-1,0]) do begin data[j,0]:=data[j-1,0]; data[j,1]:=data[j-1,1]; j:=j-1; end; data[j,0]:=jg; data[j,1]:=sl; end;

从便 宜的 买起 直到 达到 规定 数量

i:=1; ans:=0; 判断是否达到规定数量 while m<>0 do begin if m<data[i,1] then begin ans:=ans+m*data[i,0]; m:=0; end else begin ans:=ans+data[i,1]*data[i,0]; m:=m-data[i,1]; end; i:=i+1; end; writeln(ans); end.

如果当前商 家贺卡数量 大于规定数 量则买入m 张贺卡,同 时m清零, 否则买入商 家所有贺卡 ,同时从m 中减去购买 量。

优化方法

program gmhnk; var slb:array[1..1000] of integer; m,n,i,jg,sl:integer; ans:longint; begin fillchar(slb,sizeof(slb),0); readln(m,n); for i:=1 to n do begin readln(jg,sl); 读入所有单价和数量 slb[jg]:=sl; end; i:=1; ans:=0; while m<>0 do begin if m<slb[i] then begin ans:=ans+i*m; 从便宜的买 m:=0; 起直到达到 end 规定数量 else begin ans:=ans+i*slb[i]; m:=m-slb[i]; end; i:=i+1; end; writeln(ans); end.

下标表示价格,值表示数量

由于下标本身就是从小到 大排的所以不用排序

【舞伴的搭配】 学校将要举行一年一度的文艺汇演,笑笑所在的年级决定排练一个舞蹈,为选择表演者,老师定了如下

的规则,为了舞蹈的美观,当且仅当一男一女的身高之差不超过给定的整数c时,这两个人可以成为舞伴进
行演出。笑笑所在的年级共有m名男生和n名女生,给定每个人的身高(身高是从120到220之间的整数),问 最多有多少对舞蹈者进行演出。 例如,有3名女生和3名男生,女生的身高为 160厘米,170厘米,180厘米,男生身高为170厘米,175厘 米,185厘米,那么最多有2对舞蹈者:可以是女2和男1一组,女3和男2一组(女一不能和任何一个男生成为

一组),随意这个情况下,最多有2组舞者。
【输入格式】 第一行三个整数m,n,c,分别表示男生人数,女生人数,身高最大差值。 第二行m个整数,分别表示m个男生的身高。 第三行n个整数,分别表示n个女生的身高。

【输出格式】
仅一个整数,表示舞者组数的最大数目。 【输入样例】 3 3 7 170 185 175 160 170 180 【输出样例】 2 【数据规模】 m,n<=1000

问题分析: 将男生和女生的身高分别由低到高排序: boy[1]≤boy[2]≤?≤boy[m] girl[1]≤girl[2]≤?≤girl[n] 然后依次比较boy[i]和girl[j]如果abs(boy[i]-girl[j])≤c那么计数器加1,i,j后移一个 ,否则,如果男孩矮,则i向后移一个,如果女孩矮j向后移一个。
type 定义一个数组类型 sz=array[1..1000] of integer; var m,n,c,s,i,j:integer; boy,girl:sz; begin readln(m,n,c); inputdate(m,boy); 读入男女孩数据,并排序 inputdate(n,girl); i:=1;j:=1;s:=0; while (i<=m) and (j<=n) do begin 比较boy[i]和girl[j]如果 if abs(boy[i]-girl[j])<=c then abs(boy[i]-girl[j])≤c那 begin s:=s+1;inc(i);inc(j); 么计数器加1,i,j后移一个 end ,否则,如果男孩矮,则i else 向后移一个,如果女孩矮j if boy[i]>girl[j] then inc(j) else inc(i); 向后移一个。 end; writeln(s); end.

读入身 高并进 行排序

procedure inputdate(n:integer;var a:sz); var i,j,x:integer; begin for i:=1 to n do begin j:=i; read(x); while (j-1>0) and (x<a[j-1]) do begin a[j]:=a[j-1]; j:=j-1; end; a[j]:=x; end; end;

上 机 练 习
【设置喷水池】 笑笑家楼下是一条绿化带,可以用一条从0到10000的线段来表示。笑笑还知道这个绿化带上有n个地点( 坐标为0到10000的整数)可以设置喷水池。已知喷水池的半径为r(正整数)。笑笑希望知道至少需要设置多 少个喷水池才能把这个绿化带完全灌溉。 [源文件]:water.pas [输入文件]:water.in [输出文件]:water.out

[输入格式]: 第一行两个整数n和r ,分别表示可以设置喷水池的地点数和喷水池的半径。 第二行有n个数,分别表示可以设置喷水池的地点坐标。 [输出格式]:一个数,表示所需要设置喷水池的最小数量。

[输入样例] 5 4000 0 1000 3000 2000 9000

[输入样例]
2 [数据规模] n<=1000

【均分纸牌】(NOIP2002tg) [问题描述] 有 N 堆纸牌,编号分别为 1,2,?, N。每堆上有若干张,但纸牌总数必为 N 的 倍数。可以在任一堆上取若干张纸牌,然后移动。移牌规则为:在编号为 1 堆上取的纸牌,只 能移到编号为 2 的堆上;在编号为 N 的堆上取的纸牌,只能移到编号为 N-1 的堆上;其他堆 上取的纸牌,可以移到相邻左边或右边的堆上。现在要求找出一种移动方法,用最少的移动次数 使每堆上纸牌数都一样多。例如 N=4,4 堆纸牌数分别为: ① 9 ② 8 ③ 17 ④ 6

移动3次可达到目的: 从 ③ 取 4 张牌放到 ④ (9 8 13 10) -> 从 ③ 取 3 张牌放到 ②(9 11 10 10)-> 从 ② 取 1 张牌放到①(10 10 10 10)。 [输入格式]:共两行,第一行1个整数表示N堆纸牌,第二行N个整数表示每堆的纸牌数。 [输出格式]:一个整数,表示所有堆均达到相等时的最少移动次数。 [输入样例] 4 9 8 17 6

[输入样例]
3

第十五讲

递推与递归

递推和递归是两种重要的数学方法。它们之间是相互关联的,很多问 题即可以用递推法来编程,也可以用递归法来解决,它们之间可以相互转 化。所谓递推,就是从已知的初始条件出发,依据某种递推关系,逐次推 出所要求的各种中间结果及最后结果。而所谓递归,就是依据这种递推关 系,从问题的目标状态出发,反推到初始状态。在此过程中,采用子程序 递归调用的方式,来解决问题。

【斐波那契数列】 1 1 2 3 5 【递推式】 1 f(n)

8

13

21

34

55

89 ?

当n=1,n=2时

f(n-1)+f(n-2) 当n>2时
program fbnq; var f1,f2,fn,n,i:longint; begin readln(n); if (n=1) or (n=2) then fn:=1 else for i:=3 to n do begin fn:=f2+f1; f1:=f2; f2:=fn; end; writeln(fn); end. program fbnq; var n:longint;
function f(n:longint):longint; begin if (n=1) or (n=2) then f:=1 else f:=f(n-1)+f(n-2); end; begin readln(n); writeln(f(n)); end.

递 推 法

递 归 法

【淘气的钥匙】 班里出了个淘气包,经常搞得老师苦笑不得。淘气包今天的杰作是将班里每个 同学橱柜的钥匙放在了别人的橱柜里,这样每个人的橱柜里放着的都不是自己的钥 匙。当然,也就都锁不上橱柜的门了。老师对淘气包说:你在考验老师,那么老师 也考考你,好不好?淘气包跃跃欲试,老师的问题是:淘气包这种放置钥匙的方法, 会有多少种不同的情况呢?
【输入格式】 一个整数n :橱柜的个数即不同钥匙的个数(n<=12)。 【输出格式】 仅一个数,不同方案数。 【输入样例】 3 【输出样例】 2

问题分析: 这实际上是一个错位排列的问题。

Dn = n!(1-1/1!+1/2!-1/3!+…+(-1)n/n!)
假设n把钥匙共有f(n)种方法。 1)把第n把钥匙放到别人的柜子里共有n-1种方法 。 2)假设把第n把钥匙放到第k个柜子里,那么第k把钥匙的放法有两种可能,要么放到第 n个柜子里,要么不放到第n个柜子里。 3)如果放到第n个柜子里,则其余的钥匙有f(n-2)种放法。 4)如果不放到第n个柜子里,则除第n把钥匙,共有f(n-1)种放法。

【递推式】 0 当n=1时 当n=2时 当n>2时

f(n)

1 (n-1)×(f(n-2)+f(n-1))

program key; var n:longint; function f(n:longint):longint; begin case n of 1:f:=0; 2:f:=1; else f:=(n-1)*(f(n-2)+f(n-1)); 递 end; 推 end;

program key; var n,i,f1,f2,fn:longint; begin readln(n); if n=1 then fn:=0 else if n=2 then fn:=1 else begin f1:=0; f2:=1; for i:=3 to n do begin fn:=(i-1)*(f1+f2); f1:=f2; f2:=fn; end; end; writeln(fn); end.

递 归 法



begin readln(n); write(f(n)); end.

【生日蛋糕】 过生日的时候,生日蛋糕是不可缺少的快乐元素。 一般情况下,人们切蛋糕总 是经过蛋糕的中心,刀痕交叉地将蛋糕切分成若干块规则而美观的小块。淘气包生 日这一天,开始时,他还能规规矩矩地切蛋糕,可是切了几刀,他就不耐烦了,又 开始淘气了。一边看似杂乱的切着,一边他还振振有词:有一些刀不过中心点,可 以切分成更多的蛋糕小块。事实是这样吗? 我们来算一下,如果淘气包一共切了 n刀,其中只有m刀没有经过蛋糕的中心点, 那么他最多可以将蛋糕切分成多少块? 知道这个数字,和规则切分方案比较一下,就知道淘气包是不是正确的了。
【输入格式】 一行两个整数:n 和m (n≤10000 ,m ≤n-2) 【输出格式】 仅一个整数,表示切出的块数。 【输入样例】 3 1 【输出样例】 7

问题分析: 我们可以将这个问题分成两部分看,第一部分是经过同一点的直线共n-m条可以把蛋糕分成 2×(n-m)块,第二部分是n-m条以外的直线,例如第k条直线(k>n-m),这条直线最多可以和前 面k-1条都相交,因此会在原来的基础上再增加k块蛋糕,即f(k)=f(k-1)+k。如图所示:

【递推式】
f(k) 2*(n-m) f(k-1)+k k=n-m时 k>n-m时
program cake; var n,m:integer; function f(k:integer):integer; begin if k=n-m then f:=2*(n-m) else f:=f(k-1)+k; end; begin readln(n,m); writeln(f(n)); end.

第k条

递 推 法

program cake; var n,m,f,k:integer; begin readln(n,m); f:=2*(n-m); for k:=n-m+1 to n do f:=f+k; writeln(f); end.

递 归 法

上 机 练 习
【骨牌问题】 有2×n的一个长方形方格,用一个1×2的骨牌铺满方格。例如n=3时,为2×3方格。此时用一个1×2的骨牌 铺满方格,共有3种铺法,根据n值求解有多少中铺法。

[源文件]:gp.pas [输入文件]:gp.in [输出文件]:gp.out

[输入格式]:一个整数表示n [输出格式]:一个数,表示所铺法总数。

[输入样例] 5 [输出样例] 8 [数据规模]:0<n<=30

第十六讲

回溯算法

回溯算法初探
利用递归算法,我们可以很容易的求出问题的一个解,但要想求出 问题的多个解,所有解,或最优解,一般会采用递归回溯的方法,进行 试探式求解。 【楼梯问题】楼梯有n(n<=20)级台阶,上楼可以一步上1级,也可以 一步上2级,请你输出每一种走法。
共3级台阶 第1步 第2步 1级 1级 2级 1级 2级

第3步

1级

program ztj; var n,now_tj:integer; a:array[1..100] of integer; procedure try(step:integer); var i:integer; begin if now_tj=n then begin for i:=1 to step-1 do write(a[i]:3); writeln end else for i:=1 to 2 do if now_tj+i<=n then begin a[step]:=i; now_tj:=now_tj+i; try(step+1); now_tj:=now_tj-i end; end; begin readln(n); now_tj:=0; try(1) end.

由n*n(n<=1000)个单位正方形格子构成的迷宫,每个格子要么是一块空地 (用‘.’表示)要么是一堵墙(用‘#’表示)。已知起点是(1,1),终点是( n,n),要求判断是否有起点到终点的路径,如果有,输出任意一条;否则,输出 无解信息。可以保证起点和终点均为空地。

. . . . .. . . #.#.#.## #.#.#. . . ## . . # . # . . . .. #. . .

回溯问题举例 【8皇后问题】在一个国际棋盘上,放置8个皇后,使她们相 互之间不能进攻。求出所有布局。
Procedure try(h:integer); Begin if h>8 then 输出a[1]..a[h] else for L:=1 to 8 if L 与a[1]..a[h-1]不冲突 begin a[h]:=L; try(h+1) end; End.

思 路

then

回溯问题举例 【置棋问题】在m*n的主格中任意指定x个格子构成一个棋盘, 在任意一个构成的棋盘上放置k个棋子,要求任意两个棋子 不得位于同一行或同一列,要求输出满足条件的方案数。 (注意棋盘是稀疏的,即x<1/2mn。1<m,n<10)
输入样例: 5 5 0 1 1 1 0 0 1 0 0 0 1 1 1 0 0 0 0 1 0 0 0 0 1 1 0 输出样例: The maxnumber=4 1:10 2:28 3:24 4:5

第十七讲

进制转换原理及应用

常用的各种进制数

进制名称 十进制

基数
10

运算规则 逢10进1

举例
13

二进制
八进制 十六进制

2
8 16

逢 2进 1
逢 8进 1 逢16进1

(101)2
(27)8 (3F)16

进制转换原理
十进制整数转换成n进制整数的算法:除n取余,并以逆序输出
2 13 1 0 1 1 8 68 4 0 1

2 6
2 3 2 1 0

8 8
8 1 0

(68)10=(104)8

(13)10=(1101)2

十进制小数转换成n进制小数的算法:乘n取整
例如:(0.9)10转二进制 0.9*2=1.8 取 1 0.8*2=1.6 取 1 0.6*2=1.2 取 1 0.2*2=0.4 取 0 0.4*2=0.8 取 0 0.8*2=1.6 取 1 (0.9)10≈(0.111001)2

【进制转换问题】 将一个十进制整数x(x<10000)转换成n进制整数(n<10) 输入格式:两个整数,一个表示十进制整数x,另一个表示n进制 输出格式:一个整数表示转换后的n进制数。 输入样例:245 8 输出样例:365 【问题分析】 我们可以用一个数组a存放转换后的结果,i为数组的下标,转换过程为:

重复做:
i:=i+1; a[i]:=x mod n;

x:=x div n;
直到x=0为止,然后从数组的高位到低位(i...1)依次输出,

var x,n,i,j:integer; a:array[1..100] of integer; begin readln(x,n); i:=0; repeat i:=i+1; a[i]:=x mod n; x:=x div n; until x=0; for j:=i downto 1 do write(a[j]); writeln; end.

上 机 练 习
【进制转换问题】
将一个十进制实数x(x<10000)转换成n进制整实数(n<10),结果保留6位 小数。

输入格式:两个数,一个表示十进制实数x,另一个表示n进制(n为整数)
输出格式:一个带有6位小数的实数,表示转换后的n进制数。 输入样例:245.9 2 输出样例:11110101.111001

n进制转十进制的算法:按权展开 例如:十进制数123.45=1*102+2*101+3*100+4*10-1+5*10-2这里10i称为对应位 的权,这种表示方式称为“按权展开式”在其他进制中也是通用的,我们可以使用这

种方法将n进制数转换为十进制数

例如:
(1001.01)2=1*23 + 0*22 + 0*21 + 1*20 + 0*2-1 + 1*2-2 =(9.25)10 (25.31)8=2*81 + 5*80 + 3*8-1 + 1*8-2 =(21.390625)10

非十进制转非十进制的算法:先转换成十进制,再转换成所要求的进制

【进制转换问题】 将一个n进制整数x(不超过30位)转换成十进制整数(n<10) 输入格式: 共两行 第一行1个整数,表示n进制 第二行1串数字,表示n进制整数 输出格式:一个整数表示转换后的十进制数。 输入样例: 2

100110
输出样例:38

【问题分析】 我们可以用一个字符串str存储n进制数字串; i作下标; 通过循环从低位到高位i=length(str)…1依次访问每个数字; 让每个数字乘以该位的权值ni再累加到s中

最后输出累加的和s

program jzzh; var str:string; n,i:integer; s,t:longint; begin readln(n); readln(str); s:=0; t:=1; for i:=length(str) downto 1 do begin s:=s+(ord(str[i])-ord('0'))*t; t:=t*n; end; writeln(s); end.

上 机 练 习
【进制转换问题】 将一个n(n<10)进制数x(不超过30位)转换成十进制数,小数点后保留6位有效 数字。 输入格式: 共两行 第一行1个整数,表示n进制 第二行1串数字,表示n进制数

输出格式:一个数表示转换后的十进制数。
输入样例: 2

100110.101
输出样例:38.625000

4)二进制转八进制、十六进制。

方法:从低位到高位,每三位二进制可转换成一位八进制,每四位二进制可转换为 一位十六进制。
例如: (1101010)2=(152)8 (1101010)2=(6A)16

进制转换原理的应用
在解决实际问题时,巧妙的运用数的进制转换原理,可以解决不少问题 【问题1】1000个苹果放入10个箱子。客户如果要获得1~1000个苹果中的任意个数,都可以 整箱搬,而不用拆开箱子。问是否有这样的装箱方法?
51 2 25 6 12 8 64 32 16 √ 8 √ 4 2 √ 1

26个苹果

1

1

0

1

0

【问题2】天平,称40克以内的任意重量,每种砝码只能1个,最少要几个砝码?

6个砝码:

32

16

8

4

2

1

【天平称重】 用1克、3克、9克、27克和81克的砝码称物体的重量,最大可称出121克。如果砝 码允许放在天平的两边,编程输出称不同重量物体时,砝码放置的位置。 例如:所称物体的重量m=14克时,因为m+9+3+1=27,所以m=27-9-3-1,即 天平一端放该物体和9克,3克,1克的砝码,另一端放27克的砝码。 输入格式:1个整数,表示待称物体的重量m(m<=121) 输出格式:1个表达式,表示天平砝码的方法。 输入样例:14 输出样例:14=0+27-9-3-1 输入样例:1

输出样例:1=0+0+0+0+1
【问题分析】问题的关键在于如何体现砝码放在天平的左边、右边还是不放。我们可 以用-1,0,1分别表示砝码放在天平的左边,右边还是不放。由于砝码只有三种状态 ,故类似于“三进制数” 被称物体的重量计算公式为:m=a*81+b*27+c*9+d*3+e 其中a,b,c,d的取值可以是-1,0,1

var a,b,c,d,e,m,t:integer; begin readln(m); for a:=0 to 1 do for b:=-1 to 1 do for c:=-1 to 1 do for d:=-1 to 1 do for e:=-1 to 1 do begin t:=a*81+b*27+c*9+d*3+e; if m=t then begin write(m,'=',a*81); if b<0 then write(b*27) else write('+',b*27); if c<0 then write(c*9) else write('+',c*9); if d<0 then write(d*3) else write('+',d*3); if e<0 then write(e) else write('+',e); end; end; end.

【数列】 给定一个正整数k,将所有k的方幂及所有有限个互不相等的k的方幂之和构成一个递 增序列。例如,当k=3时,序列为1,3,4,9,10,12,13,…,该序列实际上就 是30,31,30+31, 32,30+32,31+ 32,30+31+32, 。 输入格式:2个整数,分别表示k和n(3≤k≤15,10≤n≤1000) 输出格式:1个整数,表示数列中的第n个数。 输入样例:3 5 输出样例:10 【问题分析】通过观察我们可以发现这个数列是有规律的,规律如下:
n(十进制) 1 2 3 4 5 n(二进制) 1 10 11 100 101

对应数列中的数
1 3 4 9 10

对应数列中的数(按k展开后 )

30 31 30+31 32

30+32 第5个数为:1*32 +0*31+ 1*30=10

var n,k,t,i,j:integer; s:longint; a:array[1..1000] of integer; begin readln(k,n); i:=0; repeat i:=i+1; a[i]:=n mod 2; n:=n div 2; until n=0; s:=0; t:=1; for j:=1 to i do begin s:=s+a[j]*t; t:=t*k; end; writeln(s); end.

上机练习
【二进制位】 对于一个十进制整数,我们可以很容易地将它转化为二进制数,例如: 5—101 13—1101 23—10111 现在我们关心的是,一个数的二进制表示中,出现多少相邻的1的情况。例如5表示成的 101,没有出现相邻的1;13表示成的1101,开头两个1相邻,所以有1个;23表示成 的10111,最后三位全是1,所以出现两个。 现在给出n,请求出1到n之间所有的数的二进制共出现多少相邻的1的情况。 输入格式:一个整数n(1<=n<=1,000,000)。 输出格式:一个整数,为所求的答案。 输入样例:22 输出样例:14 输入文件:jzw.in 输出文件:jzw.out

上机练习
【波浪数】 波浪数是在一对数字之间交替转换的数,如1212121,双重波浪数则是指在两种进制下 都是波浪数的数,如十进制数191919是一个十进制下的波浪数,它对应的十一进制数 121212也是一个波浪数,所以十进制数191919是一个双重波浪数。 输入格式:一行,包含四个用空格隔开的十进制整数,前两个数表示进制的范围( 2~32),第三与第四个数表示指定的范围(1~10000000)。 输出格式:个数。 输入样例:10 11 190000 960000 输出样例:5 输入文件:bls.in 输出文件:bls.out 说明:这5个数是 191919 383838 575757 767676 959595

第十八讲

高精度运算

在编程运算时,我们有时会遇到运算精度 要求特别高,远远超过各种数据类型的精度范 围;或者运算数据特别大,远远超过各种数据 类型的极限值的情况,这时我们就需要进行“ 高精度计算”

在进行高精度计算时需要处理好的几个问题
1、数据的接收和存储 当数据很长时,可采用字符串方式进行输入,然后将字符串中的每一位逐一取 出并转换为数字后存入数组。 2、计算结果的位数 在输出结果前我们通常要知道计算结果的位数 加法:C=A+B LC=max(LA,LB)+1 (<=AB中最大的数据长度加1) 减法:C=A-B LC=max(LA,LB) (<=AB中最大的数据长度) 乘法:C=A*B LC=LA+LB (<=AB长度之和) 3、进位与借位处理

例1:高精度加法程序

//输入计算数据 //计算数据长度(位数) //将字符串转换为数值 //判断相加的最高位

//计算进位 //计算当前位的值 //加进位加到高位中 //逐位输出运算结果(逆序输出)

例2:高精度减法

判断运算结果的符号, 并将大数作为被减数, 小数作为减数 //将字符串转换为数值

//逐位相减

//逐位输出运算结果(逆序输出)

例3:高精度乘法程序

//计算乘法进位 //将本次结果x和上一次结果c[t]相加 //将乘法进位和加法进位放到t+1位中

例4:高精度除法程序
问题分析:
1)用数组存储除法的商 program cf; var a:array[0..100] of integer; bcs,cs,i,j,ys:integer; begin readln(bcs,cs); a[0]:=bcs div cs; write(a[0],'.'); ys:=bcs mod cs; i:=1; repeat a[i]:=ys*10 div cs; ys:=ys*10 mod cs; i:=i+1; until (ys=0) or (i>50); if a[i]=0 then i:=i-1; for j:=1 to i do write(a[j]); writeln; end.

[0]号元素存储商的整数部分
后面的元素存储小数部分 2)商:=被除数 div 除数

a[0]:=bcs div cs;
3)余数:=被除数 mod 除数 ys:=bcs mod cs; 4)新商:=余数*10 div 除数 a[i]:=ys*10 div cs; 5)新余数:=余数*10 mod 除数 ys:=ys*10 mod cs;

第十九讲

数据查找与排序

第二十讲

组合数学

第二十一讲

数据结构初步

数据(data):是信息的载体,是计算机处理的对象。
数据可分为数值型数据(如:整数,实数)和非数值型数据(如:字符,图像)两种 数据的基本单位称为数据元素,如:数组元素,树结点,图顶点,记录等。

结构(structure):是指数据元素之间的关系。
这种关系分为四种:

1)集合关系(松散关系)
2)线性关系(一对一关系) 3)树形关系(一对多关系) 4)图形关系(多对多关系) 数据结构(data structure):包括逻辑结构和物理结构两部分 逻辑结构:是数据结构抽象出来的数学模型 物理结构(又叫:存储结构):是数据结构在计算机中的表示 存储结构有顺序存储和链式存储两种

线 性 表
①—②—③—④—⑤—⑥—⑦—⑧—⑨—⑩
特点:

1)均匀性:同一线性表的各个数据元素的类型是一致的,且数据项也相同。
2)有序性:除第一个和最后一个元素外,每个数据元素只有唯一的直接前趋、唯一的 直接后继(第一个元素无前趋,最后一个元素无后继)各元素之间是1:1的关系。

例1:卡布列克运算 一个任意的四位正整数(数字全相同的除外)。将其数字重新组合成一个最大 的数和最小的数,然后用大数减小数,得到一个新四位数(高位零保留),重复这 个过程,最多7步,必得6174。编程输出计算过程。 输入格式:一个整数,表示n 输出格式:若干行,每行一个表达式 输入样例:1000 输出样例:

1000 – 1 = 999
9990 – 999 = 8991 9981 – 1899 = 8082 8820 – 288 = 8532 8532 – 2358 = 6174
问题分析: 1)把一个整数n各位上的数字分解出来,存入数组。 2)对数组中的数字进行排序。 3)将排序后的数,组合成最大的4位整数。和最小的整数。 4)输出大数减小数的表达式。

5)如果大数减小数不等于6174,则将结果存入n重复步骤1~4

问题分析2: 1)把一个整数n各位上的数字分解出来。然后用一个下标为0~9的数组存储每个分解出来的 数字出现的次数。 例如:1000分解后,1出现了1次,0出现了3次,存储结构为:

[0] [1] 3 1

[9 ]

2)将出现的数字逆序组合就是最大的数,不足4位的后面补0,顺序组合就是最小的数 3)输出大数减小数的表达式。 4)如果大数减小数不等于6174,则将结果存入n重复步骤1~3

采用不同的数据结构,就会有不同的算法,效率可能不一样。

分解n中的各位数并将数字出现的次数存入数组a

将a中出现数字逆序组合 形成最大的整数,不足4 位末位补0

将a中出现数字顺序组合形成最小的整数

例2:分数数列 数列{ai}的各项是斐波那契数列{fi}的前后两项之商,即f1=f2=1。当i>2时,fi=fi-2+fi-1, ai=fi/fi+1。例如:{fi}的前6项为1,1,2,3,5,8,{ai}的前5项为1,1/2, 2/3, 3/5, 5/8。 输入格式:一个整数,表示n(n<=10) 输出格式:输出{ai}的前n项之和,输出格式参见输出样例,分数一定要是最简真分数 输入样例:5 输出样例:3+47/120 问题分析1: 1)用一个实型数组a存储{ai}的每一项ai=fi/fi+1, 2)求前n项和,并将其转换为最简真分数。

存在问题:在计算ai=fi/fi+1时,由于用实数表示,会有误差,另外求和后还要将其转

换为最简真分数,较麻烦。

问题分析2: 1)定义两个数组fz和fm,分别存储数列{ai}的每一项分子和分母。 2)然后将分子和分母组成的分数相加,求出最简真分数。 分数相加算法:

找出两个分数的分母的最小公倍数再“通分”
例如:13/6+3/5=(13*(30 div 6)+3*(30 div 5)/30=83/30 (30是6和5的最小公倍数) 最后分子分母再进行约分(即除以分子分母的最大公约数)

(注意:这里最小公倍数,分子,分母,都可能很大,最好用longint或int64)

生成存放分子和分母的数组 fz=1,1,2,3,5,8… fm=1,2,3,5,8,13…

栈(stack)
栈(stack)又称为堆栈,是一种特殊的线性表。

特点:只能在表的一端进行插入和删除操作的线性表,即先进后出规则。

进栈

出栈

栈顶

a4 a3 a2

栈底

a1

栈的存储结构
顺序栈:通过一维数组表示栈的存储结构。定义如下: const

max=10000;
type arraytype=array[0..max] of integer; var stack:arraytype; top:integer; stack [0 ] [1 ] …[max]

top 栈底 栈顶

链式栈:通过链表结构来表示栈的存储结构。定义如下:
type link=^node; node=record

data:integer;
next:link; end;

var
hs:link;

data

a1

a2

a3

a4

hs

next
栈底 栈顶

记录型栈:栈也可以定义成记录类型。它有两个域,一个是一维数组,用于存储
栈数据元素,另一个是栈顶指针。定义如下: const max=10000; type stack=record

data:array[0..max] of integer;
top:integer; end; var s:stack;

栈的基本操作
(1)建栈
算法:建栈的算法就是将栈顶指针置为0 const max=10000; type arraytype=array[0..max] of integer; var [max ]

stack:arraytype;
top:integer; procedure setnull(var stack:arraytype); top [1] [0]

begin
top:=0; end;

stack

(2)测试栈为空还是为满 算法:如果top=0,则栈空,如果top=max,则栈满 function sempty(stack:arraytype):boolean; begin sempty:=(top=0); end; top stack top

[max ]

[1] [0]

function sfull(stack:arraytype):boolean; begin sfull:=(top=max); end;

[max ]

[1] [0] stack

(3)进栈(压栈,入栈) 算法:先将栈顶指针的值加1,再把新元素存储到栈顶,但要注意,进栈操作必须 保证栈不满,否则会溢出
procedure push(var stack:arraytype;var top:integer;max,x:integer); begin if top=max then begin

writeln(‘stack full’);
halt; end else

[max ] top x [1] [0] stack

begin
top:=top+1; stack[top]:=x; end

end;

(3)出栈(退栈,弹出) 算法:先把栈顶元素的值赋给x,再把栈顶指针的值减1。但要注意,出栈操作前必 须保证栈不为空
procedure pop(var stack:arraytype;var top,x:integer;); begin if top=0 then begin

writeln(‘stack empty!’);
halt; end else

[max ]

begin
x:=stack[top]; top:=top-1; end

top

[1] [0] stack

end;

(3)读栈 算法:查看当前栈顶元素。若top=0,即空栈,无栈顶元素,则输出出错信息,中 止程序;若top<>0,则将栈顶元素的值赋值给某个变量。
function readtop(stack:arraytype):integer; begin if top=0 then writeln(‘underflow!’)

else
readtop:=stack[top] end;

[max ]

top

[1] [0] stack

栈的应用举例
【括号匹配】 栈在计算机科学领域有着广泛的应用。比如在编译和运行计算机程序的过程汇 总,就需要用栈进行语法检查,如检查begin和end、“(”和“)”等是否匹配。

另外在计算表达式的值,实现过程和函数的递归调用等方面都要用到栈。
现在,假设一个表达式只由英文字母(小写)运算符(+,—,*,/)和左右 小(圆)括号构成,请编写一个程序检查表达式中的左右圆括号是否匹配,若匹配,

则返回“Yes”;否则返回“No”。
假设:表达式长度小于255,左圆括号少于20个。

问题分析:
1)现将表达式字符串存入字符串变量s 2)利用循环扫描每个字符s[i],如果遇到’(‘则将其入栈,如果遇到’)’则让栈顶元素

出栈。
3)当发生下溢或扫描完成后栈非空时,意味着表达式中的括号不匹配。否则匹配

function check(s:string):boolean; var stack:array[0..256] of char; i,top,len:integer; begin len:=length(s); top:=0; for i:=1 to len do begin if s[i]='(' then begin top:=top+1; 如果遇到’(‘则入栈 stack[top]:=s[i]; end else if (s[i]=')') then if top<>0 then top:=top-1 如果遇到’)‘若top<>0则出栈否则下溢 else exit(false); end; if top=0 then check:=true else check:=false; end;

【后缀表达式求值】
表达式有三种表示方法,分别称为中缀表达式(又称代数式,如a+b)、后缀表达式(又 称逆波兰式,如ab+)和前缀表达式(又称波兰式,如+ab)。 把数学中的一个代数式(中缀表达式)转换成后缀表达式的方法是:把每个运算符移到 它的两个运算数后面,每个运算数后多加上一个空格(用以分割各个运算数),然后去掉所 有的括号。例如: 3/5+6 -------------- 3 5 / 6 + 16-9*(4+3) --------- 16 9 4 3 +*由于后缀表达式是没有括号的,而且计算机只要从前往后扫描一遍后缀表达式就能算出 它的值,因此,计算机中广泛使用后缀表达式,而不是数学中使用的中缀表达式。 现要求编程求一个后缀表达式的值。具体要求如下:从键盘读入一个后缀表达式(字符

串),其中只含有0~9组成的运算数及加(+),减(-),乘(*),除(/,当做div运算)
四种运算符。每个运算符之间用一个空格隔开,不需要判断表达式是否合法。 问题分析: 1)扫描后缀表达式,凡遇到操作数就将其压栈 2)遇到运算符就弹出两个操作数进行运算,然后再将运算结果压栈。

3)继续扫描,直到后缀表达式结束,此时栈顶元素就是表达式计算的结果

function js(s:string):integer; var stack:array[0..200] of integer; i,top,x,y:integer; begin i:=1; top:=0; while i<=length(s) do begin case s[i] of '0'..'9':begin x:=0; while s[i]<>' ' do begin x:=x*10+ord(s[i])-ord('0'); i:=i+1; end; top:=top+1; stack[top]:=x; end; //如果遇到’+’号弹出两个数并计算,最后将结果再入栈 '+':begin x:=stack[top];top:=top-1;y:=stack[top];stack[top]:=y+x; end; '-':begin x:=stack[top];top:=top-1;y:=stack[top];stack[top]:=y-x; end; '*':begin x:=stack[top];top:=top-1;y:=stack[top];stack[top]:=y*x; end; '/':begin x:=stack[top];top:=top-1;y:=stack[top];stack[top]:=y div x; end; end; i:=i+1; end; js:=stack[top]; end;

如果遇到数字入栈

上机练习 程序员输入程序,出现差错时可以采取以下的补救措施:敲错了一个键时,可 以补敲一个退格符“#”,以表示前一个字符无效;发现当前一行有错,可以敲入 一个退行符“@”,以表示“@”与前一个换行符之间的字符全部无效。 如:在终端上输入了这样两行字符: PRKJ##OGRAN#M LX;

VAR@CONST N:#=10;
则实际有效的是: PROGRAM LX; CONST N=10; 从文件edit.in中输入数据,数据有若干行,每行有若干字符,表示程序员在 终端上输入的字符,把实际有效的字符输出到文件edit.out中

队列(queue)
队列(queue)也是一种种特殊的线性表。

特点:限定只能在表的一端进行插入,在表的另一端进行删除的线性表,即先进
先出规则。

出队列

hhhhhhhh
出队列 a1 a2 a3 a4 a5 a6

入队列

入队列

队头(front)

队尾(rear)

队列的存储结构
顺序队列:通过一维数组表示队列的存储结构。定义如下: const

max=10000;
type arraytype=array[0..max] of integer; var queue:arraytype; front,rear:integer; queue [0 ] [1 ] …[max]

front

rear

记录型队列:队列也可以定义成记录类型。它有三个域,一个是一维数组,用于
存储队列数据元素,另一个是对头指针,还有一个是队尾指针。定义如下: const max=10000; type queue=record

data:array[0..max] of integer;
front,rear:integer; end; var q:queue;

队列的存储结构
记录型队列:队列也可以定义成记录。定义如下:

max=10000;
type arraytype=array[0..max] of integer; var queue:arraytype; front,rear:integer; queue [0 ] [1 ] …[max]

front

rear

队列的基本操作
(1)队列初始化
算法:将队头和队尾指针置为0 front:=0;rear:=0; queue [0 ] [1 ] …[max]

(2)测试队列的空与满

front rear

算法:若front=rear,则队列为空;若front=0且rear=max,则队列为满。

queue

[0 ]

[1 ]

…[max]

queue

[0 ]

[1 ]

…[max]

front rear
队空

front 队满

rear

(3)进队(插入) 算法:把一个新元素添加到队尾。
procedure addqueue(var queue:arraytype;var rear:integer;max,x:integer) begin if rear=max then begin writeln(‘queue full!’); halt; end else

queue
begin
rear:=rear+1; queue[rear]:=x; end

[0 ]

[1 ]

…[max]

x
rear

front

end;

(3)出队(删除) 算法:撤去对头元素。
procedure delqueue(var queue:arraytype;var front:integer;x:integer) begin if front=rear then begin writeln(‘queue empty!’); halt; end else begin

queue
front:=front+1;
x:=queue[front];

[0 ]

[1 ]

…[max]

front rear

end end;

循环队列
假溢出问题
[0 ] [1 ] …[max] 队满(假溢出)

queue

front

rear

为了充分利用空间,克服“假溢出”现象,可以将队列的首,尾连接起来,形 成一个“环”这种队列称为“循环队列” [max] front [0] rear [0] 初始化 [max]

[1]
[2]

[1]
[2]

如何判断队空和队满?
rear 队满条件:rear+1=front [max] front [0] [1] [2] front rear [max] [0] [3] [4] rear [max] [0] [1] [2] front 情况2 [max] [0] [3] [4]

情况1

队空条件:front+1=rear

front
[4] [2] [3] rear [1] [2] 情况1 [3] [4]

[1]

情况2

方法2:设一个计数器count,如果count=max则队满,count=0则队空

队列实际长度:count:=(rear-front+max) mod max

队列应用举例

第二十二讲

数据结构——树

第二十三讲

数据结构——图

ASCII 对照表
字符 NUL SOH STX ETX EOT ENQ ACK BEL BS SH LF VT FF CR SO SI DEL DC1 DC2 DC3 DC4 NAK 序号 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 字符 SYN ETB CAN EM SUB ESC FS GS RS US SP ! " # $ % & ' ( ) * + 序号 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 字符 , _ . / 0 1 2 3 4 5 6 7 8 9 : ; < = > ? @ A 序号 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 字符 B C D E F G H I J K L M N O P Q R S T U V W 序号 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 字符 X Y Z [ \ ] ^ ' a b c d e f g h i j k l m 序号 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109

字符 n o p q r s t u v w x y z { | } ~ DEL

序号 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127

第十一讲

指针

静态存储与动态存储
静态数据类型:只能在程序说明部分加以说明,在程序执行之前就以决定所 占空间大小的数据类型 动态数据类型:程序在编译阶段不对其变量分配内存空间,而在程序执行时 根据需要动态建立和分配空间,以致这种类型的数据所占的内存空间可动态的发 生改变的数据类型。

指针的概念
内存中的每一个变量都包括“内容”和“地址”两各部分 2000H a 2020H b 2020H 56 地址

内容

2000H 指针 a b

2020H 56

指 针 变 量 定 义
方法一 Type 类型标识符=^基类型标识符; Var 变量名:类型标识符; 方法二 Var 变量名:^基类型标识符;

例如: Type point=^integer; Var p1,p2:point;
整型指针

例如: Var p1,p2:^integer;

指 针 变 量 的 基 本 使 用 方 法
1、申请存储单元 new(指针变量)

例如: Var p1:^integer; begin new(p1); p1^:=138 end.
2、释放存储单元 dispose(指针变量) 例如: dispose(p1);

p1 p1 2001 p1 2001 2001 2001 138

指 针 变 量 的 基 本 使 用 方 法
3、指针变量的赋值 例如: Var p1,p2:^integer; b:integer; begin b:=100; p1:=@b p2:=p1; p2^:=200 end. 指针变量可以赋空值例如:p1:=nil; 注意:指针变量中存储的地址不能通过输入输出语句输入或输出

p1 3004 2001 p2 4008 2001 2001

b 200 100

例 题
思考下列程序运行后的结果是什么?

Program jh; Var p1,p2,t:^integer; a,b:integer; begin a:=3;b:=4; p1:=@a;p2:=@b; t:=p1;p1:=p2;p2:=t; writeln(p1^:3,p2^:3); writeln(a:3,b:3) end.

输出结果: 4 3 3 4

线 性 链 表
线性表:线性表是指数据排列呈直线状,即除了第一个和最后一个元素 以外,所有数据都只有唯一的一个后继元素和维一的一个前趋元素。第 一个元素只有后继,最后一个元素只有前驱。 例如:数组就是一种典型的线性表。
[1] [2] [3] [4] [5] [6] [7] [8] … a [n]

但数组无法动态分配空间,因此经常造成空间的浪费,而链表就可很好的解决这一问题。 data next 结点

线 性 链 表 的 结 点 定 义
线性链表结点的定义:
Type point=^node; node=record date:integer; next:point; end;

基类型为node类型的指针类型 node是一种我们自定义的记录类型

node类型包括两个域,一个是名为date的整型数据,一个是名为next的指针型数据

data next node

线 性 链 表 的 建 立
问题:输入一个正整数序列,遇到负数时停止,以建立一个按输入顺序排列 的线性链表。 算法步骤 head nil

Head指针

q指针

q指针

Data

x p

Data

x nil p

next

next

线 性 链 表 的 建 立
算法步骤 1)建立空表,即头指针为nil 2)读入一个数据
3)while 读入没结束时 do begin if 链表为空表 then begin 申请新结点; 将刚才读入的数填入新结点的数据域;指针域置为nil; 将头指针指向新结点; end else begin 申请新结点; 将刚才读入的数填入新结点的数据域;指针域置为nil; 将新结点链接到表尾; 尾指针后移一个结点,指向表尾; end 读入下一个数 end;

建 表 的 过 程

head:=nil; read(x); while x>=0 do begin if head=nil then begin new(p); p^.data:=x; q:=p; head:=p; end else begin new(p); p^.data:=x; p^.next:=nil; q^.next:=p; q:=p; end; read(x) end;

线 性 链 表 的 输 出
如何遍历和输出链表 链表的遍历和输出必须从表头开始,按照链接的顺序依次访问至表尾 步骤:

1)将指针p指向链表头结点
2)while p<>nil do begin 输出p所指结点(当前结点)的数据域 p向后移一个结点; end;

线 性 链 表 的 查 找 与 插 入 操 作
问题:输入一个按从小到大排好序的正整数序列,遇到负数时停止,然后再 输入一个正整数,并将其插入该序列中。

Head指针

q指针

Data next

2

4

6 nil

5

p指针

表间插入

Head指针

q指针

Data next

2

4

6 nil

p指针

5 nil

表尾插入

查 找 插 入 位 置

read(y); p:=head; while (y>p^.data) and (p^.next<>nil) do begin q:=p; p:=p^.next; end; new(np); np^.data:=y; if p^.next<>nil then begin q^.next:=np; np^.next:=p; end else begin p^.next:=np; np^.next:=nil; end;

插 入 新 结 点


相关文章:
选修课程的实施(一)
选修课程的实施(一)_其它课程_高中教育_教育专区。选修课程分为知识拓展、职业技能...《奇妙的 pascal》 《科技创新之路》 技术学科 《计算机维修与应用》 《装璜...
选修课《信息学竞赛》
记录类型(PASCAL)/结构类型(C) D.程序设计: 1.结构化程序设计的基本概念 2....(选修) 下节课讲数组 ,冒泡排序,好好复习; 第 22 页,共 55 页 广州外国...
必修部分加选修
必修部分加选修 隐藏>> 必修部分-信息技术基础第一章 信息与信息技术 1、信息...(机器语言、汇编、vb、c、pascal 等) 23、加解密程序设计(设计思想,流程图)...
选修模块1 练习练习
选修模块1 练习练习_随笔_生活休闲。试题(一) 选修模块 1 算法与程序设计一、...( C ) A、BASIC B、C 语言 C、汇编语言 D、PASCAL 2、下列逻辑表达式的值...
选修训练答案
选修算法与程序设计复习训练 一 1、 用计算机程序解决实际问题时,合理的步骤是(...D.Pascal 17. 下列逻辑表达式的值为“假”的是( A.3+5>7 B.8/4<4 C...
算法与程序设计(选修)复习提纲
算法与程序设计(选修)复习提纲_其它课程_高中教育_教育专区。算法与程序设计(...A:如:Fortran、Basic、Pascal、C、C++、Java,Visual Basic 简称 VB 1/8 第...
江苏省信息选修知识点
开始或结束 输入或输出 判断 处理或运算 3.算法的特征 (选修书 P5) 连接点 流程线 (二)程序设计基础(1)常用高级编程语言:BASIC、VB、Pascal、C、C++、Java ...
算法与程序设计(高中选修)复习资料
算法与程序设计(高中选修)复习资料_其它课程_高中教育_教育专区。主题一 利用...A、汇编语言 B、Pascal 语言 C、Basic 语言 D、机器语言 14、下列关于程序...
选修课VB知识点
选修课:算法与程序设计知识点 选修课:算法与程序设计知识点第一章: 第一章:计算机...常用的高级语言如:BASIC,C,FORTRAN,PASCAL,COBOL ,,,等。 5、程序的编辑和...
《算法与程序设计》(选修)课件
《算法与程序设计》(选修)课件_其它课程_高中教育_教育专区。高中信息技术《算法...(1)常用高级编程语言:BASIC、VB、Pascal、C、C++、Java 1 面向对象的程序设计...
更多相关标签:
pascal | free pascal | pascal语言 | titan x pascal | pascal voc | titanx pascal | free pascal下载 | pascal下载 |