tceic.com
简单学习网 让学习变简单
当前位置:首页 >> 学科竞赛 >>

编程竞赛第二步


例1:将数组a的内容颠倒
分析:数组a中放置n个元素,最终实现a[1]—a[n]对 换,A[2]—a[n-1]对换,……,可以用for循环实现。 假设把数组看成一个线性表,除了第一个元素和 最后一个元素没有前驱和后继,每个元素都只有 一个前驱和一个后继,这样我们可以用两个指针 分别指向第一个和最后一个,逐个交换, 也能实现数组内容的交换。 i:=1;j:=n; Whil

e I<j do begin t:=a[I];a[I]:=a[j];a[j]:=t; i j I:=I+1;j:=j-1; End;

例2:设有n个正整数(n<=20),将它们连 结成一排,组成一个最大的多位整数。 例如:n=3时,3个整数13,312,343,连接 成的最大整数为34331213 又如:n=4时,4个整数为7,13,4,246,连 接成的最大整数为7424613 程序输入:n n个整数 程序输出:连接称得多位数

分析(1)数值的连接,数值大的连接是不一定就 放在最前面 (2)如何比较大小

设计一个线性表存放读入的数 Num:array[1..maxn] of longint; 再设计一个线性表存放将数值转换后生成的字符串 Digitstr:array[1..maxn] of string; 将数值转换字符串 For I:=1 to n do while num[I]<>0 do begin k:= num[I] mod 10; digitstr[I]:=chr(ord(?0‘)+k)+digitstr[I]; num[I]:=num[I] div 10; end;

修正字符串比较大小的规则: 如果:A+B>B+A 则:A>B 反之不成立 例如:‘321‘>?32‘连接后的‘32132‘<?32321‘ 所以:连接前需要将digitstr线性表按照新规则排 序后才能连接 For I:=1 to n-1 do for j:=I+1 to n do if digitstr[I]+ digitstr[j]< digitstr[I]+ digitstr[j] Then 交换 digitstr[I]与digitstr[j]

例3对任意给定的一个自然数n(n<=100),将 分母小于等于n的不可约的真分数按上升次序 排序,并且在第一个分数前加0/1,而在最后一 个分数后加1/1,这个序列称为n级的法雷序列, 当n=8时序列为: 0/1,1/8,1/7,1/6,1/5,1/4,2/7,1/3,3/8,2/5,3/7,1/2,4/7, 3/5,5/8,2/3,5/7,3/4,4/5,5/6,6/7,7/8,1/1 编程求出n级的法雷序列,每行输出10个分数 分析(1)首先需要两个线性表分别存放分子和分母, Fz,fm:array[1..maxn] of integer; (2)初始化,将两个线性表中分别存储最初的两个值 Fz[1]:=0;fm[1]:=1;fz[2]:=1;fm[2]:=1; Total:=2;total记录线性表中数据的个数即最后的下标

(3)怎样才能产生中间的若干数呢? 分母的范围是2---n,而分子呢?怎样设计? (4)得到的新分数怎样插入到表中?需要与 当前表中数据比较大小,才能确定插入位置。

For m:=2 to n do for z:=1 to m-1 do begin k:=1; while z*fm[k]>m*fz[k] do k:=k+1; If z*fm[k]<>m*fz[k] then begin 插入表中 end; end;

(5)插入表中 for I:=total downto k do fz[I+1]:=fz[I]; for I:=total downto k do fm[I+1]:=fm[I]; fz[k]:=z;fm[k]:=m;total:=total+1; (6)打印 For I:=1 to total do begin write(fz[I],‘/‘,fm[I],‘ ?); if I mod 10=0 then writeln; end;

移位 处理

例4编程找出所有的三位到七位的水仙花数,若 一个n为自然数的各位数字的n次方之和等于它 本身,称之为水仙花数。 分析:1)任何数据都是0—9组成的,如果每求一 次水仙花数都计算0—9的指数就会浪费计算的时 间,就考虑用一个线性表记录0-9的指数值, power[I,j]等于i的j次方。 Power:array [0..9,0..maxlen] of longint; for I:=0 to 9 do begin power[I,0]:=1; for j:=1 to maxlen do power[I,j]:=power[I,j-1]*I end;

(2)从100开始逐一穷举到9999999检查出符合条 件的数。为了避免分解数字,可以将整数用数组 分为存放。Digit:array[1..maxlen+1] of 0..9; For I:=1 to maxlen do digit[I]:=0; 初始化 Digit[3]:=1;high:=3;number:=100;total:=0; (3)查表求各位数字指数和,与当前数是否符合。 Sum:=0 ; for I:=1 to high do sum:=sum+power[digit[I],high]; if sum=number then 打印 (4)以上步骤重复进行,直到digit[maxlen+1]=0 (5)怎样才能产生下一个数呢?只需将 digit[i]:=digit[i]+1即可,但需要注意当digit[i]=10 时的处理。

Digit[1]:=digit[1]+1;I:=1; While digit[I]=10 do Begin digit[I+1]:=digit[I+1]+1; digit[I]:=0;I:=I+1; End;

考虑999等情况

本题的完整程序: Const maxlen=7; Var I,j,number,high,sum,total:integer; Digit:array[1..maxlen+1] of 0..9; Power:array [0..9,0..maxlen] of longint;

Begin for I:=0 to 9 do begin power[I,0]:=1; for j:=1 to maxlen do power[I,j]:=power[I,j-1]*I end; For I:=1 to maxlen do digit[I]:=0; Digit[3]:=1;high:=3;number:=100;total:=0; While digit[maxlen+1]=0 do begin Sum:=0 ; for I:=1 to high do sum:=sum+power[digit[I],high];

if sum=number then begin total:=total+1; write(number:maxlen+3); if total mod6=0 then writeln; end; Digit[1]:=digit[1]+1; I:=1; While digit[I]=10 do Begin digit[I+1]:=digit[I+1]+1; 位数增加处理 digit[I]:=0;I:=I+1; End; If I>high then high:=I; 控制实际位数 Number:=number+1; End;writeln; End.

例5某种货币体系的元角分分别用ABC来表示, 它们之间的换算关系是: 元的面值为1元,2元,3元 角的面值为1角,2角,3角 分的面值为1分,2分,3分 在这种货币体系下,对于某一给定的钱数,不论 该堆钱有何种面值的钞票组成,总是可以从中拿 出某种金额的钱币,比如有一堆钱总数为5.27元, 不论该堆钱又何种面值的钞票组成,总可以从中 抽取0.22元钱币,我们称之为0.22元是总可以抽 出的钱币,相对地,存在不一定能抽取的钱币, 比如5.27元由面值为2元2元1元1角1角5分1分1分 组成,能抽出0.17元,若由5元2角5分2分组成, 就抽不出0.17元

编程实现这样的功能:对于任意给定的不超过十元的 钱币找出全部对该堆钱而言一定可以抽出的钱币值。

分析:问题中对元角分的抽取是相对独立的,因为 金额为元的货币化为角后抽取是没有意义的,同样 金额为角的货币化为分后的抽取也是无意义的,这 样问题就转化成了从0—9分中的抽取问题了。 对某金额为k(0<=k<=9),将所有的由1,2,5三 种面值组成的k的方案全部列举一遍,在对每种组 成方案,找出其中能够抽取的。 线性表able[I,j]存放每个金额k中能够抽取和不能抽 取的情况,用able[I,j]=1,表示从I中能抽取j, able[I,j]=0,表示从I中不能抽取j。

Var value,I,j,k,n,x,y,z,total:integer; Temp:array[0..9] of integer; Able[I,j]=1表示 Able:array[0..9,0..9] of integer; 能从I中抽取j,反 Begin 之不能 for I:=0 to 9 do 初始化 for j:=0 to 9 do able[I,j]:=1; For value:=0 to 9 do for x:=0 to value div 5 do 列举面值为5的钱币数 for y:=0 to value div 2 do 列举面值为2的钱币数 begin z:=value-x*5-y*2; 列举面值为1的钱币数 for I:=0 to 9 do temp[I]:=0; for I:=0 to x do 组合形成的钱币数 for j:=0 to y do for k:=0 to z do temp[5*I+2*j+k]:=1;

For I:=0 to 9 do if temp[I]=0 then able[value,I]:=0

End; Readln(value); I:=value div 100;j:=value div 10 mod 10; k:=value mod 10;Total:=0; For n:=1 to value do begin x:=n div 100;y:=n div 100 mod 10;z:=n mod 10; If (able[I,x]=1) and (able[j,y]=1) and (able[k,z]=1) then begin total:=total+1;write(n:6); if total mod 10=0 then writeln end; End; Writeln End.

第一讲 过程和函数
程 序 的基本 顺序结构 自顶向下、逐步求精 程 序 设 计 选择结构 的基本思 循环结构 : 程序的模块化 过程和函数 想

结构

说明:程序中可以只有主程序而没有子程序,但不
能没有主程序,也就是说不能单独执行子程序。

标准函数有:abs(x)/ sqrt(x)/ round(x)… 标准函数的调用 X:=abs(-10);
Y:=sqrt(81); Z:=round(35.9);

2+...+ 1-1 :编程求 12+2 2!+ 102 的和 例例 1_2 :编程求 1!+ 3!+...+ 10!的和。 PROGRAM sum(input,output); VAR i:integer; s:longint; BEGIN s:=0; for i:=1 to 10 do s:=s+sqr(i) fac(i) ; writeln('s=',s); END.

一、函数的定义及调用 Function 函数名(形参表):函数类型; 函数首部 局部变量说明; 函数值的类型 begin 语句1; 函数体 …; 函数名:=表达式; end; 将函数值传递给函数名 注意:自定义函数先定义后使用。 在表达式中调用:函数名(实参)
函数值通过函数名 传送回调用程序。

如:x= Abs(n) abs为函数名,n为实参,函数类型为integer or real

例1-2 编写一个求n!的函数fac.
形式参数

函 数 说 明

函数首部 function fac(n:integer):longint; var 局部变量说明 函数的结果类型 k:integer; t:longint; begin t:=1; 函数执行部分 for k:=2 to n do t:=t*k; fac:=t; 将函数值传递到函数名中 end; {endfac}

注 意 :
1、使用函数前应先说明。 2、函数首部以保留字function开头,函数名由用户自定义 的一个标识符,用来存放最终函数值。 3、形参就是函数的自变量,其初值来源于主程序的调用,只有 在程序的执行过程中调用了函数,形参才能得到具体的值并参与 运算,得到函数值。注意:形参表类似于变量说明,形参可缺省。 4、函数的类型也就是函数值的类型,函数值将通过函数名传送 回调用程序。 5、函数体内所用的类型、常量、变量等只在本函数内有效,退出 函数体后,分配的存储单元被释放。这些量与函数体外的同名变 量无关。 6、在函数体中至少有一条将函数值传给函数名的赋值语句。

例 若求 1-23编写一个求 !+5!+7!的值,如何修改程序? n!的函数fac.
Program ex1-2a(input,output); var s:longint; 形式参数 函数首部 function fac(n:integer):longint; var k:integer; 局部变量说明 函 t:longint; begin 数 t:=1; 函数执行部分 说 for k:=2 to n do 明 t:=t*k; fac:=t; 将函数值传递到函数名中 end; {endfac} begin 主 S:=fac(3)+fac(5)+fac(7); 函数调用出现在表达式中 程 Writeln(?s=?,s) 序 End.

调用函数时注意:
1、自定义函数中的形参,不是实际存在的变量,故又称为虚拟 变量,它们并不占用内存单元,只是在调用函数时,才临时开 辟相应的内存单元,存放实在参数的值,如fac(3)中的3。它是 在调用函数时的所用的自变量。形参实质上是实参的一个“替 身”。在调用函数时,实参将值赋给形参,因此实参的个数、 类型应与形参一一对应,并且要有确定的值。 2、函数调用步骤是:首先在调用程序中计算实参的值,传送 给对应的形参,接着执行函数体,最后将函数值返回给调用程 序。 3、函数的定义是静态的,若定义后未被调用,则该函数永远 不会被执行。

例1-3 计算如图所示的多边形面积。 分析: 用海伦公式求三角形的面积:s= p(p-a)(p-b)(p-c)
a,b,c为三角形的边长,p为半周长,即p=(a+b+c)/2 Program ex1-3(input,output); var b1,b2,b3,b4,b5,b6,b7,s:real;

b1 b6 b5

b2 b3

b7 b4

function area(a,b,c:real):real; 函数首部 var 函数area结果类型为实型 三个形式参数 p:real; begin p:=(a+b+c)/2; area:=sqrt(p*(p-a)*(p-b)*(p-c)); 给函数名area赋值 end;
Begin readln(b1,b2,b3,b4,b5,b6,b7); s:=area(b1,b5,b6)+area(b2,b6,b7)+area(b3,b4,b7); writeln(?s=‘,s:10:3); End. 调用函数

2、过程定义及调用
标准过程有: read/readln/write/writeln 标准过程调用: Read(a,b,c); 自定义过程的格式: Procedure 过程名(形参表); 过程首部 局部变量说明; begin 过程体 语句1; … end;

注意:
1、过程体内所用的类型、常量、变量只在本过程内有效, 退出过程体后,该单元被释放。 2、不能给过程名赋值,过程名不能代表任何数据。

Program ex1_4(input,output); var x,y:integer; procedure swap(var x,y:integer); var t:integer; begin t:=x; x:=y; y:=t; end; begin x:=10; y:=20; writeln(?x= ‘,x, ?y=‘: 6,y); swap(x,y); writeln(?x=‘,x,‘y=‘:6,y) End.

过程和函数的主要区别:

操 作







完成一系列的数据处理, 或与计算无关的各种操作
无 由独立的过程调用语句来 完成 通过变参将运算的结果传 给调用程序

往往求一个函数值
函数有类型,最终要将函 数值传送给函数名。 函数调用出现在表达式中

结果类型

调用方式

返回值 的方法

函数值是通过函数名传回调 用程序

例1-5 设计一个过程将数组中的元素从小到大排列。 type atype=array[1..10] of integer; 将数组作为参数。 var a:atype; I:integer; procedure sort(var p:atype); var I,j,k:integer; begin for I:=1 to 9 do for j:=I+1 to 10 do if p[I]>p[j] then begin k:=p[I];p[I]:=p[j];p[j]:=k; end end; begin for I:=1 to 10 do read(a[I]); sort(a); for I:=1 to 10 do write(a[I],? ‘) end.

