Pascal教程(整理版)

《Pascal教程(整理版)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

第一章　简单程序2第一节Pascal程序结构和基本语句2第二节顺序结构程序与基本数据类型7第二章　分支程序11第一节条件语句与复合语句11第二节情况语句与算术标准函数13第三章　循环程序16第一节　for循环16第二节　repeat循环22第三节　While循环27第四章　函数与过程32第一节　函数32第二节　自定义过程35第五章　Pascal的自定义数据类型39第一节　数组与子界类型39第二节　二维数组与枚举类型47第三节　集合类型55第四节　记录类型和文件类型59第五节指针类型与动态数据结构66第六章程序设计与基本算法72第一节　递推与递归算法72第二节　回溯算法79第七章　数据结构及其应用85第一节　线性表85第二节　队列89第三节　栈92第四节　数组96第八章搜索99第一节　深度优先搜索99第二节　广度优先搜索110第九章其他常用知识和算法114第一节　图论及其基本算法114第二节　动态规划121125 第一章　简单程序无论做任何事情，都要有一定的方式方法与处理步骤。计算机程序设计比日常生活中的事务处理更具有严谨性、规范性、可行性。为了使计算机有效地解决某些问题，须将处理步骤编排好，用计算机语言组成“序列”，让计算机自动识别并执行这个用计算机语言组成的“序列”，完成预定的任务。将处理问题的步骤编排好，用计算机语言组成序列，也就是常说的编写程序。在Pascal语言中，执行每条语句都是由计算机完成相应的操作。编写Pascal程序，是利用Pascal语句的功能来实现和达到预定的处理要求。“千里之行，始于足下”，我们从简单程序学起，逐步了解和掌握怎样编写程序。第一节Pascal程序结构和基本语句在未系统学习Pascal语言之前，暂且绕过那些繁琐的语法规则细节，通过下面的简单例题，可以速成掌握Pascal程序的基本组成和基本语句的用法，让初学者直接模仿学习编简单程序。[例1.1]编程在屏幕上显示“HelloWorld!”。Pascal程序：Programex11;BeginWriteln(‘HelloWorld!’);ReadLn;End.这个简单样例程序，希望大家的程序设计学习能有一个良好的开端。程序中的Writeln是一个输出语句，它能命令计算机在屏幕上输出相应的内容，而紧跟Writeln语句后是一对圆括号，其中用单引号引起的部分将被原原本本地显示出来。[例1.2]已知一辆自行车的售价是300元，请编程计算a辆自行车的总价是多少？解：若总售价用m来表示，则这个问题可分为以下几步处理：①从键盘输入自行车的数目a；②用公式m=300*a计算总售价；③输出计算结果。Pascal程序：ProgramEx12;{程序首部}Vara,m:integer;{说明部分}Begin{语句部分}Write(‘a=’);ReadLn(a);{输入自行车数目}125 M:=300*a;{计算总售价}Writeln(‘M=’,m);{输出总售价}ReadLn;{等待输入回车键}End.此题程序结构完整，从中可看出一个Pascal程序由三部分组成:(1)程序首部由保留字Program开头，后面跟一个程序名(如:Exl1)；其格式为:Program程序名；程序名由用户自己取，它的第一个字符必须是英文字母，其后的字符只能是字母或数字和下划线组成，程序名中不能出现运算符、标点符和空格。(2)说明部分程序中所用的常量、变量，或类型、及过程与自定义函数，需在使用之前预先说明，定义数据的属性（类型）。[例1.2]程序中VarS，R，C:Real；是变量说明，此处说明S，R，C三个变量均为实数类型变量。只有被说明为某一类型的变量，在程序中才能将与该变量同类型的数值赋给该变量。变量说明的格式为:Var变量表：类型；(3)语句部分指由保留字Begin(开始)至End.(结尾)之间的语句系列，是解决问题的具体处理步骤，也是程序的执行部分。Pascal程序不管是哪部分，每句末尾都必须有分号(；)，但允许最接近End的那个语句末尾的分号省略；程序结束的End末尾必须有圆点(.)，是整个程序的结束标志。程序中花括号“{}”之间的部分为注释部分。Pascal程序结构可归纳用如下的示意图来表示：Program程序名；程序首部标号说明；(Label)常量说明；(Const)说明部分类型说明；(Type)变量说明；(Var)过程或函数说明；Begin程序体(主程序)语句系列；语句部分End.图1.1Pascal程序的结构把处理问题的步骤编成能从上到下顺序执行的程序，是简单程序的基本特征。再来分析下面两道例题的Pascal程序结构和继续学习基本语句。［例1.3］编程计算半径为R的圆的面积和周长。解：这是一个简单问题，按数学方法可分以下几步进行处理：①从键盘输入半径的值R；{要求告诉圆的半径R}②用公式S=πR2计算圆面积；125 ③用公式C=2πR计算圆周长；④输出计算结果。Pascal程序:ProgramEx13；{程序首部}VarR，S，C:Real；{说明部分}Begin{语句部分}Write('R=?')；Readln(R)；{输入半径}S:=Pi*R*R；｛圆面积公式S=πR2｝C:=2*Pi*R；｛圆周长公式C=2πR｝Writeln('S='，S)；{输出结果}Writeln('C='，C)；Readln｛等待输入回车键｝End.程序中Pi是Pascal提供的标准函数，它返回圆周率的近似值：3.1415926…。(:=)是赋值符号，赋值语句的格式为:变量:=表达式；赋值语句的作用是将:=右边表达式的值记录到左边的变量中。Writeln是输出语句，输出语句有三种格式:①Write(输出项1，输出项2)；｛执行输出后光标不换行｝②Writeln(输出项1，输出项2)；｛执行输出后光标换到下一行｝③Writeln｛仅输出空白且光标换到下一行｝Writeln语句后面的圆括号以内部分均为输出项，可以是多项，各项间用逗号分隔；对单引号里的内容按照引号内的原样(字符)输出显示。如果输出项是表达式，则只输出表达式的值，而不是表达式本身。125 [例1.4]输出两个自然数相除的商和余数。解:设被除数、除数、商和余数，分别为A，B，C，D，均为变量，且都是整数类型。题中未给出具体的自然数A、B，可采用键盘输入方式。①给出提示，从键盘输入a,b；②显示两数相除的数学形式；③求出a除以b的商c；④求出a除以b的余数d；⑤紧接等式后面输出显示商和余数。Pascal程序:ProgramEx14；Vara,b,c,d:integer；BeginWrite('INPUTA，B：')；｛给出提示信息｝Readln(a，b)；｛输入a，b｝Writeln；｛输出一空行｝Write(a，'/'，b，'=')；｛输出等式之后不换行｝c:=adivb；｛整除运算，取商的整数部分｝d:=amodb；｛相除求余运算，取商的余数部分｝Writeln(C，'…'，d)；{输出后自动换行}Readln{等待输入回车键}End.执行本程序中第一个Write语句，输出其引号以内的一串提示信息，是给紧接着的输入语句提供明确的提示(要求)，有“一目了然，人机对话”之效果。Readln是一个特殊的输入语句，要求输入一个回车(换行)才能往下执行。Readln是输入语句，它的一般格式为:①Read(变量1，变量2)；②Readln(变量1，变量2)；③Readln前两种格式均要从键盘给变量输入数据，输入时，所键入的数据之间以空格为分隔，以回车为输入结束。若多输入了数据(即数据个数超过变量个数)，Read语句读完数据之后，能让后续的读语句接着读取多下来的数据；而Readln语句对本行多输入的数据不能让后续语句接着读取多下来的数据。为了防止多输入的数据影响下一个输入语句读取数据，建议尽量使用Readln语句输入数据。第三种格式不需输入数据，只需按入一个回车键。[例1.5]自然数的立方可以表示为两个整数的平方之差，比如43=102－62，请输出自然数1996的这种表示形式。(这里的43用自乘三次的形式4*4*4表示；102也用自乘二次的形式10*10表示)解:此题没有现成的计算公式能直接利用，但可以自行推出处理方法或构建适当的运算公式，按着构想的处理方案编排出各步骤。设这个自然数为N，两个平方数分别为X，Y，将问题表示为求N3=X2—Y2①125 先找出X的值，仔细观察题中的示例，用数学方法归纳可得出X=N*(N+1)/2；（构成本题可用的计算公式）②再仔细观察，发现Y值比X小一个N值，即Y=X—N；③输出等式N3=X2—Y2或N*N*N=X*X—Y*YPascal程序:ProgramEx15；ConstN=1996；{常量说明}VarX，Y:Longint；{变量说明，此题计算中的数值较大，用长整型}BeginX:=N*(N+1)div2；{div是整除运算}Y:=X-N；Writeln(N,'*',N,'*',N,'=',X,'*',X,'—',Y,'*',Y)；{输出结果}ReadlnEnd.本程序中N是常量，X，Y是变量，为长整数类型(Longint)；程序中的div是整除运算，其结果只取商的整数部分；[例1.6]求一元二次方程x2+3x+2=0的两个实数根。解:方程的系数是常量，分别用a，b，c表示，可运用数学上现成的求根公式求方程的根，采取如下方法:①先求出d=b2-4ac；（求根公式中需用开方运算的那部分）②再用求根公式算出x1，x2的值。(x1，x2=?)③输出x1，x2.Pascal程序:programEx16；Consta=1；{常量说明}b=3；c=2；｛a，b，c表示方程系数｝Vard:integer；｛d为整型变量｝X1，X2:Real；｛X1，X2为实型变量｝Begind:=b*b-4*a*c；x1:=(-b+sqrt(d))/(2*a)；｛求方程的根｝x2:=(-b-sqrt(d))/(2*a)；Writeln('X1='，X1，'':6，'X2='，X2)；{输出结果}Readln｛等待输入一个回车键｝End.本程序中的a，b，c均为常量；变量d是整数类型，而变量x1，x2则是实数类型，因为运算式中的Sqrt(d)开平方运算和(/)除法运算使结果为实数。Sqrt()是开平方函数，是Pascal系统的一个标准函数。习题1.1模仿例题编程1.加法计算器：编程由键盘输入两个整数a和b，计算出它们的和并输出到屏幕上。125 ）2.某梯形的上底、下底和高分别为8，12，9，求该梯形的面积。(梯形面积公式为S=3.求右图所示边长为5.6的正立方体表面积。4.已知图园柱体的高为12，底面园的半径为7，求园柱体表面积。5.计算某次考试语文、数学、英语和计算机等四科的总成绩与平均成绩。(请用输入语句从键盘输入各科成绩分)第二节顺序结构程序与基本数据类型前面的简单程序已体现出处理问题步骤、思路的顺序关系，这就是顺序结构程序。［例1.7］交换两个变量的值：由键盘输入两个正整数A和B，编程交换这两个变量的值。解：交换两个变量的值，可以想象成交换两盒录音带（称为A和B）的内容，可以按以下步骤处理：步骤①：拿一盒空白录音带C为过渡，先将A翻录至C；步骤②：再将B翻录至A；步骤③：最后将C翻录至B。这样操作，可达到题目要求。Pascal程序：ProgramExam17;Vara,b,c:integer;BeginWrite(‘A,B=’);Readln(a,b);C:=A;｛等价于步骤1｝A:=B;｛等价于步骤2｝B:=C;｛等价于步骤3｝Writeln(A,B);End.[例1.8]分钱游戏。甲、乙、丙三人共有24元钱，先由甲分钱给乙、丙两人，所分给的数与各人已有数相同；接着由乙分给甲、丙，分法同前；再由丙分钱给甲、乙，分法亦同前。经上述三次分钱之后，每个人的钱数恰好一样多。求原先各人的钱数分别是多少?解:设甲、乙、丙三人的钱数分别为A，B，C。用倒推(逆序)算法，从最后结果入手，按反相顺序，分步骤推算出每次各人当时的钱数:（在每个步骤中，各人钱数分别存在A、B、C中）步骤①:A=8B=8C=8{这是最后结果的钱数，三人都一样多}步骤②:A=A/2(=4)B=B/2(=4)C=A+B+C(=16){A，B未得到丙分给的钱时，只有结果数的一半；C应包含给A，B及本身数三者之和}步骤③:A=A/2(=2)C=C/2(=8)B=A+B+C(=14)125 {A，C未得到乙分给的钱时，只有巳有数的一半；B应包含给A，C及本身数三者之和}步骤④:B=B/2(=7)C=C/2(=4)A=A+B+C(=13)C未得到甲分给的钱时，只有巳有数的一半；A应包含给B，C及本身数三者之和}步骤⑤:输出A（=13）B（=7）C（=4）{此时的A，B，C就是三人原先的钱数}Pascal程序:ProgramExam18；Vara，b，c:integer；Begina:=8；b:=8；c:=8；{对应于步骤①}a:=adiv2；b:=bdiv2；c:=a+b+c；{对应于步骤②}a:=adiv2；c:=cdiv2；b:=a+b+c；{对应于步骤③}b:=bdiv2；c:=cdiv2；a:=a+b+c；{对应于步骤④}Writeln('a='，a，'':4，'b='，b，'':4，'c='，c)；　{输出}ReadlnEnd.细心观察，会发现本程序语句的顺序很关键。此例用反推顺序(逆序)，按步骤正确推算出各变量的值。当然，有的问题可按正序步骤编程，这类程序都称为顺序程序。本程序Writeln语句的输出项含有('':4)，这里的冒号用来指定该项显示所占宽度，此处是输出4个空格即(空格项占4格)。[例1.9]有鸡兔同笼，头30，脚90，究竟笼中的鸡和兔各有多少只?解:设鸡为J只，兔为T只，头为H，脚为F，则:J+T=30①2*J+4*T=90②解此题暂不必采用数学上直接解方程的办法，可采用“假设条件与逻辑推理”的办法：假设笼中30个头全都是兔，那么都按每头４只脚计算，总脚数为(4*H)，与实际脚数(F)之差为(4*H—F)，如果这个差=0，则笼中全是兔（即鸡为0只）；如果这个差值>0，说明多计算了脚数，凡是鸡都多给算了两只脚，用它除以2就能得到鸡的只数，处理步骤为:①J=(4*H—F)/2{先用脚数差值除以2算出鸡的只数}②T=H—J{再用总头数减鸡数算出免的只数}按此方法，这两步运算必须注意先后顺序才会符合运算逻辑。Pascal程序:ProgramExam16；ConstH=30；{常量说明}F=90；VarJ，T:byte；{为字节类型的整数}BeginJ:=(4*H-F)div2；{整除运算}T:=H-JWriteln('J='，J，'':6，'T='，T)；ReadlnEnd.125 本程序中H，F为常量，变量J，T为byte类型，属于整数类型。Pascal定义了五个标准整数类型，如下表所示:类型取值范围占字节数格式Shortint（短整型）-128..1271带符号8位Integer　（整型）-32768..327672带符号16位Longint（长整型）-2147483648..21474836474带符号32位Byte　（字节型）0..2551无符号8位Word　（字型）0..655352无符号16位在前面程序中常用的数据类型除整数类型,还有实数类型。Pascal还定义了五个标准实数类型，列表所示如下:类型取值范围占字节数有效数字Real2.9×10-39~1.7×103867~8位Single1.5×10-45~3.4×1038411~12位Double5.0×10-324~1.7×10308815~16位Extended1.9×10-4951~1.1×1049321019~20位Comp-263+1~238-1819~20位在TurboPascal中实数的表示用科学记数法，可认为由三部分组成:#.##E+##或#.##E-##①#．##表示有效数字；②E表示以10为底的幂；③+##或-##是指数部分，+号可省略。例如:1.7E+38可写成1.7E38(等同于1.7×1038)。在实数类型定义下，即使是整数，在程序执行时系统也将自动转换成科学记数形式，试请运行下面程序并注意观察运行结果:ProgramExam17；Varx:real；{x为实数类型}BeginX:=180；{把整数180赋给实数类型变量X}Writeln('x='，x)；　　　{输出的x自动表示成实数形式}ReadlnEnd.习题1.21.已知△ABC中的三边长分别为25.76，74.03，59.31，求△ABC的面积。(计算公式:S=。其中P=)2.某车棚存有自行车和三轮车共65辆，它们的轮子数合计为150个。求该棚内存有的自行车和三轮车各是多少辆？3.甲、乙、丙三人分别有磁带36，48，64盒。先由甲把自己的磁带平均分为三份，分给乙、丙各一份，自己留下一份；接着是乙，最后是丙，都按甲的方法处理。编程输出甲、乙、丙在上述过程中各人的磁带数分别是多少?(输出所有的中间结果)125 4.五位好朋友相聚。第一位朋友带来了很多糖块赠送给各位朋友，使每人的糖块在各自原有的基础上翻了一倍；接着第二位好友也同样向每人赠送糖块，他同样使每人的糖块在各人已有的数量上翻了一倍；第三、第四、第五位好友都照此办理。经过这样的赠送之后，每人的糖块恰好都为32块。问各位好友原先的糖块数分别是多少?125 第二章　分支程序在程序设计中，许多问题是在一定条件下才选择某种处理方式的，这就需要用条件判断语句或情况选择语句进行处理。程序执行中将出现选择(分支)，根据条件只选择执行部分语句,不一定都是按原顺序从头到尾地执行所有语句，这样的程序称为分支程序。第一节条件语句与复合语句[例2.1]某服装公司为了推销产品，采取这样的批发销售方案:凡订购超过100套的，每套定价为50元，否则每套价格为80元。编程由键盘输入订购套数，输出应付款的金额数。解:设X为订购套数，Y为付款金额，则:①输入X;②判断X值；③根据判断结果选择符合条件的那种方法计算Y值；④输出计算结果。Pascal程序:ProgramExam21；Varx，y:integer；BeginWrite('X=')；Readln(x)；{输入X}ifx>100theny:=50*Xelsey:＝80*X；{条件判断与选择}Writeln('y='，y)；ReadlnEnd.程序中的if语句常称为条件语句，它的一般格式为:(1)if条件then语句；(2)if条件then语句1else语句2；IF语句的功能是按条件在两种可能中选择其中一种。习惯上把if后面的表达式称为条件，then后面的语句称为真项，else后面的语句称为假项。若条件成立(为真)就执行真项，然后执行if语句的后继语句；若条件不成立(为假)就跳过真项而执行假项，然后执行后继语句。而第一种格式只有真项，没有假项，当条件不成立(为假)就什么也不需做，直接往下去执行后继语句。[例2.2]读入三个不同的数，编程按由小到大的顺序排列打印出来。125 解:设读入的三个数为a，b，c，为了把较小的数排在前面，可作如下处理:①如果a＞b就交换a、b的值，将较大的值换至后面；②如果a＞c就交换a、c的值，将较大的值换至后面；③如果b＞c就交换b、c的值，将较大的值换至后面；④输出处理后的a,b,c。Pascal程序:ProgranmExam22；Vara，b，c，t:Real；BeginWrite('Inputa，b，c=')；Readln(a，b，c)；ifa＞bthenbegin｛复合语句｝t:=a；a:=b；b:=t{交换a，b}end；ifa＞cthenbegin｛复合语句｝t:=a；a:=c；c:=t{交换a，c}end；ifb＞cthenbegin｛复合语句｝t:=b；b:=c；c:=t{交换b，c}end；Writeln('a，b，c:'，a:6，b:6，c:6)；ReadlnEnd.if语句规定它的真项或假项位置上只能是一个基本语句，如果需要写一组语句，就应当使用复合语句。本程序中有三处用到复合语句。每个复合语句的范围是从Begin开始到与它相对应的End为止。复合语句的地位和一个基本语句相同；其一般格式为：Begin语句系列End；习题2.11.假设邮局规定寄邮件时若每件重量在1公斤以内(含1公斤)，按每公斤1.5元计算邮费，如果超过1公斤时，其超出部分每公斤加收0.8元。请编程序计算邮件收费。2.输入三个正整数，若能用这三个数作为边长组成三角形，就计算并输出该三角形的面积，否则输出Can't。(组成三角形的条件为：任意两边之和大于第三边)3.输入一个三位数的整数，将数字位置重新排列，组成一个尽可大的三位数。例如：输入213，重新排列可得到尽可能大的三位数是321。125 第二节情况语句与算术标准函数如果有多种（两种或两种以上）选择，常用情况语句编程。将前面[例2.1]改成用如下方法来处理。根据题意，付款计算可分为两种情况：①Y=50*X(X＞100)②Y=80*X(X＜=100)显然，情况①与②的选择取决于X值。假设用N表示“情况值”，暂且先让N＝2；如果X＞100则N=1；（此题中N的值只是1或2，且取决于X值）Pascal程序:ProgramExam21_1；VarX，Y，N:integer；BeginWrite('X=')；readln(x)；n:=2；{先让n=2}ifX＞100thenn:=1；{如果X＞100则n=1}Casenof{关于情况处理}1:Y:=50*X；2:Y:=80*X；end；Writeln('Y='，Y)；ReadlnEnd.程序中的Case─end语句为情况语句，是多路分支控制，一般格式为:Case表达式of情况常量表1:语句1；情况常量表2:语句2；::情况常量表n:语句nend；执行情况语句时，先计算Case后面表达式的值，然后根据该值在情况常量表中的“对应安排”，选择其对应的语句执行，执行完所选择语句后就结束Case语句；如果常量表中没有一个与表达式值对应的语句，则什么也不做就结束本Case语句。Case语句的另一种应用格式为：Case表达式of情况常量表1:语句1；情况常量表2:语句2；::情况常量表n:语句n；else语句n+1end；这种格式的前面部分是相同的，所不同的是：如果常量表中没有一个与表达式值对应的语句，则执行与else对应的语句，然后结束Case语句。125 [例2.2]对某产品征收税金，在产值1万元以上征收税5%；在1万元以下但在5000元以上的征收税3%；在5000元以下但在1000元以上征收税2%；1000元以下的免收税。编程计算该产品的收税金额。解:设x为产值，tax为税金，用P表示情况常量各值，以题意中每1000元为情况分界:P=0:tax=0(x<1000)P=1，2，3，4:tax=x*0.02(1000<=x<5000)P=5，6，7，8，9:tax=x*0.03(500010000)这里的P是“情况”值，用产值x除以1000的整数值作为P，如果P>10也归入P=10的情况。Pascal语言用P=trunc(x/1000)取整计算，ProgramExam22；Varx，p:integer；Tax:real；BeginWrite('Number=')；readln(x)；P:=trunc(x/1000)；ifP＞9thenP:=10；CasePof0:tax:=0；1,2,3,4:tax:=x*0.2；5,6,7,8,9:tax:=x*0.3；10:tax:=x*0.5end；Writeln('tt='，tt:5:2)；ReadlnEnd.情况表达式的计算必须考虑到“全部”情况，不要有遗漏。如果情况常量表的“值”在某范围内是连续的，可将常量表写成：n1..n2：语句；因此，上面程序中的情况常量表可以写成如下程序中表示形式：ProgramExam22_1；Varx,p:integer；tax:real；BeginWrite('Number=')；readln(x)；P:=trunc(x/1000)；ifP＞9thenP:=10；CasePof0:tax:=0；1..4:tax:=x*0.2；{从1至4作为同一情况处理}5..9:tax:=x*0.3；{从5至9作为同一情况处理}10:tax:=x*0.5end；Writeln('tt='，tt:5:2)；ReadlnEnd.125 程序中的trunc(x)为取整函数，是Pascal的算术标准函数之一。Pascal常用的算术标准函数有19个:(1)abs(x)求x的绝对值(|x|)；(2)exp(x)求ex的值；（e为无理数2.71828…）(3)frac(x)求x的小数部分；(4)int(x)求x的整数部分(不舍入，函数值为实型)；(5)ln(x)求以e为底的x的对数（logex)；(6)odd(x)判断x的奇偶数(当x为奇数时odd(x)值为true，否则为false)；(7)ord(x)求x的序号，结果为整型(x为有序类型量)；(8)piπ值(3.1415926535897932…)；(9)pred(x)求x(有序类型)的前趋值；(10)succ(x)求x(有序类型)的后继值；(11)random随机函数，产生0～1的随机值；(12)random(n)产生0～n的随机数(n为word类型，先执行randomize，才能得到随机整数)；(13)round(x)求x的四舍五入整数；(14)trunc(x)求x的整数部分(截掉小数部分，结果为整型)；(15)sqr(x)求x的平方值(x2)；(16)sqrt(x)求x的开平方根值()；(17)sin(x)求x的正弦函数(x为弧度)；(18)cox(x)求x的余弦函数(x为弧度)；(19)arctan(x)正切的反三角函数(x为数值)；习题2.21.运输公司计算运费时，距离(S)越长，每公里运费越低，标准如下:如果S＜250公里；运费为标准运价的100%如果250公里＜＝S＜500公里，运费为标准运价的98%；如果500公里＜＝S＜1000公里，运费为标准运价的95%；如果1000公里＜＝S＜2000公里，运费为标准运价的92%；如果2000公里＜＝S＜3000公里，运费为标准运价的90%；如果S＝＞3000公里，运费为标准运价的85%；。请编计算运费的程序。2.输入考试成绩，如果获85分以上为A等，获60分～84分为B等，60分以下为C等，编程输出考试等级。3.某车间按工人加工零件的数量发放奖金，奖金分为五个等级：每月加工零件数N<100者奖金为10元；100<=N<110者奖金为30元；110<=N<120者奖金为50元；120<=N<130者奖金为70元；N>130者为80元。请编程，由键盘输入加工零件数量，显示应发奖金数。125 第三章　循环程序在编程中经常遇到需要多次规律相同的重复处理，这就是循环问题。TurboPascal采用不同的循环方式来实现，常用的环循有三种:for、repeat、while.第一节　for循环for循环是一种自动计数型循环。[例3.1]试打印出1~20的自然数。解：①用a代表1~20各数，同时也用a兼作计数，以控制循环次数；②让a从1开始；③输出a；④a自动计数（加1），如果未超越所规定的循环范围则重复步骤③，否则结束循环。Pascal程序:ProgramExam12；Vara:byte；Beginfora:=1to20doWriteln(a)；ReadlnEnd.程序中fora:=1to20doWriteln(a)；是for循环语句。for循环语句有两种格式:(1)for　循环变量:=初值To终值do语句；(2)for　循环变量:=初值　downto终值do语句；第(1)种格式的初值小于等于终值，循环变量值按自动加1递增变化；第(2)种格式的初值大于或等于终值，循环变量值按自动减1递减变化。for循环是(以递增1或以递减1)计数型循环。比如:若将[例3.1]程序改为倒计数(递减)循环，则输出20～1的自然数数:ProgramExam31；Vara:byte；Beginfora:=20downto1doWriteln(a)；ReadlnEnd.[例3.2]打印出30至60的偶数。]解：方法一：125 ①设a表示30至60的所有的数，可用for循环列出；②用式子　amod2=0　筛选出其中的偶数并输出。Pascal程序：Programex32;Vara:integer;BeginFora:=30to60doIf(amod2=0)thenwriteln(a);Readln;End.在这个程序中，for循环后的循环语句是一个条件分支语句。方法二：我们知道，在式子a=2*n中，若n取自然数1、2、3、…，时，则a依次得到偶数2、4、6、…。因此要想得到30至60的偶数，就可以让上面式子中的n取15至30的自然数就可以了。所以本题还可以按以下步骤处理：①设n表示15至30的所有自然数，可用for循环列出；②用式子　a:=2*n　求出其中的偶数；③将结果输出至屏幕。Pascal程序：Programex32;BeginForn:=15to30doBegina:=2*n;Writeln(a);End;Readln;End.[例3.3]自然数求和：编一个程序，求从1至100的自然数的和。解：①令S＝0；②令a表示1至100的自然数，用循环列出；③将这些自然数用公式S:=S+a逐一累加到S中去；④循环结束后，S即为1至100的自然数的和，输出即可。Pascal程序：Programex33;vars,a:integer;BeginS:=0;Fora:=1to100doS:=S+a;Writeln(‘S=’,S);125 Readln;End.[例3.4]一个两位数x，将它的个位数字与十位数字对调后得到一个新数y，此时y恰好比x大36，请编程求出所有这样的两位数。解：①用for循环列举出所有的两位数，x为循环变量；②用公式a:=xdiv10分离出x的十位数字；③用公式b:=xmod10分离出x的个位数字；④用公式y:=b*10+a合成新数y；⑤用式子y-x=36筛选出符合条件的数x并输出。Pascal程序：Programex34;BeginForx:=10to99doBegina:=xdiv10;b:=xmod10;y:=b*10+a;ify-x=36thenwriteln(x);End;Readln;End.[例3.5]把整数3025从中剪开分为30和25两个数，此时再将这两数之和平方，(30+25)2=3025计算结果又等于原数。求所有符合这样条件的四位数。解:设符合条件的四位数为N，它应当是一个完全平方数，用(a*a)表示。①为了确保N=(a*a)在四位数（1000～9999）范围内，可确定a在32～99循环；②计算N=a*a；将四位数N拆分为两个数n1和n2；③若满足条件(n1+n2)*(n1+n2)＝N就输出N。Pascal程序:ProgramExam35；VarN，a，x，n1，n2:Integer；Beginfora:=32to99dobeginN:=a*a；n1:=Ndiv100；｛拆取四位数的前两位数｝n2:=N-n1*100；｛拆取四位数的后两位数｝X:=n1+n2；ifx*x=Nthenwriteln(N)；end；Readln125 End.[例3.6]用“*”号打印出如下的长方形图案。　　************************************解：①上面给出的图例共有4行，我们可以用一个循环控制行的变化；②在每行中又有9列，我们可以在前面控制行的循环中再套一个循环来控制列的变化。Pascal程序：Programex36;BeginFora:=1to4do{外循环控制行的变化}BeginForb:=1to9do{内循环控制列的变化}write(‘*’);Writeln;{输出一行的“*”后换行}End;Readln;End.程序中的循环对于a的每个值都包含着一个b=(1～9)次的内循环。外循环fora将内循环forb包含在里面，称为for循环的嵌套。嵌套形式如:fora:=n1ton2doforb:=m1tom2do循环体语句；[例3.7]打印出九九乘法表:解:设a为被乘数，范围为1～9；b为乘数，范围为1～a；乘式为a*b=(a,b的乘积)，则a=1:b=1～a1*1=1a=2:b=1～a2*1=22*2=4a=3:b=1～a3*1=33*2=63*3=9a=4:b=1～a4*1=44*2=84*3=134*4=16：：a=9b=1～a9*1=99*2=18…9*9=81⑴从上面分解的横行中看到共有9行，这里的“行”数变化与a的变化从1～9相同，可用a控制“行”的循环；⑵每“行”里面相乘的次数与b的范围相关，由b控制每“行”里面的“内部”循环；⑶内循环被包含在最里层，执行完每“行”的内部循环，就到下一“行”去执行新“行”里面的循环，每“行”都拥有形式相同的（b=1～a）内循环。即每到一“行”都要执行该“行”的内循环。这里所指的“行”可以理解成抽象的行，不一定是实际上具体对应的行，可以是一个处理“块”。Pascal程序:125 ProgramExam37；Vara，b:byte；Beginfora:=1to9do{外循环}beginforb:=1toado{内循环}write(a，’*’，b，’=’，a*b，’’:3)；writelnend；ReadlnEnd.根据这种格式还可以实现多层循环嵌套,例如：fora:=n1ton2doforb:=m1tom2doforc:=k1tok2do循环体语句；[例3.8]从七张扑克牌中任取三张，有几种组合方法？请编程输出所有组合形式。解：设每次取出三张分别为a,b,c。用三重循环分别从1～7的范围里取值；为了排除取到重号，用(a-b)*(b-c)*(a-c)<>0进行判断。Pascal程序：programExam38;constn=7;vara,b,c,t:integer;Begint:=0;fora:=1tondoforb:=1tondoforc:=1tondoif(a-b)*(b-c)*(a-c)<>0thenBegininc(t);writeln(a:3,b:3,c:3)End;writeln(total:,t:5);readlnEnd.[例3.9]数学上把除了1和它本身，没有别的数能够整除它的自然数叫做素数(或质数)。现在由键盘输入一个自然数N，编程判断N是否是素数，是则输出“Yes”，否则输出“No”。解：根据定义，对于给定的自然数N，只需判断除1和它本身外，还有没有第三个自然数即可。125 ①令K从1循环至N；②根据NmodK是否为0可统计K的约数的个数；③若N的约数的个数超过2个，则判定N不是素数。Pascal程序:ProgramExam39；Varn，m，k，t:integer；Beginwrite(‘N=’);ReadLn(N);t:=0；fork:=1toNdo{外循环}ifNmodk=0thent:=t+1;{如果N是奇数}ift>2thenwriteln(‘No’)elsewriteln(‘Yes’);Readln;End.程序中的变量yse为布尔(或逻辑)类型(Boolean)。布尔值只有两个：True(真)False(假)布尔值与条件判断结果为真(条件成立)或为假(条件不成立)的作用相同，常用于条件语句和循环语句中。上面程序中用ifyesand(tmod7=0)thenwriteln；实现每行打印七个素数换行，程序中布尔变量yes为真，在逻辑上表示是素数；关系式（tmod7=0)的值为真时，表示该行输出素数巳是７个；用and将这两个“条件”连起来是作一种布尔(逻辑)运算。Pascal共有四种逻辑运算符：①and(与)两条件都为True时，其结果值为True；否则为False；②or(或)两条件中只要有一个为True；其结果值为True；否则为False；③xor(异或)两条件的逻辑值不相同时，其结果值为True；否则为False；④not(非)条件为True时，其结果值为False；否则为True；(取反)习题3.1:1.打印出1至20的平方数表。2.打印出100至200之间的奇数。3.鸡兔同笼(用for循环程序完成)4.一辆快车和一辆慢车开往同一地点，快车票价为18元，慢车票价为13.5元，共售出400张，共计5940元，求快车票和慢车票各多少张?.5.求出能被5整除的所有四位数的和。6.在下面式子中的二个□内填入一个合适的同样的数字，使等式成立。□3*6528=3□*82567.有一个三位数，它的各位数字之和的11倍恰好等于它自身，请编程求出这个三位数。125 8.在自然数中，如果一个三位数等于自身各位数字之立方和，则这个三位数就称为是水仙花数。如:153=13+53+33，所以153是一个水仙花数。求所有的水仙花数。9.编程序打印出下列图案：平行四边形等腰三解形　　　　　　菱形　　*******　　*************************************************************10.编程打印出如下图案：122233333444444455555555511.有三种明信片:第一种每套一张，售价2元；第二种每套一张，售价4元；第三种每套9张，售价2元。现用100元钱要买100张明信片，要求每种明信片至少要买一套，问三种明信片应各买几套？请输出全部购买方案。12.某人想把一元钱换成伍分、贰分、壹分这样的零钱，在这三种零钱中每种零钱都至少各有一个的情况下，共有多少种兑换方案。并打出这些方案。13.14.输出100以内的全部素数，要求每行显示5个。15.A、B两个自然数的和、差、积、商四个数加起来等于243，求A、B两数。16.百钱买百鸡：今有钱100元，要买100只鸡，公鸡3元一只，母鸡1元一只，小鸡1元3只，若公鸡、母鸡和小鸡都至少要买1只，请编程求出恰好用完100元钱的所有的买鸡方案。第二节　repeat循环Repeat循环是直到型循环。试将上一节的例3.1(打印出1～20的平方数表)程序改为repeat循环:ProgramExam31_1；Vara:byte；Begina:=1；writeln('a':8,'a*a':8)；repeatwriteln(a:8，a*a:8)；inc(a)；{改变a的值}Untila＞20；ReadlnEmd.125 程序中的Repeat循环格式为:repeat循环体语句；until条件表达式；｛直到条件为真｝Repeat循环首先执行由Repeat和Until括起来的循环体语句，然后检查Until后面的条件表达式：如果表达式结果为假，则继续执行循环体，接着继续检查Until后面的条件表达式，如此反复执行直到这个表达式结果为真时结束循环。Repeat循环体语句必须有能改变Until后面条件表达式值的语句，并最终使这个条件表达式的值为真，使循环自动结束。程序中inc(a)指令相当于a:=a+1，常用的同类指令格式如下:(1)inc(x)等同x:=x+1；(2)inc(x,n)等同x:=x+n；(3)dec(x)等同x:=x—1；(4)dec(x，n)等同x:=x—n；[例3.10]求两个自然数M和N的最大公约数。解：若自然数a既是M和约数，又是N的约数，则称a为M和N的公约数，其中最大的称为最大公约数。为了求得最大公约数，可以从最大可能的数（如M或N）向下寻找，找到的第一个公约数即是最大公约数。Pascal程序：Programex310;Begina:=N+1;Repeata:=a-1;Until(Mmoda=0)and(Nmoda=0);writeln(a);Readln;End.[例3.11]校体操队到操场集合,排成每行2人,最后多出1人;排成每行3人,也多出1人;分别按每行排4,5,6人,都多出1人;当排成每行7人时,正好不多。求校体操队至少是多少人?解:①设校体操队为X人,根据题意X应是7的倍数,因此X的初值为7,以后用inc(x,7)改变X值；②为了控制循环,用逻辑变量yes为真(True)使循环结束；③如果诸条件中有一个不满足,yes的值就会为假(false)，就继续循环。Pascal程序:programExam311;varx:word;yes:boolean;beginx:=0;125 repeatyes:=true;inc(x,7);ifxmod2<>1thenyes:=false;ifxmod3<>1thenyes:=false;ifxmod4<>1thenyes:=false;ifxmod5<>1thenyes:=false;ifxmod6<>1thenyes:=false;untilyes;{直到yes的值为真}writeln('All=',x);readlnend.程序中对每个X值，都先给Yes赋真值，只有在循环体各句对X进行判断时，都得到“通过”（此处不赋假值）才能保持真值。[例3.12]从键盘输入一个整数X（X不超过10000），若X的各位数字之和为7的倍数，则打印“Yes”，否则中打印“No”。解：本题考察的是数字分离的方法，由于X的位数不定，所以以往的解法不能奏效，这是介绍一种取余求商法。（1）用Xmod10分离出X的个位数字；（2）用Xdiv10将刚分离的个数数字删除，并将结果送回给X；（3）重复（1）（2）直到X＝0。Pascal程序：Programex12;varx,a,s:integer;begins:=0;repeata:=xmod10;x:=xdiv10;s:=s+a;untilx=0;ifsmod7=0thenwriteln(‘Yes’)elsewriteln(‘No’);Readln;end;[例3.13]求1992个1992的乘积的末两位数是多少？解：积的个位与十位数只与被乘数与乘数的个位与十位数字有关，所以本题相当于求1992个92相乘，而且本次的乘积主下一次相乘的被乘数，因此也只需取末两位参与运算就可以了。Pascal程序：Programex313;125 vara,t:integer;Begina:=1;t:=0;repeatt:=t+1;a:=(a*92)mod100;untilt=1992;writeln(a);Readln;End.[例3.14]尼科彻斯定理：将任何一个正整数的立方写成一组相邻奇数之和。如:33=7+9+11=2743=13+15+17+19=64解:从举例中发现:(1)n3正好等于n个奇数之和；(2)n个奇数中的最小奇数是从1开始的奇数序列中的第m个奇数，与n的关系为：m=n(n—1)/2+1。(3)奇数序列中第m个奇数的值为x，且x=2m—1，比如:n=3时，m=3(3-1)/2+1=4，即3个奇数中最小的奇数是奇数序列中的第4个，它的值为x=(2m-1)=7，所以：33=7+9+11。(4)从最小的奇数值x开始，逐个递增2，连续n个,用t从1开始计数，直到t=n为止。Pascal程序:ProgramExam35；Varn，m，x，t，s:integer；Beginwrite(’inputn:’)；readln(n)；{输入N}m:=(n*(n-1)div2)+1；{找到第m个奇数}x:=2*m-1；t:=1；{算出第m个奇数的值x，是所求的第一个}write(n’*’，n，’*’，n，’=’，x)；{输出第一个}s:=x;{用S计算和}ifn＞1thenRepeatinc(x,2)；{计算下一个奇数}write(’+’，x)；{加上下一个奇数}inc(t)；inc(s，x)；{计个数并累加和}Untilt=n；{直到n个}Writeln(’=’，s)；ReadlnEnd.[例3.15]猜价格：中央电视台的“幸运52”栏目深受观众喜爱，其中的“猜商品价格”125 的节目更是脍炙人口，现在请你编一个程序模拟这一游戏：由计算机随机产生200至5000之间的一个整数，作为某件商品的价格，然后由你去猜是多少，若你猜的数大了，则计算机输出提示“Gao”，若你猜的数小了，则计算机输出提示“Di”，然后你根据提示继续猜，直到你猜对了，计算机会提示“Ok”，并统计你猜的总次数。解：本题的游戏规则大家都清楚，要完成程序，必须把处理步骤理清：　　（1）用随机函数Random产生200至5000之间的一个整数X；（2）你猜一个数A；（3）若A＞X，则输出“Gao”；（4）若A＜X，则输出“Di”；(5)若A＝X则输出“Ok”；(6)重复(2)(3)(4)(5)直到A=X。Pascal程序：Programex315;Vart,X,a:integer;BeginRandomize;X:=Random(4800)+200;t:=0;Repeatt:=t+1;write(‘[‘,t,’]Qingcaiyigezhengshu:‘);readln(a);ifa>xthenwriteln(‘Gao’);ifaF就做(J=J+1,T=H-J)；④当4*T+2*J=F时,说明所推算的J和T是正确的，应结束循环，并输出T,J。Pascal程序:ProgramExam38;ConstH=30;F=90;VarJ,T:integer;BeginJ:=0;T:=H－J;{初始时让J从0开始计算}While4*T+2*J＜＞Fdo{当条件为真就做do后面的循环体}begininc(J);　　{递推改变J值}T:=H－J　　{计算兔的只数}end;Writeln('T=',T,'':6,'J=',J);ReadlnEnd.程序中采用While当型循环，While循环语句的格式为:While条件式do语句;其中do后面的“语句”是被重复执行的,称为循环体;若循环体是多个语句,必须用begin--end包起来成为复合语句。While循环首先判断条件式，当条件式的值为真就执行do后面的语句（循环体）。While的循环体内也必须包含能改变控制变量取值语句,影响条件式的值,最终使条件式为false(假),才能结束循环。[例3.9]输入任一的自然数A,B,求A,B的最小公倍数。解:这里采用适合计算机查找的方法:设D是它们的最小公倍数。先找出A,125 B当中的较大者并存放在A中,将较小者存放在B中,让D=A,当D能够整除B时,则D是所求的最小公倍数;当D不能整除B，就逐次地让D增加A。例如：A=18,B=12,步骤如下：①让D=A(D=18)②当(DmodB)＜＞0为真时(D不能整除B)就做D=D+A,重复②;③当(DmodB)＜＞0为假时结束循环，并输出D。Pascal程序:programExam39;vara,b,d,t:word;beginwrite('inputa,b:');readln(a,b);ifa0do{当条件为真时就做do后面的语句}inc(d,a);writeln('[',a,',',b,']=',d);readlnEnd.Pascal语言的三种基本循环方式,for循环对循环范围有明确规定,且循环变量只能是递增加1或递减1自动计数控制;而repeat--until循环和while--do循环比较灵活,只要对条件表达式的值能控制满足一定要求就能组成循环,但在循环体中必须有改变循环变量值的语句,使条件判断（逻辑值）最终为True或flase,让循环能够终止。[例3.10]求自然数A,B的最大公约数。解:采用如下方法步骤:(1)求A除以B的余数；(2)当余数＜＞0就做n=a;a=b;b=nmodb,重复(1)和(2);(3)当余数=0就结束循环，并输出b值。比如a=18,b=12时，处理步骤为：(1)=，得余数为6；(2)此余数不为零，让a=12,b=6；(3)重复=,得余数为0；(4)结束循环，输出6（余数为零时的b值即是所求的最大公约数）。此方法称为辗转相除法求最大公约数。Pascal程序:programExam310;vara,b,n:word;beginwrite('inputa,b:');readln(a,b);write('(',a,',',b,')=');125 whileamodb<>0dobeginn:=a;a:=b;b:=nmodb;end;writeln(b);readlnEnd.[例3.11]将一根长为369cm的钢管截成长为69cm和39cm两种规格的短料。在这两种规格的短料至少各截一根的前提下,如何截才能余料最少。解:设两种规格的短料分别为:规格为69cm的x根，可在1至(369-39)/69范围循环取值;规格为39cm的y根，用y=(369-69*X)/39)计算;余料R=369-69*X-39*Y。①设最小余料的初始值min=369；②在X循环范围内,每一个X值都计算出对应的Y和R；③如果R＜min,就将R存入min,x存入n,y存入m，记录余料最小时的x和y；④重复步骤②,当x值超出(（369—39）/69)时结束循环。Pascal程序:programexam311;varx,y,r,min,n,m,a:integer;beginmin:=369;a:=(369-39)div69;x:=1;whilex<=adobeginy:=(369-69*x)div39;r:=369-69*x-39*y;ifr0thenbegins:=50*a+35*b+25*c;ifs=225thenwriteln(n:3,a:3,b:3,c:3,s:5);end;inc(b);end;inc(a);end;dec(n);end;readlnend.程序运行结果获得两组填数答案。如果改用for循环，程序将更加简明:ProgramExam312_1;Vara,b,c,n,s:Integer;BeginWriteln('N':3,'A':3,'B':3,'C':3,'S':5);forn:=8downto6do{125 N取值8，7，6，并分别代表甲、乙、丙}fora:=0to4do{中50环的可能范围}forb:=0to6do{中30环的可能范围}beginc:=n-a-b;{计算中25环的子弹数}ifc＞0thenbegin{如果不是负数}s:=50*a+35*6+25*c;{计算总成绩}ifs=225thenwriteln(n:3,a:3,b:3,c:3,s:5);endend;readlnEnd.习题3.31.求S=1-1/2+1/3-1/4+1/5-1/6+……（求前N项的和)2.Faibonacci数列前几项为:0,1,1,2,3,5,8,…,其规律是从第三项起,每项均等于前两项之和。求前30项,并以每行5个数的格式输出。3.小球从100高处自由落下,着地后又弹回高度的一半再落下。求第20次着地时,小球共通过多少路程?4.某登山队员第一天登上山峰高度的一半又24米;第二天登上余下高度的一半又24米；每天均如此。到第七天,距山顶还剩91米。求此山峰的高度?5.给出某整数N,将N写成因数相乘的形式。如:N=12,输出:12=1*2*2*3.6.出售金鱼者决定将缸里的金鱼全部卖出。第一次卖出全部金鱼的一半加二分之一条;第二次卖出剩余的三分之一加三分之一条金鱼;第三次卖出余下金鱼的四分之一加四分之一条;第四次卖出余下的五分之一加五分之一条金鱼。还剩下11条金鱼。当然,出售金鱼时都是整数条,不能有任何破损。求缸里原有的金鱼数?7.外出旅游的几位朋友决定次日早晨共分一筐苹果。天刚亮,第一个人醒来,他先拿了一个,再把筐里的八分之一拿走;第二个人醒来,先拿两个,再把筐里的八分之一拿走;第三个人醒来,先拿三个,再拿走筐里的八分之一;…每个人依次照此方法拿出各人的苹果,最后筐里的苹果全部拿完,他们每人所拿到的苹果数正巧一样多。求原先筐里的苹果数和人数。8.图中由6个圆圈构成三角形,每条边上有三个圈,将自然数1--6不重复地填入各圆圈位置上,使每条边圆圈上的数字之和相等,请编程输出所有的填法。9．请编程显示出下面数字金字塔图形：125 第四章　函数与过程程序中往往需要把主要任务分成若干个子任务，每个子任务只负责一个专门的基本工作。每个子任务就是一个独立的子程序。TurboPascal可以把函数和过程作为子程序调用。第一节　函数Pascal允许用户在程序中自己说明定义所需要的函数并在程序中调用这些函数。[例4.1]编程找出由键盘任意输入五个整数中的最大整数。解:设输入的五个整数为n1、n2、n3、n4、n5，为了便于处理，引入一个中间变量t1，按如下步骤处理：①令t1=n1;②将t1与n2比较，将两者中较大的数放入t1；③将t1与n3比较，将两者中较大的数放入t1；④将t1与n4比较，将两者中较大的数放入t1；⑤将t1与n5比较，将两者中较大的数放入t1；⑥经过以上5步处理后，t1即为5个数中最大者。从上面规划的步骤看来，从步骤②到步骤⑤需处理的目标是相同的，因此我们可以设计一段子程序Max(x1,x2)，以找出x1和x2中最大的值并返回。Pascal程序:ProgramExam41_a;Varn1,n2,n3,n4,n5,t1:integer;Functionmax(x1,x2:integer):integer;BeginIfx1>x2thenMax:=x1ElseMax:=x2;End;BeginWrite(‘Input5numbers:‘);Readln(n1,n2,n3,n4,n5);T1:=n1;T1:=Max(t1,n2);T1:=Max(t1,n3);T1:=Max(t1,n4);T1:=Max(t1,n5);Writeln(‘Maxnumber:‘,t1);End.125 从上例看出，引入函数实际上是将一个复杂的问题划分成若干个易于处理的子问题，将编程化简的一种有效办法，而化简的方法是多种多样的，如前面已经做过求三个数中的最大数，所以可定义一个专门求三个数中最大数的函数(Max)。第一次用这个函数求出n1,n2,n3三个数中的最大数t1;第二次调用这个函数求出t1与n4,n5三个数中的最大数，也就是前三个数的最大数(已在t1中)和后面二个数再求一次，就得到五个数的最大数。因此，需要两次使用“求三个数中的最大数”，步骤如下：①调用函数Max(n1,n2,n3)，求出n1，n2，n3中的最大者t1；②调用函数Max(t1,n4,n5)，求出t1,n4,n5中的最大者t2；③输出最大数t2。ProgramExam41_b;Varn1,n2,n3,n4,n5,t1:integer;functionMax(x1,x2,x3:integer):integer;｛自定义函数Max｝VarXX:integer;｛函数内部变量说明｝begin｛函数体｝ifX1＞X2thenXX:＝X1elseXX:＝X2;ifX3＞XXthenXX:＝X3;Max:＝XXend;Begin｛主程序｝Write('Input5numb:');Readln(n1,n2,n3,n4,n5);｛输入五个数｝t1:＝Max(n1,n2,n3);｛用函数求n1,n2,n3的最大数｝t1:＝Max(n4,n5,t1);｛用函数求n4,n5,t1的最大数｝Writeln('MaxNumber:',t1);ReadlnEnd.主程序中两次调用自定义函数。自定义函数的一般格式为:function函数名(形式参数表):类型;｛函数首部｝局部变量说明部分;begin语句系列;{函数体}end;函数中的形式参数接受调用函数时所传入的值，用来参与函数中的运算。[例4.2]求任意输入的五个自然数的最大公约数。解:⑴自定义一个专门求两自然数的最大公约数的函数GCD;⑵调用自定义函数,第一次求前两个数的最大公约数;从第二次开始,用每次求得的最大公约数与下一个数再求两个数最大公约数,直到最后。本题共四次“求两个数的最大公约数”，设输入的五个自然数分别是a1,a2,a3,a4,a5,采用如下步骤：①求a1,a2两个数的最大公约数→存入a1；125 ②求a1,a3两个数的最大公约数→存入a1；③求a1,a4两个数的最大公约数→存入a1；④求a1,a5两个数的最大公约数→存入a1；⑤输出a1，此时的a1已是五个数的最大公约数。Pascal程序:ProgramExam42;Vara1,a2,a3,a4,a5:integer;functionGCD(x,y:integer):integer;{自定义函数}Varn:integer;beginWhilexmody＜＞0dobeginn:=x;x:=y;y:=nmodyend;GCD:=yend;Begin{主程序}Write('input5Numper:');readln(a1,a2,a3,a4,a5);｛输入五个数｝Write('(',a1,',',a2,',',a3,',',a4,',',a5,')=');a1:＝GCD(a1,a2);｛调用函数GCD｝a1:＝GCD(a1,a3);a1:＝GCD(a1,a4);a1:＝GCD(a1,a5);Writeln(a1);readlnEnd.函数的结果是一个具体的值,在函数体中必须将所得到的运算结果赋给函数名；主程序通过调用函数得到函数的运算结果。调用函数的一般格式为:函数名(实在参数表)调用函数时,函数名后面圆括号内的参数必须有确定的值,称为实在参数。调用时即把这些实际值传送给函数形参表中的相应形参变量。函数不是单独的语句,只能作为运算赋值或出现在表达式中。习题4.11.数学上把从1开始的连续自然数相乘叫做阶乘。例如把1*2*3*4*5称作5的阶乘，记为5！。编写一个求n!的函数,调用此函数求:D＝2.求从键盘输入的五个自然数的最小公倍数。3.哥德巴赫猜想的命题之一是:大于6的偶数等于两个素数之和。编程将6～100所有偶数表示成两个素数之和。4.如果一个自然数是素数,且它的数字位置经过对换后仍为素数,则称为绝对素数,125 例如13。试求出所有二位绝对素数。第二节　自定义过程自定义函数通常被设计成求一个函数值，一个函数只能得到一个运算结果。若要设计成能得到若干个运算结果,或完成一系列处理,就需要自定义“过程”来实现。[例4.3]把前面［例2.2］(输入三个不同的整数,按由小到大排序)改为下面用自定义过程编写的Pascal程序:Programexam43;Vara,b,c:integer;ProcedureSwap(varx,y:integer);{自定义交换两个变量值的过程}Vart:integer;Begin｛过程体｝t:=x;x:=y;y:=t{交换两个变量的值end;Begin{主程序}Write('inputa,b,c=');Readln(a,b,c);ifa＞bthenswap(a,b);｛调用自定义过程｝ifa＞cthenswap(a,c);ifb＞cfhenswap(b,c);Writeln(a:6,b:6,c:6);Readln;End.程序中ProcedureSwap是定义过程名，从作用来看，过程与函数是相似的，都能将复杂的问题划分成一些目标明确的小问题来求解，只不过函数有值返回而过程则没有。自定义过程的一般格式如下:Procedure过程名(形式参数表);｛过程首部｝局部变量说明部分；begin语句部分;｛过程体部分｝end;[例4.4]如果一个自然数除了1和本身,还有别的数能够整除它,这样的自然数就是合数。例如15,除了1和15,还有3和5能够整除,所以15是合数。14,15,16是三个连续的合数,试求连续十个最小的合数。解：从14,15,16三个连续合数中可看出,它们正好是两个相邻素数13和17之间的连续自然数,所以求连续合数问题可以转化为求有一定跨度的相邻两个素数的问题。因此，求连续十个最小的合数可用如下方法：125 ①从最小的素数开始，先确定第一个素数A;②再确定与A相邻的后面那个素数B;(作为第二个素数)；③检查A,B的跨度是度否在10以上,如果跨度小于10,就把B作为新的第一个素数A,重复作步骤②;④如果A、B跨度大于或等于10，就打印A、B之间的连续10个自然数，即输出A+1,A+2,A+3…,A+10。Pascal程序:Programexam44;vara,b,s,n:integer;yes:boolean;proceduresub(x:integer;varyy:boolean);{过程：求x是否为素数}vark,m:integer;{用yy逻辑值转出}begink:=trunc(sqrt(x));form:=3tokdoifodd(m)thenifxmodm=0thenyy:=false;end;begin{主程序}b:=3;repeata:=b;{a为第一个素数}repeatyes:=true;inc(b,2);{b是a后面待求的素数}sub(b,yes);{调用SUB过程来确认b是否为素数}ifyesthens:=b-a;{如果b是素数，则求出跨度s}untilyes;untils>=10;forn:=a+1toa+10dowrite(n:6);writeln;readlnend.程序中的过程SUB,用来确定b是否为素数。过程名后面圆括号内的变量是形式参数，简称为形参。过程SUB(x:integer;Varyy:boolean)中的x是值形参,而前面冠有Var的yy是变量形参。值形参只能从外界向过程传入信息,但不能传出信息;变量形参既能传入又能传出信息。本程序过程SUB中的x是由调用过程的实在参数b传入值，进行处理后，不需传出；而yy是把过程处理结果用逻辑值传出，供调用程序使用。试把［例4.3］程序中的过程SWAP(Valx,y:integer)，将x,125 y前面的Var去掉，就变成了纯粹的值形参，就不能将过程所处理的结果传出去，也就无法得到处理后的结果，通过运行程序比较，可以非常明显地看到值形参和变量形参的区别。调用过程的格式为：过程名（实在参数表）；调用过程名后面圆括号内的实在参数与定义过程的形参表必须相对应，调用过程相当于一个独立语句，可单独使用。［例4.5］将合数483的各位数字相加（4+8+3）=15，如果将483分解成质因数相乘：483=3*7*23，把这些质因数各位数字相加（3+7+2+3），其和也为15。即某合数的各位数字之和等于它所有质因数的各数字之和。求500以内具有上述特点的所有合数。解：①设n为所要求的合数，让n在1～500间循环做以下步骤；②用t1，t2分别累计合数n及n的质因数的各位数字之和，初值均为0；③调用过程SUB3进行非素数判定，以布尔变量yes的真假值判定是否，yes的初值为true，如果为(nottrue)非素数，就做步骤④，⑤，⑥；否则取新的n值，重复步骤③；④调用SUB1，求n的各数字之和，传送给t1；⑤调用SUB2，求n的各质因数，对于每个质因素都通过SUB1求它各位数字之和，将所有各质因数字传送给t2。⑥如果t1=t2（各位数字之和等于它所有质因数的各数字之和），则输出此n。PASCAL程序：programexam45;varn,t1,t2,tatol:integer;yes:boolean;proceduresub1(x:integer;vart:integer);{过程:分离x的各位数字}begin{并求各位数字之和}repeatt:=t+xmod10;x:=xdiv10;untilx=0end;proceduresub2(x:integer;vart:integer);{过程：分解质因数}varxx,tt:integer;beginxx:=2;whilex>1doifxmodxx=0thenbegintt:=0;sub1(xx,tt);t:=t+tt;x:=xdivxxendelseinc(xx)end;125 proceduresub3(x:integer;varyy:boolean);{过程：判断x是否为素数}vark,m:integer;begink:=trunc(sqrt(x));form:=2tokdoifxmodm=0thenyy:=false;end;begin{主程序}forn:=1to500dobegint1:=0;t2:=0;yes:=true;sub3(n,yes);{调用过程求素数}ifnotyesthen{如果非素数就…}beginsub1(n,t1);{调用过程求n的各位数字之和}sub2(n,t2);{调用过程求n的各质因数的数字之和}ift1=t2thenwrite(n:6);{打印合格的合数}endend;readlnend.程序定义了三个过程SUB1，SUB2，SUB3，其中SUB2过程中又调用了SUB1。在过程中定义的变量或参数，只在本过程内部使用有效。这些变量称为局部变量。如SUB2中的xx只在SUB2中使用，属于局部变量。习题：4.21.输入自然数n，求前n个合数（非素数），其素因子仅有2，3，或5。2.自然数a的因子是指能整除a的所有自然数，但不含a本身。例如12的因子为：1,2,3,4,6。若自然数a的因子之和为b，而且b的因子之和又等于a，则称a,b为一对“亲和数”。求最小的一对亲和数。3.求前n个自然数的平方和，要求不用乘法。例如：3的平方不用3*3，可用3+3+3。4.试用容积分别为17升、13升的两个空油桶为工具，从大油罐中倒出15升油来，编程显示出具体的倒油过程。5.如果一个数从左边读和从右边读都是同一个数，就称为回文数。例如6886就是一个回文数，求出所有的既是回文数又是素数的三位数。6.任何大于2的自然数都可以写成不超过四个平方数之和。如：8=22＋22；14=12＋22＋32由键盘输入自然数N（2Trunc(sqrt(N))为止；⑸打印输出a数组中留下来、未被筛掉的各元素值，并按每行五个数显示。用筛法求素数的过程示意如下（图中用下划线作删去标志）：①23456789101112131415…9899100｛置数｝②23456789101112131415…9899100{筛去被2整除的数}③23456789101112131415…9899100{筛去被3整除的数}……23456789101112131415…9899100{筛去被整除的数}Pascal程序：ProgramExam53;constN=100;125 typexx=1..N;　　　{自定义子界类型xx（类型名）}Vara:array[xx]ofboolean;i,j:integer;BeginFillchar(a,sizeof(a),true);a[1]:=False;fori:=2toTrunc(sqrt(N))doifa[I]thenforj:=2toNdivIdoa[I*j]:=False;t:=0;fori:=2toNdoifa[i]thenBeginwrite(a[i]:5);inc(t);iftmod5=0thenwritelnend;readlnEnd.程序中自定义的子界类型，在用法上与标准类型（如integer）相同，只是值域上界、下界在说明中作了规定，而标准类型的值域由系统内部规定，其上界、下界定义是隐含的，可直接使用。例如：Typeinteger=-32768...32768；Pascal系统已作了标准类型处理，不必再作定义。[例5.4]在一次宴会上，有来自八个不同国家的宾客被安排在同一张圆桌就坐。A是中国人，会讲英语；B是意大利人，他能讲西班牙语；C是英国人，会讲法语；D是日本人，能讲汉语；E是法国人，会讲德语；F是俄国人，懂意大利语；G是西班牙人，能讲日语；最后一个是德国人，懂俄语。编程序安排他们的座位，使他们在各自的座位上能方便地跟两旁的客人交谈。解：①根据题目提供条件与数据，建立如下关系代码表：国家名中国意大利英国日本法国俄国西班牙德国宾客代码ABCDEFGH语言代号12345678懂外语代号37518246总代码A13B27C35D41E58F62G74H86表中总代码实际上是前三项代码的归纳：第一个字母表示哪国人；第二个数字表示本国语代号；第三个数字表示懂哪国外语。如A13，A表示中国人，1表示汉语（本国语），3表示会说英语。所以每个宾客的情况均用总代码（三个数据组成的字符串）表示；②定义由8个元素组成的数组（NAME），元素类型为字符串类型（String);125 ③元素的下标号影响各人座位关系，必须满足后一个元素的下标号应与前一个元素字符串中的第三个数据相同。例如：若第一个位置总代码为A13，则第二个位置应根据A13中最后的3，安排C35。即A与C可以交谈。以此类推。用字符串处理函数COPY，截取字符串的第一个字母作为宾客代码打印，再取第三个字符，用VAL将其转换成数字，将这个数字作为下标号，把这个下标号的元素安排在旁边（相邻）；④重复步骤③的方法，安排其后的元素，直到八个数据全部处理完为止。Pascal程序:ProgramExam54;constname:array[1..8]ofstring{定义字串类型数组并赋常量｝=('A13','B27','C35','D41','E58','F62','G74','H86');Vari,code:integer;｛整数类型｝x:1..8;｛子界类型｝s:string;｛字符串类型｝Begin　s:=copy(name[1],1,1);｛截取第一个元素字串的第一个字符｝write(s:4);｛确定第一个位置｝s:=copy(name[1],3,1);｛截取元素字串的第三个字符作为相邻｝Val(s,x,code);｛将字串s的值转换成数字存入x｝fori:=1to7do｛确定后面7个位置｝Begins:=copy(name[x],1,1);｛找到相邻者的代码｝write(s:4);｛打印相邻者代码｝s:=copy(name[x],3,1);｛确定下一个相邻元素｝Val(s,x,code);end;readlnEnd.Pascal常用的字符串处理标准函数有7个：设变量s，str，str1，str2均为字符串类型（string）｛多个字符｝；ch为字符类型（char）｛单个字符｝；（1）copy（str，n，m）从字符串str的左边第n个开始截取m个字符；如：copy（'Pascal'，3，2）的结果为'sc'；（2）concat（str1，str2）将两个字串连接成为一个新的字串；如：s:=str1+str2；同等于两串字符相加（3）Length(str)求字串str的长度（字符个数）；（4）chr(x)求x（x为1…255整数)的ASII代码对应的字符；如：chr（65）结果为'A'。（5）ord(ch)求字符ch对应的ASCII代码值；如ord('A')结果为65；（6）pos（str1，str2）求字串str1在字串中开始的位置；如:pos（'sca'，'pascal'）结果为3；（7）upcase(ch)将字符ch转为大写字母，如upcase('a')结果为'A'；125 Pascal常用的字符串处理标准过程有4个：（1）Val(str，x，code)将数字型字串转为数字并存入变量x中；如：Val(‘768’,x,code),x值为768，code为检测错误代码，若code=0表示没有错误；（2）str(n，s)将数字n转化为字串存入s中，如str(768，s)s的结果为'768'；（3）insert(str1，str2，n)把字串str1插入在字串str2的第n个字符之前，结果在str2中；｛此过程中的str2为变量形参，具有传入传出的功能｝；（4）delete(str，n，m)从字串str的第n个开始，删除m个字符，把剩余的字符存在str中，｛此过程中的str为变量形参，具有传入传出的功能｝；[例5.5]一个两位以上的自然数，如果左右数字对称，就称为回文数，编程找出所有不超过6位数字的回文数，同时又是完全平方数的数。如121是回文数，又是11的平方，所以是完全平方数。解:①不超过6位数的完全平方数用循环在10～999范围产生（fori:=10to999)；②将完全平方数(i*i)转成字串类型存入s中；③逐个取s的左右字符，检查是否相同（对称），检查对数不超过总长度的一半；④如果是回文数，就调用打印过程(Print)。ProgramExam55;Varn,k,j,t:integer;s:string;{字符串类型}i:longint;{长整数类型}ProcedurePrint;{打印过程(无形参)}beginwrite(s:10);inc(t);{打印s,用t计数}iftmod6=0thenwriteln{打印6个换行}end;Begint:=0;fori:=10to999dobeginstr(i*i,s);{将完全平方数转换成字串}k:=length(s);{计算字串长度}n:=kdiv2;{计算字串长度的一半}j:=1;whilej<=ndo{取左右字符检查是否对称}ifcopy(s,j,1)<>copy(s,k+1-j,1)thenj:=1000elseinc(j);{若不对称让j=1000,退出循环}ifj<1000thenPrint{j<1000即是回文数,调打印}end;writeln;writeln('Total=':8,t);{打印总个数}readlnEnd.125 习题5.11.裴波那契数列：数列1、1、2、3、5、8、13、21…称为裴波那契数列，它的特点是：数列的第一项是1，第二项也是1，从第三项起，每项等于前两项之和。编程输入一个正整数N，求出数列的第N项是多少？（N不超过30）。2.下面的竖式是乘法运算，式中P表示为一位的素数，编程输出此乘法竖式的所有可能方案。3.节目主持人准备从N名学生中挑选一名幸运观众，因为大家都想争当幸运观众，老师只好采取这样的办法：全体同学排成一列，由前面往后面依顺序报数1，2，1，2，…，报单数的同学退出队伍，余下的同学向前靠拢后再重新由前往后1，2，1，2，…报数，报单数者退出队伍，如此下去最后剩下一人为幸运观众。编程找出幸运观众在原队列中站在什么位置上？（N由键盘输入，N<255）。4.1267*1267=1605289，表明等式右边是一个七位的完全平方数，而这七个数字互不相同。编程求出所有这样的七位数。5.校女子100米短跑决赛成绩如下表，请编程打印前八名运动员的名次、运动员号和成绩。（从第一名至第八名按名次排列）运动员号017168088105058123142055113136020032089010成绩(秒)12.312.613.011.812.113.112.011.911.612.412.913.212.211.46.求数字的乘积根。正整数的数字乘积这样规定：这个正整数中非零数字的乘积。例如整数999的数字乘积为9*9*9，得到729；729的数字乘积为7*2*9，得到126；126的数字乘积为1*2*6，得到12；12从数字乘积为1*2，得到2。如此反复取数字的乘积，直至得到一位数字为止。999的数字乘积根是2。编程输入一个长度不超过100位数字的正整数，打印出计算数字乘积根的每一步结果。输出格式如下：（N=3486784401）348678440151609616201227.有一组13个齿轮互相啮合,各齿轮啮合的齿数依次分别为6,8,9,10,12,14,15,16,18,20,21,22,24,问在转动过程中同时啮合的各齿到下次再同时啮合时,各齿轮分别转过了多少圈?8.集合M的元素的定义如下:(1)数1属于M;(2)若X属于M,则A=2X+1,B=3X+1,C=5X+1,也属于M;(3)再没有别的数属于M。(M={1,3,4,6,7,9,10,13,15,16...，如果M中的元素是按递增次序排列的,求出其中的第201,202和203个元素。125 9.一个素数,去掉最高位,剩下的数仍是素数;再去掉剩下的数的最高位,余留下来的数还是素数,这样的素数叫纯粹素数。求所有三位数的纯粹素数。10.自然数4,9,16,25等叫做完全平方数,因为22=4,32=9,42=16,52=25,当某一对自然数相加和相减,有时可各得出一个完全平方数。例如:8与17这对自然数：17+8=2517—8=9试编程,找出所有小于100的自然数对,当加和减该数对时，可各得出一个完全平方数。第二节　二维数组与枚举类型[例5.6]假设四个商店一周内销售自行车的情况如下面表一所示，自行车牌号永久牌飞达牌五羊牌第一商店354055第二商店205064第三商店103218第四商店383628表一几种牌号自行车的单价如表二所示。求各店本周出售自行车的总营业额。单价元永久牌395飞达牌398五羊牌384表二解：①把表一看成是由行（每个店占一行）与列（每种牌号占一列）共同构成的数据组，按表格排列的位置顺序，用A数组表一各数据表示如下：A[1,1]=35A[1,2]=40A[1,3]=55{第一行共三个数据}A[2,1]=20A[2,2]=50A[2,3]=64{第二行共三个数据}A[3,1]=10A[3,2]=32A[3,3]=18{第三行共三个数据}A[4,1]=38A[4,2]=36A[4,3]=28{第四行共三个数据}A数组有4行3列，每个数组元素由两个下标号表示，这样的数组称为二维数组。②表二的数据按排列顺序用B数组表示如下：B[1]=395B[2]=398B[3]=384②B数组有3个数据，用一维数组表示，下标号与表一中列的序号有对应关系。③计算各店营业额并用T数组表示：T[1]=A[1,1]*B[1]+A[1,2]*B[2]+A[1,3]*B[3]{计算第一商店的营业额}T[2]=A[2,1]*B[1]+A[2,2]*B[2]+A[2,3]*B[3]{计算第二商店的营业额}T[3]=A[3,1]*B[1]+A[3,2]*B[2]+A[3,3]*B[3]{计算第三商店的营业额}T[4]=A[4,1]*B[1]+A[4,2]*B[2]+A[4,3]*B[3]{计算第四商店的营业额}T数组共有4个数据，为一维数组，下标号与商店号有对应关系。④输出T数组各元素的值。Pascal程序：ProgramExam56;125 VarA:array[1..4,1..3]ofinteger;{定义二维数组，整数类型}B:array[1..3]ofinteger;{一维数组，3个元素}T:array[1..4]ofinteger;{一维数组，4个元素}i,j:integer;Beginfori:=1to4do{输入表一的数据}BeginWrite(‘A[‘,i,‘]:’);{提示输入哪一行}forj:=1to3doRead(a[i,j]);{每行3个数据}Readln;{输完每行按回车键}end;fori:=1to3do{输入表二的数据}BeginWrite(’B[’,I,’]:’);{提示第几行}Readln(B[i]);{输入一个数据按回车}end;fori:=1to4do{计算并输出}BeginT[i]:=0;Write(’’:5,I:4);forj:=1to3doBeginWrite(A[i,j]:6);T[i]=T[i]+A[i,j]*B[j];end;Write(T[i]:8);end;Readln;end.程序中定义二维组方式与一维数组形式相同。二维数组的元素由两个下标确定。二维数组元素的格式如下：数组名[下标1，下标2]常用下标1代表数据在二维表格中的行序号，下标2代表所在表格中列的序号。[例5.7]输入学号从1101至1104的4名学生考试语文、数学、化学、英语、计算机六门课的成绩，编程求出每名学生的平均分，按每名学生数据占一行的格式输出。125 NameChinMathPhysChemEnglCompAve1101879178856778110269847995918911038669798990881104888992878881解：根据题目所给数据及要求，定义如下数据类型：①学生成绩：在数据表格中每人的成绩占一行，每行6列（每科占一列）；定义二维数组s，各元素为实型；②个人平均分：定义一维数组av，各元素为实型；③个人总分：是临时统计，为计算机平均分服务，用简单实型变量t；处理步骤为：①用双重循环按行i按列j输入第i个人第j科成绩存入s[i,j]；②每读入一科成绩分，就累计到个人总分t中；③输完第i个人的各科成绩，就计算出第i个人平均分并存入数组av(i)中；④重复上述步骤，直到全部学生的成绩处理完毕；⑤用双重循环按行列形式输出完整的成绩表。Pascal程序：ProgramExam57;constNB=1101;NE=1104;Vars:array[NB..NE,1..6]ofreal;{定义二维数组(学生成绩)}av:array[NB..NE]ofreal;{定义一维数组(平均成绩)}i:NB..NE;{i为子界类型(学号范围)}j:1..6;{j为子界类型(课程范围)}t:eal;{t为实数类型(计总成绩)}Beginfori:=NBtoNEdo{用i控制处理一位学生成绩}begint:=0;write(i,':');forj:=1to6do{输入并计算每人的６门成绩}beginread(s[i,j]);t:=t+s[i,j];{累加个人总分}end;av[i]:=t/6;{求个人平均分}readln{输完６门分按一次回车键}end;writeln;{输出学生成绩表}writeln('':5,'*****************************************');writeln('':5,'NameChinMathPhysChemEnglCompAve');writeln('':5,'---------------------------------------------');fori:=NBtoNEdobeginwrite('':5,i:4,'':2);{输出学号}forj:=1to6dowrite(s[i,j]:4:1,'':2);{输出６门成绩}125 writeln(av[i]:4:1);{输出平均分}end;readlnEnd.程序中的学生成绩用键盘输入方式赋给二维数组各元素，如果是少量已知数据，也可在常量说明部分，直接给二维数组各元素赋常数，现将本例题改为如下程序：ProgramExam57_1；ConstNB=1101;NE=1104;{定义常量}TypeCou=(Chin,Math,Phys,Chem,Engl,Comp);{自定义枚举类型}Num=NB..NE;{自定义子界类型}Consts:array[Num,Cou]ofreal{定义二维数组并赋常数}=((87,91,78,85,67,78),(69,84,79,95,91,89),(86,69,79,89,90,88),(88,89,92,87,88,81));Varav:array[Num]ofreal;{定义一维数组(平均成绩)}i:Num;{i为子界类型(学号范围)}　j:Cou;{j为子界类型(课程范围)}t:real;{t为实数类型(计总成绩)}Beginfori:=NBtoNEdo{用i控制处理一位学生成绩}begint:=0;forj:=ChintoCompdo{计算每人的６门成绩}t:=t+s[i,j];{累加个人总分}av[i]:=t/6;{求个人平均分}end;writeln;{输出学生成绩表}writeln('':5,'****************************************');writeln('':5,'NameChinMathPhysChemEnglCompAve');writeln('':5,'---------------------------------------------');fori:=NBtoNEdobeginwrite('':5,i:4,'':2);{输出学号}forj:=ChintoCompdowrite(s[i,j]:4:1,'':2);{输出６门成绩}writeln(av[i]:4:1);{输出平均分}end;End.程序说明部分定义了枚举类型。枚举类型常用自然语言中含义清楚、明了的单词（看成代码）来表示“顺序关系”，是一种顺序类型，是根据说明中的排列先后顺序，才具有0，1，2…n125 的序号关系，可用来作循环变量初值和终值，也可用来作数组下标。但枚举类型不是数值常量或字符常量，不能进行算术运算，只能作为“序号关系”来使用。[例5.8]从红(red)、黄(yellow)、兰(blue)、白(white)、黑(black)五种颜色的球中，任取三种不同颜色的球，求所有可能的取法？解：①将五种颜色定义为枚举类型;②a,b,c都是枚举类型中取不同颜色之一；③a的取值范围从redtoblack;b的取值范围从redtoblack,但必须a<>b;c的取值范围从redtoblack,且必须(a<>b)and(c<>b);④每次打印取出的三个球的颜色，即第一个到第三个（forn:=1to3)当n=1：取a的值，根据a的“顺序”值输出对应颜色字符串；当n=2：取b的值，根据b的“顺序”值输出对应颜色字符串；当n=3：取c的值，根据c的“顺序”值输出对应颜色字符串；⑤直至a,b,c的取值范围全部循环完毕。Pascal程序：programex58;typecolor=(red,yellow,blue,white,black);vara,b,c,dm:color;nn:1..3;s:integer;begins:=0;fora:=redtoblackdoforb:=redtoblackdoifa<>bthenforc:=redtoblackdoif(c<>a)and(c<>b)thenbegininc(s);write(s:5);fornn:=1to3dobegincasennof{找每种球的颜色“顺序”值}1:dm:=a;{dm是所取得的“顺序”值}2:dm:=b;3:dm:=cend;casedmof{根据“顺序”值打印对应字串}red:write('red':9);yellow:write('yellow':9);blue:write('blue':9);white:write('white':9);black:write('blcak':9);125 end;end;writelnend;writeln;writeln('totalnum:':12,s:4);readlnend.程序中的从red到black的顺序关系本来是不存在的，但经过枚举类型定义之后，就建立了这种“枚举”先后而产生的顺序排列关系。这种“关系”完全取决于类型说明时的位置排列。[例5.9]新录A、B、C三个工人，每人分配一个工种，每个工种只需一人，经测试，三人做某种工作的效率如下表所示。如何分配三人的工作才能使他们工作效益最大？工种工人一二三A433B243C452解：①定义各元素值为整数型的X数组，将表中的数据按行列关系作如下处理：A为第一行，将其三种工作效率(4,3,3)分别存入(x[A,1],x[A,2],x[A,3]);B为第二行，将其三种工作效率(2,4,3)分别存入(x[B,1],x[B,2],x[B,3])；C为第一行，将其三种工作效率(4,5,2)分别存入(x[C,1],x[C,2],x[C,3])。在这里，x数组第一个下标为枚举型，表示工人(A,B,C)；第二个下标为子界型，表示工种（一、二、三）：②计算三人工作的总效率：S=x[A,i]+x[B,j]+x[C,k]A的工种i：1～3（用循环fori:=1to3）；B的工种j：1～3（用循环forj:=1to3且j<>i）；C的工种k=6-i-j（工种代号总和为6，减去两个代号就得到第三个）；③将每次计算得到的S与“最大值”m比较，（m的初值为0），只要有大于m的S值即取代m原来的值，使之最大，同时用数组dd记录最大S值时的工种i,j,k值;④当循环全部结束时，打印记录下来的每个人的工种。Pascal程序：Programexam59;typema=(a,b,c);{定义枚举类型）wk=1..3;{定义子界类型}Constx:array[ma,wk]ofinteger{给x数组（二维）}125 =((4,3,3),(2,4,3),(4,5,2));{赋常量(表中值)}m:integer=0;{给m赋初值0}Vardd:array[wk]ofwk;{用DD数组记忆工种号}i,j,k:wk;s:integer;beginfori:=1to3doforj:=1to3doifj<>ithenbegink:=6-i-j;s:=x[a,i]+x[b,j]+x[c,k];ifs>mthenbeginm:=s;{记下最大效益}dd[1]:=i;{记下最佳分配方案}dd[2]:=j;dd[3]:=kendend;fori:=1to3do{输出}writeln(chr(64+i):8,dd[i]:8);writeln('最大效益:':12,m:4);readlnend.输出语句中的chr(64+i)是将(64+i)数值转换成对应的ASCII字符。程序中用枚举类型表示工人代码（A,B,C）,比较直观、清晰、易读好理解。在程序中枚举类型都可以用数字序号来取代，下面程序用1,2,3代表工人A,B,C：programexam59_1;typen=1..3;Constx:array[n,n]ofinteger=((4,3,3),(2,4,3),(4,5,2));m:integer=0;Vardd:array[n]ofn;i,j,k:n;s:integer;beginfori:=1to3doforj:=1to3do　ifj<>ithenbegink:=6-i-j;125 s:=x[1,i]+x[2,j]+x[3,k];　ifs>mthenbeginm:=s;dd[1]:=i;dd[2]:=j;dd[3]:=kendend;fori:=1to3dowriteln(chr(64+i):8,dd[i]:8,x[i,dd[i]]:8);writeln('最大效益:':12,m:4);readlnend.程序中的x[i,dd[i]]是分配给i号工人做dd[i]号工种的效率值，在这里，以数组元素值作为下标，称为下标嵌套。[例5.10]下面是一个3阶的奇数幻方。618753294它由1到32的自然数组成一个3*3的方阵，方阵的每一行，每一列和两个对角线上的各数字之和都相等，且等于n(n2+1)/2（n是方阵的行数或列数）。编程打印出n为10以内的奇数阶幻方。解：仔细观察示例，有如下规律：①在顶行中间填数字1；{横坐标（行）X=1，纵坐标（列）Y=(n+1)/2}②后继数放在前一个数的左上方；{X=X-1；Y:=Y-1}若超出了行，则认为是最后一行；{ifX<1thenX=n}若超出了列，则认为是最后一列；{ifY<1thenY=n}③若左上方已有数，则放在原数的正下方；{X=X+1，Y=Y}④重复步骤②、③，直至填满方阵为止。Pascal程序：ProgramExam510;UsesCrt;Vara:array[1..10,1..10]ofinteger;x,y,xx,yy,s,n:integer;BeginClrscr;{清屏｝fillchar(a,sizeof(a),0);{将a数组各元素置0}repeatwrite('InputNumberPlease!');{提示输入n}readln(n)untilodd(n);s:=1;x:=1;y:=(ndiv2)+1;a[x,y]:=1;repeat125 inc(s);xx:=x;yy:=y;dec(x);dec(y);ifx<1thenx:=n;ify<1theny:=n;ifa[x,y]<>0thenbeginx:=xx+1;y:=yyend;a[x,y]:=s;untils=n*n;forx:=1tondobeginfory:=1tondowrite(a[x,y]:3);writelnend;repeatuntilkeypressed;End.程序中fillchar(a,sizeof(a),0)是给a数组各元素置0。Clrscr是清屏。习题5.2:1．输入四个学生考试五门功课，要求按个人总分从高到低排列输出二维成绩表格。（即每行有学号，五科成绩及总分）1111211331146412．杨晖三角形的第n行对应着二项式n次幂展开式的各个系数。例如第3行正好是(a+b)3=a3+3a2b+3ab2+b3展开式各项系数1，3，3，1。右图是n从0～4的杨晖三角形：第一行n=0,即(a+b)0=1，系数为1；第二行n=1,即(a+b)1=a+b，系数为11；第三行n=2,即(a+b)2=a2+2ab+b2,系数为121；编程输出n行的杨晖三角形。3．下面是一个4*4的矩阵，它的特点是：(1)矩阵的元素都是正整数；(2)数值相等的元素相邻，这样，这个矩阵就形成了一级级“平台”，其上最大的“平台”面积为8，高度（元素值）为6。若有一个已知的N*N的矩阵也具有上面矩阵的特点，求矩阵最大“平台”的面积和高度。4．打印一个n*n的数字螺旋方阵。这个数字方阵的特点是：以左上角1开始向下，数字以外圈向里按自然数顺序转圈递增，一直到中心位置的n2为止。例如n=3:187296345125 第三节　集合类型Pascal系统把具有共同特征的同一有序类型的对象汇集在一起，形成一个集合，可将集合类型的所有元素作为一个整体进行集合运算。[例5.11]用随机函数产生20个互不相同的40到100的随机整数，然后按从小到大顺序打印。解：按以下步骤处理：①为使产生的随机整数互不相同。因此，每产生一个数，都要判断集合中已否包含，如果没有包含，就放到集合中，并统计个数，直到20个。②将集合中的数移到数组中，此题利用下标序号从小到大的特征进行映射排序打印。Pascal程序：ProgramExam511;UsesCrt;Vara:Array[40..100]Ofboolean;dd:setOf40..100;{定义集合dd}n:Integer;ProcedureInit;｛定义产生并处理随机数的过程｝Vari,m:Integer;Beginn:=0;dd:=[];{集合dd初值为空}repeatbeginRandomize;｛将随机发生器作初始化处理｝m:=Random(100);{产生随机整数m}ifnot(mindd)and(m>40)thenbegindd:=dd+[m];inc(n){把m放入集合dd中}end;enduntiln=20;End;ProcedurePrint;｛定义打印过程｝Vari,j,k:Integer;Beginfillchar(a,sizeof(a),false);{将数组a的各元素置false值}Fori:=40To100Doifiinddthena[i]:=true;{以集合元素值为下标的数组元素赋真值}Fori:=40To100Do{以下标号为序(从小到大)输出}Ifa[i]ThenWrite(i:4);{输出a数组中元素值为真的下标号}End;Begin｛主程序｝Clrscr;125 init;{产生随机数，并存入集合中}print;{打印}RepeatUntilKeyPressed;End.程序中定义了集合类型DD，集合的元素为子界类型。Var集合变量名:setof元素的类型；定义集合类型的一般格式是：集合的值放在一对方括号中，各元素用逗号隔开，与排列的顺序无关，因此，[9,2,5]和[2，5，9]的值相等，没有任何元素的集合是空集合，用[]表示。如果集合的元素是连续的，可用子界表示，如[5,6,7,8,9]可表示为[5..9]。集合变量名:=集合表达式；集合的赋值格式为：集合有以下几种运算：1.集合的交、并、差运算：（设两个集合a:=[1,2,4,6]和b:=[4,6,7,8])①集合的并:a+b即组合成新的集合(为[1,2,4,6,7,8])；②集合的交:a*b即将a,b集合中的公共元素组合成新的集合(为[4,6,])；③集合的差:a-b即在a中的元素去掉在b中出现的之后，所剩下的集合(为[1,2])。2.集合的比较：①相等：a=b，若两个集合中的元素个数相等，每个元素相同，则两个集合相等，比较结果为真（ture)，否则为假（false)；②不等：a<>b表示两个集合不相等；③包含：a>=b表示a集合包含b集合中的所有元素；a<=b表示a集合是b集合的子集。3.集合的测试运算：检查某个数据在集合中，测试结果为ture；不在集合中，测试结果为false；例如：6in[8,6,9,4]结果为ture；{6在集合[8,6,9,4]中为真}2in[8,6,9,4]结果为false;{2在集合[8,6,9,4]中为假}从程序Exam511的输出部分可看到，集合类型的值不能直接输出,要用测试方法进行输出或转换成数组元素的值。[例5.12]用集合进行筛法求200以内的素数。解：①将[2..200]放入集合S中；②取S中的第一个元素值nxt,放入集合P中，同时将S中的凡是nxt的倍数的元素全部“划”去；③重复步骤②，直至S集合为空；④用测试运算打印P集合中全部元素值。Pascal程序：ProgramExam512;Usescrt;constn=200;125 vars,p:setof2..n;{s,p为集合类型}nxt,j,t:byte;beginclrscr;s:=[2..n];{将[2..n]赋给s}p:=[];nxt:=2;t:=0;repeatwhilenot(nxtins)donxt:=succ(nxt);{后继函数}p:=p+[nxt];j:=nxt;{将nxt放入P中}whilej<=ndobegins:=s-[j];inc(j,nxt){筛掉S中的处理过的元素}end;ifnxtinpthen{用测试运算进行输出}begininc(t);write(nxt:6);iftmod6=0thenwritelnend;untils=[];readlnend.集合内的元素个数不能超过255个，如果要用超过255个成员的集合类型求素数，必须用小集合的数组来表示大集合，即把大集合分成若干个小集合，每个小集合只是数组的元素，（数组元素为一个小集合）整个数组就是一个大集合。筛法运用在每个数组元素（小集合）中进行。[例5.13]将自然数1--9这九个数分成三组，将每组的三个数字拼成为三位数，每个数字不能重复，且每个三位数都是完全平分数。请找出这样的三个三位数。解：①自定义函数yes，用集合判定九个数字是否有重复，采用逆向思维，假设做邓了三个三位完全平方数：将三个三位完全平方数分离成单个数字放入集合dd中，检查集合dd，如果自然数1～9每个数恰好都在集合dd中，函数yes赋真（ture）；只要有一个不在集合中，九个数字没有占完集合中的九个位置，则必有重复，函数值为假（false)，因为集合中对相同数字视为同一成员，如果有重复，则集合中不足9个成员（用测试运算）。②程序用11～31平方产生三位的完全平方数。用循环方式每次取三个数为一组，存入a数组。③对a数组的三位数调用自定义函数yes处理；④如果函数yes值为真，就打印a数组中的三个数。Pascal程序：Programexam513;UsesCrt;125 Vara:Array[1..3]OfInteger;i,j,k,x:Integer;Functionyes:Boolean;{处理是否有重复数字}Vari:Integer;d:SetOf0..9;{集合元素为子界类型}Begind:=[];{集合的初值为空集合}Fori:=1To3Do{将a数组中三个数分离成单个数并放入集合d}d:=d+[a[i]Div100,(a[i]Mod100)Div10,a[i]Mod10];yes:=true;Fori:=1To9DoIfNot(iInd)Thenyes:=false;{只要有一个不在集合中即为假}End;Beginwriteln;fori:=11to29do{在三位完全平方数范围内循环推出三个数}Begina[1]:=i*i;{第一个三位的完全平方数}forj:=i+1to30dobegina[2]:=j*j;{第一个三位的完全平方数}fork:=j+1to31dobegina[3]:=k*k;{第一个三位的完全平方数}IfyesThen{调用自定义yes函数结果为真就输出}Forx:=1To3DoWriteln(x:8,':',a[x]:8);endendend;RepeatUntilKeyPressed;End.习题5.31.设计一个将十六进制数转换为十进制数的程序。2.将自然数1--9数字不重复组成三个三位数，且三个数之比为1∶2∶3。求出能满足条件的全部方案。3.从键盘输入一个20位以内的自然数，然后将组成这个数的各位数字重新排列，得到一个数值为最小的新数，且新数的位数保持不变。打印出重新排列后的新数。4.现有五件物品，重量分别为4、8、10、9、6.5公斤,它们的价值分别为12、21、24、125 17、10.5元。有一个背包，装入物品总量不得超过19公斤，该选哪几件物品放入背包内使总价值最大?第四节　记录类型和文件类型前面介绍的数组类型和集合类型有一个共同点，那就是在同一个数组或集合中的各有元素都必须具有相同的类型。如果要处理如下表所示的学生档案卡片上的数据，各栏目的数据类型不一样（学号，姓名，成绩…）,需要用不同的类型表示。学号姓名性别出生年月语文数学英语平均分为此，PASCAL系统定义了记录类型，可用来表示不同类型的数据。[例5.14]建立一张学生情况表格，求出每位学生的平均成绩，并输出这张表格。解：①定义记录类型：Date(表示日期记录，有三个域：day日，mon月，yea年）；Studa(表示学生情况记录，有六个域：nu学号，na姓名，dd出生年月，se性别，s成绩，ave平均分)；②读入记录数据；③计算学生的平均成绩；④输出记录内容。PASCAL程序：ProgramExam514;Constn=2;m=3;{为了简单,人数N=2课目M=3}TypeDate=Record{定义Date(日期)记录类型}day:1..31;{域名day表示天,为子界型(1..31)}mon:1..12;{域名mon表示月,为子界型(1..12)}yea:1970..1999;{域名yea表示年,为子界类型}End;Studa=Record{定义Studa(学生情况)记录类型}nu:string[5];{域名nu表示学号,为字符串类型}na:string[8];{域名na表示姓名,为字符串类型}dd:Date;{域名dd表示日期,为记录类型(Date)}se:char;{域名se表示性别,为字符类型}s:array[1..m]ofreal;{域名s表示成绩,为数组类型}ave:real{域名s表示平均分,为实数类型}End;Sarr=array[1..n]ofStuda;{定义Sarr为数组类型,各元素为记录类型}VarStu:sarr;{变量Stu为数组(Sarr)类型}Procedurerrd(varstu:sarr);{定义输入和计算过程}vari,k:integer;125 t:real;a:studa;{变量a为记录(Studa)类型}beginfork:=1tondobeginwitha,dddo{开域语句,打开当前记录a和dd,进行以下操作}beginwrite(k:2,'nu:');readln(nu);{输入学号}write(k:2,'na:');readln(na);{输入姓名}write(k:2,'se:');readln(se);{输入性别}write(k:2,'day:');readln(day);{输入出生日}write(k:2,'mon:');readln(mon);{输入出生月}write(k:2,'yea:');readln(yea);{输入出生年}t:=0;fori:=1tomdo{输入m科的成绩分}beginwrite('s[',i,']=');read(s[i]);t:=t+s[i]{累加总分}end;readln;ave:=t/m;{计算平均分}stu[k]:=a{将当前记录存入stu[k]中}end;endend;Procedureprint1;{打印表格线}vari:integer;beginfori:=1to60dowrite('-');writeln;type记录类型名=record域名：类型；…域名：类型；end;end;Procedureprint2;{打印表头和表格栏目}beginwriteln('':18,'________table_________');print1;write('num.','':6,'name','':7,'mm/dd/yy','':4);writeln('sex','Chin','':2,'math','':2,'Engl','':2,'vaer');print1end;Procedureprint3(stu:sarr);{打印记录数据}vari,j:integer;125 beginprint2;forj:=1tondowithstu[j],dddobeginwrite(nu:5,na:9,'':8,mon:2,'/',day:2,'/',yea:4,'');write(se:3,'');fori:=1tomdowrite(s[i]:6:1);writeln(ave:6:1);print1endend;Beginrrd(stu);print3(stu);readlnend.程序自定义Date记录类型，用来表示学生的出生年月日，含三个分量（称为域）：day（日）为子界类型（1..31）；mon（月）为子界类型（1..12）；yea（年）为子界类型（1970..1999）；自定义Stuta记录类型,用来表示学生情况，含六个域：nu（学号）为字符类型（string[5]为5个字符）；na（学号）为字符类型（string[8]为8个字符）；dd（出生年月日）是前面所定义的date记录类型；se（性别）是char字符类型；s（表示学生成绩）是数组类型，各元素为real实型；ave(学生平均分）是real实型；程序定义的数组sarr的每个元素为Stuta记录（每个记录相当于一张学生情况卡片，整个数组相当于全体学生的情况卡片）。自定义记录类型的一般格式为：访问记录中的分量，有两种方式：①记录名.域名例如对记录a中的nu赋值，可写成a.nu:=1008;{将1008赋给记录a中的分量nu}②with记录名do语句开域语句，with后面可同时打开多个记录，例如：witha,dddo语句;{a,dd都是记录名}[例5.15]利用记录类型将N个数由大到小排序，输出排序结果并显示每个数原来的位置序号。PASCAL程序：ProgramEx59;Typedd=Record{定义DD记录类型}125 ii:integer;{域名ii表示数}id:integer{域名id表示数ii的位置序号}End;Vara:array[1..100]ofdd;i,j,k,n:integer;t:dd;BeginWrite('PleaseInputNumberofelements:');read(n);writeln('Inputelements:');fori:=1tondobeginread(a[i].ii);a[i].id:=i;forj:=1toi-1doifa[j].ii1)X3=X*X2(n>1)……(n>1)Xn=X*Xn-1(n>1)因此将Xn转化为：其中求Xn-1又用求Xn的方法进行求解。①定义过程xn(x,n:integer)求Xn;如果n>1则递归调用xn(x,n-1)求Xn—1;②当递归调用到达n=0，就执行tt:=1,然后执行本“层”的后继语句;③遇到过程的END就结束本次的调用，返回到上一“层”调用语句的地方，并执行其后续语句tt:=tt*x;④继续执行步骤③，从调用中逐“层”返回，最后返回到主程序，输出tt的值。Pascal程序：ProgramExam2;Vartt,a,b:integer;Procedurexn(x,n:integer);｛过程xn(x,n)求xn｝beginifn=0thentt:=1elsebeginxn(x,n-1);｛递归调用过xn(x,n-1)求xn-1｝tt:=tt*x125 end;end;beginwrite(’inputx,n:’);readln(a,b);｛输入a,b｝xn(a,b);｛主程序调用过程xn(a,b)求ab｝writeln(a,’^’,b,’=‘,tt);readlnend.递归算法，常常是把解决原问题按顺序逐次调用同一“子程序”(过程)去处理，最后一次调用得到已知数据，执行完该次调用过程的处理，将结果带回，按“先进后出”原则，依次计算返回。如果处理问题的结果只需返回一个确定的计算值，可定义成递归函数。[例3]用递归函数求x!解：根据数学中的定义把求x!定义为求x*(x-1)!,其中求(x-1)!仍采用求x!的方法，需要定义一个求a！的过程或函数，逐级调用此过程或函数，即：(x-1)!=(x-1)*(x-2)!;(x-2)!=(x-2)*(x-3)!;……直到x=0时给出0!=1，才开始逐级返回并计算各值。①定义递归函数：fac(a:integer):integer;如果a=0，则fac:=1;如果a>0，则调用函数fac:=fac(a-1)*a;②返回主程序，打印fac(x)的结果。Pascal程序：ProgramExam3;Varx:integer;functionfac(a:integer):integer;｛函数fac(a)求a!｝beginifa=0thenfac:=1elsefac:=fac(a-1)*a｛函数fac(a-1)递归求(a-1)!｝end;beginwrite(’inputx’);readln(x);writeln(x,’!=’,fac(x));｛主程序调用fac(x)求x!｝125 readlnend.递归算法表现在处理问题的强大能力。然而，如同循环一样，递归也会带来无终止调用的可能性，因此，在设计递归过程（函数）时，必须考虑递归调用的终止问题，就是递归调用要受限于某一条件，而且要保证这个条件在一定情况下肯定能得到满足。[例4]用递归算求自然数A，B的最大公约数。解：求最大公约数的方法有许多种，若用欧几里德发明的辗转相除方法如下：①定义求X除以Y的余数的过程;②如果余数不为0，则让X=Y，Y=余数，重复步骤①，即调用过程;③如果余数为0，则终止调用过程;④输出此时的Y值。Pascal程序：ProgramExam4;Vara,b,d:integer;ProcedureGdd(x,y:nteger);{过程}beginifxmody=0thend:=yelseGdd(y,xmody){递归调用过程}end;beginwrite(’inputa,b=’);readln(a,b);Gdd(a,b);writeln(’(’,a,’,’,b,’)=’,d);readlnend.简单地说，递归算法的本质就是自己调用自己，用调用自己的方法去处理问题，可使解决问题变得简洁明了。按正常情况有几次调用，就有几次返回。但有些程序可以只进行递归处理，不一定要返回时才进行所需要的处理。[例5]移梵塔。有三根柱A，B，C在柱A上有N块盘片，所有盘片都是大的在下面，小片能放在大片上面。现要将A上的N块片移到C柱上，每次只能移动一片，而且在同一根柱子上必须保持上面的盘片比下面的盘片小，请输出移动方法。解：先考虑简单情形。如果N=3，则具体移动步骤为：125 假设把第3步，第4步，第6步抽出来就相当于N=2的情况（把上面2片捆在一起，视为一片）：125 所以可按“N=2”的移动步骤设计：①如果N=0，则退出，即结束程序;否则继续往下执行;②用C柱作为协助过渡，将A柱上的（N-1）片移到B柱上，调用过程sub(n-1,a,b,c);③将A柱上剩下的一片直接移到C柱上;④用A柱作为协助过渡，将B柱上的（N-1）移到C柱上，调用过程sub(n-1,b,c,a)。Pascal程序：ProgramExam65;Varx,y,z:char;N,k:integer;Proceduresub(n:integer;a,c,b:char);beginifn=0thenexit;sub(n-1,a,b,c);inc(k);writeln(k,’:from’,a,’--＞’,c);sub(n-1,b,c,a);end;beginwrite(’n=’;readln(n);k:=0;x:=’A’;y:=’B’;Z:=’C’;sub(n,x,z,y);125 readlnend.程序定义了把n片从A柱移到C柱的过程sub(n,a,c,b)，这个过程把移动分为以下三步来进行：①先调用过程sub(n-1,a,b,c)，把(n-1)片从A柱移到B柱,C柱作为过渡柱;②直接执行writeln(a,’--＞’,c），把A柱上剩下的一片直接移到C柱上，;③调用sub(n-1,b,c,a)，把B柱上的(n-1)片从B移到C柱上，A柱是过渡柱。对于B柱上的(n-1)片如何移到，仍然调用上述的三步。只是把(n-1)当成了n，每调用一次，要移到目标柱上的片数N就减少了一片，直至减少到n=0时就退出，不再调用。exit是退出指令，执行该指令能在循环或递归调用过程中一下子全部退出来。习题6.11.过沙漠。希望一辆吉普车以最少的耗油跨越1000km的沙漠。已知该车总装油量500升，耗油率为1升/km，必须利用吉普车自己沿途建立临时加油站，逐步前进。问一共要多少油才能以最少的耗油越过沙漠？2.楼梯有N级台阶，上楼可以一步上一阶，也可以一步上二阶。编一递归程序，计算共有多少种不同走法？提示：如N级楼梯有S(N)种不同走法，则有：S(N)=S(N-2)+S(N-1)3.阿克曼(Ackmann)函数A(x,y)中，x,y定义域是非负整数，函数值定义为：A(x,y)=y+1(x=0)A(x,0)=A(x-1,1)(x>0,y=0)A(x,y)=A(x-1,A(x,y-1))(x,y>0)设计一个递归程序。4.某人写了N封信和N个信封，结果所有的信都装错了信封。求所有的信都装错信封共有多少种不同情况。可用下面公式：Dn=(n—1)(Dn—１+Dn—２)写出递归程序。第二节　回溯算法在一些问题求解进程中，有时发现所选用的试探性操作不是最佳选择，需退回一步，另选一种操作进行试探，这就是回溯算法。例[6.6]中国象棋半张棋盘如下，马自左下角往右上角跳。现规定只许往右跳，不许往左跳。比如下图所示为一种跳行路线。编程输出所有的跳行路线，打印格式如下：<1>(0,0)—(1,2)—(3,3)—(4,1)—(5,3)—(7,2)—(8,4)125 解：按象棋规则，马往右跳行的方向如下表和图所示：水平方向用x表示;垂直方向用y表示。右上角点为x=8,y=4,记为(8,4);用数组tt存放x方向能成行到达的点坐标;用数组t存放y方向能成行到达的点坐标;①以(tt(K),t(k))为起点，按顺序用四个方向试探，找到下一个可行的点(x1,y1);②判断找到的点是否合理(不出界)，若合理，就存入tt和t中;如果到达目的就打印，否则重复第⑴步骤;③如果不合理，则换一个方向试探，如果四个方向都已试过，就退回一步(回溯)，用未试过的方向继续试探。重复步骤⑴;④如果已退回到原点，则程序结束。Pascal程序：ProgramExam66;Constxx:array[1..4]of1..2=(1,2,2,1);yy:array[1..4]of-2..2=(2,1,-1,-2);Varp:integer;t,tt:array[0..10]ofinteger;procedurePrn(k:integer);Vari:integer;Begininc(p);write(‘<‘,p:2,’>‘,’‘:4,’0,0’);fori:=1tokdowrite(‘—(‘,tt[I],’,’,t[I],’)’);writelnEnd;ProcedureSub(k:integer);Varx1,y1,i:integer;Begin125 forI:=1to4doBeginx1:=tt[k-1]+xx[i];y1:=t[k-1]+yy[i];ifnot((x1>8)or(y1<0)or(y1>4))thenBegintt[k]:=x1;t[k]=y1;if(y1=4)and(x1=8)thenprn(k);sub(k+1);end;end;end;Beginp:=0;tt[0]:=0;t[0]:=0;sub(1);writeln(‘From0,0to8,4Allofthewaysare’,p);readlnend.例[6.7]输出自然数1到n所有不重复的排列，即n的全排列。解：①在1～n间选择一个数，只要这个数不重复，就选中放入a数组中;②如果这个数巳被选中，就在d数组中作一个被选中的标记(将数组元素置1);③如果所选中的数已被占用（作了标记），就另选一个数进行试探;④如果未作标记的数都已试探完毕，那就取消最后那个数的标记，退回一步，并取消这一步的选数标记，另换下一个数试探，转步骤①;⑤如果已退回到0，说明已试探全部数据，结束。Pascal程序：ProgramExam67;Varp,n:integer;a,d:array[1..500]ofinteger;Procedureprn(t:integer);Vari:integer;Beginwrite(‘<‘,p:3,’>‘,’‘:10);forI:=1totdowrite(a[I]:4);writeln;end;Procedurepp(k:integer);varx:integer;beginforx:=1tondobegin125 a[k]:=x;d[x]:=1;ifk’,’’:4);write(path[1]:2);forI:=2tokdowrite(’--’,path[i]:2);writelnend;proceduretry(k:byte);varj:byte;begin123456X89101112131415j:=1;repeatpath[k]:=roadnet[path[k-1],j];ifnot(path[k]inb)thenbeginb:=b+[path[k]];ifpath[k]=nthenprn(k)elsetry(k+1);b:=b-[path[k]];end;inc(j);untilroadnet[path[k-1],j]=0end;beginb:=[1];p=0;path[1]:=1;try(2);readlnend.习题[6.2]1.有A,B,C,D,E五本书，要分给张、王、刘、赵、钱五位同学，每人只能选一本。事先让每个人将自己喜爱的书填写在下表中。希望你设计一个程序，打印分书的所有可能方案，当然是让每个人都能满意。ABCDE张YY125 王YYY刘YY赵Y钱YY2.右下图所示的是空心框架,它是由六个单位正方体组成,问:从框架左下外顶点走到右上内顶点共有多少条最短路线?3.城市的街道示意图如右:问从甲地去到乙地可以有多少条最短路线?4.有M×N张(M行,N列)邮票连在一起,但其中第X张被一个调皮的小朋友控掉了。上图是3×5的邮票的形状和编号。从这些邮票中撕出四张连在一起的邮票,问共有多少种这样四张一组的邮票?注:因为给邮票编了序号,所以1234和2345应该看作是不同的两组。5.有分数，，，，，，，，，求将其中若干个相加的和恰好为1的组成方案，并打印成等式。例如：<1>++=1<2>...6.八皇后问题。在8*8的国际象棋盘上摆上8个皇后。要求每行，每列，各对角线上的皇后都不能互相攻击，给出所可能的摆法。125 第七章　数据结构及其应用数字，字符，声音，图像，表格等信息，均可输入计算机中进行处理。在计算机科学中，象这种能输入到计算机中并被计算机程序处理的信息，都可称为数据。数据的基本单位是数据元素。数据之间存在有线性与非线性两种基本的逻辑结构，同时在存储结构上还有顺序和链式之分。数据结构则是研究数据元素的逻辑结构，存储结构和与之有关的各种基本操作的一门学科。作为一个程序设计者，应当掌握好数据结构的有关知识，在解题时针对问题的特点，选择适当的数据结构，并构造算法，编出优美高效的好程序。本章将介绍一些线性的数据结构及其基本操作。第一节　线性表“线性表”是指由有限多个类型相同的数据元素组成的集合，它有以下的特点：(1)有唯一的头结点(即第一个数据元素)和尾结点(即最后一个数据元素)；(2)除结点外，集合中的每个数据元素均只有一个前驱；(3)除尾结点外，集合中的每一个数据元素均只有一个后继。“线性表”是一种运用非常广范的数据结构。例一、某旅馆有100个房间，以1到100编号，第一个服务员来了，他将所有的房门都打开，第二个服务员再把所有编号是2的倍数的房门都关上，第三个服务员对编号是3的倍数的房门原来开的关上，原来关上的打开，此后的第四，五...服务员均照此办理。问第100个服务员走进后，有哪几扇门是开着的。解：Pascal程序：Programlt7_1_1；usescrt；vardoor：array[1..100]ofboolean；1到100号房门状态，false--关，true--开i，j：integer；beginclrscr；fillchar(door，sizeof(door)，true)；第一个服务员打开全部房门fori：=2to100doi表示服务员号码forj：=1to100dividodoor[i*j]：=notdoor[i*j]；对房号为i的倍数的房门进行相反处理write('Thecodeofopeningdooris：')；fori：=1to100doifdoor[i]thenwrite(i，'')；end.125 分析：(1)这里用door[1..100]来存储1到100号房门的开关状态，即是一种线性表，其中：door[1]可以看成是头结点，而door[100]是尾结点；同时由于数组在内存中是按顺序占有一片连续的内存空间，因此这种存储结构即是顺序存储结构。(2)这里用布尔变量true和false分别表示开和关两种状态，对某一房门进行相反处理时只要取反(not)即可，比如：若door[10]为false，notdoor[10]则为true。例二、插入排序：在一个文本文件中存放的N个人的姓名，文本文件的格式为：第一行为N，以下第二至第N+1行分别是N个人的姓名(姓名不重复，由英文字母组成，长度不超过10)，请编一个程序，将这些姓名按字典顺序排列。解：Pascal程序：Programlt7_1_2；usescrt；typepoint=^people；定义结点类型people=recordname：string[10]；name--数据域，存放姓名next：point；next--指针域，存放后继结点的地址end；varhead：point；n：integer；procedureinit；初始化beginnew(head)；head^.next：=nil；定义头结点，初始链表为空end；procedureinsert(p：point)；将P指向的结点插入以head开头的线性表中varq1，q2：point；beginifhead^.next=nilthenhead^.next：=p将P指向的结点插入空链表elsebeginq1：=head；q2：=q1^.next；while(q2<>nil)and(q2^.namenildobeginwriteln(p^.name)；p：=p^.next；end；end；beginclrscr；init；work；print；end.分析：(1)排序有多种方法，插入排序是其中的一种，其原理同摸扑克牌类似：摸到一张牌，把它按大小顺序插入牌中，每一张都如此处理，摸完后，得到的就是一副有序的扑克牌。本题可以用插入排序求解；(2)为了减少移动数据的工作，可以采用链式存储结构。每个结点由两个域构成，数据域(用来存放姓名)和指针域(用来存放后继结点的地址)。如图A是将1，3，6，7按顺序构成一个线性链表的示意图。这样在这个有序表中插入一个5时，只需对指针进行相应地操作即可，如下图B：┌─┬─┐┌─┬─┐┌─┬─┐┌─┬─┐头结点→│1│--→│3│--→│6│--→│7│^│←尾结点└─┴─┘└─┴─┘└─┴─┘└─┴─┘图A┌─┬─┐┌─┬─┐┌─┬─┐┌─┬─┐125 头结点→│1│--→│3│││6│--→│7│^│←尾结点└─┴─┘└─┴┼┘└↑┴─┘└─┴─┘↓┌┘┌─┬┼┐│5││←插入的结点└─┴─┘图B练习一1、求1987乘幂的尾数：M和N是自然数，N>M>=1，而1987^M与1987^N的末三位数相同，求最小的M和N。分析：(1)本题只须记录1987的乘幂的末三位数，故不必高精度计算；(2)用数组a[1..n]存储1987的1至n次幂的末三位数；(3)n的初始值为2，计算1987的n次幂的末三位数，并和1987的1至n-1次幂进行比较，若无相等的，则n=n+1，重复(3)；否则，第一次找到相等的，即是所求的m，n值。2、一个特殊的数列：写出两个1，然后在它们中间插入2成为121，下一步是在任意两个相邻的和数为4的数之间插入3，成为13231；再下一步又在任意两个相邻的和数为4的数之间插入4，成为1432341，...，由键盘输入N(1<=N<=9)，求出用上面方法构造出来的序列，其最后插入的数为N。分析：字符串也可以看做是一个特殊的线性表，本题初始串是11，对应N=1时的情况；然后在串中寻找相应的位置，依次插入2，3，...，K。3、求序列的第300项：把所有3的方幂及互不相等的3的方幂和排列成一个递增序列：1，3，4，9，10，12，13，...，求这个序列的第300项。分析：本题可以用一个线性表来记录这个递增的序列，通过递推可以将整个序列构造出来。方法如下：(1)数组a存放线性表，t为尾指针，b存放3的幂，初始时t=1，b=1；(2)将b放入表尾，尾指针加1；a[t]←b；t←t+1；(3)将b依次与1至t-1的元素相加，按顺序放入表尾；(4)重复(2)，(3)，直至第300项放入表中。4、约瑟夫环(Joseph)编号为1，2，...，N的N个人按顺时针方向围成一圈，每人持有一个密码(正整数)。一开始任选一个正整数作为报数上限值M，从第一个人开始按顺时针方向自1开始报数，报到M时停止，报M的人出列，将他的密码作为新的M值，从他在顺时针方向上的第一个人开始重新从1报数，如此下去，直至所有有人全部出列为止。试设计一个程序求出列的顺序。分析：这是一个数学游戏。N个人围成一圈，依次报数，可以用一个循环链表模拟这一过程。将链表的表尾指向表头，即形成循环链表。从某个人开始报数，报到M125 的人出列，也就是在在循环链表中删除相应的结点，然后依次删除完所有的结点，此时链表为空，头指针与尾指针相等。在具体操作中，要注意删除头结点和尾结点时指针的处理，谨防出错。5、多项式的加法：试编程完成两个一元多项式的加法。分析：大家都知道，两个一元多项式相加实际上就是合并同类项，最后结果一般要求按字母的升幂或降幂排列，比如：(2X^10+4X+1)+(3X^5-4X+2)=2X^10+3X^5+3。那么一元多项式在计算机中如何表示呢?为了节省空间，一个元多项式一般用一个线性表表示，线性表的每一个结点包括两个域：一个用来存放系数，一个用来存放指数，比如，上面相加的两个一元多项式可以分别表示为：┌─┬─┬─┐┌─┬─┬─┐┌─┬─┬─┐│2│10│─→│4│1│─→│1│0│^│└─┴─┴─┘└─┴─┴─┘└─┴─┴─┘┌─┬─┬─┐┌─┬─┬─┐┌─┬─┬─┐│3│5│─→│-4│1│─→│2│0│^│└─┴─┴─┘└─┴─┴─┘└─┴─┴─┘这样两个一元多项式相加就可以看成是归并两个链表。第二节　队列在日常生活中有许多“队列“的例子，如车站售票口买票的队伍，排在前面的人先买到票离开队伍，后来的人则加入队伍的末尾等候买票；其特点是“先进先出”(FirstInFirstOut)或“后进后出”(LastInLastOut)。“队列”是在一端插入，另一端删除的特殊的线性表。进行删除的一端称为“队首”，进行插入的一端称为“队尾”(如下图)；插入也叫入队，删除则叫出队；在对队列进行操作时，一定要注意一头一尾。─┬──┬──┬──┬──┬─出队←│a1│a2│...│an│←入队─┴──┴──┴──┴──┴─↑↑队头队尾例1、有N张牌，记为1，2，...，N，应当怎样排放，才能使：打开第一张是1，然后报两张依次放在末尾；打开上面一张，刚好是2，再依次打开上面一张，刚好是3；如此继续下去，直至打开最后一张是N。写一个程序解决这个问题。解：Pascal程序：Programlt7_2_1；usescrt；vara，b：array[1..1000]ofinteger；i，j，t，h，n：integer；beginclrscr；write('N=')；readln(n)；fori：=1tondoa[i]：=i；a[1]：=1；h：=2；t：=n；b[1]：=1；125 fori：=2tondobeginforj：=1toidobegininc(t)；a[t]：=a[h]；inc(h)；end；b[a[h]]：=i；inc(h)；end；fori：=1tondowrite(b[i]：5)；end.分析：这是一个典型队列的例子，请大家仔细体会在队列操作过程中头指针和尾指针的变化。例2、集合的前N个元素：编一个程序，按递增次序生成集合M的最小的N个数，M的定义如下：(1)数1属于M；(2)如果X属于M，则Y=2*X+1和Z=3*1也属于M；(3)此外再没有别的数属于M。解：Pascal程序：Programlt7_2_1；usescrt；vara，b：array[1..1000]ofinteger；x，ha，hb，t，total，n：integer；beginclrscr；write('N=')；readln(n)；x：=1；a[1]：=1；ha：=1；hb：=1；t：=0；total：=1；whiletotal<=ndobeginwrite(x：5)；inc(t)；a[t]：=2*x+1；b[t]：=3*x+1；ifa[ha]>b[hb]thenbeginx：=b[hb]；inc(hb)；endelsebeginx：=a[ha]；ifa[ha]=b[hb]theninc(hb)；inc(ha)；end；inc(total)；125 end；end.分析：可以用两个队列来存放Y和Z中的数，分别用数组a和数组b存放。然后递推求出第N项，方法如下：(1)令ha和hb分别为队列a和队列b的头指针，它们的尾指针为t。初始时，X=1，ha=hb=t=1；(2)将2*x+1和3*x+1分别放入队列a和队列b的队尾，尾指针加1。即：a[t]←2*x+1，b[t]←3*x+1，t←t+1；(3)将队列a和队列b的头结点进行比较，可能有三种情况：(A)a[ha]>b[hb](B)a[ha]=b[hb](C)a[ha]0)or(hb>0)dobeginifha>0thenx：=ord(a[ha])-48elsex：=0；ifhb>0theny：=ord(b[hb])-48elsey：=0；m[lm]：=x+y+c；c：=m[lm]div10；m[lm]：=m[lm]mod10；inc(lm)；dec(ha)；dec(hb)；125 end；ifc>0thenm[lm]：=celsedec(lm)；write(a，'+'，b，'=')；fori：=lmdownto1dowrite(m[i])；end.2、基数排序：将278，109，063，930，589，184，505，269，008，083利用基数排序法按从小到大的顺序排列。分析：基数排序法是一种基于对关键字进行分配和收集的排序法，常用最低位优先法(LeastSignificantDigitfirst)，简称LSD法。它先从最低位的关键字开始进行排序，然后对次低位关键字进行排序，依此类推，直到对最高位进行排序为止。例如本题，关键字是各位上的数码，从0到9共10个。首先，将需要排序的数放在队列A中，如图：3、有1至2N的自然数，按从小到大的顺序排成一列，对这2N个数进行如下操作：（1）将这2N个数等分成A，B两组，即：A组：1，2，...，N；B组：N+1，N+2，...，2N（2）轮流从A，B两组中按顺序取数：1，N+1，2，N+1，...，N，2N（3）再将取过的数等分为两组，并重复上述操作，直到这2N个数又按从小到大的顺序排好为止。例如：当N=3时，操作如下：初始序列为：1，2，3，4，5，6(1)1，4，2，5，3，6(2)1，5，4，3，2，6(3)1，3，5，2，4，6(4)1，2，3，4，5，6分析：将1至2N的自然数分成两组，用两个队列来模拟上述过程即可。4、有一个数，它的末位数字是N，将N移到这个数的首位，得到的新数恰好是原数的N倍，现输入N的值，求满足条件的最小的数。第三节　栈“栈”是一种先进后出(FirstInLastOut)或后进先出(LastInFirstOut)的数据结构。日常生活中也常能见到它的实例，如压入弹夹的子弹，最先压进去的子弹最后射出，而最后压入的子弹则最先发射出来。“栈”是一种只能在一端进行插入和删除的特殊的线性表，进行插入和删除的一端称为“栈顶”，而不动的一端称为栈底(如下图)。插入的操作也称为进栈(PUSH)，删除的操作也称为出栈(POP)。出栈←─┐┌──进栈││↓│125 ├───┤栈顶→│an│├───┤│...│├───┤│a2│├───┤栈底→│a1│└───┘例1、算术表达式的处理：由键盘输入一个算术表达式(含有+，-，*，/，(，)运算)，且运算结果为整数)，编一程序求该算术表达式的值。分析：表达式的运算是程序设计中一个基本的问题，利用栈求解是一种简单易行的方法，下面介绍的是算符优先法。比如：4+2*3-10/5我们都知道，四则运算的法则是：(1)先乘除后加减，同级运算从左到右；(2)有括号先算括号。因此上例的结果是8。算符优先法需要两个栈：一个是操作数栈，用来存放操作数，记为SN；另一个是操作符栈用来存放运算符，记为SP。具体处理方法如下：(1)将SN，SP置为空栈；(2)从左开始扫描表达式，若是操作数压入SN中；若是操作符则与SP的栈顶操作符比较优先级有两种可能：（a）优先级小于栈顶算符，此时从SN中弹出两个操作数，从SP弹出一个操作符，实施运算，结果压入SN的栈顶。（b）优先级大于栈顶算符，此时将操作符压入SP中。(3)重复操作(2)直至表达式扫描完毕，这时SP应为空栈，而SN只有一个操作数，即为最后的结果。为了方便起见，可以将#作为表达式的结束标志，初始化时在SP的栈底压入#，并将其优先级规定为最低。下面给出的是计算4+2*3-10/5#的示意图步骤SNSP读入字符│说明─────────────────┼──────────1空#4│将4压入SN24#+│将+压入SP34#+2│将2压入SN442#+*│将*压入SP542#+*3│将3压入SN6423#+*-│-的优先级小于*，因此将SN中的3，2弹出，│将SP中的*弹出，将2*3的结果压入SN中746#+-│-的优先级小于其左边的+，因此将SN中的│4，6弹出，将SP中的+弹出，将4+6的结果压│入SN中125 810#-│-压入SP中910#-10│10压入SN中101010#-/│将/压入SP中111010#-/5│将5压入SN中1210105#-/#│#优先级小于/，故SN中的10，5弹出，SP中│的/弹出，将10/5的结果压入SN中13102#-#│#优先级小于-，故SN中的10，2弹出，SP中│的-弹出，将10-2的结果压入SN中148##│#与#相遇，运算结束，SN中的8是最后计算│的结果解：Pascal程序：Programlt7_3_1；usescrt；constnumber：setofchar=['0’..'9']；op：setofchar=['+'，'-'，'*'，'/'，'('，')']；varexpr：string；sp：array[1..100]ofchar；sn：array[1..100]ofinteger；t，tp，n，tn：integer；functioncan_cal(ch：char)：boolean；beginif(ch='#')or(ch=')')or((sp[tp]in['*'，'/'])and(chin['+'，'-']))thencan_cal：=trueelsecan_cal：=false；end；procedurecal；begincasesp[tp]of'+'：sn[tn-1]：=sn[tn-1]+sn[tn]；'-'：sn[tn-1]：=sn[tn-1]-sn[tn]；'*'：sn[tn-1]：=sn[tn-1]*sn[tn]；'/'：sn[tn-1]：=sn[tn-1]divsn[tn]；end；dec(tn)；dec(tp)；end；beginclrscr；write('Expression：')；readln(expr)；write(expr+'=')；125 expr：=expr+'#'；tn：=0；tp：=1；sp[1]：='#'；t：=1；repeatifexpr[t]innumberthenbeginn：=0；repeatn：=n*10+ord(expr[t])-48；inc(t)；untilnot(expr[t]innumber)；inc(tn)；sn[tn]：=n；endelsebeginif(expr[t]='(')ornotcan_cal(expr[t])thenbegininc(tp)；sp[tp]：=expr[t]；inc(t)；endelseifexpr[t]=')'thenbeginwhilesp[tp]<>'('docal；dec(tp)；inc(t)；endelsecal；end；until(expr[t]='#')and(sp[tp]='#')；writeln(sn[1])；end.练习三1、假设一个算术表达式中可包含三种括号：圆括号“(”和“)”；方括号“[”和“]”以及花括号“{”和“}”，且这三种括号可按任意的次序嵌套使用，试利用栈的运算，判别给定的表达式中所含括号是否正确配对出现。分析：如果括号只有一种，比如说是“(”和“)”，则判断是否正确匹配可以这样进行：用一个计数器T来记录左括号与右括号比较的情况，初始时T=0，表达式从左向右扫描，如果遇到左括号则T←T+1，遇到右括号则T←T-1，中间如果出现T<0的情况，说明右括号的个数大于左括号的个数，匹配出错；扫描结束时，如果T<>0，说明左右括号的个数不相等，匹配出错。但本题的括号有三种，这里用栈可以较好地解决，方法如下：(1)将“(”，“[”，“{”定为左括号，“)”，“]”，“}”定为右括号，建一个栈来存放左括号，初始时，栈为空；(2)从左向右扫描表达式，如果是左括号，则将其压入栈中；如果是右括号则（a）栈顶是与该右括号匹配的左括号，则将它们消去，重复(2)125 （b）栈顶的左括号与该右括号不匹配，则匹配错误；(3)扫描结束时，若栈非空，则匹配错误。2、计算四个数：由键盘输入正整数A，B，C，D(1<=A，B，C，D<=10)；然后按如下形式排列：A□B□C□D=24；在四个数字之间的□处填上加，减，乘，除四种运算之一(不含括号)，输出所有满足条件的计算式子。若不能满足条件，则打印“NORESULT!“。分析：A，B，C，D四个数的位置已经固定，因此只需将+，-，*，/四种运算符依次放入三个□中，穷举所有可能的情况，再计算表达式的值即可。第四节　数组数组是大家非常熟悉的，我们可以把它看成是一个长度固定的线性表。本节在研究数组的一些处理方法的同时，还将介绍一些特殊的数组的存储和处理。例一、矩阵填数：给出N*N的矩阵，要求用程序填入下列形式的数：25242322212019181716151413121110987654321解：Pascal程序：Programlt7_4_1；usescrt；constmax=10；vara：array[1..max，1..max]ofinteger；n：integer；procedurework1；vari，j：integer；beginfori：=ndownto1doforj：=ndownto1doa[i，j]：=(n-i)*n+(n-j+1)；end；procedureprint；vari，j：integer；beginwriteln；fori：=1tondobeginforj：=1tondo125 write(a[i，j]：5)；writeln；end；end；beginclrscr；write('N=')；readln(n)；work；print；end.例二、在一个矩阵(N*N)中，若上三角中的元素全部为零，如下图所示：为了节省空间，可用一个一维数组来表示这个矩阵。如右图100可表示成为：(123304)，在此种方法下，编程完成两个230矩阵的加法。304Programlt7_4_2；usescrt；constmax=1000；vara，b，c：array[1..max]ofinteger；n：integer；procedureread_data；vari：integer；beginwrite('N=')；readln(n)；write('A：')；fori：=1ton*(n+1)div2doread(a[i])；write('B：')；fori：=1ton*(n+1)div2doread(b[i])；end；procedureadd；vari：integer；beginfori：=1ton*(n+1)div2doc[i]：=a[i]+b[i]；end；procedureprint；125 vari，j，t：integer；begint：=1；fori：=1tondobeginforj：=1tondoifj>ithenwrite('0'：5)elsebeginwrite(c[t]：5)；inc(t)；end；writeln；end；end；beginclrscr；read_data；add；print；writeln('Pressanykeytoexit...')；repeatuntilkeypressed；end.分析：本题应弄清楚下三角形矩阵中压缩存储及矩阵的加法运算法则。练习四1、数组的鞍点：己知数组X(M，N)中的所有元素为互不相等的整数，编一个程序，先从每一行元素中找出最小的数，然后再从这些最小的数中找出最大的数。打印出这最大的数和它在数组中的下标。2、稀疏矩阵：所谓的稀疏矩阵是指矩阵中的非0元素很少的一种矩阵，对于这种矩阵，可以用一个三元组表来存储非0元素，从而达到压缩存储，节省空间的目的。具体方法如下：假设v是稀疏矩阵A中第i行第j列的一个非0元素，那么该非0元素可以用一个三元组(i，j，v)表示；请编一个程序，从文件中读入一个用三元组表表示的稀疏矩阵，然后输出该稀疏矩阵的转置矩阵。(文件第一行为：M，N，K，分别表示稀疏矩阵的行和列以及非0元素的个数，以下K+1行是K个三元组)3、蛇形填数：给一个N*N矩阵按下列方式填数。13410112591219681318207141721241516222325125 第八章搜索搜索是人工智能的基本问题。在程序设计中，许多问题的求解都需要利用到搜索技术，它是利用计算机解题的一个重要手段。问题的状态可以用图来表示，而问题的求解则往往是从状态图中寻找某个状态，或是寻找从一个状态到另一个状态的路径。这一求解的过程可能并不象解一个一元二次方程那样有现成的方法，它需要逐步探索与总是问题有关的各种状态，这即是搜索。本章将介绍广度优先搜索和深度优先搜索及其递归程序的实现。第一节　深度优先搜索所谓"深度"是对产生问题的状态结点而言的，"深度优先"是一种控制结点扩展的策略，这种策略是优先扩展深度大的结点，把状态向纵深发展。深度优先搜索也叫做DFS法(DepthFirstSearch)。例一、设有一个4*4的棋盘，用四个棋子布到格子中，要求满足以下条件:(1)任意两个棋子不在同一行和同一列上;(2)任意两个棋子不在同一条对角线上。试问有多少种棋局，编程把它们全部打印出来。解：PASCAL程序：Programlt9_1_1;usescrt;constn=4;vara:array[1..n]ofinteger;total:integer;functionpass(x，y:integer):boolean;vari，j:integer;beginpass:=true;fori:=1tox-1doif(a[i]=y)or(abs(i-x)=abs(a[i]-y))thenbeginpass:=false;exit;end;end;procedureprint;vari，j:integer;begininc(total);125 writeln('['，total，']');fori:=1tondobeginforj:=1tondoifj=a[i]thenwrite('O')elsewrite('*');writeln;end;end;proceduretry(k:integer);vari:integer;beginfori:=1tondoifpass(k，i)thenbegina[k]:=i;ifk=nthenprintelsetry(k+1);a[k]:=0;end;end;beginclrscr;fillchar(a，sizeof(a)，0);total:=0;try(1);end.分析:这里要求找出所有满足条件的棋局，因此需要穷举所有可能的布子方案，可以按如下方法递归产生:令D为深度，与棋盘的行相对应，初始时D=1;Proceduretry(d:integer);beginfori:=1to4doif第i个格子满足条件thenbegin往第d行第i列的格子放入一枚棋子;如果d=4则得一方案，打印否则试探下一行，即try(d+1);恢复第d行第i列的格子递归前的状态;end;125 end;这种方法是某一行放入棋子后，再试探下一行，将问题向纵深发展;若本行试探完毕则回到上一行换另一种方案。这样必定可穷举完所有可能的状态。从本题可以看出，前面所说的递归回溯法即体现了深度优先搜索的思想。上面对深度优先算法的描述就是回溯法常见的模式。例二、在6*6的方格中，放入24个相同的小球，每格放一个，要求每行每列都有4个小球(不考虑对角线)，编程输出所有方案。解:Pascal程序:Programlx9_1_2;usescrt;constn=6;varmap:array[1..n，1..n]ofboolean;a:array[1..n]ofinteger;total:longint;procedureprint;vari，j:integer;begininc(total);gotoxy(1，3);writeln('['，total，']');fori:=1tondobeginforj:=1tondoifmap[i，j]thenwrite('*')elsewrite('O');writeln;end;end;proceduretry(k:integer);vari，j:integer;beginfori:=1ton-1doifa[i]<2thenbeginmap[k，i]:=true;inc(a[i]);forj:=i+1tondoifa[j]<2thenbeginmap[k，j]:=true;inc(a[j]);ifk=nthenprint125 elsetry(k+1);map[k，j]:=false;dec(a[j]);end;map[k，i]:=false;dec(a[i]);end;end;beginclrscr;fillchar(map，sizeof(map)，false);fillchar(a，sizeof(a)，0);try(1);end.分析:本题实际上是例一的变形;(1)把枚举每行每列四个小球转化成为每行每列填入2个空格;(2)用两重循环实现往一行中放入两个空格;(3)用数组B记录搜索过程中每列上空格的个数;(4)本题利用深度搜索求解时要注意及时回溯，以提高效率，同时要注意退出递归时全局变量的正确恢复。例三、跳马问题:在半张中国象棋盘上，有一匹马自左下角往右上角跳，今规定只许往右跳，不许往左跳，图(A)给出的就是一种跳行路线。编程计算共有多少种不同的跳行路线，并将路线打印出来。解：PASCAL程序：Programlt9_1_2;usescrt;constd:array[1..4，1..2]ofshortint=((2，1)，(1，2)，(-1，2)，(-2，1));vara:array[1..10，1..2]ofshortint;total:integer;functionpass(x，y，i:integer):boolean;beginif(x+d[i，1]<0)or(x+d[i，1]>4)or(y+d[i，2]>8)thenpass:=falseelsepass:=true;125 end;procedureprint(k:integer);vari:integer;begininc(total);write('['，total，']:(0，0)');fori:=1tokdowrite('->('，a[i，1]，'，'，a[i，2]，')');writeln;end;proceduretry(x，y，k:integer);vari:integer;beginfori:=1to4doifpass(x，y，i)thenbegina[k，1]:=x+d[i，1];a[k，2]:=y+d[i，2];if(a[k，1]=4)and(a[k，2]=8)thenprint(k)elsetry(a[k，1]，a[k，2]，k+1);end;end;beginclrscr;total:=0;try(0，0，1);writeln('Pressanykeytoexit..。');repeatuntilkeypressed;end.分析:(1)这里可以把深度d定为马跳行的步数，马的位置可以用它所在的行与列表示因此初始时马的位置是(0，0);(2)位置在(x，y)上的马可能四种跳行的方向，如图(B)，这四种方向，可以按x，y的增量分别记为(2，1)，(1，2)，(-1，2)，(-2，1)(3)一种可行的跳法是指落下的位置应在棋盘中。练习一:1、有一括号列S由N个左括号和N个右括号构成，现定义好括号列如下:(1)若A是好括号列，则(A)也是;(2)若A和B是好括号列，则AB也是好的。例如:(()(()))是好的，而(()))(()则不是，现由键盘输入N125 ，求满足条件的所的好括号列，并打印出来。解:Pacal程序:Programlx9_1_1;usescrt;varn:integer;total:longint;proceduretry(x，y:integer;s:string);vari:integer;beginif(x=n)and(y=n)thenbegininc(total);writeln('['，total，']'，s);endelsebeginifx0)and(y1>0)and(x1<=n)and(y1<=n)and(a[x1，y1]=0)thenbegina[x1，y1]:=k;ifk=n*nthenprintelsetry(x1，y1，k+1);a[x1，y1]:=0;end;end;end;125 beginclrscr;write('x0，y0=');readln(x0，y0);fillchar(a，sizeof(a)，0);total:=0;a[x0，y0]:=1;try(x0，y0，2);writeln('Total='，total);writeln('Pressanykeytoexit..。');repeatuntilkeypressed;end.5、填数游戏二。有一个M*N的矩阵，要求将1至M*N的自然数填入矩阵中，满足下列条件:(1)同一行中，右边的数字比左边的数字大;(2)同一列中，下面的数字比上面的数字大。打印所有的填法，并统计总数。解:Pascal程序:$Q-，R-，S-Programlx9_1_4;usescrt;constm=3;n=6;vara:array[0..m，0..n]ofinteger;used:array[1..m*n]ofboolean;total:longint;procedureprint;vari，j:integer;begininc(total);gotoxy(1，3);writeln('['，total，']');fori:=1tomdobeginforj:=1tondowrite(a[i，j]:3);writeln;end;end;proceduretry(x，y:integer);vari:integer;beginfori:=x*ytom*n-(m-x+1)*(n-y+1)+1doifnotused[i]and(i>a[x-1，y])and(i>a[x，y-1])then125 begina[x，y]:=i;used[i]:=true;ifi=m*n-1thenprintelsebeginify=nthentry(x+1，1)elsetry(x，y+1);end;used[i]:=false;end;end;beginclrscr;fillchar(used，sizeof(used)，false);fillchar(a，sizeof(a)，0);a[1，1]:=1;a[m，n]:=m*n;used[1]:=true;used[m*n]:=true;try(1，2);writeln('Total='，total);end.分析:本题可以将放入格子中的数字的个数作为深度，先往格子(1，1)放第一个数，然后依次往格子(1，2)，(1，3)，...，(m，n-1)，(m，n)填数字，每填一个数时应如何判断该数是否满足条件，做到及时回溯，以提高搜索的效率是非常关键的。为此需要认真研究题目的特点。根据题意可以知道:在任何一个K*L的格子里，最左上角的数字必定是最小的，而最右下角的数字必定是最大的，故有:(1)格子(1，1)必定是填数1。格子(m，n)必定填数m*n;(2)若A是格子(x，y)所要填入数，则有:x*y<=A<=m*n-(m-x+1)*(n-y+1)+1;6、反幻方:在3*3的方格中填入1至9，使得横，竖，对角上的数字之和都不相等。下图给出的是一例。请编程找出所有可能的方案。┌─┬─┬─┐│1│2│3│├─┼─┼─┤│4│5│8│├─┼─┼─┤│6│9│7│└─┴─┴─┘图一分析:(1)深度优先搜索。用一个二维数组A来存储这个3*3的矩阵。(2)用x表示行，y表示列，搜索时应注意判断放入格子(x，y)的数码是否符合要求;（a）如果y=3，就计算这一行的数码和，其值存放在A[x，4]中，如果该和己出现过，则回溯;125 （b）如果x=3，则计算这一列的数码和，其值存放在A[4，y]中，并进行判断是否需要回溯;（c）如果x=3，y=1还应计算从左下至右上的对角线的数码和;（d）如果x=3，y=3还应计算从左上至右下的对角线的数码和。为了提高搜索速度，可以求出本质不同的解，其余的解可以由这些本质不同的解通过旋转和翻转得到。为了产生非本质解，搜索时做如下规定:（a）要求a[1，1]a[1，2].解：略7、将M*N个0和1填入一个M*N的矩阵中，形成一个数表A，│a11a12...a1n│A=│a21a22...a2n││....…││am1am2...amn│数表A中第i行和数的和记为ri(i=1，2，...，m)，它们叫做A的行和向量，数表A第j列的数的和记为qj(j=1，2，...，m)，它们叫做A的列和向量。现由文件读入数表A的行和列，以及行和向量与列和向量，编程求出满足条件的所的数表A。分析:本题是将例题一一般化，将若干个1放入一个M*N的方阵中，使得每行和每列上的1的个数满足所给出的要求。思路:(1)应该容易判断，若r1+r2+...+rn<>q1+q2+...+qm，则问题无解;(2)将放入1的个数看做是深度，1的位置记为(x，y)，其中x代表行，y代表列，第一个1应从(1，1)开始试探;(3)往k行放入一个1时，若前一个1的位置是(k，y)，则它的位置应在第k行的y+1列至(m-本行还应放入1的个数+1)这个范围内进行试探;若这一列上己放入1的个数小于qy，则该格子内放入一个1，并记录下来;否则换一个位置试探。Programlx9_1_6;usescrt;constmax=20;varm，n，s1，s2:integer;map:array[1..max，1..max]of0..1;a，b，c，d:array[1..max]ofinteger;total:longint;procedureerror;beginwriteln('NOANSWER!');writeln('Pressanykeytoexit..。');repeatuntilkeypressed;halt;end;procedureinit;varf:text;125 fn:string;i，j:integer;beginwrite('Filename:');readln(fn);assign(f，fn);reset(f);readln(f，m，n);s1:=0;s2:=0;fori:=1tomdobeginread(f，a[i]);s1:=s1+a[i];end;fori:=1tondobeginread(f，b[i]);s2:=s2+b[i];end;close(f);ifs1<>s2thenerror;fillchar(map，sizeof(map)，0);fillchar(c，sizeof(c)，0);fillchar(d，sizeof(d)，0);end;procedureprint;vari，j:integer;begininc(total);gotoxy(1，3);writeln('['，total，']');fori:=1tomdobeginforj:=1tondowrite(map[i，j]:3);writeln;end;end;proceduretry(x，y，t:integer);vari，j:integer;beginfori:=y+1ton-(a[x]-c[x])+1doif(map[x，i]=0)and(d[i]0dobegininc(t);b[t]:=r;r:=o[r].ft;end;gotoxy(1，1);writeln('':5，v[1]:5，v[2]:5，v[3]:5);writeln('--------------------');forl:=tdownto1dobeginwrite('['，t-l:2，']');forp:=1to3dowrite(o[b[l]].a[p]:5);writeln;end;halt;end;beginclrscr;witho[1]dobegina[1]:=10;a[2]:=0;a[3]:=0;end;h:=1;t:=2;repeatifis_ans(h)thenprint(h);125 fori:=1to3doifo[h].a[i]>0thenforj:=1to3doif(i<>j)and(o[h].a[j](v[j]-a[j])thenbegina[i]:=o[h].a[i]+a[j]-v[j];a[j]:=v[j];endelsebegina[j]:=a[j]+o[h].a[i];a[i]:=0;end;end;ifnew_node(t)theninc(t);end;inc(h);until(h>t);writeln('NOANSWER!');end.例二、中国盒子问题:给定2*N个盒子排成一行，其中有N-1个棋子A和N-1个棋子B，余下是两个连续的空格，如下图，是N=5的一种布局。┌─┬─┬─┬─┬─┬─┬─┬─┬─┬─┐│A│B│B│A│││A│B│A│B│└─┴─┴─┴─┴─┴─┴─┴─┴─┴─┘移子规则为:任意两个相邻的棋子可移到空格中，且这两个棋子的次序保持不变。目标:全部棋子A移到棋子B的左边。练习二:1、跳棋:跳棋的原始状态如下图(A)，目标状态如下图(B)，其中0代表空格，W代表白子，B代表黑子，跳棋的规则是:(1)任一个棋子可以移到空格中去;(2)任一个棋子可以跳过1个或两个棋子移到空格中去。试编一个程序，用最少的步数将原始状态移成目标状态。┌─┬─┬─┬─┬─┬─┬─┐┌─┬─┬─┬─┬─┬─┬─┐││B│B│B│W│W│W│││W│W│W│B│B│B│└─┴─┴─┴─┴─┴─┴─┘└─┴─┴─┴─┴─┴─┴─┘图A图B125 2、七数码问题:在3*3的棋盘上放有7个棋子，编号分别为1到7，余下两个是空格。与空格相邻的一个棋子可以移到空格中，每移动一次算一步，现任给一个初始状态，要求用最少的步数移成下图所示的目标状态。┌─┬─┬─┐│1│2│3│├─┼─┼─┤│4│5│6│├─┼─┼─┤│7│││└─┴─┴─┘3、N个钱币摆放一排，有的钱币正面朝上(记为1)，有的钱币正面朝下(记为0)，每次可以任意改变K个钱币的状态，即正反面互换。编一个程序判定能否在有限的步数内使得所有钱币正面朝上，若能，请给出步数最少的方案。4、下图A所示的是一个棋盘，放有编号为1到5的5个棋子，如果两个格子中没有线分隔，就表示这两个格子是相通的，编一个程序，用最少的步数将图A的状态移成图B所示的状态(一次移动一子，无论多远算一步)。┌─┬─┬─┐┌─┬─┬─┐│││┌─┼─┼┼─┼─┐┌─┼─┼┼─┼─┐│54321││12345│└─┴─┴─┴─┴─┘└─┴─┴─┴─┴─┘图A图B5、迷宫问题：在一个迷宫中找出从入口到出口的一条步数最少的通路。125 第九章其他常用知识和算法本章将抛砖引玉地探讨一些程序设计中常用的知识及算法，包括图论及其基本应用，动态规划等。要想对这些问题进行深一步地研究，可以系统地学习图论、组合数学、运筹学等书籍。第一节　图论及其基本算法图是另一种有层次关系的非线性的数据结构。在日常生活中有图的许多实例，如铁路交通网，客运航空线示意图，化学结构式，比赛安排表等。下面的如几个例子都可称为图。在实际运用中，我们可以用图来表示事物间相互的关系，从而根据需要灵活地构建数学模型。例如：图(A)，可以用点来表示人，如果两个人相互认识，则在表示这两个人的点之间连一条线。这样从图中我们就可以清楚地看到，这些人之间相互认识的关系。图(B)：可以用点表示城市，若两城市间有连线则表示可在这两城市架设通信线路，线旁的数字表示架设这条线路的费用。图(C)：4个点表示4支足球队，它们进行循环比赛，若甲队胜乙队，则连一条由甲队指向乙队的有向线段。在上面三个例子中，(A)，(B)又可称为无向图，(C)称为有向图，其中(B)是一个有权图。图常用的存储方式有两种，一种是邻接表法，另一种是邻接矩阵法。邻接表表示图有两个部分：一部分表示某点的信息，另一部分表示与该点相连的点。例如：图A的邻接表如下所示：┌─┬─┐┌─┬─┐┌─┬─┐┌─┬─┐│v1│─┼→│v2│─┼→│v3│─┼→│v4│^│└─┴─┘└─┴─┘└─┴─┘└─┴─┘┌─┬─┐┌─┬─┐┌─┬─┐│v2│─┼→│v1│─┼→│v3│^│└─┴─┘└─┴─┘└─┴─┘┌─┬─┐┌─┬─┐┌─┬─┐│v3│─┼→│v1│─┼→│v2│^│└─┴─┘└─┴─┘└─┴─┘┌─┬─┐┌─┬─┐│v4│─┼→│v1│^│125 └─┴─┘└─┴─┘邻接矩阵是用一个二维数组表示图的有关信息，比如图A的邻接矩阵为：┌─┬─┬─┬─┬─┐│点│v1│v2│v3│v4│├─┼─┼─┼─┼─┤│v1│0│1│1│1│├─┼─┼─┼─┼─┤│v2│1│0│1│0│├─┼─┼─┼─┼─┤│v3│1│1│0│0│├─┼─┼─┼─┼─┤│v4│1│0│0│0│└─┴─┴─┴─┴─┘在邻接矩阵中，第i行第j表示图中点i和点j之间是否有连线，若有则值为1，否则为0。比如说：点v1和v2之间有连线，则矩阵的第一行第二列的值为1。而矩阵的第四行行三列的值为0说明图中点v4和v3之间没有连线。图A是一个无向图，它的邻接矩阵是一个关于主对角线对称的矩阵。而有向图的邻接矩阵则不一定是对称的。比如图C的邻接矩阵为：┌─┬─┬─┬─┬─┐│点│v1│v2│v3│v4│├─┼─┼─┼─┼─┤│v1│0│1│1│1│├─┼─┼─┼─┼─┤│v2│0│0│1│1│├─┼─┼─┼─┼─┤│v3│0│0│0│0│├─┼─┼─┼─┼─┤│v4│0│0│1│0│└─┴─┴─┴─┴─┘例一、图的遍历：请编一个程序对下图进行遍历。分析："遍历"是指从图的某个点出发，沿着与之相连的边访问图中的每个一次且仅一次。基本方法有两种：深度优先遍历和广度优先遍历。深度优先和广度优先遍历，与前面所说的树的深度与广度优先遍历是类似的：比下图中，如果从点V1出发，那么：深度优先遍历各点的顺序为：v1，v2，v4，v7，v5，v3，v6，v8。广度优先遍历各点的顺序为：v1，v2，v3，v4，v5，v6，v7，v8。下面是两种方法的Pascal程序：125 解：程序一：深度优先遍历可以仿照前面树的深度优先遍的得出图的深度优先遍历的递归算法，这里是用栈来实现的非递归算法，算法如下：(1)利用一个栈S来记录访问的路径，由于从点1出发，因此初始时S[1]：=1;(2)找一个与栈顶的点相连而又未被访问过的点，如找到，则输出并压入栈顶;如果未找到，则栈顶的点弹出。(3)重复(2)直到所有的点均己输出。如果栈指针为0，而尚的点未输出，说明该图不是一个连通图。Programlt8_1_a;usescrt;constn=8;v：array[1..8，1..8]of0..1=((0，1，1，0，0，0，0，0)，(1，0，0，1，1，0，0，0)，(1，0，0，0，0，1，1，0)，(0，1，0，0，0，0，0，1)，(0，1，0，0，0，0，0，1)，(0，0，1，0，0，0，1，0)，(0，0，1，0，0，1，0，0)，(0，0，0，1，1，0，0，0));varvisited：array[1..n]ofboolean;s：array[1..n]ofbyte;top，p，i，total：integer;find：boolean;beginclrscr;fillchar(visited，sizeof(visited)，false);write('V1');s[1]：=1;visited[1]：=true;total：=1;top：=1;p：=1;repeatfind：=false;fori：=1tondoifnotvisited[i]and(v[p，i]=1)thenbegininc(top);s[top]：=i;p：=i;visited[p]：=true;find：=true;inc(total);write('V'，p，'');break;end;ifnotfindthenbeginp：=s[top];dec(top);end;untiltotal=n;writeln;end.125 程序二：进行广度优先遍历(程序略)例二、最短路径。下图是一个铁路交通图的例子。图中的顶点表示车站，分别用1，2，...，6编号，两个点之间的连线则表示铁路线路，而线旁的数字则表示该条线路的长度。要求编一个程序，求出从车站1至车站6的最短路径。解：本题是在一个有权图中求给定两点之间的最短路径，也许大家会考虑用搜索的方法试探所有可能经过的路线，再从中找出最小者，这样在理论上是成立的，但可能效率不高，这里介绍一种有效的算法，就是Dijkstra算法。PASCAL程序：Programlt8_2;usescrt;constmax=100;varmap：array[1..max，1..max]ofinteger;d：array[1..max，1..2]ofinteger;p：array[1..max]ofboolean;n：integer;procedureinit;vari，j：integer;f：text;fn：string;beginwrite('Filename：');readln(fn);assign(f，fn);reset(f);readln(f，n);fori：=1tondoforj：=1tondoread(f，map[i，j]);close(f);fillchar(p，sizeof(p)，false);fillchar(d，sizeof(d)，0);end;functionfind_min：integer;vari，min，t：integer;beginmin：=maxint;fori：=1tondo125 ifnotp[i]and(d[i，1]>0)and(d[i，1]0)and(d[i，1]=0)or(d[i，1]>d[t，1]+map[t，i])thenbegind[i，1]：=d[t，1]+map[t，i];d[i，2]：=t;end;end;proceduredijkstra;vari，j，t：integer;beginp[1]：=true;t：=1;repeatchange(t);t：=find_min;p[t]：=true;untilp[n];end;procedureprint;vari，t：integer;r：array[1..max]ofinteger;begint：=1;r[1]：=6;whiled[r[t]，2]>0dobeginr[t+1]：=d[r[t]，2];inc(t);end;writeln('FromV1toV6');fori：=tdownto2dowrite('V'，r[i]，'->');writeln('V'，r[1]);writeln('Min='，d[6，1]);end;125 beginclrscr;init;dijkstra;print;end.练习一、1、拓扑排序。有N个士兵(1<=N<=26)，依次编号为A，B，...，Z。队列训练时，指挥官要把士兵从高到矮依次排成一行，但现在指挥官不能直接获得每个人的身高信息，只能获得"P1比P2高"这样的比较结果，记为"P1>P2"，如"A>B"表示A比B高。现从文本文件读入比较结果的信息，每个比较结果在文本文件中占一行。编程输出一种符合条件的排队方案。若输入的数据无解，则打印"NOANSWER!"。例如：若输入为：A>BB>DF>D则一种正确的输出为：ABFD分析：(1)由局部可比信息求得全局可比信息就是拓扑排序。(2)局部信息可以用一个有向图表示。如A>B，则在加一条由点A指向点B的有向线。那么上例可以用右图表示出来。(3)拓扑排序的方法：（a）从图中选一个无前驱的点输出，同时删去由该点出发的所有的有向线;（b）重复a，直至不能进行为止。此时若图中还有点未输出，则问题无解;否则，输出的序列即为一可行方案。注意：在步骤(3)的b中，如果图中还有点未输出，说明图中有一个回路(即环)。这在拓扑排序中是矛盾的。比方说有如右图所示的一个环，其表示出来关于身高的信息是：A>B，B>C，C>A，这显然是矛盾的，因此无解。解：略2、地图四色：用不超过四种的颜色给一个地图染色，使得相邻的两个地区所着的颜色各不相同。3、最小部分树。有一个城市分为N个区，现要在各区之间铺设有线电视线路。任意两个区之间铺设线路的费用如下图所示，其中图的顶点表示各个区，线旁的数字表示铺设该条线路的费用。要求设计一个费用最省的铺线方案使得每一个区均能收看到有线电视分析：(1)这个问题实际上是求图的最小部分树。因为每一个区均能收看到有线电视，所以该图是连通的;又因为要求费用最省，所以该图无圈。(2)求图的最小部分树常用Prim算法(也称加边法)和Kurskal算法(也称破圈法)125 这里介绍的是Prim算法。具体操作如下：（a）去掉图中所有的线，只留下顶点;（b）从图中任意选出一个点加入集合S1，余下的点划入集合S2;（c）从所有连接集合S1与S2的点的线中选一条最短的加入图中，并将该线所连的集合S2中的点从集合S2中删去，加入集合S1中;（d）重复步骤c，直至往图中加入N-1条边(N为顶点的个数)。4、一笔画：编一个程序对给定的图进行一笔画。分析：图的一笔画是指从图的某一个顶点出发，经过图中所有的边一次且仅一次。现由文本文件读入一个图的邻接矩阵，判断该图能否一笔画，若能，则给出一笔画的方法。分析：一笔画是图论中研究得比较早的一个问题，一个图能够一笔画的条件是：(1)该图是一个连通图;(2)该图至多有2个度为奇数的点。这里所说的"度"是指与一个点相连的边的数目，如果边的条数是奇数，则该点的度是奇数，否则是偶数。在一笔画问题中，如果连通图所有的点的度均为偶数，则一笔画时可以从任意一点出发，最后又能回到起点。如果有两个点的度为奇数，则一笔画时，一定是从一个奇数度的点出发，最后到达另一个奇数度的点。此外，在连通图中，奇数度的点总是成对出现的。一笔画所经过的路线又叫欧拉路(如果是回路的话，也叫欧拉回路)。找欧拉路(或回路)可以用Fleury算法，如下：(1)找一个出发点P(如果图中有两个奇数度的点话，任取其一)。(2)找一条与P相连的边，伸展欧拉路(选边的时候应注意，最后再选取断边;断边是：当去掉该边后使得图不连通的边)。(3)将选出的边所连的另一个点取代P，去掉该边，重复(2)，直至经过所有的边。5、哈密尔顿问题。哈密尔顿问题是指在一个图中找出这样的一条路：从一个图的顶点出发，经过图中所有顶点一次且仅一次。象这样的路称为哈密尔顿路。现由文本文件读入一个图的邻接表，判断该图是否有哈密尔顿路，若有则输出。6、图的关节点。如果从一个连通图中删去某点V，使得该图不连通，那么V点就称为该图的一个关节点。现从文本文件中读入一个图的邻接矩阵，试编程找出该图所有的关节点。7、有一集团公司下有N个子公司，各子公司由公路连接，现要在N个子公司中选一个出来成立总装车间，装配各子公司送来的部件，且使得各子公司到总装车间的路程总和最小。125 第二节　动态规划动态规划是近来发展较快的一种组合算法，是运筹学的一个分支，是解决多阶段决策过程最优化的一种数学方法。我们可以用它来解决最优路径问题，资源分配问题，生产调度问题，库存问题，装载问题，排序问题，设备更新问题，生产过程最优控制问题等等。在生产和科学实验当中，有一类活动的过程，可将它分成若干个阶段，在它的每个阶段要作出决策，从而使全局达到最优。当各个阶段决策确定后，就组成一个决策序列，因而也就决定了整个过程的一条活动路线。这种把一个过程看作一个前后相关具有链状结构的多阶段过程就称为多阶段决策过程。所谓动态是指在多阶段决策问题中，各个阶段采取的决策，一般来说是与时间有关的，决策依赖于当前的状态，又随即引起状态的转移，一个决策序列就是在变化的状态中产生，故有"动态"的含义。下面，我们结合最短路径问题来介绍动态规划的基本思想。求下图中点O到点U的最短距离(假设只许往上和往右走)。从点O到点U，可以按经过的路径，分成七个阶段，分别为：O->AB->CDE->FGHJ->KLMN->PQR->ST->U。最短路径有一个重要特性：如果点O经过点H到达点U是一条最短路径，则在这条最优路径上由点H出发到达点U的子路径，是由点H出发到达点U所有可能选择的不同路径的最短路径(证明略)。根据这一特点，寻找最短路径的时候，可以从最后一段开始，用由后向前逐段递推的方法，求出个点到点U的最短路径。如若考虑到从点O到点U的最短路径，也是该路径上个点到点的最短路径，令O点到U点的最短距离为dO，A点到U点的最短距离为dA，...，故有：dO=min{2+dA，1+dB}，dA=min{3+dC，2+dD}，dB=min{2+dD，3+dE}，................dQ=min{5+dT，2+dS}.下面按照动态规划的方法，将上例从最后一段开始计算，由后向前逐步递推移至O点。计算步骤如下：阶段7：从S点或T点到达U点，这时各自只有一种选择，故：125 dS=2;dT=3;阶段6：出发点有P，Q，R三个，其中Q点到达U点有两种选择，或是经过S点，或是经过T点，故：dQ=min{2+dS，5+dT}=min{4，8}=4;dP=min{1+dS}=min{3}=3;dR=min{3+dT}=min{6}=6;阶段5：出发点有K，L，M，N四个，同理有：dK=min{3+dP}=min{6}=6;dL=min{2+dP，4+dq}=min{5，8}=5;dM=min{2+dQ，4+dR}=min{6，10}=6;dN=min{4+dR}=min{10}=10;阶段4：出发点有F，G，H，J四个，同理有：dF=min{2+dK}=min{8}=8;dG=min{1+dK，3+dL}=min{7，8}=7;dH=min{1+dL，1+d}=min{6，7}=6;dJ=min{3+dM，3+dN}=min{9，13}=9;阶段3：出发点有C，D，E三个，同理有：dC=min{2+dF，2+dG}=min{10，9}=9;dD=min{4+dG，2+dH}=min{11，8}=8;dE=min{1+dH，2+dJ}=min{7，11}=7;阶段2：出发点有A，B两个，同理有：dA=min{3+dC，2+dD}=min{12，10}=10;dB=min{2+dD，3+dE}=min{10，10}=10;阶段1：出发点是O，同理有：dO=min{2+dA，1+dB}=min{12，11}=11.由此得到全过程的最短路径是11，并且可以由以上推导过程反推得最短的路线是：O->B->D->H->L->P->S->U;或O->B->E->H->L->P->S->U。从上可以知道，能应用动态规划解决的问题，必须满足最优性原则，动态规划的关键在于正确的写出基本的递推关系式和恰当的边界条件。它需要把问题的过程化成几个互相联系的阶段，恰当的选取状态变量和决策变量及定义最优值函数，从而把一个大问题化成一族同类型的子问题，然后逐个求解。即从边界条件开始，逐段递推寻优，在每一个子问题的求解中，都利用到前面的子问题的最优化结果，依次进行，最后一个子问题的最优解，就是整个问题的最优解。例一、数字三角形：下图给出了一个数字三角形.请编一个程序计算从顶至底的某处的一条路径，使得该路径所经过的数字的总和最大。对于路径规定如下：(1)每一步可沿左斜线向下走或右斜线向下走;⑦(2)1<三角形的行数<=100;③8(3)三角形中的数字为整数0，1，...，99;⑧10输入数据：由文件INPUT.TXT中首先读出的2⑦44是三角形的行数。在例子中INPUT.TXT表示如下：4⑤26557125 38810274445265输出最大的总和。如上例为：30(其路径如图圈的数字)。分析：(1)假设最优路径(即总和最大)为⑦→③→⑧→⑦→⑤，则子路径⑦→③→⑧→⑦必定是从初始点⑦到中间点⑦的所有路径中最优的，否则，如果从初始点⑦到中间点⑦还有另一条的路径更优，假设为⑦→a1→a2→⑦，则新路径⑦→a1→a2→⑦→⑤则优于原来假设的最优路径⑦→③→⑧→⑦→⑤，与假设矛盾。从以上反证法可以清楚地知道：数字三角形问题满足动态规划的最优性原则，可以利用动态规划求解。(2)采用顺推法：记第i行第j列的数字为a(i，j)，从初始点到a(i，j)的最大总和记为f(i，j);则应有第一层上的数字的a(1，1)的最大总和为它本身，即：f(1，1)=a(1，1);以下各层按如下方法递推：f(i，j)=a(i，j)+max{f(i-1，j-1)，f(i-1，j)}(3)用以上方法递推计算完最后一层，最后一中寻最大值即为本题的解.解：Pascal程序：Programlt10_2_1;usescrt;constmax=100;varn：integer;a：array[0..max，0..max]oflongint;procedurework;varf：text;i，j：integer;beginassign(f，'input.txt');reset(f);readln(f，n);fillchar(a，sizeof(a)，0);fori：=1tondoforj：=1toidobeginread(f，a[i，j]);ifa[i-1，j-1]>a[i-1，j]thena[i，j]：=a[i，j]+a[i-1，j-1]elsea[i，j]：=a[i，j]+a[i-1，j];end;close(f);end;125 procedureprint;varmax：longint;i：integer;beginmax：=0;fori：=1tondoifa[n，i]>maxthenmax：=a[n，i];writeln('Max='，max);end;beginclrscr;work;print;end.习题二：1、某工业生产部门根据国家计划的安排，拟将某种高效率的五台机器，分配给所属的A，B，C三个工厂，各工厂若获得这种机器后，可以为国家盈利如下表，问：这五台机器如何分配给各工厂，才能使国家盈利最大?单位：万元PSABC000013542710639111141211125131112其中：p为盈利，s为机器台数。2、己知：f(x)=x1^2+2x2^2+x3^2-2x1-4x2-2x3x1+x2+x3=3且x1，x2，x3均为非负整数。求f(x)的最小值。3、N块银币中有一块不合格，不合格的银币较正常为重，现用一天平找出不合格的来，要求最坏情况不用天平的次数最少。4、某一印刷厂有6项加工任务，对印刷车间和装订车间所需时间见下表：任务J1J2J3J4J5J6印刷车间31252911装订车间8109631时间单位：天完成每项任务都要先去印刷车间印刷，再到装订车间装订。问怎样安排这6项加工任务的加工工序，使得加工总工时最少。5、有一个由数字1，2，...，9组成的数字串(长度不超过200)，问如何M(1<=M<=20)个加号插入这个数字串中，使得所形成的算术表达式的值最小。125 注意：(1)加号不能加在数字串的最前面或最末尾，也不应有两个或两个以上的加号相邻;(2)M保证小于数字串的长度。例如：数字串79846，若需加入两个加号，则最佳方案是79+8+46，算术表达式的值是133。输入格式：从键盘读入输入文件名。数字串在输入文件的第一行行首(数字串中间无空格且不换行)，M的值在输入文件的第二行行首。输出格式：在屏幕上输出最小的和。125