例1-5 设计一个过程将数组中的元素从小到大排列。 type atype=array[1..10] of integer; 将数组作为参数。 var a:atype; I:integer; sort(var p:atype); 注意:当函数或 procedure var 过程的形式参数为 I,j,k:integer; 数组类型时,相应 beginsort(var p:array[1..10] of integer); Procedure 的实在参数必须是 for I:=1 to 9 do 一致的数组类型。 for j:=I+1 to 10 do 当形参为数组类型 if p[I]>p[j] then begin 时,在TP中必须用 k:=p[I];p[I]:=p[j];p[j]:=k; 类型名进行定义, end 而在FP中是可以这 end; begin 样定义的: for I:=1 to 10 do read(a[I]); sort(a); for I:=1 to 10 do write(a[I],? ‘) end.

3、变量及其作用域
例1-6 a读程序写结果。

Program ex1-6(input,output); m为全程变量。 var 全程量的作用域有两种情况: m:integer; 1、在全程变量和局部变量 procedure test1; begin 不同名时,其作用域是整 m:=100; 个程序。 end; 2、在全程变量和局部变量 begin 同名时,全程变量的作用域 m:=5; writeln(?m=?,m); 不包含同名局部变量的作用 test1; 域。 writeln(?m=?,m); end.
结果为: m=5 m=100

例1-6b 读程序写结果。

Program ex1-6b(input,output); var m:integer; procedure test2; var m:integer; M是局部量,结果被屏蔽,它不影响到 begin 全程量m的值。 m:=100; end; begin m=5 结果为: m:=5; m=5 writeln(?m=?,m); test2; writeln(?m=?,m); end.

全局变量:在主程序中被说明 作用域:整个程序; 局部变量:在子程序中被说明

作用域:主程序及其下级的程序。
全程量的作用域分两种情况: ①当全程量和局部量不同名时,其作用域是整个程序。 ②当全程量和局部量同名时,全程量的作用域不包含局 部量的作用域。

当局部变量所在子程序被调用时,局部变量才被分配有
效的存储单元;当返回调用程序时,局部变量所占的存储单 元就被释放。

练一练:
Program ex1-2(input,output); var x,y:integer; procedure change; var 结果为: x:integer; begin 1 1 x:=2; y:=2; 2 2 writeln(x,y); 1 2 end; begin x:=1; y:=1; writeln(x,y); change; writeln(x,y); end.

4、参数的传递
值形参 Function fac(x,y:integer):real;

形参 参数

变形参 procedure fac(var x,y:integer);

实参 a:=fac(5,6);
值参类似于局部变量,仅为过程和函数的执行提供初值而不 影响调用时实际参数的值。 对变参操作实际上就是对实参本身的操作。

Program ex1-7-1(input,output); Program ex1-7-2(input,output); var var a:integer; a:integer; procedure sum(b:integer); procedure sum(var b:integer); begin begin 值参 变参 b:=b+10; b:=b+10; writeln(?b=?,b); writeln(?b=?,b); end; end; begin begin a:=10; a:=10; sum(a); sum(a); writeln(?a=?,a); writeln(?a=?,a); end. end. 运行结果为: b=20 运行结果为:b=20 a=10 a=20

Program lx1-2-1(input,output); 练一练 var x,n:integer; procedure chan(x:integer; var y:integer); begin x:=x+5; y:=y+5; writeln(?x=‘,x, ?y=‘,y); 结果为: end; X=10 n=10 begin x:=10; X=15 y=15 n:=10; X=10 y=15 writeln(?x=‘,x, ?n=‘,n); chan(x,n); writeln(?x=‘,x, ?n=‘,n); end.

值参与变参的区别:
1、传值:为值参分配存储单元,过程体内对值参的操作不 影响实参的值。一旦过程体执行结束后,系统将收回值参 所占用的存储单元,值参的值也就不再存在。 2、变参是传地址:变参所占用的存储单元中存放的是实参 的地址,因此对变参的操作就是对实参的操作。一旦过程体 执行完毕,系统将收回变参所占用的存储单元,但运算结果 已保留在对应的实参中。 形参种类不同决定了实参的单、双向传递。 值参实现单向传递,仅将过程外部的值传递 实参 值参 过程 给过程,故称为输入参数,它所对应的实在 变参 过程 参数可以是常量、变量或表达式;变参实现 实参 的是双向传递,除了将过程外部的值传递给 过程外,更重要的是它能将过程中变化的形 参值带出来,故又称为输出参数,其对应的 实参必须是变量。

练习:

指出程序中的全程变量、局部变量、值参、变参, 并写出程序运行后的输出结果。
全程变量 a,b,c 局部变量 m,n 值参:y 变参:x 结果: x=4 y=13 m=9 n=17 x=5 y=13 m=12 n=18 x=6 y=13 m=15 n=19

Program lx(input,output); var a,b,c:integer; Procedure suan(var x:integer;y:integer); var m,n:integer; begin m:=x*y;x:=x+1; y:=y+10;n:=x+y; writeln(‘x=‘,x, ‘ y= ’:4,y,’m=’:4,m‘ n=’:4,n) end; begin a:=3;b:=3; suan(a,b); suan(a,b); suan(a,b) end.

综合应用:
例1-8数组归并问题:数组a,b均已从小到大排好序,各数组内 无相同元素。现将a,b合并为数组c,要求数组c也是从小到大排 好序(有相同元素时只保留一个)。 问题分析:(1)如果数组a、b的值如下: a: 2 5 6 10 17 m=5 b: 1 4 5 20 n=4 则合并后, c: 1 2 4 5 6 10 17 20 k=8 m、n、k表示数组元素的个数,设m<=10,n<=10。 (2)在程序中,I,j,k控制a,b,c的下标。设计过程du完成a,b数组的赋值。 (3)设计过程copy完成在c数组中插入指定的元素: copy(x:arrtype;var y:arrtype; var I,j:integer); 其中x为值参,I,j,y为变参,假设相应的实参为copy(a,c,4,3),则表示待 插入的元素是a[3],而当前c数组的最后一个有值的元素是c[4],因此过程 体完成的工作是将a[3]的值赋给c[5]。

program ex1-8(input,output); type while (i<=m) and(j<=n) do atype=array[1..20] of integer; begin var a,b,c:atype; if a[i]<b[j] then copy(a,c,k,i); i,j,k,m,n:integer; if a[i]>b[j] then copy(b,c,k,j); procedure du(var d:atype;h:integer); if a[i]=b[j] then begin var p:integer; copy(a,c,k,i); begin for p:=1 to h do read(d[p]); end; j:=j+1; procedure copy(x:atype; var y:atype; end; var i,j:integer); end; begin while i<=m do copy(a,c,k,i); i:=i+1; y[i]:=x[j]; j:=j+1; end; while j<=n do copy(b,c,k,j); begin write(?c:‘); readln(m,n); write(?a:‘);du(a,m); for i:=1 to k do write(c[i], ? ‘) write(?b:‘);du(b,n); end. i:=1 ;j:=1; k:=0;

例1-9 对6-1000内的偶数验证哥德巴赫猜想:任何一 个大于6的偶数总可以分解为两个素数之和。
分析:哥德巴赫猜想是一个古老而著名的数学难题, 它的理论证明十分复杂。在这里我们用计算机对有限范围 内的数加以验证,即任意输入一个大于6的偶数,若能拆 分成两个素数,则认为该猜想成立。 解题的关键是判素数。假设定义函数pan(x),用来判断 x是否为素数。若x为素数,则函数pan值为1,若不是素数 则pan值为0。

Program ex1_9(input,output); var n,m:integer; Function pan(x:integer):integer; var f,k:integer; begin f:=1; for k:=2 to trunc(sqrt(x)) do if x mod k=0 then f:=0; pan:=f end; begin repeat write(‘n=‘); readln(n); until(n>6) and (n<1000) and (n mod 2=0); for m:=2 to n div 2 do if pan(m)+pan(n-m)=2 then writeln(n,’=‘,m,’+’,n-m); end.

例1_10多精度处理。
[问题描述]设有两个多字节的数,将这两个数作加法处理。 a,b:array[1..n] of 0..9;即: a[1]a[2]…a[n-1]a[n] + b[1]b[2]…b[n-1]b[n] a[1]a[2]…a[n-1]a[n]
分析:(1)多精度数的表示: 用一维数组存放多精度数,每一个数 组元素存放一位数字,其个位放在最后一个元素。用数组 int[1..n]表示多精度数,通过键盘读入一串0-9组成的数字, 放入数组int中; (2)求和,用g表示进位,初始值为0; (3)多精度的输出.

Const n=100; Type arrtype=array[1..n] of integer; Var a,b:arrtype; g,s:integer; Procedure readdata(var int:arrtype); var ch:char; i,k:integer; Begin read(ch); k:=0; while (ch>=‘0’) and (ch<=‘9’) do begin k:=k+1; int[k]:=ord(ch)-ord(‘0’); ( ? ) read(ch) end; readln; if k<n then (?) for i:=k downto 1 do begin int[n+i-k]:=int[i]; int[i]:=0; end; end;

Procedure add(var a:arrtype; b:arrtype); var k:integer; Begin g:=0; for k:=n downto 1 do begin s:=a[k]+b[k]+g; ( ? ) a[k]:=s mod 10; g:=s div 10; end;

Procedure outdata(a:arrtype;); var k:integer; Begin k:=1; while a[k]=0 do k:=k+1; while k<=n do begin write(a[k]); k:=k+1; end; writeln; end;

Begin for s:=1 to n do begin a[s]:=0; b[s]:=0; end; readdata(a); readdata(b); add(a,b); outdata(a); End.

上机练习:
1、求正整数A和B之间的完全数(A<B). 完全数是指它的小于 该数本身的因子之和等于它本身,如6=1+2+3,6即是一个 完全数。 2、编写一个程序,它将输入到一维数组中的任意10个数按升 序排列,再从终端读入一个待查找的数x,查找出x在数组中 的位置。 要求排序由过程实现, 查找由函数实现。 3、哥德巴赫猜想:将一个奇数拆分成三个素数之和。 样例: 输入:9 输出:9=3+3+3 4、高精度处理:要求处理两个高精度的减法及多位高精度与 一位数的乘法。

数组: 特点:所有元素的值都是相同的类型

学号

语文

数学

英语

学号 姓名 性别 语文 数学

1
2 ……

45
89 ……

67
98 ……

65
76 ……

1 2 2

张三 李四 李四

男 女 女

45 89 89

67 98 98

…… …… …… …… ……

定义: A[学号代码,学科代码]
各个对应值类型不 一样,很难用数组 定义

记录

记录特点:所有元素的值可以是不同类型。

学号

姓名

性别

民族

住址

成绩 语文 数学 英语

1003
……

张三
……


……


……

延河路60号
……

89
……

87
……

67
……

学号 姓名 性别 民族 住址 成绩

字符串类型 字符串类型 布尔型 字符串类型 字符串类型 数组类型
一名学生的记录由六个 “域”组成:学号、姓名、 民族、住址等,“域”可 以具有不同的数据类型, 每个域都有名称,称为域 名。

记录类型的定义 格式
type 类型名=record 域名1:类型1; 域名2:类型2; …… …… end;
如上面学生的记录定义为:

注意点:
?在同一记录类型中,各个域名不能相同 ?各域的数据类型可以是数组、记录等其
它构造类型。

TYPE studata=record num:string[9]; name:string[8]; sex: char; ty:Boolean; age:1..150; score: real; end;

存储每位学生的五门课成绩,定义一个域: score:array[1..5] of real;

?同数组一样,记录类型的定义和记录变
量的定义可以合并定义。

记录类型的定义 记录变量的定义
TYPE studata=record num:string[9]; name:string[8]; sex: char; ty:Boolean; age:1..150; s: real; end; Var VAR stud:record num:string[9]; name:string[8]; sex: char; ty:Boolean; age:1..150; s: real; end;

合写成

stud:studata
习惯上最好先定义记录类型,再定义 变量,一般情况下不会只存储一条记 录,往往有多条记录,一般形式如: Var

st:array[1..100] of studata;

记录类型的定义 记录变量的定义

记录的访问

?记录中的域(域变量),一般引用形式为:记录名.域名。
如:Stud.name stud.name stud.ty ……

TYPE studata=record num:string[9]; 如:st.num …… st.s[1] st.s[2] …… name:string[8]; sex: char; ?对于记录数组,域的基类型又是数组的,引 用形式具体为:记录名[i].数组名[j]; ty:Boolean; age:1..150; 如st[1].num …… st[1].s[1] st[1].s[2] ……st[2].s[1] s: array[1..5] real; of real; st[2].s[2] …… end; Var Var Var

?对于域的基类型又是数组的,引用形式具体
为:记录名.数组名[i];

st:array[1..100] of studata st: studata stud:studata

记录域变量的访问 记录域变量的赋值
?可以直接赋值,也可以通过read语句从键盘上输入

记录类型的定义 记录域变量的定义

?对于记录数组,域的基类型又是数组的,一般形式为:
for i:=1 to n do for j:=1 to m do read(stu[i].score[j]);

?对同一个记录类型的变量可以整体进行赋值操作
如定义a,b两个记录变量: VAR a,b:studdata;
a:=b {把b记录中的每个域的值赋给a记录中的各个 同名的域 }

记录的应用
例1:输入10名学生的基本情况(学号、姓名、性别、年龄、成绩)后,
输出年龄最小的学生的基本情况,同时输出他们的平均成绩。

分析:先输入10位同学的个人信息,存储在记录数组中,然后 对数组找出年龄最小的学生,输出这条记录,统计平均成绩后 输出。设计几个过程和函数模块。程序代码如下:

程序如下:

program ex1_1(input,output); const n=10; type studata=record {定义学生的记录类型} num:1..10000; name:string; age:1..150; score:real; end; stud=array[1..n] of studata; var st:stud; avg:real;

{学生记录的输入过程} procedure inputstud(var students:stud); var i:integer; begin for i:=1 to n do begin write(‘Please input the number’,i,’:’); readln(students[i].num,students[i].name); readln(students[i].age,students[i].score); end; end;

{学生记录的输出} procedure outputstud(st:studdata); var ch:string; begin write(‘The number is :’,st.num); write(‘ ‘,st.name,st.age,st.score:5:1); end;

{求学生的平均成绩} function average(students:stud):real; var i:integer;s:real; begin s:=0; for i:=1 to n do s:=s+students[i].score; average:=s/n; end;

{查找年龄最小的学生记录} function findmin(students:stud):integer; var: I,a:integer; begin a:=1; for i:=2 to n do if students[i].age<students[a].age then a:=i; findmin:=a; end;

begin inputstud(st); writeln(‘The average score is:’,average(st):5:2); outputstud(st[findmin(st)]; end.

记录中域的数据类型,也可以是另一个记录类型。如果一个记录类型 中的域也是一个记录类型,则构成了记录类型的嵌套。说明一个嵌套的记 录类型时,要先说明被嵌套的记录类型。
如上例中,若要把学生的基本情况中的年龄改为出生日期,一个日期可以用年、 月、日三个数据项来描述,可以定义成一个记录类型来表示: type date=record year:1900..2003; month:1..12 day:1..31 end;

可以把上例中定义的记录合并在一起: type studata=record num:1..10000; name:string; birthday:record year:1900..2003; month:1..12; day:1..31; end; end;

源程序段如下: program ex1_1(input,output); const n=10; type studata=record {定义学生的记录类型} num:1..10000; name:string; birthday:record {定义学生的出生日期} year:1900..2003; month:1..12; day:1..31; end; end; var stud:array[1..n] of studata; st:stud; avg:real;

procedure inputstud(var students:stud); {学生记录的输入} var i:integer; begin for i:=1 to n do begin write(‘Please input the number’,i,’:’); readln(students[i].num,students[i].name); write(‘Please input his birthday :’); read(students[i].birthday.year, students[i].birthday.month); readln(students[i].birthday.day); end; end;

在访问这些域变量时在它们前面都要添加同样的记录变量 名,这就显得十分不便,尤其对于有嵌套的记录变量来说,在 访问域变量时就显得更为烦琐,这对程序的阅读和书写来说都 不方便。

开域语句
格式
With语句的形式: With 记录变量名 语句; do

说明:操作时,在do后面语句中使 用With后的记录域时,只要简单地 写出域名就可以了,域名前的记录 变量和“.”均可省略。

如下列语句: for i:=1 to n do begin write(‘Please input the number’,i,’:’); readln(students[i].num,students[i].name,students[i].age); end;
可以写成: for i:=1 to n do with students[i] do begin write(‘Please input the number’,i,’:’); readln(num, name, age); end;

练习:请同学们将上例 的程序中有记录的其它 地方用开域语句改写出 来。

开域语句
说明:对于记录的嵌套关系,可以在with后面有多个记录变量名, 之间用“,”隔开。
for i:=1 to n do begin write(‘Please input the number’,i,’:’); readln(students[i].num,students[i].name); write(‘Please input his birthday :’); read(students[i].birthday.year, students[i].birthday.month); readln(students[i].birthday.day); end; for i:=1 to n do with students[i],birthday do begin write(‘Please input the number’,i,’:’); readln(num,name); write(‘Please input his birthday :’); read(year, month,day); end;

文件
? ? ? ? 文件的概述 文件的分类 文件的基本操作 文件的应用

文件的概述
文件
按照其内在的逻辑联系分别组织在一起,构成不同的数据集合
如果文件中的信息是某个应用程序要处理的数据,则称其为该应用程序的数据文件。

利用文件的优点:
(1)文件可以永久保存,其中的数据不会因应用程序的结束而消失;

(2)文件中的数据可以为多个应用程序所共享;
(3)文件中的数据可以多次重复使用; (4)文件中存放的数据的数量在理论上没有限制。

文件的分类
按照对文件的读写方式

按文件的存储方式 作,可以交叉进行,所以也称直接文件。 第一个元素开始一个一个地顺序读每个元素,也 文本文件 只能从第一个元素开始一个一个地向文件中顺序 以ASCII代码形式(字符形式)存放的, 地写数据。由于顺序文件具有这种特征,所以对 TEXT类型文件 。 类型文件 称为 以二进制代码形式存放的文件 顺序文件的读写不能交叉进行

顺序文件 对文件的读写操作只能按文件中元素的顺序,从 随机文件 前到后依次进行,而不能跳过前面的元素直接对 可以直接对文件中的某个元素进行读写操 文件中的某个元素进行读写。所以只能从文件的

文本文件是顺序文件,类型文件是随机文件。

对文件的操作:

读取操作不会改变文件的原有内容;在读 读操作或取操作:写操作将会改变文件原有内容。写入数据的 过程与从文件中读数据的过程相反,应用程 取文件中的数据时,必须先把文件中的数 写操作或存操作: 序先把数据写入文件缓冲区,再把文件缓冲 据元素从文件中通过一定的方式复制到计 区中的内容存入外存中的实际文件中去。 算机的内存中暂存起来,然后再处理。

对文件的读写操作过程:

第一步:内存中建立一个文件缓冲区,并为指定文件分配一个通道, 使得这个实际的文件与文件缓冲区建立联系。这一过程通常被 称为打开一个文件; 第二步:对文件进行读写操作(实际是对文件缓冲区中的数据元素 进行读写操作) 第三步:文件操作结束后应释放占用的通道,切断实际文件与文件 缓冲区之间的联系,并释放文件缓冲区。这一过程通常被称为 关闭一个文件。

文件的操作
文本文件的操作
文本文件的结构

按行排列的,行与行之间用行结 束标记隔开,最后有一个文件结束标 记。

文本文件是标准文件,其实计算机已给予了定义,用户无需定义类型,直接引用

定义

var f1,f2,fil:text;
这里的text标识符为保留字,表示为文本文件类型。

文本文件的基本操作过程
文件名的定义 向文件中写数据的过程 向文件中读数据的过程 var f1:text; var f1:text; begin begin …… …… assign(f1,’abc.txt’); assign(f1,’abc.txt’); rewrite(f1); reset(f1); abc.txt为实际文件的名字,默认位置在 创建一个新的磁盘文件, …… f1Pascal 是文件变量, 安装目录下,可以用文件的绝对路 …… 并以写的方式打开该文 在变量说明部 径,如:assign(f1,’c: \text1\abc.txt’) ,当然, write(f1,a1,a2,a3,……); … not eof(f1) … 分说明 件 也可以通过读语句读入文件名。 打开一个已存在的文件, …… 并将文件指针指向开始 close(f1); 判断文件有没有结束 … not eoln(f1)… 位置 向文件f1中写入变量 …… 无论是向磁盘写文件还是从磁盘上读取文件 a1,a2,a3,……,an 的值 read(f1,a1,a2,a3,……); 内容,读写完毕必须用close命令关闭已打 判断文件行有没有结束 …… 开的文件,以保证文件的完整性和可靠性, close(f1); 从文件中读入若干个数据 否则引起文件处理错误。

文本文件的形成 [例]:从键盘上输入一段文本,将它复制到指定磁

盘文件中,然后再显示器上输出。
Program ex2_2_1(input,output); Var ch:char; str1:string; fil:text; {定义文件变量fil} begin write(‘Please input a file name:’);readln(str1); {输入文件名,建立新文件} assign(fil,str1);
{将输入的文件名赋给fil文件变量,即将内部变量与外部文件建立关联} rewrite(fil); {以写的方式打开文件fil,准备写入} while not eof do {文件未结束(即未从磁盘输入ctrl+Z)就写}

begin while not eoln do {一行未结束(即从键盘上输入一个回车符),就继续写} begin read(ch); {从键盘上读入一个字符ch}

write(fil,ch); {将ch写入文件中} end; readln; {键盘上换行} writeln(fil); {写一个行结束符到文件中} end; {写文件结束,关闭文件} close(fil); writeln; {屏幕换行} {以读方式打开文件} reset(fil); while not eof(fil) do {文件未结束} begin {一行未结束,读一行数据} while not eoln(fil) do begin read(fil,ch); {从文件中读一个字符给ch} write(ch); {将ch字符输出在屏幕上} end; {遇到行结束标志结束} {遇到了换行符,换下一行继续读} readln(fil); writeln; {屏幕输出也换行} end; {遇到文件结束标志结束} close(fil); end. {关闭文件}

思考:
生成一个文本文件(含有若干个数值数据)?

说明:数值数据与字符数据不同,数据之间 用一个空格分隔,所以在程序中要特别注意。 用文件评测时是比较两个文件是否一致, 这就要求形成的文件格式要相当规范和严格, 否则两个文件就是不一样的文件,前功尽弃。

[例] 产生n个随机整数(500以内),存放在text 文件 file1中,再从此文件中读取所有数据进行排序,把排好 序的数存放在 text 文件 file2 中,最后把 file2 中的文件 显示器上输出。

program ex2_2_4(input,output); const n=40; type arr=array[1..40] of integer; var s:arr; x,a:integer; file1,file2:text;

{ 产生随机数到f文件中 }
procedure getfile(var f:text) ; var i,a:integer; begin assign(f, 'f1.dat') ; { 产生的文本文件实际存放在f1.dat } rewrite(f); randomize; for i:=1 to n do begin a:=random(501); { 填什么? if (I mod}10<>0) and (i<>n) then write(f,a,‘ ') else writeln(f,a); end; close(f); end;

{ 将f中的原始数据转存到数组a中 } procedure readfile(var a:arr;var f:text) ; procedure sort(var a:arr) ; var i:integer; var i,j,p,t:integer; begin begin i:=0; assign(f, 'f1.dat') ; for i:=1 to n-1 do reset(f); begin while not eof(f) do p:=i; begin for j:=i+1 to n do i:=i+1; if a[j]<a[p] then p:=j; read(f,a[i]) ; if eoln(f) then readln(f) ; t:=a[i] ; end; a[i]:=a[p] ; close(f) ; a[p]:=t; end;

{ 对数组a中的数据利用选择法进行排 序}

end; end;

{ 将排好序的数存放到文件f中 }
procedure writefile(a:arr;var f:text) ; var i:integer; begin assign(f, 'f2.dat'); rewrite(f); for i:=1 to n do if (i<>n) and (I mod 10<>0) then write(f,a[i],‘ ') else writeln(f,a[i]); close(f); end;

{主程序} begin getfile(file1); readfile(s,file1); sort(s); writefile(s,file2); writescreen(file2); end.

{ 将排好序的文件输出到屏幕上,也可 直接输出数组a } procedure writescreen(var f:text); var a:integer; begin assign(f, 'f2.dat'); reset(f); while not eof(f) do begin while not eoln(f) do begin read(f,a); write(a:5); end; readln(f); writeln; end; close(f); end;

[例2]:编写程序:将文本文件input.txt复制到当 前文件夹下,文件名为output.txt。
分析:文件的复制,其实就是新建一个文本文件 output.txt,将文本文件input.txt的内容写入到 output.txt中。

从文本文件input.txt中读一个数据,向 output.txt中写这个数据。

程序如下:

Program ex2_2; var assign(input,‘work.in');reset(input); f1,f2:text; assign(output,'work.out');rewrite(output); ch:char; begin assign(f1,’input.txt’); assign(f2,’output.txt’); reset(f1);rewrite(f2); while not eof(f1) do begin while not eoln(f1) do begin Read(ch);write(ch); read(f1,ch);write(f2,ch); end; Readln;writeln; readln(f1);writeln(f2); end; close(f1);close(f2) Close(input);close(output)
end.

总结
从结构类型的特征来说,文件的构造能力并 不是很强的,这是因为它只能容纳其它类型的 结构来作为它的分量,而其本身却不能充当另 种结构的成份。然而文件在程序中的作用却是 任何一种其它类型所不能取代的。文件的价值 在于:它是程序与环境的通讯工具,是内存在 空间上的扩大,是程序信息之保存寿命在时间 上的延伸。因此,在程序需要使用或大批量信 息数据时,就要使用文件这一类型。

任务1:试一试:利用所给的文件评测程序,调试文件。 任务2:调试例题程序 任务3:编写程序 1、利用随机函数产生2个整数数列A,B,每个数列包含20个数 (0到50之间),编写程序完成下列要求: ①找出在B中出现而在A中没有出现的那些数,并输出。 ②找出在B中出现而在A中也出现的那些数,并输出。 2、有N个学生的记录(数据项有学号、语文、数学、英语)文 件(input.in)(每条记录一行),编写程序求出每个学生的总分,并 按总分进行从高到低排序,最后将所有数据输出到output.out文 件(要求一行一条记录,并含有总分项)中。 说明:学号为整数,语文、数学、英语、总分均为实数。 3、有文本文件f.dat,其中每行的字符不等,也可能有空行。编 写程序把此文件复制为ok.dat,但每行含10个字符。

不高兴的津津
【问题描述】津津上初中了。妈妈认为津津应该更加用功学习,所以津津除了上 学之外,还要参加妈妈为她报名的各科复习班。另外每周妈妈还会送她去学 习朗诵、舞蹈和钢琴。但是津津如果一天上课超过八个小时就会不高兴,而 且上得越久就会越不高兴。假设津津不会因为其它事不高兴,并且她的不高 兴不会持续到第二天。请你帮忙检查一下津津下周的日程安排,看看下周她 会不会不高兴;如果会的话,哪天最不高兴。 【输入文件】输入文件unhappy.in包括七行数据,分别表示周一到周日的日程安 排。每行包括两个小于10的非负整数,用空格隔开,分别表示津津在学校上 课的时间和妈妈安排她上课的时间。 【输出文件】输出文件unhappy.out包括一行,这一行只包含一个数字。如果不 会不高兴则输出0,如果会则输出最不高兴的是周几(用1, 2, 3, 4, 5, 6, 7分别 表示周一,周二,周三,周四,周五,周六,周日)。如果有两天或两天以 上不高兴的程度相当,则输出时间最靠前的一天。 【样例输入】 53 62 72 53 54 04 06 【样例输出】 3

算法分析
设津津在校上课的时间序列为a,妈妈安排上课的时间序列为b,津 津的学习时间序列为c,其中星期i津津在校上课的时间为a[i],妈 妈安排上课的时间为b[i],两者之和即为津津在星期i的学习时间 c[i]=a[i]+b[i]。 显然,若每天的学习时间不超过8小时,则津津整个一星期都高兴; 若出现c[i]>8,则说明星期i是津津不高兴的一天;在津津不高兴 {c[i ]} 的所有日子里,学习时间为max max= 的一天,是津津最不 1?i ? 7 高兴的。由此得出算法: for i:=1 to 7 do{读入津津每天在校上课的时间和妈妈安排上课的时 间,并计算该天学习时间} begin readln(a[i],b[i]);c[i]:=a[i]+b[i];end;{for} max:=0; maxi:=0;{计算上课时间最多的日期maxi 和该天的学习时间 max } for i:=1 to 7 do if c[i]>max then begin max:=c[i];maxi:=i;end;{then} if max<=8{若每天上课的最多时间不超过8小时,则津津不会不高 兴;否则上课最多的那天是津津最不高兴的日子} then writeln('0') else writeln(maxi);

关键是一维数组的使用

津津的储蓄计划
【问题描述】津津的零花钱一直都是自己管理。每个月的月初妈妈 给津津 300元钱,津津会预算这个月的花销,并且总能做到实际 花销和预算的相同。 为了让津津学习如何储蓄,妈妈提出,津津可以随时把整百的钱存 在她那里,到了年末她会加上20%还给津津。因此津津制定了一 个储蓄计划:每个月的月初,在得到妈妈给的零花钱后,如果她 预计到这个月的月末手中还会有多于100元或恰好100元,她就会 把整百的钱存在妈妈那里,剩余的钱留在自己手中。 例如 11 月初津津手中还有 83元,妈妈给了津津 300 元。津津预计 11 月的花销是 180 元,那么她就会在妈妈那里存 200 元,自己留下 183元。到了11月月末,津津手中会剩下3元钱。 津津发现这个储蓄计划的主要风险是,存在妈妈那里的钱在年末之 前不能取出。有可能在某个月的月初,津津手中的钱加上这个月 妈妈给的钱,不够这个月的原定预算。如果出现这种情况,津津 将不得不在这个月省吃俭用,压缩预算。 现在请你根据 2004 年 1 月到 12 月每个月津津的预算,判断会不会出 现这种情况。如果不会,计算到2004年年末,妈妈将津津平常存 的钱加上20%还给津津之后,津津手中会有多少钱。

【输入文件】输入文件save.in包括12行数据,每行包含一个小于 350的非负整数,分别表示1月到12月津津的预算。 【输出文件】输出文件save.out包括一行,这一行只包含一个整 数。如果储蓄计划实施过程中出现某个月钱不够用的情况,输出X,X表示出现这种情况的第一个月;否则输出到2004年年末津 津手中会有多少钱。 【样例输入2】 【样例输入1】 290 290 230 230 280 280 200 200 300 300 170 170 330 340 50 50 90 90 80 80 200 200 60 60 【样例输出1】 【样例输出2】 -7 1580

设 月预算序列为a,其中a[i]为第i个月的预算(1≤i≤12); total为当前剩余的钱;p为百元为单位的储蓄数。 var i,total,p:integer; {total为当前剩余的钱;p为百元为单位的 储蓄数; a:array[1..12] of integer;{每个月的预算} 由于每个月的月初妈妈给津津300元钱,因此津津第i个月 剩余的钱total=total+(300-a[i])。若total<0,则说明第i 个月的钱不够用;否则应该储蓄个100元,这样到了月 底,津津剩余的钱实际为total=total mod 100。 按照上述方法递推至12月后,储蓄在妈妈那儿有p个100 元,津津剩余的钱为total。由于年末妈妈会加上20%还 给津津,因此津津手中的钱实际为p*120+total。由此得 出算法

for i:=1 to 12 do readln(a[i]);{读入每个月的预算} for i:=1 to 12 do begin inc(total,300-a[i]);{计算第i个月剩余的钱} 这道题属于一道基础题,出题的目的, if total<0 {若第i个月的钱不够用,则输出预算失败信 息并退出 } 主要是为了考核同学能不能应用程序设 then begin write('-',i);halt;end;{then} 计语言的基本知识(一维数组、程序的 if total>100{若剩余的钱够储蓄,则以百元为单位累 三种控制结构(复合、循环、选择)) 计储蓄数,并计算剩余的钱 } 和数学推理的一般方法,编程解决简单 then begin inc(p,total div 100);total:=total mod 100;end; {then} 的实际问题。 end;{for} writeln(p*120+total);{输出年末手中的钱}





pascal语言中,如果在一个函数、过程等定
义内部又直接或间接地出现有对自身的引用,则称它

们是递归的或者是递归定义的。
例如,在数学上,所有偶数的集合可递归地定义为: ①0是一个偶数; ②一个偶数和2的和是一个偶数。 可见,仅需两句话就能定义一个由无穷多个元素组成 的集合。在程序中,递归是通过函数或过程的调用来 实现的。函数或过程直接调用其自身,称为直接递归;

函数或过程间接调用其自身,称为间接递归。

例1: 用递归计算n! n!可以由下列公式表示:

这是递归定义简单而典型的例子。

程序:
a=0 {fac(0)} a=1 {fac(1)} 1

1

2 a=2 {fac(2)}

6 a=3 {fac(3)}
a=4 24 {fac(4)}

a=5120 {fac(5)}

栈用于存放递归 调用中不断产生 的新的局部变量

program p1(input,output); var n:integer;s: longint; function fac(a:integer):longint; begin if a=0 then fac:=1 else fac:=a*fac(a-1); end; begin readln(n); s:=fac(n); writeln(n,‘!=‘,s) end.

在调用过程或函数之前,系统需完成三件事: ⑴为被调用过程的局部变量分配存储区; ⑵将所有的实在参数、返回地址等信息传递给被调 用过程保存; ⑶将控制转移到被调过程的入口。 从被调用过程返回调用过程之前,系统也应完成三 件工作: ⑴保存被调过程的计算结果; ⑵释放被调过程的数据区; ⑶依照被调过程保存的返回地址将控制转移到调用 过程。

例2: 用递归方法求两个数m和n的最大公约数。 (m>0,n>0) 求两个数的最大公约数可以用辗转相除法,即求m
与n的最大公约数等价于求(m mod n)的值与n的 最大公约数,此时的n可以当作新的m ,而(m mod n)的值当作新的n ,所以原问题的求解又变 成求新的m与n的最大公约数问题,继续下去,直 至(m mod n)为0,最大公约数就是最终存放在n中

的值。 递归公式:

program p2(input,output); var m,n,g:longint ; function gcd(m,n:longint):longint; var r:integer; begin r:=m mod n; if r=0 then gcd :=n else gcd:=gcd(n, r);{递归调用} end; begin { 主程序 } read (m,n); g:= gcd( m,n); writeln (?m=‘,m ,‘n=‘,n ,‘gcd=‘,g ); end.

思考: 0,1,1,2,3,5,8,13,21,34, 55……从第三项起,每一项都是紧挨着的前两 项的和。写出计算斐波那切数列的任意一个数 据项递归函数形式。

function fic(m:integer):longint;

begin
if m=1 then fic:=0

else if m=2 then fic:=1
else fic:=fic(m-1)+fic(m-2) {递归调用} end;

例3 0-1背包问题。设有一个背包,可以放入的重量 为 s 。现有 n 件物品,重量分别为 w1,w2…wi… , wn , (1≤i≤n)均为正整数,从n件物品中挑选若干件,使 得放入背包的重量之和正好为s。找到一组解即可。
分析:用knap(s,n)代表这一问题。 (1) 先取最后一个物品wn放入包中,若wn=s,则问题解 决,输出结果(n,wn) (2) 若wn<s,则可以放入包中,但重量还不够;若还剩 物品(即n>1),那么问题转化为从剩余的n-1个物品中选 取若干个,使得它们的重量和等于包里剩下的可放入重量 (s-wn),即问题发生转化knap(s,n)→knap(s-wn,n-1);而 选中的wn是否有效还要看后续的问题knap(s-wn,n-1)是否有 解,无解则说明先取的wn不合适,就要放弃wn,在剩余物 品中重新开始挑选,此时问题也转化为: knap(s,n)→knap(s,n-1)。

(3) 若wn>s,则不能放入包中,还得继续挑选; 若还剩物品(n>1),那么问题转化为从剩余的 n-1个物品中选取若干个,使得它们重量和等于s, 即knap(s,n)→knap(s,n-1)。 显然( 2 )( 3)中出现了递归定义,而( 1 )是 递归结束的条件; 但这仅仅是有解时出现的递归结束条件,还有可能 无解,(2)、(3)中所剩物品不够的话(n≯1) 问题就不能继续,这也是递归结束的条件。
为了标志knap(s,n)是否有解,将knap(s,n)设置布 尔函数,true为有解,false为无解。

演 示

Function knap(s,n:integer):boolean; Begin Case sgn(s-w[n]) of 0:begin writeln(?number:‘,n:4,‘weight:‘,w[n]:4); knap:=true; end; {s=w[n]情况} 1:begin if n>1 then if knap(s-w[n],n-1)=true {递归(1)} then begin writen(?num:‘,n:4,‘weight:‘,w[n]:4); knap:=true; end; else knap:=knap(s,n-1) {递归(2)} else knap:=false end; {s>w[n]情况} -1:if n>1 then knap:=knap(s,n-1) {递归(3)} else knap:=false {s<w[n]情况} end; {case} end;{knap}

例4:输入一串以‘!‘结束的字符,按逆序输出。 program p4(input,output); procedure rever; 程序中,c 是过程rever var c:char; 的局部变量。每一次递 begin 归调用,都要为局部变 read(c); if c<>'!' then rever; 量重新分配单元,因此 else write(c); 各层的变量c实际上是 end; begin {主程序} 不同的量,它们分别用 rever; 于保存执行本层调用时 end. 运行: 的输入值。 输入 hey! 输出 !yeh。

例5用递归算法把任一给定的十进制正整数 (<=32000)转换成八进制数输出。 分析:利用短除法不断除以8取余数这个重复过 程,将原数据不断缩小,形成递归关系,当数据 规模缩小至0时,递归结束。 procedure tran(n:longint); {递归过程} var k:longint; begin k:=n mod 8; {取除以8以后的余数} n:=n div 8; {取除以8以后的商} if n<>0 then tran(n); {直到商为0,结束递归过程} write(k:1) end;

例6:汉诺塔(tower of Hanoi)问题。有n个大小不 等的中空圆盘,按照从小到大的顺序迭套在立柱A上, 另有两根立柱B和C。现要求把全部圆盘从A柱(源柱) 移到 C 柱(目标柱),移动过程中可借助 B 柱(中间 柱)。移动时有如下的要求: ①一次只移动一个盘; ②不允许把大盘放在小盘上边; ③可使用任意一根立柱暂存圆盘。

先以三个盘的移动为例,看一下移动过程。

运行结果: Enter the number of disks in Hanoi tower:3 A→C A→B C→B A→C B→A B→C A→C 分析:首先将A柱上方的n-1个盘子从A柱移到B柱, 此过程中C柱为中间柱;接着将A柱剩下的一个盘子 移到C柱;最后再将 B柱上的n-1个盘子移到C柱,此 过程中 A 柱为中间柱,这就变成了移动 n-1 个盘子的 问题了。定义过程hanoi,实现这一递归算法: 若n=1,则A→C 若n>=2,则 hanoi(n-1,A,C,B) A→C hanoi(n-1,B,A,C)

语句: Hanoi(3,‘A‘,‘B‘,‘C‘)
在执行过程中,递归工作栈要为每一层 的递归保留数据,由于递归过程 hanoi 只含有四个值参数,也无其它局部变量, 因而每一层递归需记录五个数据项:返 回地址和四个值参。 ( 栈中内容为返回 的程序行号,参数 n ,参数 x ,参数 y , 参数z) 演 示

程序:

1program p6(input,output); 2 var 3 n:integer; 4 procedure hanoi(n:integer;x,y,z:char); 5 begin 6 if n=1 then writeln(x, ?->‘,n, ?->‘,z) 7 else begin 8 hanoi(n-1,x,z,y); 9 writeln(x, ?->‘,n, ?->‘,z); 10 hanoi(n-1,y,x,z) 11 end 12 end; 13begin {主程序) 14 write(?Enter the number of disks :’); 15 readln(n); 16 hanoi(n,?A‘,?B‘,?C‘) 17end.

例7用递归算法完成折半查找。
分析:折半查找是在一列升序或降序的数中查找目 标数。设数放置在数组a中,top、mid、bot分别作 为低、中、高指针,若需要查找的数是x,可以完成 以下三种比较: (1) 若x=a[mid],则表示找到。 (2) 若x<a[mid],则进行下一步查找,top不变, bot变成mid-1。 (3) 若x>a[mid],则进行下一步查找,top变成 mid+1,bot不变。 显然,(2)、(3)出现了递归关系,数据规模在 不断缩小,递归结束的条件有两个,要么找到,即 x=a[mid];要么找不到,即出现top>bot

procedure search(x,top,bot:integer); var mid: integer; begin if top<=bot then begin mid:=(top+bot) div 2; {递归调用} if x=a[mid] then writeln(?find:‘,x,‘position:‘,mid) else if x<a[mid] then search(x,top,mid-1) else search(x,mid+1,bot) end else writeln(?not been found‘,x) end; {递归调用} Begin For I:=1 to 20 read(a[I]);readln;Readln(x); First:=1 ;last:=20; Search(x,first,last); End.

思考1:求N个数的全排列。
分析: 1 个数直接输出; 2 个数有两种排列,如( a,b ) , (b,a); 3个数有六种排列;如:(a,b,c)(a, c, b)(b,a, c) (b, c, a)(c ,b, a)(c, a,b)仔细观察会发现规律: (1) a后随(b,c)的所有排列; (2) b后随(a,c)的所有排列; (3) c后随(b,a)的所有排列; 可以这样看上面的(2),它是将(1)中的a,b互换位置 实现的,( 3 )是将( 1 )中的 a,c 互换位置实现的。这样可 以重复执行“交换为止,后随剩余序列的所有排列”,使得 问题规模缩小,形成递归过程;当后随元素没有时,就到了 递归的边界。 设有n个元素a=(a1,a2…ak…,an),过程perm(a,k,n) 是求 a 的第 k到 n个元素的全排列, swap(a,k,I)是将 a的第 k个 元素和第I个元素对换,I=k,……,n.

如求a=(a,b,c)的全排列。图示如下: Prem(?abc‘,1,3)

Swap(?abc‘,1,1) Prem(?abc‘,2,3)
Swap(‘abc’,2,2) Prem(‘abc’,3,3) Swap(‘abc’,2,3) Prem(‘acb’,3,3)

Swap(?abc‘,1,2) Prem(?bac‘,2,3) Swap(‘bac’,2,2) Prem(‘bac’,3,3) Swap(‘bac’,2,3) Prem(‘bca’,3,3)

Swap(?abc‘,1,3) Prem(?cba‘,2,3) Swap(‘cba’,2,3) Prem(‘cba’,3,3) Swap(‘cba’,2,3) Prem(‘cab’,3,3)

abc acb

bac bca

cba cab

Var a:string;k,n:integer; Procedure swap(var a:string;k,I:integer); Var t:char; Begin t:=a[k];a[k]:=a[I];a[I]:=t; end; procedure perm(a:string ;k,n:integer); var i:integer; begin if k=n then writeln(a) else for i:=k to n do begin swap(a,k,I); perm(a,k+1,n) end end; Begin readln(a); {主程序} n:=length(a);perm(a,1,n); End.

递归要素:完成递归必须考虑的因素有两个。
(1)边界条件。也就是所描述问题的最简单情况,它 本身不再使用递归的定义。如阶乘,当n=0时,f(n)=1, 不使用f(n-1)来定义。 (2)递归关系。使问题向边界条件转化的规则。递 归定义必须能使问题的规模越来越简单。 递归的优点:长处是,它能使一个蕴含递归关系且结构 复杂的程序简介精炼,增加可读性。 特别是在难于找到 从边界到解的全过程的情况下,如果把问题推进一步,其 结果仍维持原问题的关系,则采用递归算法编程比较合 适。

递归的缺点:递归算法的效率往往很低,费时和费 内存空间。Free Pascal理论上可以使用4GB

(2^32byte)的内存,因此实际上几乎可以使用 系统中的所有剩余内存(但有时赛题中有内存限 制),这是因为Free Pascal使用的是32位的编译 器。但大量数据的处理过程将会耗时,有时将出 现超时。

递归转化为非递归
递归可以使一些复杂的问题处理起来简单明了,但 是,递归在每一次执行时都要为局部变量、返回地 址分配栈空间,这就降低了运行效率,也限制了递 归的深度。因此,在必要的时候可以只使用递归的 思想来求解,而程序则转用非递归的方式书写。一 般来说转化方式有两种。

利用堆栈技术来进行递归处理 一般包含四步骤: (1)在运行时,首先为递归调用建立一个栈,栈元

素类型包含值参域、局部变量域和返回地址域;
(2)这样每次在执行递归调用前,先把算法中用到 的值参和局部变量的当前值以及调用后的返回地址压 入栈中; (3)递归调用结束后,把栈顶各域的值分别赋给相 应的值参和局部变量,这样它们便得到了调用前的值 了; (4)接着无条件的转向又返回地址域所指定的位置

执行。

应用举例
例8将例5任一给定的十进制正整数(<=32000)
转换成八进制数输出。 改成非递归算法。 分析:首先为递归调用建立一个栈 S 包含值域 n 、局

部变量 k 域和返回地址的 r 域,把递归调用转化为将
值参n和局部变量的当前值以及调用后的返回地址压 入栈 S 中,再转向重复执行取余和取商;当栈 S 非空 时完成退栈,并将原栈顶中的各域分别赋给各自对 应的值参和局部变量;再转向本次返回地址所指定

的位置。为了程序中的无条件转向,需要设置语句
标号。

procedure tran(n:integer); label 1,2,3 type node=record {定义栈的成分类型} n,k:integer; r:integer; {返回地址域} end; stack=record vec:array [1..7] of node; top:integer; 因十进制整型数n不超过5 end; 位,所以对应的八进制数不 var s:stack; 会超过7位 x:node;{作为进出栈的缓冲变量} k:integer;

begin s.top:=0 {置栈空} 1:k:=n mod 8 n:=n div 8 if n<>0 then begin x.n:=n;x.k:=k;x.r:=2; push(s,x);{压栈} goto 1 end; 2:write(k:1); 3:if s.top>0 then begin x:=pop(s) {出栈} n:=x.n;k:=x.k; if x.r=2 then goto 2 {转向返回地址} end; end;

一般递归转化成非递归的算法步骤为: 假设p是一个递归算法,假定p中共有m个值参数和局 部变量,共有t处递归调用p的过程语句或函数应用, 则把p改写成一个非递归算法如下: (1)定义一个栈s,用来保存每次递归调用前值参 和局部变量的当前值以及调用后的返回地址,s栈中 的成分类型应包含m+1个域,其中前m个域是为值 参和局部变量而设置的,后一个域为返回地址而设, s栈的深度应足够大,使得在递归调用中不会溢出; (2)定义t+2个标号,其中用一个标号标在原算法中 的第一句上,用另一个标号标在做返回处理的第一条 语句上,其余t个标号作为t处递归调用的返回地址, 分别标在相应的语句上;

(3)把每个递归调用的语句或函数改写为: (Ⅰ)把值参和局部变量的当前值以及调用后的返 回地址压入栈中; (Ⅱ)把值参所对应的实在参数表达式的值赋给值 参变量; (Ⅲ)无条件转向原算法的第一条语句 (4)在算法结尾之前增加返回处理,当栈非空时作: (Ⅰ)退栈 (Ⅱ)把原栈顶中前m个域的值分别赋给各对应的 值参和局部变量; (Ⅲ)无条件转向由本次返回地址所指定的位置 (5)增设变量,作为进出栈的缓冲变量,对于递归函 数,还需要再增设一个保存函数值中间结果的临时变量, 用这个变量替换函数体中所有函数名,待函数过程结束 前,再把这个变量的值赋给函数名返回;

(6)在原算法的第一条语句前,增加一条置栈空的
语句;

(7)对于递归函数而言,若某条赋值语句中包含有
两处或多处(设有n处,n>=2)递归调用,则应首

先把它拆成n条赋值语句,使得每条赋值语句中只
包含一处递归调用,同时对增加n-1条赋值语句,

要增设n-1个局部变量,然后再按照以上六条规则
转换成非递归函数。

思考1:把求阶乘递归函数的算法改写成 非递归函数的算法。 Function f(n:integer):integer; Label:1,2,3; Var a:array [1..m0] of integer; top,f1:integer; Begin 保存计算函数值的中间结果 Top:=0; 1:if n=0 then begin f1:=1;goto 3;end; top:=top+1;a[top]:=n; n:=n-1;goto 1; 2:f1:=n*f1; 3:if top>0 then begin n:=a[top];top:=top-1;goto 2 end; F:=f1; End;

Function fib(n:integer):integer; Label 1,2,3,4 Type node=record n,b,r:integer; end; Stack=record vec :array[1..m0] of node; Top:integer; End; Var s:stack;x:node; B,fb:integer; Begin s.top:=0 1:if n<2 then begin fb:=n-1; goto 4 end; x.n:=n;x.b:=b;x.r:=2;push(s,x); N:=n-2;

例9:写出计算Fibonacci数列中任一项数据的非递归算法
Goto 1; 2:b:=fb; x.n:=n;x.b:=b;x.r:=3;push(s,x); N:=n-1;goto 1; 3:fb:=b+fb; 4:if s.top>0 then begin x:=pop(s); n:=x.n;b:=x.b; case x.r of 2:goto 2; 3:goto 3 end; fib:=fb; End;

直接将递归转化成递推
当递归关系有明确的定义时,一般来说,相邻的两 个数之间有着规律性的变化,我们常常可以利用这 种规律性的变化,一步一步递推出结果,而将递归 结束条件作为递推的初始条件。实现这种递推通常

使用循环迭代的方法,如循环累乘、计算斐波那切
数据项等。 当递归关系没有明确的递归式时,也可以转化成递

推来完成,这就需要不断的缩小问题的规模,找出
规律性的变化。

例10:将折半查找的递归算法改成非递归算法 procedure search(x,top,bot:integer); var mid:integer; begin while top<=bot do {利用循环完成重复搜索的过程} begin mid:=(top+bot) div 2; if x=a[mid] then begin writeln(?find:‘,x,‘position:‘,mid); exit end; Else if x<a[mid] then bot:=mid-1 else top:=mid+1; {形成规律,缩小问题的规模} end; writeln(?not been found‘) end;

综合应用举例
例11皇后问题。在一个8X8格国际象棋棋盘上,

放置8个皇后,使他们相互之间不能进攻,即任
意两个皇后都不能处于同一行、同一列或同一斜

线上,求出所有布局。国际象棋的棋盘是一个
8*8的方格阵,国际象棋中皇后的走棋规则是沿

横、竖直线及方格对角线的方向行走。

6

4 2

7 3

1 4

8 5

2 6

5 7

3 8

列号1

分析: 仔细观察上 面8个皇后的排列位 置,每行、列都只 有一个皇后,于是 可以设计一个一维 数组x来描述皇后的 分布局势,下标表 示皇后所在的列号, 存储单元中存放皇 后所在的行号,这 样,第k列皇后所在 的位置便是 (x(k),k)。

设1到k-1个皇后已经放好,第k个皇后放在第k列,
用过程place(k)来完成;从第k列的第一行开始往 下逐个位置试放,若在第k列的第I行上放置成功,

则x(k):=I,接着用同样的方法放置第k+1个皇后,从
而出现了递归调用place(k+1),当不断地递归调用到 超出最后一列,则递归终止,打印出1种结果;如 果在k列上所有位置放置都不满足条件,则本次调 用结束,返回到上一次调用处,即place(k-1)处,

对第k-1个皇后的原来位置进行后延,如果仍然不
行,则继续返回place(k-1),……,就这样进进退 退,打印出所有的摆放情况。

演示

function try(I,k:integer):Boolean {测试第k列的第I行能否放置皇后} var j:integer; begin j:=1;

while j<k do 点(x(j),j)与(I,k)是否在对角线上 begin if(x[j]=I) or (abs(x[j]-I)=abs(j-k)) then begin try:=false;exit end ;

j:=j+1; end; try:=true; end;

Procedure print Var I:integer; Begin cont:=cont+1; for I:=1 to n do write(x[I]); writeln(?solution:=‘,cont); End;

procedure place(k:integer); var I:integer; begin if k>n then print else for I:=1 to n do if try(I,k) then begin x[k]:=I; place(k+1) ;{递归} end; end;

回 溯
一般回溯法思路是这样的: ①这个方向有路可走,我没走过 ②往这个方向前进

③是死胡同,往回走,回到上一个路口
④重复第一步,直到找着出口

这种不断“回溯”寻找解的方法,称作“回
溯法”。回溯是较简单、较常用的搜索策

略。

Procedure place(n:integer); Var k:integer; Begin x[1]:=0;k:=1; While k>0 do {回溯结束条件} Begin x[k]:=x[k]+1; while (x[k]<=n) and not try(x[k],k) do x[k]:=x[k]+1; if x[k]<=n then if k=n then print else begin k:=k+1; x[k]:=0; end; else k:=k-1; {走到最后一列回溯} End; End.

例12 有如下图所示的七巧板,试编写一源程序如下, 使用至多四种不同颜色对七巧板进行涂色(每块涂一种 颜色),要求相邻区域的颜色互不相同,打印输出所有 可能有涂色方案。本题实际上就是著名的“地图四色” 问题。无论地图多么复杂,只需用四种颜色就可以将 相邻的区域分开。 分析:为了解题方便, 我们可以把七巧板上 每一个区域看成一个 5 6 顶点,若两个区域相 7 4 邻,则相应的顶点间 用一条边相连,这样, 2 就转化为一个图来处 3 1 理了。

6 7

5 4 2 3 1 2 3 4 5 6 7

1
1

R[I,j]=
0

表示区域I 与j相邻 表示区域I 与j不相邻

分析:从图中可以得到一 个关系矩阵来描述各区域 之间的关系。 R:array[1..n,1..n] of 0..1; 1 2 3 4 5 6 7 0 1 0 0 0 0 1 1 0 1 1 1 1 1 0 1 0 1 0 0 0 0 1 1 0 1 0 0 0 1 0 1 0 1 0 0 1 0 0 1 0 1 1 1 0 0 0 1 0

分析:按顺序分别对1号、2号、 ...... 、7号区域 进行试探性涂色,用1、2、3、4号代表4种颜色。

数据采用数组存储。s:array[1..n] of integer,s[i]表示
i区域填的颜色。 (1)对某一区域涂上与其相邻区域不同的颜色。

( 2 )若使用4种颜色进行涂色均不能满足要求,
则回溯一步,更改前一区域的颜色。 ( 3 )转步骤(1)继续涂色,直到全部结束为止, 输出。

procedure mapcolor(r,n,s); begin s[1]:=1; {第1个区域图第1种颜色} I:=2;j:=1; {I表示下一个区域,j表示第1种颜色} While I<=n do While (j<=4) and (I<=n) do Begin k:=1;{k表示已涂色区域} While (k<I) and (s[k]*r[I,k]<>j) do k:=k+1; {检查第I区与第k区是否相邻}

End;

If k<I then j:=j+1 {不能涂色} Else begin S[I]:=j; I:=I+1; j:=1 End; If j>4 then {回溯} Begin I:=I-1;j:=s[I]+1; End;

End;

例13自然数的拆分。任何一个大于1的自然数n,总可 以拆分成若干个小于n的自然数之和。试求n的所有拆 分析:设自然数n拆分为s1,s2……sk 必需满足 分。

(1)n=s1+s2+……+sk 且 2<=k<=n (2)s1<=s2<=……<=sk 设数组 s[1..m]为一个栈,用来存储自然数 n拆分后的若 干自然数 s1 、 s2 、 …… 、 sk 开始搜索,求满足条件的解。 假 设 已 求 得 部 分 的 拆 分 (s1 、 s2 、 …… 、 si), 在 s1+s2+……+sI-1<n 的情形,须添加下一个元素 si, 根据条 件可知si的起始值为sI-1 。对新元素si,有三种情形: (1) s1+s2+……+si=n,得到一个解,输出结果,且回 溯求下一种解。 (2) s1+s2+……+si<n,再添加下一个元素si+1 (3) s1+s2+……+si>n,表示在si-1后面已无法添加新元 素,则回溯,用si-1新的取值再试探。

拆分过程: else begin 第一步:初始化 {继续添加下一个元素} Readln(n); I:=I+1; I:=0;sum:=0;j:=0,count:=0 J:=s[I-1]-1; 第二步:I<>0重复 end j:=j+1;sum:=sum+j; Else begin {回溯} if sum<=n then Sum:=sum-j;{撤消j} begin s[I]:=j; {进栈} I:=I-1; {栈顶元素出栈} if sum=n then begin {回溯} 输出; Sum:=sum-s[I] sum:=sum-s[I];I:=I-1; J:=s[I]; sum:=sum-s[I]; End; j:=s[I]; 第三步:I=0 回溯中止。 end;

思考:平面中的直线。一个人用刀在意大利馅饼上做 n次直线切割,能把馅饼切成多少份?要求在切割时不 允许两条直线平行,直线间交点不允许重合。 分析:没有直线的平面具有一个区域;有一条直线的 平面具有两个区域;有 2 条直线的平面有 4 个区域;( 每条直线可以两个方向无限延伸) L0=1 L1=2 L2=4 L3=7 可以猜想Ln=2n,然而当再加入第3条新直线,出现了 问题,区域并没有按倍增加,而是增加了 3 个区域。 L3= L2+3。再做几个推广,(图略)第N条直线(n>0 )增加的区域数为 k ,当且仅当它切了 K 个老区域,而 它切K个老区域当且仅当它在K-1个不同的位置碰到前面 的直线,2条直线至多相交于一点,所以新的直线至多 与N-1条老直线相交于 N-1个不同的点,且一定有k<=n 。所以可知递归关系为 Ln=Ln-1+n(n>0) ,边界条件为 L0=1。

思考 2 :假设我们用弯曲的线来代替直线,每个弯曲 线含有一个“锯齿形的转角”,平面中 n 个这样的弯 曲线确定的区域最大数为Zn是多少?
( 2) ( 3) ( 1) ( 4)

可以看出: 1 条弯曲线像“ 2 条”直线过交点不做 延伸而合并了一些区域的 2 条直线。就 2 条直线来 说,区域 2 、 3 、 4 是不同的,当 1 条弯曲线时,变 成了 1 个区域,也就是说我们失去了 2 个区域。可 以 猜 想 为 : Zn=L2n-2n ( n>=0 ) 边 界 条 件 为 Z0=L0=1。

上机练习
1、斐波那切数列0,1,1,2,3,5,8,13,21,34, 55……从第三项起,每一项都是紧挨着的前两项的和。 写出计算斐波那切数列的任意一个数据项递归程序。 2 、 0-1 背包问题。设有一个背包,可以放入的重量为 s 。现有 n 件物品,重量分别为 w1,w2…wi… , wn ,( 1≤i≤n)均为正整数,从n件物品中挑选若干件,使得放 入背包的重量之和正好为s。找到一组解即可。 3、用递归算法写程序,输入一个非负整数,输出这个 数的倒序数 4、求阶乘的非递归程序 5、编程求安置n皇后问题的总方案数(1<n<14) 6、写出求杨辉三角的递归程序

7、棋子移动。有2n个棋子(n>=4)排成一行,开始 位置为白子全部在左边,黑子位置全部在右边。移动 棋子的规则是:每次必须同时移动相邻两个棋子,颜 色不限,可以左移也可以右移到空位上去,但不能调 换两个棋子的左右位置。每次移动必须跳过若干个棋 子(不能平移),要求最后形成黑白相间的一行棋子 。如:


一、栈的概念
栈(stack):限定只能在表尾进行插入、 删除数据元素的线性表。(后进先出表LIFO) 栈顶(top):允许插入和删除数据元素的一端。

栈底(bottom ): 固定的一端。
空栈:不含任何元素。

进栈(压栈):插入元素。
出栈(退栈):删除元素。

系统栈
在调用过程或函数之前,系统需完成三件事:
⑴将所有的实在参数、返回地址等信息传递给被调用 过程保存; ⑵为被调用过程的局部变量分配存储区; ⑶将控制转移到被调过程的入口。

从被调用过程返回调用过程之前,系统也应完 成三件工作:
⑴保存被调过程的计算结果; ⑵释放被调过程的数据区; ⑶依照被调过程保存的返回地址将控制转移到调用过 程。当有多个过程构成嵌套调用时,按照“后调用先 返回”的原则

二、顺序存储 1.定义
用一组连续的存储单元依此存放自栈底 到栈顶的数据元素,同时设立指针top (称为栈顶指针)以指示栈顶元素的当 前位置。

1.设栈S的初始状态为空,现有序列1,2,3,4,5,对该 序列在栈S上依次进行如下操作(从序列中的1开始): 进栈、进栈、进栈、出栈、进栈、出栈、进栈。问出 3,4 栈的元素序列是: 出栈的元素
4 3 5 2 3 4 4 3 5 2

出栈的元素
4 3 5 此时能出栈 的只能是2

1

1

2.若进栈的序列是1、2、3、4、5,问能 否得到出栈序列4、3、5、1、2 ?

不能

const smaxsize={栈的最大长度}; type elemtype={栈中元素的数据类型}; stack=record data:array[1..smaxsize] of elemtype; top:0 . . smaxsize end; var s:stack;

2、基本操作
⑴栈的初始化setnull(s):将s设为空栈 procedure setnull(var s:stack); begin s.top:=0 end; ⑵判断栈空sempty(s):true或false。 function sempty(s:stack):boolean; begin sempty:=(s.top=0); end;

⑶入栈 push(s , x) :若栈 S 不满,把元 素x插入到栈顶;否则返回信息 overflow(上溢)。
procedure push(var s:stack;x:elemtype); begin
if s.top=smaxsize then writeln(?overflow‘)

else begin s.top:=s.top+1; s.data[s.top]:=x end end;

⑷出栈pop(s,x):若栈s不空,把栈顶元素 赋给x,栈顶指针下移;否则返回信息 underflow(下溢)。
procedure pop(var s:stack;var x: elemtype); begin if s.top=0 then writeln(?underflow‘) else begin x:=s.data[s.top]; s.top:=s.top -1; end end;

出栈也可用函数来实现:
function pop(var s:stack): elemtype ; begin if s.top =0 then writeln(?underflow‘) else begin pop:=s.data[s.top]; s.top:=s.top -1; end end; 出栈操作之后,原栈顶元素依然存在, 只是栈顶指针下移,不再指向它。

⑸取栈顶元素 readtop(s) :若栈 s 不空 , , 返回栈顶元素的值;否则返回信息 underflow。 function readtop(s:stack):elemtype ; begin if s.top=0 then writeln(?underflow‘) else readtop:=s.data[s.top] end;
这个算法中栈顶指针保持不变,注意与 pop(s)的区别 。

更为常用的定义方式: type arraytype= array[1.. n] of integer; var stack:arraytype; top:integer; 栈顶指针做为独立变量使用。
此时的几个基本过程如何书写

练习
1、若已知一个栈的入栈顺序是1,2,3,…,n,其输 出序列为P1,P2,P3,…,Pn,若P1是n,则Pi是 ( C )。 A)i B)n-1 C)n-i+1 D)不确定
2、以下哪一个不是栈的基本运算( B )。 A)删除栈顶元素 B)删除栈底的元素 C)判断栈是否为空 D)将栈置为空栈 3、设栈S和队列Q初始状态为空,元素e 1 ,e 2 ,e 3 , e 4 ,e 5 ,e 6依次通过栈S,一个元素出栈后即进入队 列Q,若出队的顺序为e 2 ,e 4 ,e 3 ,e 6 ,e 5 ,e 1 , 则栈S的容量至少应该为( )。 B A)2 B)3 C)4 D)5

4、设栈S的初始状态为空,现有5个元素组成的序列 {1,2,3,4,5},对该序列在S 栈上依次进行如下操作(从序 列中的1开始,出栈后不再进栈):进栈,进栈,进栈,出栈, 进栈,出栈,进栈,问出栈的元素序列是:_________,栈顶 指针的值为______,栈顶元素 为 :___________________ 解答:出栈序列为 {3,4}。 ,栈顶指针值为3,栈顶元 素为5。

5、如下图,有一个无穷大的的栈S,在栈的右边排列着 1,2,3,4,5共五个车厢。其中每个车厢可以向左行走, 也可以进入栈S让后面的车厢通过。现已知第一个到 达出口的是3号车厢,请写出所有可能的到达出口的 车厢排列总数(不必给出每种排列)。 解答:9
出口
s

1 2

3

4

5

三、栈的应用
例1 :括号匹配 假设一个表达式有英文字母(小写)、 运算符(+,—,*,/)和左右小(圆) 括号构成,以“@‖作为表达式的结束符。 请编写一个程序检查表达式中的左右圆 括号是否匹配,若匹配,则返回“YES‖; 否则返回“NO‖。表达式长度小于255, 左圆括号少于20个。

分析:假设输入的字符串存储在c中 (var c:string[255]) 我们可以定义一个栈: var s:array[1..maxn] of char;top:integer; 用它来存放表达式中从左往右的左圆括号。 算法的思路为:顺序(从左往右)扫描表达式 的每个字符c[i],若是“(”,则让它进栈;若 遇到的是“)”,则让栈顶元素出栈;当栈发生 下溢或当表达式处理完毕而栈非空时,表示不匹 配,返回“NO‖,否则表示匹配返回“YES‖。

程序代码如下: var c:string;{c为字符串} function doit(c:string):boolean; var s:array[1..20] of char; top,i:integer; Begin {主程序} ch:char; assign(input,'in.txt'); begin reset(input); top:=0; readln(c); i:=1;ch:=c[i]; writeln(doit(c)); while ch<>'@' do close(input); begin end. if (ch='(') or (ch=')') then

case ch of '(':begin top:=top+1;s[top]:='(' end; ')':if top>0 then top:=top-1 else begin doit:=false;exit end; end; {case} i:=i+1;ch:=c[i]; {while} end; if top=0 then doit:=true else doit:=false; end;

例2:输入程序

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

分析:可在程序中设一个栈来逐行处理从终端
输入的字符串。每次从终端接受一个字符后作 如下判别:既不是退格符#也不是退行符@, 则将该字符插入栈顶;是退格符#,则从栈顶 删去一个字符;是退行符@ ,就把字符栈清为 空栈。

请看:COM#N89##ST
# : # : # : M出栈 9出栈 8出栈

T 9 S 8 N M O C

程序:

program p_1(input,output); type stack=record data:array[1 . . 100] of char; top:0 . . 100; end; var s:stack;ch:char;i:integer;

procedure setnull(var s:stack);{置栈为空} begin s.top:=0 end; procedure pop(var s:stack);{出栈} begin if s.top=0 then writeln(?underflow‘) else s.top:=s.top -1; end;

procedure push(var s:stack;x:char); {入栈} begin if s.top=100 then writeln(?overflow‘) else begin s.top:=s.top+1; s.data[s.top]:=x end end;

Begin {主程序} while not eof do {eof为全文结束符} begin setnull(s); while not eoln do {eoln为行结束符} begin read(ch); case ch of ?#‘:pop(s); {出栈} ?@‘: setnull(s) {置栈为空} else push(s,ch) {入栈} end; end; for i:=1 to s.top do write(s.data[i]); {输出} writeln; read(ch); end End.

[补充]关于表达式的三种表示法。

1、 中缀表达式:a+b 2、 后缀表达式:ab+ 3、 前缀表达式:+ab 4、 中缀转后缀的方法及举例转换: 一般方法:把每个运算符移到它的两个运算数 后面,每个运算数后多加上一个空格(为了 分隔各个运算数),然后去掉所有括号即可。 如:
3/5+6——3□5□/6□+ {□表示空格,下同} 16-9*(4+3)——16□9□4□3□+*2*(x+y)/(1-x)——2□x□y□+*1□x□-/ (25+x)*(a*(a+b)+b)—25□x□+a□a□b□+*b□+*

5、中缀表达式的运算规则比较多,包括优先级、 左右次序和括号;计算机去做很麻烦,且效率不 高。所以,计算机科学中是把中缀表达式先转换 成后缀表达式,在利用计算机来计算后缀表达式 的值。 后缀表达式又称“逆波兰式”,在后缀表达式 中,不存在括号,也不存在优先级的差别,计算 过程完全按照运算符出现的先后顺序进行,整个 计算过程仅需一遍扫描即可完成。 6、两个任务: (1)把中缀表达式转换成后缀表达式; (2)求后缀表达式的值;

练习:

中缀转换成后缀

例如: 3/5+6 —— 3 5 /6 +
16-9*(4+3)—— 16 9 4 3 +*-

2*(x+y)/(1-x)—— 2 x y +*1 x -/
(25+x)*(a*(a+b)+b)—— 25 x +a a b +*b +*

例3:根据后缀表达式的求值 后缀表达式:把每个运算符移到它的两个运

算对象的后面,删除所有括号。
中缀表达式 3/5+6 16 – 9 * ( 4 + 3 ) 2 * ( x + y ) / ( 1- x ) 后缀表达式 35/6+ 16 9 4 3 + * – 2 x y + * 1 x - /

分析:
栈S用来存放原始数据、中间结果和最 终结果。将后缀表达式以@结束存入字符 数组,且每个数据后面加一个空格。扫描 中,数据入栈,遇到运算符,就依次弹出 两个操作数进行运算,运算结果入栈。遇 到字符@结束,栈顶的值就是算式的结果。

后缀表达式16 9 4 3 + * – 在字符数组A中的形式为:

栈中的变化情况:

运行结果: -47

程序:
program p2(input,output); type stack=record data:array[1 . . 100] of real;{存放实型数} top:0 . . 100; end; var s:stack;ch:char;i:integer;x:real; a:array[1..30] of char;
function pop(var s:stack): real;{出栈} begin pop:=s.data[s.top]; s.top:=s.top -1; end;

procedure push(var s:stack;x:real); {入 栈} begin s.top:=s.top+1; s.data[s.top]:=x end;

begin {主程序} i:=0; repeat i:=i+1; read(a[i]); {将表达式存入数组a} until a[i]=‘@‘; s.top:=0; {清空栈} i:=1; {i为a数组的下标} ch:=a[i];

while ch<>‘@‘ do begin case ch of ?0‘..‘9‘:begin {产生完整的数} x:=0; while ch<>? ‘ do begin x:=x*10+ord(ch)-ord(?0‘); i:=i+1;ch:=a[i]; end; end; ?+‘:x:=pop(s)+pop(s) ?-‘:begin x:=pop(s);x:=pop(s)-x;end; ?*‘:x:=pop(s)*pop(s); ?/‘: begin x:=pop(s);x:=pop(s)/x; end; end; push(s,x); {将上面得到的x入栈} i:=i+1;ch:=a[i]; {继续扫描a数组} end; writeln(pop(s)) end.

例4:中缀表达式转化为后缀表达式
算法思路: 用一个栈s存放运算符 1。输入一个算术表达式,设以字符方式,并用@作为结 束符,将该表达式存放在字符数组e中。 2。对e数组的扫描,当遇到数字字符时,就把以它开始的 一组数(扫描到非数字字符为止)和空格依次输入a数 组中,当扫描到运算符时,需要检查它的运算级别是否 落后于栈顶的运算符,若是则弹出栈顶运算符并入a数 组,以此反复,直到扫描的运算符不落后于栈顶运算符 为止,若它的优先级别高于栈顶运算符,则进s栈。 3。重复第2步,直到遇到结束符@

举例

分析: 9-6/(8-5)*2

P1为栈顶元素 P1<P2 入栈 P1>P2出栈 P1=P2出栈

字符数组E 9 – 6 / ( 8 – 5 ) * 2 @ ) = ( 出栈 用 @ < – 入栈 – / > *出栈 以 ( – < / 入栈 存 – < *入栈 放 / * / < ( 入栈 * > @ 出栈 算 – – > @出栈 ( < – 入栈 符 @ @= @ 结束 – > ) 出栈
结果数组A(后缀) 9

6

8

5

– / 2

*– @

+ > > < < < > > > > < < < > > * > > > > < > > / > > > > < > > ( < < < < < = ) > > > > > > = < < < < < @ 补充的是:左括号的优先级是最高的,而里层的左括号比 外层的左括号更优先,右括号的优先级是除@号以外最低 的,但左括号和右括号的优先级则是相等的,这样定义的 目的是为了消去括号。

运算的优先级:设p1和p2分别表示前后 相邻出现的两个算符,若p1>p2则p1运 算优先p2,若p1<p2则p2优先p1。 P2 + @ * / ( ) P1

程序:
const cha:array[1..7] of string=(('>><<<>>'), ('>><<<>>'), ('>>>><>>'), ('>>>><>>'), ('<<<<<= '), ('>>>> >>'), ('<<<<< =')); type stack=array[1..100] of char; var top,i,j:integer; ch,w:char; a,s:stack;{a数组用以记录结果}

procedure push(var s:stack; ch:char); begin inc(top); s[top]:=ch; end;
procedure pop(var s:stack); begin dec(top); end; function readtop(s:stack):char; begin readtop:=s[top]; end;

Function t(p1,p2:char):char; var x1,x2:1..7; begin case p1 of '+': x1:=1; '-': x1:=2; '*': x1:=3; '/': x1:=4; '(': x1:=5; ')': x1:=6; '@': x1:=7; end;

Case p2 of '+': x2:=1; '-': x2:=2; '*': x2:=3; '/': x2:=4; '(': x2:=5; ')': x2:=6; '@': x2:=7; end; t:=cha[x1,x2]; end;

begin push(s,?@‘);{栈s用以存放运算符,初始化} j:=1;{ j 为记录a数组位置的指针} read(ch); while ch<> chr(13) do begin if ch in ['0'..'9'] then begin while ch in ['0'..'9'] do begin a[j]:=ch; inc(j); read(ch); end; a[j]:=' ';inc(j); end;

if ch in ['+','-','*','/','(',')'] then begin w:=readtop(s); while t(w,ch)=?>‘ do{w的优先级低于ch, 运算符出栈} begin a[j]:=w;{出栈进入a数组} inc(j); pop(s); w:=readtop(s); end; if t(w,ch)=?<‘ then {运算符入栈} push(s,ch) else pop(s); end; read(ch); end;

w:=readtop(s);{出空最后的操作符} pop(s); while w<>'@' do begin a[j]:=w; inc(j); w:=readtop(s); pop(s); end;

for i:=1 to j do{输出结果} write(a[i]); writeln; end.

例5:中缀表达式的求值。
9-6/(8-5)*2= 9-6/3*2= 9-2*2= 9-4= 5

算符优先算法中把运算符和左右括号统称为运 算符,在运算的每一步中,任意两个相继出现 的算符P1和P2之间的优先关系为下面三种关系 之一(E可认为出错): P1<P2 表示P1的优先权低于P2 P1=P2 表示P1的优先权等于P2 P1>P2 表示P1的优先权高于P2

在表达式的开始和结束各设置一个“#”,构成整个表达式的 一对括号;当#与#相遇时,表示整个表达式运算结束。

#9-6/(8-5)*2#

使用算符优先算法计算表达式时,需要设立两个工作栈: 一个是算符栈(fu)用以存储算符(包括#);另一个是 操作数栈(shu),用于存储操作数、中间结果和最终结 果。算法的主要思路如下: ①初始化栈fu和shu; ②读入第一个算符“#‖,入栈 fu,则“#”为栈底元素; ③读入下一个字符x; ④若x=―#‖且fu栈顶元素为“#‖时,转⑦; ⑤若x为数字,则将x入栈shu,转③; ⑥若 x 为算符,则将 x 作为 P2 , fu 栈顶元素作为 P1 ,比较 P1与P2的优先权; 若P1<P2,则P2压栈fu,转③; 若P1=P2,弹出fu栈顶元素,转③; 若P1>P2,则弹出fu栈顶元素赋给OP变量,连续弹出shu 栈顶元素分别赋给b、a,并计算a OP b,将结果压入栈 shu,转④; ⑦取shu栈顶元素输出(即运算结果),结束。

_
( / * _ # fu 5 8 2 3 6 4 2 5 9 shu

此时, X为 为) ,即 P2 此时, X ) ,即 P2 此时,X为#,fu 的 重读 X1 为 , P 为 * , 为 ) , P 是* – , P >P2, , ) , P1 是 – , P1>P2 2 1 此时,P2 仍为 ) , 栈顶元素为 # ,结束。 1 P 则从 fu 中弹出 – ,从 P 为 / ,则 >P , fu – ,从 1 1 2 结果在栈 shu 中。 P 为 ( ,则 P =P , 1 1 2 shu 中弹出 5、 、8 8 分别 2中弹出 1分别给 2 shu 5 3、 6出栈, / 出栈。 ( 出栈。 给 b 、 a,算出 8-5=3 , b6/3=2, 、a ,算出 8-5=3 ,将 则2入栈shu。 将 3入栈 shu。 3入栈 shu

#9-6/(8-5)*2# 重读X为#,P2为 #, P1为* ,则P1>P2,2、 2出栈, *出栈。2*2 =4,则4入栈shu。

P 2 为 # ,P 1 为― , P2为 *, P 为―, 则 P1>P , 4 、 9出 1 2 则P1<P , *进栈 2出栈。 栈, ― 9―4 =5,则5入栈shu。

算法描述:

procedure bds; begin setnull(fu);setnull(shu); push(fu,‘#‘); {将“#”压栈,作为fu栈的栈底元素} read(x); {读入算式的第一个字符} while (x<>?#‘) and (readtop(fu)<>?#‘) do if x not in op then push(shu,x) else case precede(readtop(fu),x) of {比较fu栈顶元素与x的优先权} ?<‘:begin push(fu,x);read(x);end;{P1<P2就压栈} ?=‘:begin pop(fu);read(x);end; {p1= ?(,p2=?)‘} ?>‘:begin m:=pop(fu);b:=pop(shu); a:=pop(shu);push(shu,operate(a,m,b);end; {p1>p2,就弹出fu的栈顶运算符,弹出shu的两 个运算数,求出的运算结果入栈shu} end; writeln(readtop(shu)) {最终保留在栈shu中的就是整个算式 的运算结果} end;

四、链接存储的栈
只允许在表头进行插入和删除运算的 单链表。

HS为栈顶指针, 也是单链表的表 头变量。

type elemtype={结点的数据类型}; link=^node; node=record data: elemtype ; next:link end;

(1)置空栈的算法setnull(hs) 不回收结点的算法:

procedure setnull(var hs:link); begin hs=nil ; end; 回收结点的算法: procedure setnull(var hs:link); begin while hs<>nil do begin p:=hs;hs:=hs^.next; dispose(p) end; end;

(2)进栈算法push(hs,x) procedure push(var hs:link;x:elemtype); begin new(p);p^.data:=x; p^.next:=hs;hs:=p; end;
(3)出栈算法pop(hs) function pop(var hs:link):elemtype; begin if hs=nil then writeln(?underflow‘); pop:=hs^.data; p:=hs; hs:=hs^.next; dispose(p) end;

(4)读取栈顶元素readtop(hs) functionreadtop(hs:link):elemtype; begin if hs=nil then writeln(?underflow‘) else readtop:=hs^.data end;
(5)判断栈空sempty(hs) function sempty(hs:link):elemtype; begin sempty:=(hs=nil); end;

五、从深度搜索看栈的应用
根结点

一个成功的解

目标结点 Program Const…; Type…; Var Stack:array[1..maxsize] of statetype; Depth:longint; …

Begin {主程序} 程序读入数据并初始化; depth:=0; repeat if 可以展开 then begin depth:=depth+1; 在stack[depth]中记录第一种决策; if depth=目标深度 then 输出方案;end else if 可以选择新决策 then 改写 stack[depth]为 新决策 else begin {返回--回溯} 消除当前深度的尝试对其它变量的影响; depth:=depth-1; end; Utnil depth=0; 程序中止;End.

自然数有序拆分
例:自然数的有序拆分。任何一个大于 1的自然数总可以拆分成若干个自然数 之和。 4=1+1+1+1 4=1+1+2 4=1+3 4=2+2 分析:设有序拆分出的数s1≤s2≤…≤sk。 定义数组s为一个栈,用来存放因子。从1 开始搜索因子,求和,若sum ≤n就将因子 压栈;若sum =n,则输出解,出栈;若 sum >n,则修改栈顶元素的值,即回溯。

top:=1;sum:=0; j:=0; {j是因子} repeat j:=j+1; sum:=sum+j; if sum<=n then begin s[top]:=j; { j进栈} if sum=n then begin print; {调用过程} sum:=sum-s[top];top:=top-1; {出栈} sum:=sum-s[top]; j:=s[top]; end else begin {继续找下一个因子} j:=s[top]; top:=top+1;end end else begin {sum>n的情况} sum:=sum-j; top:=top-1; sum:=sum-s[top];j:=s[top]; end until top=0

练习提示
? 练习1 注意回溯的条件 ? 练习2 数据规模小,可以模拟栈的操作 用一个过程来模拟进出栈的过程,可以通过循环 加递归实现回溯,重复:如果可以进栈则进一个元素, 如果可以出栈则出一个元素。就这样一个一个地试探 下去,当出栈元素个数达到n时就计数一次(也是递归 调用结束地条件)。 ? 练习3

队列的基本操作
?举例1:到医院看病,首先需要到挂 号处挂号,然后,按号码顺序救诊。 ?举例2:乘坐公共汽车,应该在车站 排队,车来后,按顺序上车。

出队

A1 A2 A3 A4……AN-1 AN
F(队头)

进队

R(队尾)

一、队列的定义 队列就是允许在一端进行插入,在另一 端进行删除的线性表。允许插入的一端 称为队尾,通常用一个队尾指针r指向

队尾元素,即r总是指向最后被插入的
元素;允许删除的一端称为队首,通常

也用一个队首指针f指向排头元素的前
面。初始时f=r=0。

? 结论:在队列这种数据结构中,最先

插入在元素将是最先被删除;反之最
后插入的元素将最后被删除,因此队

列又称为“先进先出”(FIFO—first
in first out)的线性表。

? 队列的基本操作:
(1)初始化队列 Qini (Q)

(2)入队 QADD(Q,X)
(3)出队 QDel(Q,X) (4)判断队列是否为空 qempty(Q) (5)判断队列是否为满qfull(Q)

二、队列的存储结构 1、顺序存储 Const Const m= 队列元素的上限; m= 队列元素的上限; Type Type queue=record {队列的类型定义 queue=record {队列的类型定义 }} data array[1..m]of ofelemtype elemtype data :: array[1..m] f,end; r: integer ; {队尾指针和队首指针} Var end; q:queue; {队列} Var :queue ; {队列} f, r:q integer ;{ 队尾指针和队首指针 }

二、队列的存储结构

2、链式存储
F
A1 A2 AN

R

type link= ^celltype ; celltype=record data:elemtype; next:link; end; var f,r:link;

三、队列的基本运算 1、初始化:设定Q为一空队列: procedure Qini (var Q:queue); begin

Q.f:=0;
Q.r:=0;

end;

2、判队列空:若队列Q为空,则返回值 true,否则返回值false。 function qempty(Q:queue):Boolean; begin qempty:=(Q.r=0) end;

3、判队满:若队列满,则返回值true, 否则返回值false。 function qfull(Q:queue):Boolean; begin Qfull:=(Q.r=m); end;

4、元素进队:若队列Q不满时,把元 素X插入到队列Q的队尾,否则返回信 息“Overflow”:
procedure QADD(var q:queue;x:elemtype); begin if qfull(Q) then writeln (‘overflow’) {上溢} else begin {后移队尾指针并插入元素x} Q.R:=Q.r+1; Q.data[Q.r]:=x; end;{else} end;{ADD}

5、元素出队:若队列Q不空,则把队头 元素删除并返回值给X,否则输出信息 “Underflow”: procedure Qdel(var Q:queue;var X:elemtype); begin if qempty(Q) then writeln(‘Underflow’) {下溢} else begin {后移队首指针并取出队首元素} Q.f←Q.f+1; X←Q.data[Q.f] ; end;{else} end;

应用举例 例1假设在周末舞会上,男士们和女士们 进入舞厅时,各自排成一队。跳舞开始 时,依次从男队和女队的队头上各出一 人配成舞伴。规定每个舞曲能有一对跳 舞者。若两队初始人数不相同,则较长 的那一队中未配对者等待下一轮舞曲。 现要求写一个程序,模拟上述舞伴配对 问题。 输入:第一行两队的人数 第二行舞曲的数目

分析:设计两个队列分别存放男士和女士。 每对跳舞的人一旦跳完后就回到队尾等待 下次被选。如m=3 n=2 k=6 F1 R1 A 1 2 3 1 2 3 F2 R2 ………… …………

B 1 2 1 2 1 2

const max=10000; var a,b:array[1..max] of integer; m,n,k1,k,i,f1,r1,f2,r2:integer; begin readln(m,n); for i:=1 to m do a[i]:=i; for i:=1 to n do b[i]:=i; readln(k); k1:=1; f1:=1;r1:=m;f2:=1;r2:=n;

repeat writeln(a[f1]:3,' ',b[f1]:3); r1:=r1+1;a[r1]:=a[f1]; f1:=f1+1 ; r2:=r2+1;b[r2]:=b[f2]; f2:=f2+1; k1:=k1+1;

until k1>k
end.

例2.集合的前N个元素:编一个程序,按递 增次序生成集合M的最小的N个数,M的定义 如下: (1)数1属于M; (2)如果X属于M,则Y=2*X+1和Z=3*x+1 也属于M; (3)此外再没有别的数属于M。

分析:可以用两个队列a和b来存放新产生 的数,然后通过比较大小决定是否输出, 具体方法如下: (1)令fa和fb分别为队列a和队列b的头指 针,它们的尾指针为r。初始时,X=1, fa=fb=r=1; (2)将2*x+1和3*x+1分别放入队列a和队 列b的队尾,尾指针加1。即: a[r]←2*x+1,b[r]←3*x+1,r←r+1;

(3)将队列a和队列b的头结点进行比较, 可能有三种情况: (A)a[ha]>b[hb] (B)a[ha]=b[hb] (C)a[ha]<b[hb]
将比较的小者取出送入X,取出数的队 列的头指针相应加1。 (4)重复(2),(3)直至取出第N项为止。

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

x,fa,fb,ra,rb,total,n,i:integer;
flag,flag1:boolean; begin write('N=');readln(n); x:=1;

fa:=1;fb:=1;ra:=0;rb:=0;total:=1;

while total<=n do begin write(x:5); inc(ra);inc(rb); flag:=true; for i:=fb to rb do {判重} if 2*x+1=b[i] then flag:=false; if flag then a[ra]:=2*x+1 else ra:=ra-1; b[rb]:=3*x+1;

if a[fa]>b[fb] then begin x:=b[fb];inc(fb); end else begin x:=a[fa];inc(fa); if a[fa]=b[fb] then inc(fb); end; inc(total); end; end.

算法二: var a:array[1..30000] of 0..1; f,t,n,m,i:integer; begin readln(n); for i:=1 to 30000 do a[i]:=0; a[1]:=1;f:=1;k:=1; while t<=n do begin a[f*2+1]:=1;a[f*3+1]:=1; f:=f+1; while a[f]=0 do f:=f+1; T:=t+1; end;

m:=1;i:=1; while m<=n do begin if a[i]<>0 then begin write(i,' '); m:=m+1; end; i:=i+1; end; end.

例3写出下图从入口(1)到出口(17) 的可行路线图中,数字标号表示关卡:

现将上面的路线图,按记录结构存储如下 :

请设计一种能从存储数据中求出从入口到 出口经过最少关卡路径的算法。
(17)←(16)←(19)←(18)←(1)←开始 I:=1 ; WHILE NO[I]<> 17 DO I:=I+1 REPEAT WRITE(?(?,NO[I],‘)‘); WRITE(?←‘); I:=PRE[I] ; UNTIL I=0; ;

编一个程序,找出一条通过迷宫的路径。这 里有兰色方块的单元表示走不通,将一只老鼠 从入口处经过迷宫到出口处的最短的一条通路 打印出来。 入口

例4迷宫问题

出口

分析(1)怎样来存储迷宫?将它变成0,1 二维数组。这样上述迷宫可转化为:
0 1 0 0 1 0 1 0 1 1 0 1 1 1 0 1 0 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 0 1 1 1 1 1 0 1 1 0 1 1 0 0

(2)老鼠在迷宫中怎样探索路径?有几 个方向可以探索呢? *只有三个探索方向的位置。如mg[1,1]
*有五个探索方向的位置。如mg[3,1] *有八个探索方向的位置。如mg[3,2]

思考:能否都转化为八个方向的探索呢?

这样存储的迷宫数组就转化成:
1 1 1 0 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1

1
1 1 1 1 1

1
0 0 1 0 1

0
1 1 0 1 1

1
0 1 0 1 1

0
0 1 1 0 1

1
1 0 1 0 1

0
1 0 0 1 1

1
1 1 0 1 1

0
1 1 0 0 1

1
1 1 1 1 1

(x-1,y-1( )x-1,y)(x-1,y+1) (x,y+1) (x,y-1) (x,y)

因此,数组定义为: Mg:array[0..m+1,0..n+1] of integer; 而探索方向则变成了统一的情况,都探 Dx Dy 索8个方向:
0 1 1 1 0 -1 -1 -1 1 1 0 -1 -1 -1 0 1

(x+1,y+1) (x+1,y-1( )x+1,y) 这样可以定义一个二维数组记 录探索方向。

(3)如何才能记录踪迹,并把探索的踪 迹记忆下来呢? 踪迹一般应包括来处和当前位置,可以需 要用记录类型 Node=record X,y:integer; Pre:0..r; End; 用一个对队列记忆探索的踪迹: Sqtype=array[1..r] of node;

例如:从(1,1)入口到达(6,8),往下 探索时队列的情况
1 1 1 1 1 1 1 1 1 0 1 0 0 1 0 1 1 1 0 1 1 0 1 1 1 1 1 0 1 0 1 1 1 1 0 0 1 1 0 1 1 0 1 1 0 1 0 1 1 1 0 1 0 0 1 1 1 1 1 1 1 0 1 1 1 1 0 1 1 0 0 1 1 1 1 1 1 1 1 1

(4)如何防止重复探索:将迷宫中的0替换 为-1

procedure Qini(var sQ:sqtype); begin sQ[1].x:=1;sq[1].y:=1; Sq[1].pre:=0 F:=1;r:=1;mg[1,1]:=-1; end;

Procedure mglj(var sq:sqtype); Begin Sqini; While f<=r do Begin x:=sq[f].x;y:=sq[f].y; for v:=1 to 8 do begin i:=x+zl[v,1]; j:=y+zl[v,2]; if mg[i,j]=0 then begin r:=r+1; sq[r].x:=I;sq[r].y:=j;sq[r].pre:=f; mg[I,j]:=-1; end; if (i=m) and (j=n) then [print;exit] end;

F:=f+1 End; Writeln(‘迷宫无路径’); 如何打印路径? End; Procedure print(var sq:sqtype,r:integer); Begin i:=r; repeat writeln(‘(‘,sq[i].x,’,’,sq[i].y,’)’); i:=sq[i].pre until i=0 End;

产生问题:由于顺序存储结构的存储 空间属于静态分配,所以,在添加数 据元素时,可能会出现没有剩余单元 的情况。下面我们讨论一下下图所示 的队列,称为“假溢出”现象。
0 1 2 3 4 a5 5 a6 6 a7 7 a8 rear

front

解决方法:将元素加入到第一个位置, 即将存储空间的第一个位置作为队尾。 采用首尾相接的结构后,形成一个环状, 解决假溢出问题,避免数据元素的移动。 如图所示。我们将这种形式表示的队列 称之为循环队列。 R
m m-1 am Am-1 Am-1

Am Am+1
m1 2

F

3

空闲区
Am+1

3 4

F

2
R 1

循环队列的操作 1、初始化:设定Q为一空队列,队首指 针和队尾指针均指向存储空间的最后一 个位置 procedure iniqueue(var Q:equeue); begin Q.f:=m;Q.r:=m;

end;

2、判队列空:若队列Q为空,则返回值 true,否则返回值false。 function qempty(Q:equeue):Boolean;

begin
qempty:=(Q.f=Q.r) end;

3、判队满:若队列满,则返回值true, 否则返回值false。为了区分队列空和队 列满,改用“队尾指针追上队首指针” 这一特征作为队列满标志。 function qfull(Q:equeue):Boolean; begin qfull:=((Q.r mod m)+1=Q.f);

end;

4、元素进队:若队列Q不满时,把元素 X插入到队列Q的队尾,否则返回信息 “Overflow”: procedure add(var Q:equeue;X:elemtype); begin if qfull(Q) then writeln(‘Overflow’) else begin Q.r:=Q.r mod m+1; Q.data[Q.r]:=X; end end;

5、元素出队:若队列Q不空,则把队头 元素删除并返回值给X,否则输出信息 “Underflow”: procedure del(var Q:equeue;var X:elemtype); begin if qempty(Q) then writeln(‘Underflow’) else begin {后移队首指针并取出队首元 Q.f:=Q.f mod m+1; X:=Q.data[Q.f]; end; end;

例5约瑟夫问题:编号为1,2,……n个人 按顺时针方向围坐一圈,每人持一个正整 数密码,开始给定一个正整数m,从第一 个人按顺时针方向自1开始顺序报数,报 到m者出围坐的圈子,不再参加报数,这 时将出列者的密码作为m,从出列者顺时 针方向的下一个人开始重新从1报数,如 此下去,直到所有人都出围坐的圈子为止, 输出出列者的序列。

例如有5人 M=18

序号

1 8

2 7

3 3

4 6

5 5

密码

(1)开始取m=18,从1报 1 2 4 5 8 7 6 5 数,则序号为3的人出列。 (2)开始取m=3,从4报数, 2 4 5 7 6 5 则序号为1的人出列。 (3)开始取m=8,从2报数, 2 5 7 5 则序号为4的人出列。 (4)开始取m=6,从5报数, 5 5 则序号为2的人出列。 (5)开始取m=5,从5报数, 出列顺序为:3,1,4,2,5 则序号为5的人出列。

const max=30; type people=record number,code:array[1..max] of integer end; var a:people; m,n,i,j,s,w,p:integer; begin readln(m,n); for i:=1 to n do a.number[i]:=i; for i:=1 to n do read(a.code[i]);

s:=1; for j:=n downto 1 do begin s:=(s+m-1) mod j; if s=0 then s:=j; w:=s;p:=a.number[w];write(p,' '); m:=a.code[p]; for i:=s to j-1 do a.number[i]:=a.number[i+1]; end; end.

综合举例

有10升油在10升的容器中,另有两个7升和3升的 空容器,现要求用这三个容器倒油,使得最后在 10升和7升的容器中各有5升油。 分析: 三个容器可以看作三个变量 C10,C7,C3, 每次倒油的可能性只有如下六种情况: ① C10 向 C7 倒油 ② C10 向 C3 倒油 ③ C7 向 C10 倒油 ④ C7 向 C3 倒油 ⑤ C3 向 C10 倒油 ⑥ C3 向 C7 倒油

从一个容器状态(三个容器中油的容量) 看,虽然有可能经过上述六种倒油的方法产 生六种容器状态,但实际上这六种新产生的 容器状态,许多是已经出现过的状态。例如 初始状态(10,0,0)表示 C10=10,C7=0, C3=0,经过上述六种倒油方法只能产生出两 种新的容器状态(3,7,0)和(7,0,3),再 增加一个变量记录当前状态是由什么状态产 生的,这样就形成了一个不断扩张新结点的 过程,因此这个倒油的过程就可以用队列来 记录了。

Type node=record c10,c7,c3:integer; pre:0..100; end; Var q:array [1..100] of node; f,r:integer; w10,w7,w3:integer; 三种容器中实际装油量 达到目标状态的标志 flag:boolean; Procedure out; {取队头结点} Begin w10:=q[f].c10;w7:=q[f].c7;w3:=q[f].c3; End;

Procedure push; {入队} Var flag1:boolean; {队中是否已有同结点的标志} Begin flag1:=true; for k:=1 to r do if (q[k].c10=w10) and (q[k].c7=w7) and (q[k].c3=w3) then flag1:=false; If flag1 then begin r:=r+1; q[r].c10:=w10; q[r].c7:=w7; q[r].c3:=w3 q[r].pre:=f end; End;

Procedure cup;{产生新结点的过程} Begin out; {c10→c7} If w10>0 then begin if w10+w7>=7 then begin w10:=w10+w7-7;w7:=7; End; else begin w7:=w10+w7; w10:=0; end; push; if (q[r].c10=5) and (q[r].c7=5) then begin flag:=true; exit; end; end;

out; {c10→c3} If w10>0 then begin if w10+w3>=3 then begin w10:=w10+w7-3;w3:=3; End; else begin w3:=w10+w3; w10:=0; end; push; if (q[r].c10=5) and (q[r].c7=5) then begin flag:=true; exit; end; end;

out; {c7→c10} If w7>0 then begin w10:=w10+w7;w7:=0; push; if (q[r].c10=5) and (q[r].c7=5) then begin flag:=true; exit; end; end; out; {c7→c3} If w7>0 then begin
if w7+w3>=3 then begin w7:=w7+w3-3;w3:=3; End; else begin w3:=w7+w3; w7:=0; end

push;
if (q[r].c10=5) and (q[r].c7=5) then begin flag:=true; exit; end; end;

out; {c3→c10} If w3>0 then begin w10:=w10+w3;w3:=0; push; if (q[r].c10=5) and (q[r].c7=5) then begin flag:=true; exit; end; end; out; {c3→c7} If w3>0 then begin if w3+w7>=7then begin w3:=w3+w7-7;w3:=0;end else begin w7:=w7+w3; w3:=0; end; push; if (q[r].c10=5) and (q[r].c7=5) then begin flag:=true; exit; end; end;

Procedure print; Var s:array[1..100] of 0..100; begin write('queue:'); for i:=1 to r do write(q[i].c10:3,q[i].c7:3, q[i].c3:3, q[i].pre:3); s[1]:=r;i:=1; writeln; while s[i]<>0 do begin i:=i+1;s[i]:=q[s[i-1]].pre; end; for k:=i-1 downto 1 do writeln(q[s[k]].c10:5,q[s[k]].c7:5, q[s[k]].c3:5); end;

Begin{主程序}
f:=1;r:=1; q[1].c10:=10;q[1].c7:=0;q[1].c3:=0; q[1].pre:=0;Flag:=false; Repeat cup; f:=f+1;untile flag or (f>r);

If f>r then write(‘no’)
else print;

End.

1、翻币问题:有N个硬币(6<=N<=30)正面朝 上排成一排,每次将5个硬币翻过来放在原位置, 直到最后全部硬币翻成反面朝上为止。编程让 计算机找出步数最少的翻法并把翻币过程及次 数打印出来(用o表示正面,x表示反面,‘o’ 和‘x’均为小写字母)。 2、六城市问题:下面是六个城市之间道路联系 的示意图,连线表示两城市之间有道路相通。 请编一程序,由计算机找出从C1城到C6城的没 有重复城市的所有不同的路径。


推荐相关:

江北区第九届中小学生计算机程序设计竞赛

江北区第九届中小学生计算机程序设计竞赛_营销/活动策划_计划/解决方案_实用文档...第一步:把 3 号叠到 2 号上面 第二步:把 4 号叠到 2 号上面,因为不能...


2008年东莞市小学生计算机程序设计竞赛市初赛试题和答案

2008年东莞市小学生计算机程序设计竞赛市初赛试题和答案_学科竞赛_初中教育_教育专区...(第一步上 2 级,第二步上 1 级) ,12(第一 步上 1 级,第二步上 1...


2006年青岛市程序设计竞赛试题

2006年青岛市程序设计竞赛试题_学科竞赛_小学教育_教育专区。2006 年青岛市程序...第二步:用户名为参赛选手本人的考试号,无须输入密码。 第三步:登录后,将本人...


2005年东莞市小学生计算机程序设计竞赛

2005年东莞市小学生计算机程序设计竞赛_营销/活动策划_计划/解决方案_实用文档。...X ^ 左 * 右 0 A a 请完善下面的算法: 第一步:C0=0,C1=a 第二步:...


2013年全国数学建模B题省一等奖

2013 高教社杯全国大学生数学建模竞赛 承 诺 书 ...图 3 文字特征图 利用 matlab 软件进行编程,将每个...图6 以第 9 组为例的拼接结果 1 第二步,人工干预...


小学 Pascal教程

(奥林匹克)辅导纲要 附录五:竞赛试题及参考答案 1 第一章 程序设计初步本章...第二步: 一行一行的输入程序, 发现输入错误, 可用光标移动键和 Delete 键 (...


数控编程教案

通过现场编程竞赛,增强学生的拼搏精神,培养学生学习兴趣和实践操作能力 教学目的 ...第二步: Z 方向切削外 沿 生总结 G90 程序段 的走刀路线及循环 第三步:...


VEX机器人培训流程过程心得

泊思地机器人培训这里我们还不得不提到 VEX 竞赛有...第二步,学生开始初步搭建机器人。 泊思地机器人...编程手在一遍一遍的根据场地环境调试着程序,操控手...


可编程控制器技术

器控制任务编程与实现任务要求:设计一个智力竞赛抢答控制装置,要求如下 1.当主持...第一步:A-B-C-D-E 第二步:A-AB-BC-CD-DE-EA 第三步:AB-ABC-BC-BC...


THPFSL-2型实训指导书(含使用说明书)

34 实训十一 智力竞赛抢答装置的控制 ......确定控制上的相互关 系之后,就可进行编程第二步──分配输入输出设备,在分配了 PLC 的输入输出点、内部辅助 继电器...

网站首页 | 网站地图
All rights reserved Powered by 简单学习网 www.tceic.com
copyright ©right 2010-2021。
文档资料库内容来自网络,如有侵犯请联系客服。zhit325@126.com