资源描述：
《r-PASCAL语言培训教程》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
全国青少年信息学奥赛培训教程目录第一章初识pascal语言…………………………………………………………………1第二章简单程序设计第一节数据类型、常量、变量……………………………………………………………4第二节赋值语句…………………………………………………………………………7第三节输出语句(WRITE语句)……………………………………………………………8第四节输入语句(READ语句)……………………………………………………………9第五节顺序结构程序设计………………………………………………………………13第三章选择结构的程序设计第一节如果语句(IF语句)………………………………………………………………14第二节IF语句的嵌套……………………………………………………………………17第三节情况语句(CASE语句)……………………………………………………………19第四节综合应用…………………………………………………………………………20第四章循环结构的程序设计第一节循环语句(FOR语句)……………………………………………………………21第二节当语句(WHILE语句)……………………………………………………………23第三节直到循环（REPEAT语句）………………………………………………………24第四节多重循环结构……………………………………………………………………26第五章枚举和子界类型第一节枚举类型…………………………………………………………………………28第二节子界类型…………………………………………………………………………31第六章数组第一节一维数组…………………………………………………………………………33第二节多维数组…………………………………………………………………………38第三节数组类型的应用…………………………………………………………………40第七章函数与过程第一节函数………………………………………………………………………………43第二节过程………………………………………………………………………………47第三节递推算法…………………………………………………………………………53第四节递归算法…………………………………………………………………………54第八章集合和记录类型第一节集合类型…………………………………………………………………………61第二节记录类型…………………………………………………………………………64第三节综合应用实例……………………………………………………………………67第九章文件…………………………………………………………………………………69第十章字符串处理第一节字符与字符串类型………………………………………………………………78第二节字符串的操作……………………………………………………………………79第三节字符串的综合应用………………………………………………………………82第十一章算法初步第一节回溯算法…………………………………………………………………………84第二节贪心算法…………………………………………………………………………88第三节分治算法…………………………………………………………………………90第四节穷举算法…………………………………………………………………………93第五节动态规划…………………………………………………………………………97【友情提示】邮购联系电话：0591-28717456电子信箱:abc@fjclyz.com0 全国青少年信息学奥赛培训教程第一章初识Pascal语言一、Pascal语言概述PASCAL语言也是一种算法语言，它是瑞士苏黎世联邦工业大学的N．沃思(NiklausWirth)教授于1968年设计完成的，1971年正式发表。1975年，对PASCAL语言进行了修改，作为"标准PASCAL语言"。PASCAL语言是在ALGOL60的基础上发展而成的。它是一种结构化的程序设计语言，可以用来编写应用程序。它又是一种系统程序设计语言，可以用来编写顺序型的系统软件（如编译程序）。它的功能强、编译程序简单，是70年代影响最大一种算法语言。二、Pascal语言的特点从使用者的角度来看，PASCAL语言有以下几个主要的特点：⒈它是结构化的语言。PASCAL语言提供了直接实现三种基本结构的语句以及定义"过程"和"函数"(子程序)的功能。可以方便地书写出结构化程序。在编写程序时可以完全不使用GOTO语句和标号。这就易于保证程序的正确性和易读性。PASCAL语言强调的是可靠性、易于验证性、概念的清晰性和实现的简化。在结构化这一点上，比其它（如BASIC,FORTRAN77）更好一些。⒉有丰富的数据类型。PASCAL提供了整数、实型、字符型、布尔型、枚举型、子界型以及由以上类型数据构成的数组类型、集合类型、记录类型和文件类型。此外，还提供了其它许多语言中所没有的指针类型。沃思有一个著名的公式："算法＋数据结构＝程序"。指出了在程序设计中研究数据的重要性。丰富的数据结构和上述的结构化性质，使得PASCAL可以被方便地用来描述复杂的算法，得到质量较高的程序。⒊能适用于数值运算和非数值运算领域。有些语言（如FORTRAN66,ALGOL60）只适用于数值计算，有些语言（如COBOL）则适用于商业数据处理和管理领域。PASCAL的功能较强，能广泛应用于各种领域。PASCAL语言还可以用于辅助设计，实现计算机绘图功能。⒋PASCAL程序的书写格式比较自由。不象FORTRAN和COBOL那样对程序的书写格式有严格的规定。PASCAL允许一行写多个语句，一个语句可以分写在多行上，这样就可以使PASCAL程序写得象诗歌格式一样优美，便于阅读。由于以上特点，许多学校选PASCAL作为程序设计课程中的一种主要的语言。它能给学生严格而良好的程序设计的基本训练。培养学生结构化程序设计的风格。但它也有一些不足之处，如它的文件处理功能较差等。三、Pascal语言程序的基本结构任何程序设计语言都有着一组自己的记号和规则。PASCAL语言同样必须采用其本身所规定的记号和规则来编写程序。尽管不同版本的PASCAL语言所采用的记号的数量、形式不尽相同，但其基本成分一般都符合标准PASCAL的规定，只是某些扩展功能各不相同罢了。下面我们首先来了解Pascal语言的程序基本结构。为了明显起见先举一个最简单的PASCAL程序例子：【例１】输入半径r,求圆的周长和面积。1 全国青少年信息学奥赛培训教程从这个简单的程序可以看到：1.一个PASCAL程序分为两个部分：程序首部和程序体（或称分程序）。2.程序首部是程序的开头部分，它包括：⑴程序标志。用"program"来标识"这是一个PASCAL程序"。PASCAL规定任何一个PASCAL程序的首部都必须以此字开头。在turbopascal语言中，首部也可省略。⑵程序名称。由程序设计者自己定义，如例中的exam1。在写完程序首部之后，应有一个分号。3.程序体是程序的主体，在有的书本里也称"分程序"。程序体包括说明部分（也可省略）和执行部分两个部分。⑴说明部分用来描述程序中用到的变量、常量、类型、过程与函数等。本程序中第二行是"变量说明"，用来定义变量的名称、类型。PASCAL规定，凡程序中用到所有变量、符号常量、数组、标号、过程与函数、记录、文件等数据都必须在说明部分进行定义（或称"说明"）。也就是说，不允许使用未说明先使用。⑵执行部分的作用是通知计算机执行指定的操作。如果一个程序中不写执行部分，在程序运行时计算机什么工作也不做。因此，执行部分是一个PASCAL程序的核心部分。执行部分以"begin"开始，以"end"结束，其间有若干个语句，语句之间以分号隔开。执行部分之后有一个句点，表示整个程序结束。⒋PASCAL程序的书写方法比较灵活。当然，书写不应以节省篇幅为目的，而应以程序结构清晰、易读为目的。在编写程序时尽量模仿本书中例题程序格式。⒌在程序中，一对大括号间的文字称为注释。注释的内容根据需要书写，可以用英语或汉语表示。注释可以放在任何空格可以出现的位置。执行程序时计算机对注释不予理睬。四、TurboPascal语言系统的使用目前，常用的Pascal语言系统有TurboPascal7.0与BorlandPascal7.0，下面我们就来学习TurboPascal7.0系统的使用。1．系统的启动在运行系统目录下的启动程序TURBO.EXE，即可启动系统。屏幕上出现如图1所示的集成环境。2．TurboPascal系统集成环境简介最顶上一行为主菜单。中间蓝色框内为编辑窗口，在它个编辑窗口内可以进行程序的编辑。最底下一行为提示行，显示出系统中常用命令的快捷键，如将当前编辑窗口中文件存盘的命令快捷键为F2，获得系统帮助的快捷键为F1，等等。2 全国青少年信息学奥赛培训教程3．新建程序窗口按F10进行主菜单，选择FILE菜单，执行其中New命令。就可建立一个新的程序窗口（默认文件名为Noname00.pas或Noname01.pas等）。4．程序的输入、编辑在当前程序窗口中，一行一行的输入程序。事实上，程序窗口是一个全屏幕编辑器。所以对程序的编辑与其它编辑器的编辑方法类似，这里不再重复。5.编译程序当程序输入完毕之后，一般要先按Alt+F9（或执行compile菜单中compile命令）对程序进行编译。如果程序有语法错误，则会在程序窗口的第一行处显示第一个红色错误信息。若无语法错误，则窗口正中央会出现一个对话框，提示编译成功。接下来，我们可以运行程序了。如果在编译过程中发现程序有语法错误，系统会提示第一个错误信息。如"'；'expected"，提示缺少分号；"'）'expected"，提示缺少右括号。此时，应有针对性的进行修改。修改后，再重复编译的过程，直到编译成功。6.运行程序程序的运行可以通过按ALT+R打开RUN菜单中的RUN命令，或直接按快捷键CTRL+F9。则可以在用户窗口中输出运行结果。通常在程序运行结束后系统回到Pascal系统的集成环境，因此要查看运行结果，要按ALT+F5将屏幕切换到用户屏幕。下面是该程序的运行结果************************7．程序的保存与打开选择主菜单File中的菜单项Save，或按快捷键F2，在出现的如图的对话框中输入文件名：tu.pas，单击""OK，则程序就以tu.pas为文件名保存在当前目录中了。3 全国青少年信息学奥赛培训教程第二章简单程序设计我们学习了Pascal语言的程序基本结构，在一个程序中，所有的操作都由执行部分来完成，而执行部分又都是由一个个语句组成的。因此，下面开始我们要学习pascal语言的基本语句，并且在学习过程中逐步学会程序设计的基本方法。这节课我们要学习两种语句，即赋值语句与输出语句。在语句学习之前我们要先了解一些pascal语言的基础知识。第一节数据类型、常量、变量一、常量、变量与算术表达式（一）常量在程序运行过程中，其值不能被改变的量称为常量。如123,145.88,'abc',true等。⒈整型常量整型常量采用我们平常使用的十进制整数表示。如138,0,-512等都是整型常量，而18.或18.0都不是整型常量。pascal中有一个标准标识符Maxint，它代表所使用的计算机系统允许的最大整型数，而最小的整型数即为－Maxint-1。TurboPascal还定义了长整数常量MaxLongInt，其值为2147483647。⒉实型常量实型常量包括正实数、负实数和实数零。pascal中表示实型常量的形式有两种。⑴十进制表示法这是人们日常使用的带小数点的表示方法。如0.0,-0.0,+5.61,-8.0,-6.050等都是实型常量，而0.,.37都不是合法的实数形式。⑵科学记数法5科学记数法是采用指数形式的表示方法，如1.25×10可表示成1.25E+05。在科学记数法中，字母“E”表示10这个“底数”，而E之前为一个十进制表示的小数，称为尾数，E之后必须为一个整数，称为“指数”。如-1234.56E+26,+0.268E-5,1E5是合法形式，而.34E12,2.E5,E5,E,1.2E+0.5都不是合法形式的实数。无论实数是用十进制表示法还是科学表示法，它们在计算机内的表示形式是一样的，总是用浮点方式存储。和整数相比，实数能表示的范围大得多，但值得注意的是实数的运算整数的运算速度慢且无法像整数那样精确表示，只能近似表示。⒊字符常量在Pascal语言中，字符常量是由单个字符组成，所有字符来自ASCII字符集，共有256个字符。在程序中，通常用一对单引号将单个字符括起来表示一个字符常量。如：’a’，’A’，’0’等。特殊地，对于单引号字符，则要表示成’’’’。对于ASCII字符集中，按每个字符在字符集中的位置，将每个字符编号为0－255，编号称为对应字符的序号。4.布尔常量布尔型常量仅有两个值，真和假，分别用标准常量名true和false表示。它们的序号分别为1和0。5.符号常量一个常量即可以直接用字面形式表示（称为直接常量，如124,156.8），也可以用一个标识符来代表一个常量，称为“符号常量”。但符号常量必须在程序中的说明部分定义，也就是说先定义，后使用。定义符号常量的一般格式:CONST<常量标识符>=<常量>说明：常量说明部分以关键字const开头,后面的标识符为常量标识符，其中“=”号后的常量为整数、实数、字符、字符串（字符、字符串常量在后面章节中将作介绍）。而且，在常量说明部分可以将几个常量说明成符号常量，共用一个关键字“const”。例如:4 全国青少年信息学奥赛培训教程programex;constvarr,c,s:real;beginwrite('Enterr=');readln(r);c:=2*pi*r;s:=pi*r*r;writeln('c=',c);writeln('s=',s);end.则在本程序中pi和zero作为符号常量,分别代表实数3.14159和整数0。也就是说，常量说明部分既定义了常量名及其值，又隐含定义了常量的类型。关于符号常量，应注意下列几点：⑴符号常量一经定义，在程序的执行部分就只能使用该常量标识符，而不能修改其值。⑵使用符号常量比直接用数值更能体现“见名知义”的原则，也便于修改参数，故一个较好的程序中，应尽量使用符号常量，在执行部分基本上不出现直接常量。（二）变量变量代表了一个存储单元，其中的值是可变的，故称为变量。如游戏“魂斗罗”中玩者命的个数最初为3，当你死了一次命减少一，这里命的个数就是一个变量（或者说命的个数存储在一个存储单元中）。即在程序运行过程中，其值可以改变的量，称为变量。变量有三个要素是：变量名、变量类型、变量值。一个程序中可能要使用到若干个变量，为了区别不同的变量，必须给每个变量（存贮单元）取一个名（称为变量名），该变量（存贮单元）存放的值称为变量的值，变量中能够存放值的类型为变量的类型。例如“魂斗罗”游戏中用于存放“命”的变量,在游戏程序中的名字可取为N,它的类型为整型,游戏初始时这个变量的值为3。1．变量名用一个合法的标识符代表一个变量。如n,m,rot,total等都是合法变量名。在程序中用到的变量必须在说明部分加以说明，变量名应遵循自定义标识符的命名规则，并注意“见名知义”的原则，即用一些有意义的单词作为变量名。“自定义标识符”的命名规则为：自定义标识符必须以字母（包含下划线“_”）开头，后面的字符可以是字母或数字。标识符长度不超过63个字符。2．变量的类型常量是有类型的数据，变量在某一固定时刻用来存放一个常量，因此也应有相应的类型。如整型变量用来存放整数，实型变量用来存放实数。3．变量说明在程序中若要使用变量，变量的名称及类型在程序的变量说明部分加以定义，变量的值则在程序的执行部分中才能赋给。变量说明的一般格式：VAR<变量标识符>[,<变量标识符>]:<类型>;(中括号内部分表示可省,下同)其中VAR是pascal保留字,表示开始一个变量说明段,每个变量标识符或由逗号隔开的多个变量标识,必须在它的冒号后面说明成同一类型。一个程序中，可以说明许多不同类型的变量，每种类型变量之间用分号隔开，共用一个VAR符号。例如:varage,day:integer;amount,average:real;其中，Integer(整型)、Real(实型)是标准标识符，它们是“类型标识符”，代表了确定的类型，如age和day被定义为整型变量，amount和average被定义为实型变量。5 全国青少年信息学奥赛培训教程一旦定义了变量，就确定了它的类型，也就是说，就确定了该变量的取值范围和对该变量所能进行的运算。（三）算术表达式⑴算术表达式的定义pascal语言中的算术表达式是由符合pascal语法规定的运算对象(包括常量、变量、函数)、算术运算符、圆括号组成的有意义的式子。如：A+3.14159*5/8.4-Abs(-1123)⑵算术运算符常用的有以下6个算术运算符：①＋(加)②－(减)③＊(乘)④／(实数除)得到结果为实型.如5.0/2.0=2.5，5/2=2.5，4/2=2.0而不等于2。⑤DIV(整除)DIV它要求除数和被除数均为整型,结果也为整型。如10DIV2=5,10DIV3=3,5DIV10=0.-15DIV4=-3。DIV运算只取商的整数部分，参与DIV运算的两个对象不能为实型。⑥mod(求余)，也只能用于整数运算，结果为整数。例如:10mod4=2,-17mod4=-1,4mod(-3)=1,-4mod3=-1，即amodb=a-(adivb)*b。(3)运算优先顺序如果一个表达式里出现两个或两个以上的运算符,则必须规定它们的运算次序。pascal规定：①表达式中相同优先级的运算符,按从左到右顺序计算;②表达式中不同优先级的运算符,按从高到低顺序计算;③括号优先级最高,从内到外逐层降低;在算术运算中运算符的优先顺序与数学上的四则运算一致，即“先乘除后加减”（注：“MOD”、“DIV”运算的优先级与“＊”、“/”相同）。(四)Pascal标准函数例如：odd(5)为判断自变量是否为奇数，故其值为true。Abs(—3)表示绝对值函数，因此其值为3。Sqr(5)是求平方函数，故其值为25。Sqrt(100)为求平方根函数，故其值为10。Chr(48)为求ASCII码值，故其值为’0’。Trunc(1.999)为截尾函数，故其值为1。注意：（1）round(x)是舍入函数，对于正数，舍小数后，函数值比原值要小，入小数后，函数值比原值要大。负数则正好相反。也就是说，正数舍小入大，负数舍大入小。（2）chr函数和ord函数在字符范围内构成一对反函数，如：chr(ord(‘a’))=’a’ord(chr(61))=61（3）函数和函数构成一对反函数，如：pred(succ(x))=xsucc(pred(x))=x（4）x的n次方利用换底公式表示为exp(n*ln(x))（5）sin(x)、cos(x)的自变量是弧度，若给出的是角度值，转换公式是：弧度值=3.1416/180*角度值（6）ord(true)=1,ord(false)=06 全国青少年信息学奥赛培训教程第二节赋值语句对程序已经创建的变量，如何取值？通常使用赋值语句来给变量提供数据，它具有计算和赋值的功能，程序中所进行的各种运算，大多数是在赋值语句中实现的。（1）格式变量标识符：=表达式（2）语义赋值语句的执行是“先计算，后赋值”。即先计算表达式的值，然后将值赋给变量标识符，具有计算和赋值的双重功能。例如：pi1:=3.1415*6是计算3.1415*6的值，然后将其值赋值给变量pi1.[例1]下面的程序执行后，变量b、c、d的值是多少？programp2_1(input,output);Consta=256;Varb,d:integer;c:real;Beginb:=adiv16;{计算表达式adiv16的值为16，赋值给变量b}c:=a/b;{计算表达式a/b的值，也就是将a的值256除以b的值，结果为16，但是因变量c的类型是实型，所以赋予给变量c的值应为16.0}d:=a;{变量d的值为256}Readln;{暂停}end.（3）说明１.":="称为赋值号，要注意不能与关系运算符“＝”混淆，只有在赋值语句中才使用赋值号。赋值号具有方向性，是将赋值号右边表达式的值计算出来，赋予赋值号左边的变量，所以赋值号的左边只能是变量；常量说明中只能用等号，如例４－１。２.赋值号两边的类型应该相同。只有一点可以例外，那就是当表达式的值为整型时，它可以自动转化成实型后赋给一个实型变量。３.一个赋值语句只能给一个变量赋值。变量可以进行多次赋值，赋值后的变量将在程序中一直保持不变，直到该变量重新赋值成其他的值。４.被赋值的变量本身可以作为因子参与运算，如n:=n-1,i:=i+1,s:=s+x.为了深入理解赋值语句，请看下面的例子：[例２]写出执行下面的程序后，变量a、b的值。programp4_2(input,output);vara,b:integer;begina:=3;b:=a;b:=a+1;a:=a+1;b:=b+1;Readln;{暂停}end.7 全国青少年信息学奥赛培训教程第三节输出语句（WRITE语句）输出语句的作用是将程序运算的结果输出到屏幕或打印机等输出设备。这里通常是指输出到屏幕。（一）输出语句的两种格式1、write语句格式Write(表达式1，表达式2，……)；如:write(1,2,3,4);write(1.2,3.4,5);write(‘MynameisLiping’);2、writeln语句格式:Writeln(表达式1，表达式2，……)或writeln(二)输出语句的功能计算机执行到某一输出语句时，先计算出输出语句中的每个表达式的值，并将每一个表达式的值一个接一个地输出到屏幕上。Write语句与writeln语句格式上都相似，但它们在功能上有所不同，两个语句的区别在于，write语句将其后括号中的表达式一个接一个输出后，没有换行。而writeln语句则在输出各个表达式的值后换行。例如以下两个程序段的输出分别为：write(1,2,3,4);write(5,6);输出为：123456writeln(1,2,3,4);write(5,6);输出为：123456（三）、应用例析[例3]：某仓库5月1日有粮食100吨，5月2日又调进20吨，5月3日卖出库存的3分之二，5月4日又调进库存的3倍粮食，问该仓库从5月1日到5月4日期间每天的粮食分别是多少吨？(输出每天的库存量)分析：在这个问题中，主要要描述从5月1日到5月4日期间仓库的粮食库存量，且易知它是不断变化的。因此我们可以用一个变量A来描述仓库的粮食库存量。程序可写如下：Programex1;VarA:integer;BeginA:=100;Writeln(‘5/1:’,A);A:=A+20;Writeln(‘5/2:’,A);A:=Adiv3;writeln(‘5/3:’,A);A:=A*4;writeln(‘5/4:’,A);Readln;End.[例4]：有三个小朋友甲乙丙。甲有50粒糖果，乙有43粒糖果，丙有13粒糖果。现在他们做一个游戏。从甲开始，将自己的糖分三份，自己留一份，其余两份分别给乙与丙，多余的糖果自己吃掉，然后乙与丙也依次这样做。问最后甲、乙、丙三人各有书多少粒糖果？分析：这个问题中我们关心的是在游戏过程中每个小朋友的糖果个数，且他们所拥有的的糖果数是在变化的。因此可用a,b,c三个变量分别存放甲乙丙三个小朋友在某一时刻所拥有的糖果数。对于每人，分糖后，他的糖果数一定为原来的糖果数div3（因为分糖过程糖果的数目不一定都刚好分完，用整除恰恰8 全国青少年信息学奥赛培训教程可以表示多余的糖自己吃掉）。而其他两人则增加与这个小朋友现在拥有的一样的糖果。程序可写如下：programex2;varA,B,C:integer;beginA:=50;B:=43;C:=13;{初始时每个小朋友所拥有的糖果数}A:=Adiv3;B:=B+A;C:=C+A;{甲小朋友分糖果后，每个人拥有的糖果数变化情况}B:=Bdiv3;A:=A+B;C:=C+B;{乙小朋友分糖果后，每个人拥有的糖果数变化情况}C:=Cdiv3;A:=A+C;B:=B+C;{丙小朋友分糖果后，每个人拥有的糖果数变化情况}writeln('A=',A,'B=',B,'C=',C);{输出结果}readln;end.注：上程序中倒数第三行中’A=’表示一个字符串（即用一对单引号括起来的一串字符），对于字符串，输出字符串的内容（即引号内的所得字符，而引号不输出）。以上程序的运行结果为：A=51B=35C=16【上机练习2.3】1、已知某梯形的上底A=13，下底B=18，高H=9，求它的面积S。2、已知某圆的半径R=139，求该圆的周长C与面积S？3.输入长方形的边长a,b，计算它的面积和周长，输出。第四节输入语句一、写语句的输出格式在pascal语言中输出数据时是可以按照一定格式的，对整数隐含的输出形式为按十进制数形式。对实数的输出，隐含的形式是科学记数法形式（如果不想用科学记数法输出而用小数形式输出，要自己另行定义）。事实上，输出语句中的每个输出项中的表达式之后可以加上格式说明，若输出项后没有加格式说明，则数据按系统隐含的格式输出，还可加上一定格式符号按特定格式输出。⒈隐含的输出格式pascal语言为整型量、实型量、布尔型量和字符串(用一对单引号括起来的字符序列)规定了每种数据所占的宽度(即一个数据占几列)，一个数据所占的宽度称为“场宽”或“字段宽”。系统给出的隐含场宽称为标准场宽。每一种pascal版本给定的标准场宽不尽相同。下表给出标准pascal和pc机上两种pascal版所规定的标准场宽。标准场宽数据类型标准pascalTurbopascalinteger10实际长度real2217布尔型104或5字符串串长串长在TurboPascal系统中，对于整型字符串的输出都是按数据本身长度输出，对于布尔型数据（只有True和False两种值），TRUE为4列，FALSE为5列，一律采用大写输出。而real型数据的输出时，则按17列输出，其中第一列为符号位，正号不显示，后四位为“E±nn”，中间的12列为尾数部分。如：writeln(sqrt(75));则输出□8.6602540379E+00。9 全国青少年信息学奥赛培训教程而writeln(sqrt(81));则输出□9.0000000000E+00。有时，在程序中往往根据实际情况，需要自己定义场宽。⒉指定场宽在写语句中输出项含有格式符号时,就是为了指定场宽。⑴指定单场宽.格式：write(表达式:N)或writeln(表达式:N),其中N为自然数，指定单场宽后，所有数据不再按标准场宽输出，而按指定场宽输出。若数据实际长度小于指定场宽时，则一律“向右靠齐，左留空格”。如write(1234:8);write('abcdef':12);输出结果:□□□□1234□□□□□□abcdef对于标准实型数据指定单场宽时，如果场宽大于标准场宽时，右靠齐按标准场宽格式输出17位，左留空格。若场宽小于标准场宽时，第一位仍为符号位，最后四位仍为“E±nn”，中间部分为尾数显示部分。如果指定的宽度小于8位，则数据按8位格式“*.*E±nn”输出。⑵指定双场宽如果输出项是实数时，如果希望输出的实数不用科学记数法输出,而用小数形式输出,可以用指定双场宽方法输出。双场宽输出格式为：write(实型表达式：m：n)，其中m和n都是自然数，m用以指定整个数据所占的宽度,n指定输出实数的小数位数。如:write(sqrt(75):9:4);输出:□□□8.6602如果双场宽不能满足输出数据的最低要求,系统自动突破指定的场宽限制，按实际长度输出。如:write(sqrt(75):5:4);要使小数点后有4位数字，而总场宽为5，是不可能的(因为还有一个小数点，小数点前面还有一个数字)。它最低限度要有6列，即输出为:8.6602例5写出下列程序在turbopascal下的输出结果.programex;consts='abcdefg';vari:integer;r:real;c:char;b:boolean;begini:=1234;r:=1234.5678;c:='#';b:=true;writeln(i,i:6,i:3);writeln(r,r:12:5,r:8:5);writeln(c,c:5);writeln(s,s:10,s:5);writeln(b,b:5,b:3);end.运行结果如下:1234□□12341234□1.2345678000E+03□□1234.567801234.56780#□□□□#abcdefg□□□abcdefgabcdefgTRUE□TRUETRUE3．应用例析10 全国青少年信息学奥赛培训教程例6：已知A=253，B=43，输出A*B的运算式子。即输出如下：253*43=10879253*43759+101210879分析：对于该问题，我们只要控制好输出时右靠齐即可。即前四行的总宽度一样（例如为12），第五行总宽度比前面少1。第六、七行总宽度与前四行一样。参与程序如下：vara,b:integer;begina:=253;b:=43;writeln(a:10,'*',b,'=',a*b);writeln(a:12);write('*':8);writeln(b:4);writeln('--------':12);writeln(a*3:12);write('+':6);writeln(a*4:5);writeln('--------':12);writeln(a*b:12);end.二、输入语句（读语句）在程序中变量获得一个确定的值，固然可以用赋值语句，但是如果需要赋值的变量较多，或变量的值经常变化，则使用本节介绍的输入语句──读语句，将更为方便。读语句是在程序运行时由用户给变量提供数据的一种很灵活的输入动作，它有两种格式：1.读语句的一般格式：read(<变量名表>);readln[(<变量名表>)];其中变量名表是用逗号隔开的若干个变量名组成的。功能：从标准输入文件(即INPUT,一般对应着键盘)中读入数据,并依次赋给相应的变量。说明：①read和readln是标准过程名,它们是标准标识符。②执行到read或readln语句时，系统处于等待状态，等待用户从键盘上输入数据，系统根据变量的数据类型的语法要求判断输入的字符是否合法。如执行read(a)语句，a是整型变量，则输入的字符为数字字符时是合法的，当输入结束时，则自动将刚接受的一串数字字符转换为整数赋给变量a。③在输入数值型（整型或实型）数据时，数据间要用空格或回车分隔开各个数据，输入足够个数的数据，否则仍要继续等待输入，但最后一定要有回车，表示该输入行结束，直到数据足够，该读语句执行结束，程序继续运行。例7.设a、b、c为整型变量，需将它们的值分别赋以10,20,30,写出对应下列语句的所有可能输入格式。Read(a,b,c);解根据③,即可列出所有可能输入格式(a)10□20□30←┘(b)10□20←┘30←┘(c)10←┘20□30←┘(d)10←┘20←┘30←┘其中“←┘”表示回车键。下同。④read语句与readln语句的第一个区别是：11 全国青少年信息学奥赛培训教程read语句是一个接一个地读数据，在执行完本Read语句(读完本语句中变量所需的数据)后,下一个读语句接着从该数据输入行中继续读数据，也就是说，不换行。如：Read(a,b);Read(c,d);Read(e);如果输入数据行如下:1□2□3□4□5□6□←┘则a,b,c,d,e的值分别为1,2,3,4,5,如果后面无读语句则数据6是多余的，这是允许的。Readln则不同，在读完本Readln语句中变量所需的数据后,该数据行中剩余的数据多余无用，或者说，在读完本Readln语句中变量所需数据后，一定要读到一个回车，否则多余的数据无用。例8设要达到例1同样的目的,但语句改为:readln(a,b);readln(c)则例3中的4种输入格式只有(b)(d)是有效的.⑤readln语句与read语句的第二个区别是:read后一定要有参数表,而readln可以不带参数表,即可以没有任何输入项,只是等待读入一个换行符(回车)。经常用于暂停程序的运行，直到输入一个回车。例9设有下列语句:read(a,b,c);readln(d,e);readln;readln(f,g);其中,所有变量均为整型。再设输入的数据如下：1□2←┘3□4□5□6□7□8←┘9□10←┘11←┘12□13←┘列表给出每个变量的值.分析：可以假想有一“数据位置指针”，每读一个数据后，指针后移到该数据之后，每执行一个readln语句后，指针移到下一个数据行的开头。各变量的值如下表所示。━━━━━━━━━━━━━━━━━━━━━━━━━━变量名abcdefg──────────────────────────值123451112──────────────────────────⑥为了避免可能出现的错误，建议在程序中按下列原则使用读语句：(A)如果没有特殊需要,在一个程序中尽量避免混合使用read语句和readln语句;(B)尽量用readln语句来输入数据,一个数据行对应一个readln语句;(C)由于执行read或readln语句时,系统不会提供任何提示信息,因此,编程时最好在readln语句之前加以适当提示,例如:write('Inputa,b,c:');readln(a,b,c);在执行时,屏幕上显示:Inputa,b,c:■其中,“■”为光标。执行readln语句后,系统处于待待输入状态,只有输入了所需数据后才继续往下执行。【上机练习2.4】1．求长方体的面积，长、宽、高的值由键盘输入。2.读入摄氏温度c，写程序将它转换成华氏温度f输出。已知f=9c/5+323.输入三个字符，然后按输入字符次序输出这三个字符，并输出每个字符的序号，最后按与输入字符相反的次序输出这三个字符。(求序号用ORD函数)4.输入一个三位自然数，把这个数的百位与个位数对调，输出对调后的自然数。5.键盘输入两个小数，经过取整操作后，将其整数部分交换值后输出。12 全国青少年信息学奥赛培训教程第五节顺序结构程序设计到目前为止，我们可以用读、写语句和赋值语句编写一些简单的程序。通过阅读这些程序，可以逐步熟悉pascal程序的编写方法和应遵循的规则，为以后各章的学习打基础。例10、试编一程序,输入一梯形的上底、下底、高,求该梯形的面积。分析:整个程序分为三段:输入、计算、输出。程序中用a,b,h三个变量分别存放梯形的上、下底与高，S存放面积。要而使用这些变量都要先说明，程序的执行部分中先输入上、下底与高，接着求面积S,最后输出结果S。源程序如下:programTixing;{程序首部}vara,b,h,s:real;{程序说明部分}beginwrite('Inputa,b,h:');readln(a,b,h);{程序执行部分}s:=(a+b)*h/2;write('s=',s:10:3);end.例11、某幼儿园里，有5个小朋友编号为1，2，3，4，5，他们按自己的编号顺序围坐在一张圆桌旁。他们身上都有若干个糖果，现在他们做一个分糖果游戏。从1号小朋友开始，将他的糖果均分三份（如果有多余的，则他将多余的糖果吃掉），自己留一份，其余两份分给他的相邻的两个小朋友。接着2号、3号、4号、5号小朋友也这如果做。问一轮后，每个小朋友手上分别有多少糖果。分析：这道问题与第三节中的例4基本一样，只不过这里有5位小朋友，且他们初始时糖果的数目不确定。这里用a,b,c,d,e分别存放5个小朋友的糖果。初始时它们的值改为由键盘输入。其它都与第三节中的例4类似。参考程序如下:programfentang;vara,b,c,d,e:integer;beginwrite(‘PleaseEnterinitnumbers‘);readln(a,b,c,d,e);a:=adiv3;b:=b+a;e:=e+a;{1号均分后，1、2、5号的糖果数变化情况}b:=bdiv3;c:=c+b;a:=a+b;{2号均分后，1、2、3号的糖果数变化情况}c:=cdiv3;b:=b+c;d:=d+c;{3号均分后，2、3、4号的糖果数变化情况}d:=ddiv3;c:=c+d;e:=e+d;{4号均分后，3、4、5号的糖果数变化情况}e:=ediv3;d:=d+e;a:=a+e;{5号均分后，4、5、1号的糖果数变化情况}{输出结果}writeln('a=',a);writeln('b=',b);writeln('c=',c);writeln('d=',d);writeln('e=',e);readln;｛暂停｝end.13 全国青少年信息学奥赛培训教程例12、编一程序求半径为R的圆的周长与面积?分析:程序要先输入半径R,然后求周长c和面积s,最后输出c和s.源程序如下:programcircle;constPI=3.14159;varr,c,s:real;beginwrite('EnterR=');readln(r);c:=2*pi*r;s:=pi*sqr(r);writeln('c=',c:10:2);writeln('s=',s:10:2);end.在程序中，为了输出实型周长C和面积S时,按照小数形式输出,采用了指定双场宽格式。【上机练习2.5】21、从键盘输入a、b、c求一元二次方程ax+bx+c=0的两个实数根(不考虑无解的情况)。2、输出两个自然数相除的商和余数。分析：设被除数、除数、商和余数，分别为A，B，C，D，均为变量，且都是整数类型。题中未给出具体的自然数A、B，可采用键盘输入方式。①给出提示，从键盘输入a,b；②显示两数相除的数学形式；③求出a除以b的商c；④求出a除以b的余数d；⑤紧接等式后面输出显示商和余数。3、加法计算器：编程由键盘输入两个整数a和b，计算出它们的和并输出到屏幕上。4、计算某次考试语文、数学、英语和计算机等四科的总成绩与平均成绩。(请用输入语句从键盘输入各科成绩)5、交换两个变量的值：由键盘输入两个正整数A和B，编程交换这两个变量的值。6、有鸡兔同笼，头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{再用总头数减鸡数算出兔的只数}7、五位好朋友相聚。第一位朋友带来了很多糖块赠送给各位朋友，使每人的糖块在各自原有的基础上翻了一倍；接着第二位好友也同样向每人赠送糖块，他同样使每人的糖块在各人已有的数量上翻了一倍；第三、第四、第五位好友都照此办理。经过这样的赠送之后，每人的糖块恰好都为32块。问各位好友原先的糖块数分别是多少?14 全国青少年信息学奥赛培训教程第三章选择结构的程序设计第一节如果语句（IF语句）在现实生活中，我们每天都要进行根据实际情况进行选择。例如，原打算明天去公园，但如果明天天气不好，将留在家里看电视。所以人也会根据条件进行行为的选择。计算机也会根据不同情况作出各种逻辑判断，进行一定的选择。在这课与下一课中，我们将会发现，我们是通过选择结构语句来实现程序的逻辑判断功能。一、PASCAL中的布尔（逻辑）类型在前面，我们学习了整型(integer)与实型（real）。其中integer型数据取值范围为-32768到32767-3838之间所有整数。而real型数据取值范围为其绝对值在10到10之间的所有实数。它们都是数值型的（即值都为数）。布尔型（Boolean）是一种数据的类型，这种类型只有两种值，即“真”与“假”。1、布尔常量在Pascal语言中“真”用ture表示，“假”用False表示。所以布尔类型只有TRUE与FALSE两个常量。2、布尔变量（BOOLEAN）如果我们将某些变量说明成布尔型，那么这些变量就是布尔变量，它们只能用于存放布尔值（ture或false）。例如，VARA，B：BOOLEAN；3、布尔类型是顺序类型由于这种类型只有两个常量，Pascal语言中规定ture的序号为1，false的序号为0。若某种类型的常量是有限的，那么这种类型的常量通常都有一个序号，我们称这种类型为顺序类型。如前面我们学过的整型（integer），以及后面要学到的字符型（char）都是顺序类型。4、布尔类型的输入与输出a）输出VARA，B：BOOLEAN；BEGINA：=TRUE；B：=FALSE；WRITELN（A，B）；END.TRUEFALSEb）布尔类型变量不能直接用读语句输入布尔类型变量不能通过读语句给它们提供值。事实上，我们可以通过间接方式对布尔变量进行值的输入。例如，以下程序是错误的：vara,b,c:Boolean;beginreadln(a,b,c);{错误语句}writeln(a,b,c);end.二、关系表达式与布尔表达式1、什么是关系表达式用小括号、>、<、>=、<=、=、<>将两个算术表达式连接起来的式子就称为关系表达式（比较式）。如：3+7>8,x+y<10,2*7<=13等都是关系表达式。2、关系表达式的值很显然，这几个关系表达式中第一个是正确的，第三个是错误的，而第二个表达式可能是对的，也可能是错的。所以我们很容易发现，这些表达式的值是“对”的或“不对”的（或者说，是“真”的或“假”的），即关系表达式的值为布尔值。表示该比较式两端式子的大小关系是否成立。如3+2>6是错的，故它的值为FALSE。同样，45>=32是对的,故该表达式的值为true。关系表达式用于表示一个命题。如：“ｍ为偶数”可表示为：ｍmod2=0。“ｎ为正数”可表示为：n>0。15 全国青少年信息学奥赛培训教程3.布尔运算及布尔表达式为了表示更复杂的命题，Pascal还引入三种逻辑运算符：not、and、or。它们分别相当于数学上的“非”、“且”和“或”的意义。这三个运算符的运算对象为布尔量，其中not为单目运算，只有一个运算对象，and与or为双目运算，有两个运算对象。它们的运算真值表如下：AbNotaaandbaorbaxorbfalsefalsetruefalsefalsefalsefalsetruetruefalseturetruetruefalsefalsefalsetruetruetruetruefalsetruetruefalse于是，对于一个关系表达式，或多个关系表达式用布尔运算符连接起来的式子就称为布尔表达式。布尔表达式的值也为布尔值。如果一个表达式里出现两个或两个以上的运算符,则必须规定它们的运算次序。pascal规定：①表达式中相同优先级的运算符,按从左到右顺序计算;②表达式中不同优先级的运算符,按从高到低顺序计算;③括号优先级最高,从内到外逐层降低;对于一个复杂的表达式可能同时包含算术运算、关系运算和逻辑运算以及函数运算。运算的优先顺序为：括号!函数!not!*、/、div、mod、and!+、－、or、xor!关系运算。对于复杂的命题，我们可以用布尔表达式来表示。例如，命题：“m,n都是偶数或都是奇数”可表示为“(mmod2=0)and(nmod2=0)or(mmod2=1)and(nmod2=1)”。三、简单的IF语句１、格式Ⅰ、IF＜布尔表达式＞THEN语句；Ⅱ、IF＜布尔表达式＞THEN语句１ELSE语句２；（注意Ⅱ型IF语句中语句１后无“；”号）２、功能Ⅰ、执行IF语句时，先计算＜布尔表达式＞的值，若为TRUE则执行语句，否则不执行任何操作。Ⅱ、执行IF语句时，先计算＜布尔表达式＞的值，若为TRUE则执行语句１，否则执行语句２；３、示例例1．输入一个整数A，判断是否为偶数。（是输出“YES”否则输出“NO”）。Programex4_2;Vara:integer;BeginWrite(‘a=’);readln(a);If(amod2=0)thenwriteln(‘yes’)Elsewriteln(‘no’);Readln;End.例2．联单华榕超市里卖电池,每个电池８角钱，若数量超过１０个，则可打7.5折。Programex4_3;VarNum:integer;Price,Total:real;BeginWrite(‘Num=’);readln(Num);Price:=0.8;IfNum>10thenPrice:=Price*0.75;Total:=Num*Price;Writeln(‘Total=’,Total:0:2);Readln;End.例3.编写一与电脑猜“红”或“黑”的游戏。分析：用１代表红，０代表黑。先由计算机先出答案，然后再由人猜，猜对输出“YOUWIN”否则输出“YOULOST”。为了模拟猜“红”或“黑”的随意性，程序中需要用到随机函数random(n)。16 全国青少年信息学奥赛培训教程函数是什么呢，例如大家都知道|-2|=2，|58|=58，那么|x|=?。如果我们用y表示|x|，那么.这里y=|x|就是一个函数，也就是说函数是一个关于一个或多个自变量（未知量，如上例中的x）的运算结果。在pascal语言中，系统提供了许多内部函数，其中包括|x|函数，当然它用abs(x)表示。我们如果2要求x-y的绝对值，可以调用内部函数abs(x*x-y)即可求得。Random(n)也是一个内部函数，调用它能得到0~n-1之间的整数（但它不确定的，或说是随机的）。同时由于函数是一个运算结果，所以函数的调用只能出现在表达式中。Programex4_3;VarComputer,People:integer;BeginRandomize;Computer:=random(2);Write(‘Youguess（0－Red1-Black）:’);readln(People);IfPeople=Computerthenwriteln(‘YOUWIN’)Elsewriteln(‘YOULOST’);Readln;End.【上机练习3.1】1.假设邮局规定寄邮件时若每件重量在1公斤以内(含1公斤)，按每公斤1.5元计算邮费，如果超过1公斤时，其超出部分每公斤加收0.8元。请编程序计算邮件收费。2.输入三个正整数，若能用这三个数作为边长组成三角形，就计算并输出该三角形的面积，否则输出Can't。(组成三角形的条件为：任意两边之和大于第三边)3.输入一个三位数的整数，将数字位置重新排列，组成一个尽可大的三位数。例如：输入213，重新排列可得到尽可能大的三位数是321。4、输入一个整数，打印出它是奇数还是偶数。5、某服装公司为了推销产品，采取这样的批发销售方案:凡订购超过100套的，每套定价为50元，否则每套价格为80元。编程由键盘输入订购套数，输出应付款的金额数。6、从键盘读入一个数，判断它的正负。是正数，则输出“+”，是负数，则输出“-”。7、判断两个数a，b，输出较大数的平方值。8、某市的士费起步价8元，可以行使3公里。3公里以后，按每公里1.6元计算，输入的士的公里数，请你计算顾客需付费多少元？第二节IF语句的嵌套四、IF语句的嵌套在if语句中，如果then子句或else子句仍是一个if语句，则称为if语句的嵌套。例4．计算下列函数分析：根据输入的x值，先分成x>0与x≤0两种情况，然后对于情况x≤0，再区分x是小于0，还是等于0。源程序如下:17 全国青少年信息学奥赛培训教程programex;varx:real;y:integer;beginwrtie('Inputx:');readln(x);ifx>0theny:=1｛x>0时，y的值为1｝else｛x≤0时｝ifx=0theny:=0elsey:=-1;writeln('x=',x:6:2,'y=',y);end.显然，以上的程序中，在then子句中嵌套了一个Ⅱ型if语句。当然程序也可以写成如下形式：programex;varx:real;y:integer;beginwrtie('Inputx:');readln(x);ifx>=0thenifx>0theny:=1elsey:=0elsey=-1;writeln('x=',x:6:2,'y=',y);end.但是对于本题，下面的程序是不对的。y:=0;ifx>=0thenifx>0theny:=1elsey:=-1;明显，从此人的程序书写格式可以看出，他想让else与第一个if配对，而事实上，这是错的。因为pascal规定：else与它上面的距它最近的then配对,因此以上程序段的逻辑意义就与题义不符。要使上程序段中else与第一个then配对,应将程序段修改为：y:=0;或者y:=0;ifx>=0ifx>=0thenifx>0thentheny:=1beginelseifx>0thenY:=1;elsey:=-1;endelseY:=-1;【上机练习3.2】1.输入某学生成绩，根据成绩的好坏输出相应评语。如果成绩在90分以上，输出评语：优秀（outstanding）。如果成绩在60分到90分之间，输出评语：良好（satisfactory）。如果成绩不足60分，输出评语：不及格（unsatisfactory）。2.输入三角形的三边，判断它是否是直角三角形。3.给一个不多于三位的正整数，求出它是几位数，并分别打印出各位上的数字。4.对一批货物征收税金。价格在1万元以上的货物征税5%，在5000元以上，1万元以下的货物征税3%，在1000元以上，5000元以下的货物征税2%，1000元以下的货物免税。编写一程序，读入货物价格，计算并输出税金。5．输入三角形的三个边，判断它是何类型的三角形（等边DB？等腰DY？一般YB？）。6．输入三个数，按由大到小顺序打印出来。7．将字母A、B、C、D或a、b、c、d转换成1、2、3、4，其余的字符转换成5。8．输入三个数a，b，c，打印出最大者．18 全国青少年信息学奥赛培训教程第三节情况语句（CASE语句）上面我们知道可以用嵌套的if语句实现多分支的选择结构。但是如果分支越来越多时，用嵌套的if语句实现多分支就显得繁杂。当多分支选择的各个条件由同一个表达式的不同结果值决定时，可以用case语句实现。它的选择过程，很象一个多路开关，即由case语句的选择表达式的值，决定切换至哪一语句去工作。因此在分支结构程序设计中，它是一种强有力的手段。在实现多路径分支控制时，用case对某些问题的处理和设计，比用if语句写程序具有更简洁、清晰之感。(一)、情况语句的一般形式：case<表达式>of<情况标号表1>：语句1;<情况标号表2>：语句2;:<情况标号表n>：语句nend;其中case、of、end是Pascal的保留字，表达式的值必须是顺序类型，它可以是整型、布尔型及以后学习的字符型、枚举型和子界型。情况标号表是一串用逗号隔开的与表达式类型一致的常量序列。语句可以是任何语句，包括复合语句和空语句。(二)、case语句的执行过程先计算表达式（称为情况表达式）的值，如果它的值等于某一个常量（称为情况常量，也称情况标号），则执行该情况常量后面的语句，在执行完语句后，跳到case语句的末尾end处。(三)、说明①情况表达式必须是顺序类型的；②情况常量是情况表达式可能具有的值，因而应与情况表达式具有相同的类型；③情况常量出现的次序可以是任意的；④同一情况常量不能在同一个case语句中出现两次或两次以上；⑤每个分语句前可以有一个或若干个用逗号隔开的情况常量；⑥如果情况表达式的值不落在情况常量的范围内，则认为本case语句无效，执行case语句的下一个语句。turbopascal中增加了一个“否则”的情况,即增加一个else子句，但也是可省的。⑦每个常量后面只能是一个语句或一个复合语句。例5根据x的值，求函数Y的值：分析：利用case语句进行程序设计,关键在于巧妙地构造情况表达式。本例中三种情况可用一个表达式区分出来：Trunc(x/100)。因为x在(0～100)之间时表达式值为0；x在[100,200)时表达式值为1；其余部分可用else子句表示。源程序如下:programex;varx,y:real;beginwrite('Inputx:');readln(x);casetrunc(x/100)of0:y:=x+1;1:y:=x-1;elsey:=0;end;{endofcase}writeln('x=',x:8:2,'y=',y:8:2);end.19 全国青少年信息学奥赛培训教程第四节综合应用例6输入一个年号,判断它是否是闰年。分析：判断闰年的算法是：如果此年号能被400除尽，或者它能被4整除而不能被100整除，则它是闰年。否则，它是平年。源程序如下:varyear:integer;beginwrite('Inputyear:');readln(year);write(year:6);if(yearmod400=0)thenwriteln('isaleapyear.')elseif(yearmod4=0)and(yearmod100<>0)thenwriteln('isaleapyear.')elsewriteln('isnotaleapyear.');end.例7、期未，班长小Q决定将剩余班费X元钱，用于购买若干支钢笔奖励给一些学习好、表现好的同学。已知商店里有三种钢笔，它们的单价为6元、5元和4元。小Q想买尽量多的笔（多鼓励同学），同时他又不想有剩余钱。请您编程序，帮小Q制订出一种买笔的方案。分析：对于以上的实际问题，要买尽量多的笔，易知都买4元的笔肯定可以买最多支笔。因此最多可买的笔为xdiv4支。由于小q要把钱用完，故我们可以按以下方法将钱用完：若买完xdiv4支4元钱的笔，还剩1元，则4元钱的笔少买1支，换成一支5元笔即可；若买完xdiv4支4元钱的笔，还剩2元，则4元钱的笔少买1支，换成一支6元笔即可；若买完xdiv4支4元钱的笔，还剩3元，则4元钱的笔少买2支，换成一支5元笔和一支6元笔即可。从以上对买笔方案的调整，可以看出笔的数目都是xdiv4，因此该方案的确为最优方案。源程序如下：vara,b,c:integer;{a,b,c分别表示在买笔方案中，6元、5元和4元钱笔的数目}x,y:integer;{x，y分别表示剩余班费和买完最多的4元笔后剩的钱}beginwrite(‘x=’);readln(x);{输入x}c:=xdiv4;{4元笔最多买的数目}y:=xmod4;｛求买完c支4元笔后剩余的钱数y｝caseyof0:begina:=0;b:=0;end;1:begina:=0;b:=1;c:=c-1;end;2:begina:=1;b:=0;c:=c-1;end;3:begina:=1;b:=1;c:=c-2;end;end;writeln(‘a=’,a,’b=’,b,’c=’,c);end.【上机练习3.3】1．将字母A、B、C、D或a、b、c、d转换成1、2、3、4，其余的字符转换成5。2.月收入T的所得税税率R如下：TRT<80001000>T>=8005%1500>T>=100010%3000>T>=150015%T>=300020%分别用IF语句和CASE语句编写程序，输入月收入，输出所得税率、应缴所得税款以及扣除所得税后的实际收入。20 全国青少年信息学奥赛培训教程第四章循环结构程序设计在实际应用中，会经常遇到许多有规律性的重复运算，这就需要掌握本章所介绍的循环结构程序设计。在Pascal语言中，循环结构程序通常由三种的循环语句来实现。它们分别为FOR循环、当循环和直到循环。通常将一组重复执行的语句称为循环体，而控制重复执行或终止执行由重复终止条件决定。重复语句是由循环体及重复终止条件两部分组成。第一节循环语句（FOR语句）一、for语句的一般格式for<控制变量>:=<表达式1>to<表达式2>do<语句>;for<控制变量>:=<表达式1>downto<表达式2>do<语句>;其中for、to、downto和do是Pascal保留字。表达式1与表达式2的值称为初值和终值。循环的语句格式：FOR变量名:=初值TO终值DO语句；[例]S：=0；FORI：=1TO10DOS：=S+I；求1+2+3+……+N的和。Writeln（‘S=’，S）；如何编程呢？二、For语句执行过程①先将初值赋给左边的变量（称为循环控制变量）；②判断循环控制变量的值是否已“超过”终值，如已超过，则跳到步骤⑥；③如果末超过终值，则执行do后面的那个语句（称为循环体）；④循环变量递增（对to）或递减（对downto)１；⑤返回步骤②；⑥循环结束，执行for循环下面的一个语句。三、说明①循环控制变量必须是顺序类型。可以是整型、字符型、枚举型等，但不能为实型。②循环控制变量的值递增或递减的规律是：选用to则为递增；选用downto则递减。③所谓循环控制变量的值“超过”终值，对递增型循环，“超过”指大于，对递减型循环，“超过”指小于。④循环体可以是一个基本语句，也可以是一个复合语句。⑤循环控制变量的初值和终值一经确定，循环次数就确定了。但是在循环体内对循环变量的值进行修改，常常会使得循环提前结束或进入死环。建议不要在循环体中随意修改控制变量的值。⑥for语句中的初值、终值都可以是顺序类型的常量、变量、表达式。四、应用举例例1．输出1－100之间的所有偶数。vari:integer;beginfori:=1to100doifimod2=0thenwrite(i:5);end.例2．求N！＝1＊2＊3＊…＊N，这里N不大于10。分析：程序要先输入N，然后从1累乘到N。程序如下：varn,i:integer；｛i为循环变量｝S:longint;｛s作为累乘器｝beginwrite(‘Entern=’);readln(n);{输入n}s:=1;fori:=2tondo｛从2到n累乘到s中｝s:=s*i;writeln(n,’!=’,s);｛输出n!的值｝end.21 全国青少年信息学奥赛培训教程例3、一个两位数x，将它的个位数字与十位数字对调后得到一个新数y，此时y恰好比x大36，请编程求出所有这样的两位数。分析：①用for循环列举出所有的两位数，x为循环变量；②用公式a:=xdiv10分离出x的十位数字；③用公式b:=xmod10分离出x的个位数字；④用公式y:=b*10+a合成新数y；⑤用式子y-x=36筛选出符合条件的数x并输出。Programex34;Vara,b,x,y:integer;BeginForx:=10to99doBegina:=xdiv10;b:=xmod10;y:=b*10+a;ify-x=36thenwriteln(x);End;Readln;End.例4：输入一个自然数，求这个自然数的所有约数之和。分析：输入X——>找出X的所有约数（从1到X逐个判断，看XMODY是否为0），并且累加起来存在S中——>输出S。Programex35;Vars,x,y:integer;BEGINREADLN（X）；S：=0；FORY：=1TOXDOIFXMODY=0THENS：=S+Y；WRITELN（S）；END.2例5、把整数3025从中剪开分为30和25两个数，此时再将这两数之和平方，(30+25)=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；ReadlnEnd.22 全国青少年信息学奥赛培训教程【上机练习4.1】1、计算n！，其中n由键盘输入。2.计算100之内所有的奇数之和。3.求菲波拉契数列a0,a1,a2,……a20。a0=0,a1=1,a2=a1+a0,a3=a2+a1,……,an=an-1+an-2;如0,1,1,2,3,5,8,13,21,……4.求20个数中的最大值和最小值。5.求s=1+2+3+4+…+106.求s=1+1/2+1/3+…+1/1007.按字母表的顺序，从字母A到Z顺序打印输出。8.输入10个数，打印出最大和最小的数。9．编写一个评分程序，接受用户输入10个选手的得分(0-10分)，然后去掉一个最高分和一个最低分，求出某选手的最后得分(平均分)。10.输入30个学生成绩，分别统计成绩在85—100分，60—85分，60分以下，各分数段中的人数。第二节当语句（WHILE语句）一、WHILE循环对于for循环有时也称为计数循环，当循环次数未知，只能根据某一条件来决定是否进行循环时，用while语句或repeat语句实现循环要更方便。while语句的形式为：while<布尔表达式>do<语句>；其意义为：当布尔表达式的值为true时，执行do后面的语句。while语句的执行过程为：①判断布尔表达式的值,如果其值为真,执行步骤2,否则执行步骤4;②执行循环体语句(do后面的语句);③返回步骤1;④结束循环,执行while的下一个语句。说明：这里while和do为保留字，while语句的特点是先判断，后执行。当布尔表达式成立时，重复执行do后面的语句(循环体)。例6、求恰好使s=1+1/2+1/3+…+1/n的值大于10时n的值。分析：“恰好使s的值大于10”意思是当表达式s的前n-1项的和小于或等于10，而加上了第n项后s的值大于10。从数学角度，我们很难计算这个n的值。故从第一项开始，当s的值小于或等于10时，就继续将下一项值累加起来。当s的值超过10时，最后一项的项数即为要求的n。程序如下：vars:real;n:integer;｛n表示项数｝begins:=0.0;n:=0;whiles<=10do｛当s的值还未超过10时｝beginn:=n+1;｛项数加1｝s:=s+1/n;｛将下一项值累加到s｝end;writlen('n=',n);｛输出结果｝end.例7、求两个正整数m和n的最大公约数。分析：求两个正整数的最大公约数采用的辗转相除法求解。以下是辗转的算法：分别用m,n,r表示被除数、除数、余数。①求m/n的余数r.②若r=0,则n为最大公约数.若r≠0,执行第③步.23 全国青少年信息学奥赛培训教程③将n的值放在m中,将r的值放在n中.④返回重新执行第①步。程序如下:programex4_4;varm,n,a,b,r:integer;beginwrite('Inputm,n:');readln(m,n);a:=m;b:=n;r:=amodb;whiler<>0dobegina:=b;b:=r;r:=amodb;end;writeln('Thegreatestcommondivideis:',b:8);end.【上机练习4.2】1、用WHILE循环完成如下3题：①求s=1+2+3+4+…+10②求s=1+1/2+1/3+…+1/100③求π的值。-6已知π/4=1–1/3+1/5–1/7+1/9-……，要求最后一项小于10为止。2、输入任一的自然数A,B,求A,B的最小公倍数。3、Faibonacci数列前几项为:0,1,1,2,3,5,8,…,其规律是从第三项起,每项均等于前两项之和。求前30项,并以每行5个数的格式输出。4、小球从100高处自由落下,着地后又弹回高度的一半再落下。求第20次着地时,小球共通过多少路程?5、鸡兔同笼,头30,脚90,求鸡兔各几只？第三节直到循环（REPEAT语句）用while语句可以实现“当型循环”，用repeat-until语句可以实现“直到型循环”。repeat-until语句的含义是：“重复执行循环，直到指定的条件为真时为止”。直到循环语句的一般形式:Repeat<语句1>;:<语句n>;until<布尔表达式>;其中Repeat、until是Pascal保留字，repeat与until之间的所有语句称为循环体。说明：①repeat语句的特点是：先执行循环，后判断结束条件，因而至少要执行一次循环体。②repeat-until是一个整体，它是一个（构造型）语句，不要误认为repeat是一个语句，until是另一个语句。③repeat语句在布尔表达式的值为真时不再执行循环体，且循环体可以是若干个语句，不需用begin和end把它们包起来，repeat和until已经起了begin和end的作用。while循环和repeat循环是可以相互转化的。例8、校体操队到操场集合,排成每行2人,最后多出1人;排成每行3人,也多出1人;分别按每行排4,5,6人,都多出1人;当排成每行7人时,正好不多。求校体操队至少是多少人?分析：①设校体操队为X人,根据题意X应是7的倍数,因此X的初值为7,以后用inc(x,7)改变X值；②为了控制循环,用逻辑变量yes为真(True)使循环结束；24 全国青少年信息学奥赛培训教程③如果诸条件中有一个不满足,yes的值就会为假(false)，就继续循环。programExam311;varx:integer;yes:boolean;beginx:=0;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进行判断时，都得到“通过”（此处不赋假值）才能保持真值。例9、求1992个1992的乘积的末两位数是多少？分析：积的个位与十位数只与被乘数与乘数的个位与十位数字有关，所以本题相当于求1992个92相乘，而且本次的乘积主下一次相乘的被乘数，因此也只需取末两位参与运算就可以了。Pascal程序：Programex313;vara,t:integer;Begina:=1;t:=0;repeatt:=t+1;a:=(a*92)mod100;untilt=1992;writeln(a);Readln;End.以上我们已介绍了三种循环语句。一般说来，用for循环比较简明，只要能用for循环，就尽量作用for循环。只在无法使用for循环时才用while循环和repeat-until循环，而且while循环和repeat-until循环是可以互相替代的。for循环在大多数场合也能用whiel和repeat-until循环来代替。一般for循环用于有确定次数循环，而while和repeat-until循环用于未确定循环次数的循环。【上机练习4.3】1、用REPEAT循环完成如下3题：①求s=1+2+3+4+…+10②求s=1+1/2+1/3+…+1/100③求π的值。-6已知π/4=1–1/3+1/5–1/7+1/9-……，要求最后一项小于10为止。2.读一组实数,遇零终止,打印其中正、负数的个数及各自的总和。357-73.计算sin（x）=X-X/3！+X/5！-X/7！+……直到最后一项绝对值小于10时停止计算，x由键盘输入。4.用辗转相除法求两个自然数的最大公约数。5.找出被2、3、5除时余数为1的最小的十个数。6.将一根长为369cm的钢管截成长为69cm和39cm两种规格的短料。在这两种规格的短料至少各截一根的前提下,如何截才能余料最少。25 全国青少年信息学奥赛培训教程第四节多重循环结构当一个循环的循环体中又包含循环结构程序时，我们就称之为循环嵌套。例10、求1!+2!+…+10!的值。分析：这个问题是求10自然数的阶乘之和，可以用for循环来实现。程序结构如下：forn:=1to10dobegin①N!的值!t②累加N!的值tend显然,通过10次的循环可求出1!,2!…,10!,并同时累加起来,可求得S的值。而求T=N!,又可以用一个for循环来实现:t=1;forj:=1tondot:=t*j;因此,整个程序为:programex4_5;vart,s:real;i,j,n:integer;beginS:=0;forn:=1to10dobegint:=1;forj:=1tondot:=t*j;S:=S+t;end;writeln(‘s=’,s:0:0);end.以上的程序是一个二重的for循环嵌套。这是比较好想的方法，但实际上对于求n!，我们可以根据求出的(n-1)!乘上n即可得到，而无需重新从1再累乘到n。程序可改为：programex4_5;vart,s:real;i,j,n:integer;beginS:=0;t:=1;forn:=1to10dobegint:=t*n;S:=S+t;end;writeln(‘s=’,s:0:0);end.显然第二个程序的效率要比第一个高得多。第一程序要进行1+2+…+10=55次循环，而第二程序进行10次循环。如题目中求的是1！＋2！＋…＋1000！，则两个程序的效率区别更明显。例11、一个炊事员上街采购,用500元钱买了90只鸡,其中母鸡一只15元,公鸡一只10元,小鸡一只5元,正好把钱买完。问母鸡、公鸡、小鸡各买多少只？分析：设母鸡I只,公鸡J只,则小鸡为90-I-J只,则15*I+10*J+(90-I-J)*5=500,显然一个方程求两个未知数是不能直接求解。必须组合出所有可能的i,j值，看是否满足条件。这里I的值可以是0到33，J的值可以0到50。源程序如下：programrex4_6;vari,j,k:integer;beginfori:=1to33doforj:=1to50do26 全国青少年信息学奥赛培训教程begink:=90-i-j;if15*i+10*j+5*k=500thenwriteln(i:5,j:5,k:5);end;end.例12、求100－200之间的所有素数。分析：我们可对100－200之间的每一整数进行判断，判断它是否为素数，是则输出。而对于任意整数i，根据素数定义，我们从2开始，到，找i的第一个约数。若找到第一个约数，则i必然不是素数。否则i为素数。源程序如下：programrex4_7;varI,x:integer;beginfori:=100to200dobeginx:=2;while(x<=trunc(sqrt(i)))and(imodx<>0)dobeginx:=x+1;end;ifx>trunc(sqrt(i))thenwrite(i:8);end;end.【上机练习4.4】1.求s=1!+2!+3!+…+10!2.求s=1+1/2!+1/3!+…+1/10!123N3.求s=1+2+3+..+N4．把一张一元钞票换成一分，二分和五分的硬币，每种至少一枚。问有哪几种换法？5．输入一个整数，若是素数，输出“YES”，否则输出“NO”6．任给一个自然数n，求出这个自然数不同因数的个数。如：n=6时，因为1，2，3，6这四个数均是6的因数，故输出为total=4。7．输入二个正整数，求出它们的最大公约数和最小公倍数。8．输入一列图形（字母金字塔）aababc..abc……yz9．1-100之间的所有素数（素数是大于1，且除1和它本身外，不能被任何其它整数所整除的整数）。(4.28)10.哥德巴赫猜想（任何充分大的偶数都可由两个素数之和表示）。将4-100中的所有偶数分别用两个素数之和表示。输出为：4=2+26=3+3….100=3+9711．某人想将手中的一张面值100元的人民币换成10元、5元、2元和1元面值的票子。要求换正好40张，且每种票子至少一张。问：有几种换法？应适当考虑减少重复次数。12．百鸡问题：一只公鸡值5元，一只母鸡值3元，而1元可买3只小鸡。现有100元钱，想买100只鸡。问可买公鸡、母鸡、小鸡各几只？13、编写一程序，验证角谷猜想。所谓的角谷猜想是：“对于任意大于1的自然数n，若n为奇数，则将n变为3*n+1，否则将n变为n的一半。经过若干次这样的变换，一定会使n变为1。”14．有一堆100多个的零件，若三个三个数，剩二个；若五个五个数，剩三个；若七个七个数，剩五个。请你编一个程序计算出这堆零件至少是多少个？27 全国青少年信息学奥赛培训教程第五章枚举和子界类型在前面几章中我们用到了整型、实型、布尔型、字符型的数据。以上数据类型是由pascal规定的标准数据类型，只要写integer,real,boolean,char,pascal编译系统就能识别并按这些类型来处理。pascal还允许用户定义一些类型，这是其它一些语言所没有的，这就使得pascal使用灵活、功能丰富。第一节枚举类型一、枚举类型随着计算机的不断普及，程序不仅只用于数值计算，还更广泛地用于处理非数值的数据。例如，性别、月份、星期几、颜色、单位名、学历、职业等，都不是数值数据。在其它程序设计语言中，一般用一个数值来代表某一状态，这种处理方法不直观，易读性差。如果能在程序中用自然语言中有相应含义的单词来代表某一状态，则程序就很容易阅读和理解。也就是说，事先考虑到某一变量可能取的值，尽量用自然语言中含义清楚的单词来表示它的每一个值，这种方法称为枚举方法，用这种方法定义的类型称枚举类型。枚举类型是一种很有实用价值的数据类型，它是pascal一项重要创新。(一）枚举类型的定义枚举类型是一种自定义类型，要使用枚举类型当然也要先说明枚举类型。枚举类型的一般格式:(标识符1,标识符2,…,标识符n)说明：①括号中的每一个标识符都称为枚举元素或枚举常量。②定义枚举类型时列出的所有枚举元素构成了这种枚举类型的值域（取值范围），也就是说，该类型的变量所有可能的取值都列出了。例如，下列类型定义是合法的：typedays=(sun,mon,tue,wed,thu,fri,sat);colors=(red,yellow,blue,white,black,green);而下列类型定义是错误的(因为枚举元素非标识符):typecolortype=('red','yellow','blue','white');numbers=(1,3,5,7,9);ty=(for,do,while);（二）枚举类型变量定义了枚举类型，就可以把某些变量说明成该类型。如：varholiday,workday:day;incolor:colors;也可以把变量的说明与类型的定义合并在一起,如:varholiday,workday:(sun,mon,tue,wed,thu,fri,sat);incolor:(red,yellow,blue,white,black,green);（三）枚举类型的性质⒈枚举类型属于顺序类型根据定义类型时各枚举元素的排列顺序确定它们的序号，第一个枚举元素的序号为0。例如：设有定义：typedays=(sun,mon,tue,wed,thu,fri,sat);则:ord(sun)=0,ord(mon)=1,ord(sat)=6;succ(sun)=mon,succ(mon)=tuesucc(fri)=sat;pred(mon)=sun,pred(tue)=mon,pred(sat)=fri。应注意的是：枚举类型中的第一个元素无前趋，最后一个元素无后继。⒉对枚举类型只能进行赋值运算和关系运算一旦定义了枚举类型及这种类型的变量，则在语句部分只能对枚举类型变量赋值，或进行关系运算，不能进行算术运算和逻辑运算。在枚举元素比较时，实际上是对其序号的比较。当然，赋值或比较时，应注意类型一致。例如，设程28 全国青少年信息学奥赛培训教程序有如下说明：typedays=(sun,mon,tue,wed,thu,fri,sat);colors=(red,yellow,blue,white,black,green);varcolor:colors;weekday:days;则下列比较或语句是合法的:weekday:=mon;ifweekday=sunthenwrite('rest');weekday<>sun而下面比较或语句是不合法的:mon:=weekday;mon:=1;ifweekday=sunorsatthenwrite('rest');sun>redweekday<>color⒊枚举变量的值只能用赋值语句来获得也就是说，不能用read(或readln)读一个枚举型的值。同样，也不能用write(或writeln)输出一个枚举型的值。如write(red)是非法的，会发生编译错误。千万不要误认为，该语句的结果是输出“red”三个字符。但对枚举数据的输入与输出可通过间接方式进行。输入时，一般可输入一个代码，通过程序进行转换，输出时，也只是打印出与枚举元素相对应的字符串。这在后面的例题中将有使用示例。⒋同一个枚举元素不能出现在两个或两个以上的枚举类型定义中。如:typecolor1=(red,yellow,white);color2=(blue,red,black);是不允许的，因为red属于两个枚举类型。四、枚举类型应用举例例1：现有四种水果：苹果、橘子、香蕉、菠萝。从四种水果中任取三种，不能重复和不计顺序。编程列出一切组合。（设四种水果：苹果-aplle；橘子-orange；香蕉-banana；菠萝-pineapple）programxx;（解法一）typefruit=(apple,orange,banana,pineapple);vari,j:fruit;beginfori:=appletopineappledobeginforj:=appletopineappledoifi<>jthenbegincasejofapple:write('apple':12);orange:write('orange':12);banana:write('banana':12);pineapple:write('pineapple':12);end;end;writeln;end;readln;end.programfruit2;（解法二）vari,j,k,p,l:integer;begin29 全国青少年信息学奥赛培训教程fori:=1to2doforj:=i+1to3dofork:=j+1to4dobeginforl:=1to3dobegincaselof1:p:=i;2:p:=j;3:p:=k;end;casepof1:write('apple':12);2:write('orange':12);3:write('banana':12);4:write('pineapple':12);end;end;writeln;end;end.例2、一周七天用sun,mon,tue,wed,thu,fri,sat表示，要求利用枚举类型编程：当输入星期几的数字,能输出它的后一天是星期几(也用英文表示)。源程序如下：programex6_1;typeweek=(sun,mon,tue,wed,thu,fri,sat);vari:integer;day,sucday:week;beginwrite('Whatdateisit');readln(i);caseiof{根据输入i转换成枚举型}1:day:=mon;2:day:=tue;3:day:=wed;4:day:=thu;5:day:=fri;6:day:=sat;7:day:=sun;end;if(day=sat)thensucday:=sunelsesucday:=succ(day);{计算明天sucday}write('Thenextdayis');{输出明天是星期几}casesucdayofsun:writeln('sunday');mon:writeln('monday');tue:writeln('tuesday');wed:writeln('wednesay');thu:writeln('thursday');fri:writeln('friday');sat:writeln('saturday');end;end.评注：程序中变量day、sucday分别表示今天、明天。30 全国青少年信息学奥赛培训教程第二节子界类型如果我们定义一个变量i为integer类型，那么i的值在微型机系统的pascal中,使用2字节的定义表示法,取值范围为-32768～32767。而事实上，每个程序中所用的变量的值都有一个确定的范围。例如，人的年龄一般不超过150，一个班级的学生不超过100人，一年中的月数不超过12，一月中的天数不超过31，等等。如果我们能在程序中对所用的变量的值域作具体规定的话，就便于检查出那些不合法的数据，这就能更好地保证程序运行的正确性。而且在一定程度上还会节省内存空间。子界类型就很好解决如上问题。此外，在数组的定义中，常用到子界类型，以规定数组下标的范围，上一章有关数组知识中我们已用到。（一）子界类型定义子界类型的一般格式：<常量1>..<常量2>说明:①其中常量1称为子界的下界,常量2称为子界的上界。②下界和上界必须是同一顺序类型（该类型称为子界类型的基类型），且上界的序号必须大于下界的序号。例如，下列说明：typeage=0.5..150;letter=0..'z';let1='z'..'a';都是错误的。③可以直接在变量说明中定义子界类型。如：typeletter='a'..'d';varch1,ch2:letter;可以合并成:varch1,ch2:'a'..'d';当然，将类型定义和变量定义分开，则更为清晰。（二）子界类型数据的运算规则⒈凡可使用基类型的运算规则同样适用该类型的子界类型。例如，可以使用整型变量的地方，也可以使用以整型为基类型的子界类型数据。⒉对基类型的运算规则同样适用于该类型的子界类型。例如，div，mod要求参加运算的数据为整,因而也可以为整型的任何子界类型数据。3.基类型相同的不同子界类型数据可以进行混合运算。例如：设有如下说明：typea=1..100;b=1.1000;c=1..500;varx:a;y:b;t:c;z:integer;则下列语句也是合法的：Z:=Sqr(x)+y+t;下列语句:t:=x+y+z;当X+Y+Z的值在1～500范围内时是合法的，否则会出错。（三）子界类型应用举例例3、利用子界类型作为情况语句标号，编一个对数字，大小写字母和特殊字符进行判别的程序。源程序如下：programcas;varc:char;beginreadln(c);casecof'0'..'9':writeln('digits');'A'..'Z':writeln('UPPER-CASELETTERS');31 全国青少年信息学奥赛培训教程'a'..'z':writeln('lower-caseletters');eslewriteln('specialcharactors');end;end.例4、使用子界型情况语句，当输入月、日、年(10301986)，输出30Oct1986。源程序如下:programex6_3;varmonth:1..12;date:1..31;year:1900..1999;beginwrite('Enterdate(mm-dd-yy):');readln(month,date,year);write(date);casemonthof1:write('Jan':5);2:write('Feb':5);3:write('Mar':5);4:write('Apr':5);5:write('May':5);6:write('Jun':5);7:write('Jul':5);8:write('Aug':5);9:write('Sep':5);10:write('Oct':5);11:write('Nov':5);12:write('Dec':5);end;writeln(year:7);end.枚举类型和子界类型均是顺序类型，在前面一章数组的定义时，实际上我们已经用到了子界类型，数组中的下标类型确切地讲可以是和枚举类型或子界类型，大多数情况下用子界类型。如有如下说明：typecolor=(red,yellow,blue,white,black);vara:array[color]ofinteger;b:array[1..100]ofcolor;都是允许的。【上机练习5.1】1、变量s已定义如下：vars(knife,rule,pen,rubber)且s中已有值，试写一程序，输出s中的值。2、定义枚举类型monthtype表示十二个月，输入1-12中的某一个数，输出对应月份的英文缩写和表示下一个月的数字。如输入：6输出：junnextmonth:73、由五个字符组成一个字符串，规定前四个字符为小写字母，第五个字符为数字，问有多少种排列方法。4、类型定义typeren=’A’..’F’用A至F表示6个人，输出6个人相互握手的各种情况，并统计握手的次数。5、从红(red)、黄(yellow)、兰(blue)、白(white)、黑(black)五种颜色的球中，任取三种不同颜色的球，求所有可能的取法？6、一家水果店出售4种水果，每千克价格分别是：苹果1.15元，桔子1.20元，香蕉0.95元，菠萝0.85元。编一程序使售货员主要从键盘上打入货品的代码及重量，计算机将显示货品名、单价、重量及总价。货品代码为苹果1，桔子2，香蕉3，菠萝4。32 全国青少年信息学奥赛培训教程第六章数组第一节一维数组一、为什么要使用数组例1输入50个学生的某门课程的成绩，打印出低于平均分的同学号数与成绩。【问题分析】在解决这个问题时，虽然可以通过读入一个数就累加一个数的办法来求学生的总分，进而求出平均分。但因为只有读入最后一个学生的分数以后才能求得平均分，且要打印出低于平均分的同学，故必须把50个学生的成绩都保留下来，然后逐个和平均分比较，把高于平均分的成绩打印出来。如果，用简单变量a1，a2,…，a50存放这些数据，可想而知程序要很长且繁。要想如数学中使用下标变量ai形式表示这50个数，则可以引入下标变量a[i]。这样问题的程序可写为：tot:=0;{tot表示总分}fori:=1to50do｛循环读入每一个学生的成绩，并累加它到总分｝beginread(a[i]);tot:=tot+a[i];end;ave:=tot/50;｛计算平均分｝fori:=1to50doifa[i]=<类型1>;<标识符2>=<类型2>;:<标识符n>=<类型n>;其中type是Pascal保留字,表示开始一个类型定义段。在其后可以定义若干个数据类型定义。<标识符>是为定义的类型取的名字,称它为类型标识符。类型定义后，也就确定了该类型数据取值的范围，以及数据所能执行的运算。（2）一维数组类型的定义一维数组类型的一般格式：array[下标1..下标2]of<基类型>;说明：其中array和of是pascal保留字。下标1和下标2是同一顺序类型，且下标2的序号大于下标1的序号。它给出了数组中每个元素(下标变量)允许使用的下标类型，也决定了数组中元素的个数。基类型是指数组元素的类型，它可以是任何类型，同一个数组中的元素具有相同类型。因此我们可以说，数组是由固定数量的相同类型的元素组成的。再次提请注意：类型和变量是两个不同概念，不能混淆。就数组而言，程序的执行部分使用的不是数组类型（标识符）而是数组变量（标识符）。一般在定义数组类型标识符后定义相应的数组变量，如：typearraytype=array[1..8]ofinteger;vara1,a2:arraytype;其中arraytype为一个类型标识符,表示一个下标值可以是1到8,数组元素类型为整型的一维数组；33 全国青少年信息学奥赛培训教程而a1,a2则是这种类型的数组变量。也可以将其合并起来：vara1,a2:array[1..8]ofinteger;当在说明部分定义了一个数组变量之后,pascal编译程序为所定义的数组在内存空间开辟一串连续的存储单元。例如，设程序中有如下说明：typerowtype=array[1..8]ofinteger;coltype=array['a'..'e']ofinteger;vara:rowtype;b:coltype;2、一维数组的引用当定义了一个数组，则数组中的各个元素就共用一个数组名(即该数组变量名)，它们之间是通过下标不同以示区别的。对数组的操作归根到底就是对数组元素的操作。一维数组元素的引用格式为：数组名[下标表达式]说明：①下标表达式值的类型,必须与数组类型定义中下标类型完全一致,并且不允许超越所定义的下标下界和上界。②数组是一个整体，数组名是一个整体的标识，要对数组进行操作，必须对其元素操作。数组元素可以象同类型的普通变量那样作用。如:a[3]:=34;是对数组a中第三个下标变量赋以34的值。read(a[4]);是从键盘读入一个数到数组a第4个元素中去。特殊地,如果两个数组类型一致,它们之间可以整个数组元素进行传送。如：vara,b,c:array[1..100]ofinteger;beginc:=a;a:=b;b:=c;end.在上程序中，a,b,c三个数组类型完全一致，它们之间可以实现整数组传送，例子中，先将a数组所有元素的值依次传送给数组c，同样b数组传给a，数组c又传送给b，上程序段实际上实现了a,b两个数组所有元素的交换。对于一维数组的输入与输出,都只能对其中的元素逐个的输入与输出。在下面的应用示例中将详细介绍。三、一维数组应用示例一维数组元素的输入不能整个数组输入，只能逐个元素赋值，A[I]：=X；一般用FOR循环做。如：FORI：=1TO7DOREAD（A[I]）；一维数组元素的输出不能整个数组一起输出，只能逐个元素输出，WRITE（A[I]）；一般用FOR循环做。如：FORI：=1TO7DOWRITE（A[I]）；例2输入50个数,要求程序按输入时的逆序把这50个数打印出来。也就是说，请你按输入相反顺序打印这50个数。【问题分析】我们可定义一个数组a用以存放输入的50个数,然后将数组a内容逆序输出。programex5_1;typearr=array[1..50]ofinteger;{说明一数组类型arr}vara:arr;i:integer;beginwriteln('Enter50integer:');fori:=1to50doread(a[i])；{从键盘上输入50个整数}readln;fori:=50downto1do{逆序输出这50个数}write(a[i]:10);end.34 全国青少年信息学奥赛培训教程例3、将a数组中第一个元素移到最后数组末尾,其余数据依次往前平移一个位置。【问题分析】为完成题目所要求的操作，其算法应该包括以下几个主要步骤：①把第一个元素的值取出入在一个临时单元temp中；②通过a[2]→a[1],a[3]→a[2],a[4]→a[3]，……，a[n]→a[n-1],实现其余元素前移③将temp值送入a[n].programp6-4;constn=10;vara:array[1..n]ofinteger;i:integer;temp:integer;beginwriteln(‘reak',n,'datas');fori:=1tondoread(a[i]);temp:=a[1];fori:=1ton-1doa[i]:=a[i+1];a[n]:=temp;writeln(‘Result:');fori:=1tondowrite(a[i]:3);end.运行结果:read10datas:•12345678910Result:•23456789101例4、输入十个正整数,把这十个数按由大到小的顺序排列。（选择排序）将数据按一定顺序排列称为排序，排序的算法有很多，其中选择排序是一种较简单的方法。【问题分析】要把十个数按从大到小顺序排列，则排完后，第一个数最大，第二个数次大，……。因此，我们第一步可将第一个数与其后的各个数依次比较，若发现，比它大的，则与之交换，比较结束后，则第一个数已是最大的数（最大的泡往上冒）。同理，第二步，将第二个数与其后各个数再依次比较，又可得出次大的数。如此方法进行比较，最后一次，将第九个数与第十个数比较，以决定次大的数。于是十个数的顺序排列结束。如对5个进行排序，这个五个数分别为829105。按选择排序方法，过程如下：初始数据：829105第一次排序：829105928105102895102895第二次排序：108295109285109285第三次排序：109825109825第四次排序：109852对于十个数，则排序要进行9次。源程序如下：programex5_2;vara:array[1..10]ofinteger;i,j,t:integer;beginwriteln('Input10integers:');fori:=1to10doread(a[i]);｛读入10个初始数据｝readln;35 全国青少年信息学奥赛培训教程fori:=1to9do｛进行9次排序｝beginforj:=i+1to10do｛将第i个数与其后所有数比较｝ifa[i]Trunc(sqrt(N))为止；⑸打印输出a数组中留下来、未被筛掉的各元素值，并按每行五个数显示。用筛法求素数的过程示意如下（图中用下划线作删去标志）：①23456789101112131415…9899100｛置数｝②23456789101112131415…9899100{筛去被2整除的数}③23456789101112131415…9899100{筛去被3整除的数}……23456789101112131415…9899100{筛去被整除的数}ProgramExam53;constN=100;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;End.【上机练习6.1】1、国际象棋盘中，第1格放1粒米，第2格放2粒米，第3格放4粒米，第4格放8粒米，第5格放16粒米，．．．．．．问：16个格子总共可以放多少粒米？i–1分析：第i个格子可放多少粒米：22、输出斐波列契数列的前N项（5个1行）01123581321．．．．．．．．．．3、输入N个整数，找出最大数所在位置，并将它与第一个数对调位置。方法：“比武招亲”、“打擂台”4、插入1个整数在1个有序数组中（从小到大，整型数据），要求插入后仍有序。5、将一个数组中的所有元素倒序存放。分析：A[1]←→A[N]A[2]←→A[N-1]……A[I]←→A[J]I从1开始，每交换1次，I加1；直到I=NDIV26、删除数组中的某元素，且右边的元素都向左平移一格。7、查找数组A中是否有等于NUM这个数，有则返回这个数在数组中的位置；没有，则返回0。（假设A中有N个互异的整数）8、有N个数存放于数组A中，将其按照从小到大的顺序重新排列。选择排序法：用“打擂台”法将最小的1个数找出来放在数组的最前面。然后在剩下的N-1个数中重复做上面的操作………..，一共要N–1趟。37 全国青少年信息学奥赛培训教程第二节多维数组一、多维数组的定义当一维数组元素的类型也是一维数组时，便构成了二维数组。二维数组定义的一般格式：array[下标类型1]ofarray[下标类型2]of元素类型；但我们一般这样定义二维数组：array[下标类型1，下标类型2]of元素类型；说明：其中两个下标类型与一维数组定义一样，可以看成“下界1..上界1”和“下界2..上界2”，给出二维数组中每个元素(双下标变量)可以使用下标值的范围。of后面的元素类型就是基类型。一般地，n维数组的格式为：array[下标类型1，下标类型2，…，下标类型n]of元素类型；其中，下标类型的个数即数组的维数，且说明了每个下标的类型及取值范围。二、多维数组元素的引用多维数组的数组元素引用与一维数组元素引用类似，区别在于多维数组元素的引用必须给出多个下标。引用的格式为：<数组名>[下标1,下标2,…,下标n]说明：显然，每个下标表达式的类型应与对应的下标类型一致，且取值不超出下标类型所指定的范围。例如,设有说明:typematrix=array[1..5,1..4]ofinteger;vara:matrix;则表示a是二维数组，共有5*4=20个元素，它们是：a［1，1］a［1，2］a［1，3］a［1，4］a［2，1］a［2，2］a［2，3］a［2，4］a［3，1］a［3，2］a［3，3］a［3，4］a［4，1］a［4，2］a［4，3］a［4，4］a［5，1］a［5，2］a［5，3］a［5，4］因此可以看成一个矩阵，a［4，2］即表示第4行、第2列的元素。由于计算机的存储器是一维的，要把二维数组的元素存放到存储器中，pascal是按行（第一个下标）的次序存放，即按a［1，1］a［1，2］a［1，3］a［1，4］a［2，1］…，a［5，4］的次序存放于存储器中某一组连续的存储单元之内。对于整个二维数组的元素引用时,大多采用二重循环来实现。如：给如上说明的二维数组a进行赋值:a[i,j]=i*j。fori:=1to5doforj:=1to4doa[i,j]:=i*j;对二维数组的输入与输出也同样可用二重循环来实现:fori:=1to5dobeginforj:=1to4doread(a[i,j]);end;fori:=1to5dobeginforj:=1to4dowrite(a[i,j]:5);end;三、多维数组的应用示例例7、设有一程序:programex5_3;constn=3;typematrix=array[1..n,1..n]ofinteger;vara:matrix;i,j:1..n;38 全国青少年信息学奥赛培训教程beginfori:=1tondobeginforj:=1tondoread(a[i,j]);readln;end;fori:=1tondobeginforj:=1tondowrite(a[j,i]:5);writeln;end;end.且运行程序时的输入为:2□1□3←┘3□3□1←┘1□2□1←┘则程序的输出应是:2□3□11□3□23□1□1例8、输入4名学生数学、物理、英语、化学、pascal五门课的考试成绩，求出每名学生的平均分，打印出表格。分析：用二维数组a存放所给数据,第一下标表示学生的学号,第二个下标表示该学生某科成绩，如a[i,1]、a[i,2]、a[i,3]、a[i,4]、a[i,5]分别存放第i号学生数学、物理、英语、化学、pascal五门课的考试成绩,由于要求每个学生的总分和平均分，所以第二下标可多开两列，分别存放每个学生5门成绩和总分、平均分。源程序如下：programex5_4;vara:array[1..4,1..7]ofreal;i,j:integer;beginfillchar(a,sizeof(a),0);{函数fillchar用以将a中所有元素置为0}writeln('Enter4studentsscore');fori:=1to4dobeginforj:=1to5do{读入每个人5科成绩}beginread(a[i,j]);{读每科成绩时同时统计总分}a[i,6]:=a[i,6]+a[i,j];end;readln;a[i,7]:=a[i,6]/5;{求平均分}end;writeln('No.Mat.Phy.Eng.Che.Pas.Tot.Ave.');{输出成绩表}fori:=1to4dobeginwrite(i:2,'');forj:=1to7dowrite(a[i,j]:9:2);writeln;{换行}end;end.39 全国青少年信息学奥赛培训教程【上机练习6.2】1、输入一个二维数组，找出其中最小的数，输出它的值以及所在行号和列号。2、输入一M行N列数组，将第I行与第J行元素对调（I，J'.'dobegini:=i+1;letter[i]:=ch;read(ch)end;40 全国青少年信息学奥赛培训教程{判断它是否是回文}j:=1;while(j=ithenwriteln('Yes.')elsewriteln('No.');end.例10、奇数阶魔阵2魔阵是用自然数1，2，3…，n填n阶方阵的各个元素位置，使方阵的每行的元素之和、每列元素之和及主对角线元素之和均相等。奇数阶魔阵的一个算法是将自然数数列从方阵的中间一行最后一个位置排起，每次总是向右下角排（即Aij的下一个是Ai+1,j+1）。但若遇以下四种情形，则应修正排数法。（1）列排完（j=n+1时），则转排第一列;（2）行排完（即i=n+1时），则转排第一行;（3）对An,n的下一个总是An,n-1;（4）若Aij已排进一个自然数，则排Ai－1，j－2。例如3阶方阵，则按上述算法可排成：438951276有了以上的算法，解题主要思路可用伪代码描述如下：1indiv2+1,yn/*排数的初始位置*/2a[i,j]1;3fork:=2ton*ndo4计算下一个排数位置!（i,j）；5ifa[i,j]<>0then6ii-1;7jj-2;6a[i,j]k;7endfor对于计算下一个排数位置，按上述的四种情形进行，但我们应先处理第三处情况。算法描述如下：1if(i=n)and(j=n)then2jj-1;/*下一个位置为(n,n-1)*/;3else4iimodn+1;5jjmodn+1;6endif;源程序如下：programex5_7;vara:array[1..99,1..99]ofinteger;i,j,k,n:integer;beginfillchar(a,sizeof(a),0);write(‘n=’);readln(n);i:=ndiv2+1;j:=n;a[i,j]:=1;fork:=2ton*ndobeginif(i=n)and(j=n)thenj:=j-1elsebegin41 全国青少年信息学奥赛培训教程i:=imodn+1;j:=jmodn+1;end;ifa[i,j]<>0thenbegini:=i-1;j:=j-2;end;a[i,j]:=k;end;fori:=1tondobeginforj:=1tondowrite(a[i,j]:5);writeln;end;end.【上机练习6.3】1．读入10个数，输出偶数项及它们的和，输出奇数项及它们的平均数。2．读入n个数，打印其中的最大数及其位置号。3．有一组（假设有n个），其排列顺序如下：3，6，11，45，23，70，67，34，26，89，90，15，56，50，20，10。编一程序交换这数组中任意指定的两段不重合数据。4．给定一串整数数列，求出所有的递增和递减子序列的数目，如数列7，2，6，9，8，3，5，2，1可分为（7，2），（2，6，9），（9，8，3），（3，5），（5，2，1）5个子序列，答案就是5。我们称2，9，3，5为转折元素。5．设数组a是有n个元素的整数数组，从中找出最大和子序列。6．已知数组a中含n个整型元素，求a中有多少个最大数？多少个次大数？……，多少个互不相同的数？编程实现之。7．试编一个程序，打印出1000以内以二进制和十进制正读和反读都一样的整数清单。8．约瑟夫问题：n个人围成一圈，从第一个人开始报数，数到k的人出圈。再由下一个人开始报数，数到k的人出圈，……依次输出出圈人的编号。N的值预先设定，k的值由键盘输入。比如n=8，k=6，依次出圈的为：6、4、3、5、8、7、2、1。9.输入N个同学的语、数、英三科成绩，计算他们的总分与平均分，并统计出每个同学的名次，最后以表格的形式输出。10.打印杨辉三角形的前10行。杨辉三角形形如图：1111111211211331133114641146641[图6-3][图6-4][问题分析]观察图6-3，大家不容易找到规律，但是如果将它转化为图6-4，不难发现杨辉三角形其实就是一个二维表的小三角形部分，假设通过二维数组yh存储，每行首尾元素为1，且其中任意一个非首位元素yh[i,j]的值其实就是yh[i-1,j-1]与yh[i-1,j]的和，另外没一行的元素个数刚好等于行数。有了数组元素的值，要打印杨辉三角形，只需要控制一下输出其始位置就行了。42 全国青少年信息学奥赛培训教程第七章函数与过程第一节函数PASCAL给我们提供了一些标准函数，我们不用了解这些函数如何求出来的，只管直接调用它们，挺方便的。如正弦函数，余弦函数，算术平方根．．．．．．有了这些函数，我们觉得很省事。如：求SIN（1）＋SIN（2）＋．．．＋SIN（100）＝？这个程序我们可以这样编写：例1、PROGRAMe1(input,output);VARi:integer;s:real;BEGINs:=0;fori:=1to100dos:=s+sin(i);writeln('s=',s);END.在这个程序里，我们直接用到了正弦函数，至于SIN（1），SIN（2）如何求出来的我们不需过问，只管直接用它的结果便是了。我们来看看下面一个例子：求：1！＋2！＋3！＋．．．＋10！＝？如果要编写程序，我们看到求阶乘的操作要执行10次，只不过每次所求的数不同。我们想：不至于编写10遍求阶乘的程序吧。我们希望有一个求阶乘的函数，假设为JS（X），那么我们就可以这样求这道题了：例2、PROGRAMe1(input,output);VARi:integer;s:real;BEGINs:=0;fori:=1to10dos:=s+js(i);writeln('s=',s);END.现在的问题是：TURBOPASCAL没提供JS（X）这样一个标准函数，这个程序是通不过的。如果是PASCAL的标准函数，我们可以直接调用，如TRUNC（X），LN（X），SQRT（X）．．．．．．而PASCAL提供给我们的可供直接调用的标准函数不多。没关系，我们编写自己的函数！1.2函数的编写自己编写一个函数，它的格式如下：FUNCTION函数名（形式参数表）：函数类型；VAR函数的变量说明；BEGIN函数体END；我们来分析一下，一个函数的编写可分成三部份：一是函数首部，即第一个语句。它必须以FUNCTION开头，函数名是自己取的，取名的原则是便于记忆，和文件名的取名规则类似。形式参数（简称形参）表以标识符的形式给出，相当于函数中的自变量。参数可以有多个，也可以有多种类型。不同类型的参数之间用“；”隔开，同类型的参数如有多个，则用“，”隔开，在其后得加上说明。如：FUNCTIONA1（A，B，C：INTEGER；D，E，F：REAL）：REAL；在最后，函数属于哪种类型，还得表示出来。在本例中，该函数为实型。第二部分是函数的变量说明部分，对在本函数中将要用到的变量作类型说明，这一点和以前学的变量一样。如果程序不用变量，则此部分也可省掉。第三部分是函数体，本函数的功能实现就在于此，编写的语句就在里面。例、编写一求阶乘的函数。43 全国青少年信息学奥赛培训教程我们给此函数取一名字就叫JS。FUNCTIONjs(n:integer):longint;vari:integer;s:longint;begins:=1;fori:=1tondos:=s*i;js:=s;end;在本例中，函数名叫JS，只有一个INTEGER型的自变量N，函数JS属LONGINT型。在本函数中，要用到两个变量I，S，在VAR后已加以说明。在函数体中，是一个求阶乘的语句，但有一点要注意：虽然N的阶乘的值在S中，但最后必须将此值赋给函数JS，此时JS不带任何参数。在任何函数中，最后都要把最终结果赋给函数名，因为该函数的结果是靠函数名返回的。在这里，函数的参数N是一个接口参数，说得更明确点是入口参数。如果我们调用函数：JS（3），那么在程序里所有有N的地方N被替代成3来计算。在这里，3就被称为实参。又如：SQRT（4），LN（5），这里4，5叫实参。而SQRT（X），LN（Y）中的X，Y叫形参。1．3函数的调用自定义的函数在调用前要先说明，在主程序中的位置如下:PROGRAM程序名（INPUT，OUTPUT）；VAR主程序变量说明；FOUNCTION函数名（形参表）：函数类型；VAR函数变量说明；BEGIN函数体END；{FUNCTION}BEGIN主程序END.{PROGRM}在主程序中，我们把函数的全部说明放在主程序的变量说明和程序体之间，然后在主程序的执行部分就可以直接调用自定义函数了。注意：在函数的说明部分，我们要用形参，但在程序的执行部分调用自定义函数时，就得用实参了。例3、利用前面定义的阶乘函数，求5！，9！。PROGRAMe59(input,outout);VARa1,a2:longint;fUNCTIONjs(n:integer):longint;vari:integer;s:longint;begins:=1;fori:=1tondos:=s*i;js:=s;end;BEGINa1:=js(5);a2:=js(9);writeln('5!=',a1,'','9!=',a2);END.在这个程序中，在主程序的BEGIN之前，我们对函数进行了一次说明，在后面的程序中都可以象标准函数那样直接调用自定义函数了。在FUNCTION语句中，用的是形参N，在主程序调用中，调用函数是用的实参，如：JS（5）；程序执行到这儿会自动将5代入前面的FUNCTION函数中，用5取代所有的N，最44 全国青少年信息学奥赛培训教程终将结果赋值给JS。所以在A1中一定是5！，A2中是9！。另外，函数不能单独使用，一定要结合主程序才能运行。如果是求1！＋2！＋3！＋．．．＋10！，则只需把主程序改成：A1：＝0；FORJ：＝1TO10DOA1：＝A1＋JS（J）；WRITELN（A1）；在例3中，主程序的变量A1，A2叫全程变量，它们除了主程序外，还可以在函数中出现；在函数说明中用到的变量I，S则是局部变量，只能在函数部分使用，一旦出了函数则失去意义；别外要注意：全程变量和局部变量尽量不要同名。例4、任意输入10组三角形的三边，求其面积。已知三角形的三边，是可以求出面积的。我们可以定义一个已知三角形三边求其面积的函数，设为AREA（a1,a2,a3）。PROGRAMe5(inmput,output);VARa,b,c,s:real;i:integer;FUNCTIONarea(a1,a2,a3:real):real;vars1,d:real;begind:=(a1+a2+a3)/2;s1:=Sqrt(d*(d-a1)*(d-a2)*(d-a3));area:=s1;end;BEGINfori:=1to10dobeginwriteln('inputa,b,c');readln(a,b,c);if(a+b<=c)or(a+c<=b)or(b+c<=a)thenwriteln('dataerror!')elsewriteln('s=',area(a,b,c));end;END.在函数说明中，如果形参的个数不止一个，那么在程序中调用函数的实参个数一定要与形参的个数一致，第一个实参对应第一个形参，第二个实参对应第二个形参．．．次序不能调。例5、定义一个函数CHECK（N，D），让它返回一个布尔值。如果数字D在整数N的某位中出现则送回TRUE，否则送回FALSE。例如：CHECK（325719，3）＝TRUE；CHECK（77829，1）＝FALSE；PROGRAMe6(input,output);VARa,b:integer;FUNCTIONcheck(n,d:integer):boolean;varf:boolean;e:integer;beginf:=false;while(n>0)and(notf)dobegine:=nmod10;n:=ndiv10;ife=dthenf:=true;45 全国青少年信息学奥赛培训教程end;check:=f;end;BEGINwriteln('inputn,d');read(a,b);writeln(check(a,b));END.例6、计算如图多边形的面积。从图中可以看出，五边形的面积是三个三角形面积之和。b2b1b6b5b7b3b4Programp7_4(input,output);Varb1,b2,b3,b4,b5,b6,b7,s:real;Functionarea(a,b,c:real):real;VarP:real;BeginP:=(a+b+c)/2;Area:=sqrt(p*(p-a)*(p-b)*(p-c));End;BEGIN{主程序}Write(‘pleaseinputb1,b2,b3,b4,b5,b6,b7:’);Readln(b1,b2,b3,b4,b5,b6,b7);S:=area(b1,b5,b6)+area(b2,b6,b7)+area(b3,b4,b7);{三次调用函数area}Writeln(‘s=’,s:10:3);END.函数课堂练习1.编程找出由键盘任意输入二个整数中的最大数。2.编程找出由键盘任意输入三个整数中的最大数。3.求从键盘任意输入两个自然数的最大约数。4.求从键盘任意输入三个自然数的最大约数。5.求从键盘任意输入两个自然数的最小公倍数。【上机练习7.1】R1.编程求CK=K！/（R！（K-R）！）（K>R>0）2.求正整数2和100之间的完全数。完全数：因子之和等于它本身的自然数，如6=1+2+3；3.哥德巴赫猜想的命题之一是:大于6的偶数等于两个素数之和。编程将6～100所有偶数表示成两个素数之和。4.如果一个自然数是素数,且它的数字位置经过对换后仍为素数,则称为绝对素数,例如13。试求出所有二位绝对素数46 全国青少年信息学奥赛培训教程第二节过程过程和函数一样，也是子程序。一个过程对应一个需要完成的任务。PASCAL中提供了不少标准过程，如：READ，WRITE，GET，NEW，PUT．．．．．．这些标准过程在程序中可以直接调用。但仅仅这些标准过程还不能满足我们的需要，我们还要自己定义过程，就象函数一样。但函数必须以值的形式返回，而过程不一定返回一个值，只是执行一个任务而已；函数只能返回一个值，而过程可以返回不止一个值。所以函数不能取代过程。2．1过程的定义过程定义的格式如下：PROCEDURE过程名（形式参数）；VAR过程的变量说明；BEGIN过程体END;对该格式说明如下：一个过程也分为三部分，1：过程的首部。过程必须以PROCEDURE开头，过程名的取名规则和函数名一样，括号里面是形式参数，如形参不止一种，则中间用“；”隔开，同类形参如不止一个，则中间用“，”隔开。另：有时侯过程不用加参数。2：过程的说明部分，用VAR开头，它只能对过程中的变量进行说明，同样是局部变量。另：如果过程不用变量，则可将说明部分省略。3：过程体。它是过程的执行部分。我们来定义一个打印由“＊”组成的矩阵的过程，该矩阵四行五列。例7、PROCEDUREprint;vari,j:integer;beginfori:=1to4dobeginforj:=1to5dowrite('*');writeln;end;end;该过程就没有参数，直接执行打印一个固定矩阵的任务，而且也没返回值。例8、定义一个求N！的过程。PROCEDUREjs(n:integer);vars:longint;i:integer;begins:=1;fori:=1tondos:=s*i;writeln(n,'!=',s);end.在该过程中，它的值的返回形式和函数不一样：函数是由函数名返回，而过程不是由函数名返回的；在过程的首部不用对过程的类型进行说明。例9、定义过程fa求N!。programexp7_5;varx:integer;t:real;procedurefa(n:integer);vark:integer;47 全国青少年信息学奥赛培训教程begint:=1;fork:=2tondot:=t*k;end;beginread(x);fa(x);writeln(x:5,t:8);end.这里通过全程变量T，将过程中计算结果传递到T变量中。Fa(x)仅仅作为程序中的一条命令被执行。2．2过程的调用自定义过程在程序调用之前要先说明，过程的说明就在主程序的执行语句之前。其格式如下：PROGRAM程序名（INPUT，OUTPUT）；VAR主程序的变量说明；PROCEDURE过程名（形式参数表）；VAR过程的变量说明；BEGIN过程体END;BEGIN主程序体END.例10、任意输入10个三角形的三边，用过程把其面积求出。我们把求一个已知三边的三角形的面积定义一个过程，对比一下和例5有什么不同。PROGRAMe5(inmput,output);VARa,b,c,s:real;i:integer;PROCEDUREarea(a1,a2,a3:real);vars1,d:real;begind:=(a1+a2+a3)/2;s1:=Sqrt(d*(d-a1)*(d-a2)*(d-a3));writeln('s=',s1);end;BEGINfori:=1to10dobeginwriteln('inputa,b,c');readln(a,b,c);if(a+b<=c)and(a+c<=b)and(b+c<=a)thenwriteln('dataerror!')elsearea(a,b,c);end;END.我们看到：过程的调用和函数不同。函数不能作为独立的一个语句使用，而过程可以。函数的值是由函数名返回的，而过程不能。现在我们提出一个要求：用过程求出1！＋2！＋3！＋．．．＋10！＝？求N！的问题我们在例8已写出来，但阶乘的结果是在过程里用WRITE语句输出的，不能用累加语句把结果求出来。那么，怎样用过程将类似的问题求出来？这就得用到变量形参。48 全国青少年信息学奥赛培训教程2．3变量形参在过程定义的语句中，有个参数表，在参数表中，除了前面我们已用的形参，还有变量形参。变量形参的作用是：它可以作为过程的出口参数。我们可以把过程中求出的结果用变量形参输出到过程外，在过程外面可以调用该参数，因此，该参数是全局变量。其格式上的区别是在变量形参前加上VAR即可。那么我们现在来求1！＋2！＋3！＋．．．＋10！＝？例11、PROGRAMe9(input,output);VARj:integer;s,m:longint;PROCEDUREjs(n:integer;varm:longint);vari:integer;beginm:=1;fori:=1tondom:=m*i;end;BEGINs:=0;forj:=1to10dobeginjs(j,m);s:=s+m;end;writeln('s=',s);END.在本例中。我们看到，过程JS中用到了变量形参M，在过程中定义为LONGINT类型；而在主程序的变量说明中也得对变量形参M说明为同种类型LONGINGT。于是，在过程中和主程序中都可以用该变量了。例12、任意输入一个整数，将它变成字符串输出。如：输入数34567，打印出字符“34567”。要求用过程的方法实现。PROGRAME10(input,output);vari,k:integer;s:string;PROCEDUREn_c(n:integer;vars:string);varl:inTeger;beginl:=abs(n);s:='';repeats:=char((lmod10)+ord('0'))+s;l:=ldiv10;untill=0;ifn<0thens:='-'+s;end;BEGINfori:=1to10dobeginwriteln('inputk');readln(k);n_c(k,s);writeln('thestringis:',s);end;END.49 全国青少年信息学奥赛培训教程2.4形参与变量形参（1）形参：在函数或过程定义中，没有加VAR说明的参数，在调用函数或过程时，调用程序将实参的值直接传递给形参，起着赋值作用。（2）变量形参：在函数或过程定义中，加有VAR说明的参数，在调用函数或过程时，调用程序将实参的变量地址传递给变量形参，因此当过程或函数处理中，改变变量形参的值，则实参的变量值也随之改变。（共享同一个存储单元）例如下列程序中的参数传递：Programp7_13(input,output);varx,n:integer;procedurechan(x:integer;vary:integer);beginx:=x+5;y:=y+5;writeln('x='，x，'y='，y);{语句②}end;BEGIN{主程序}x:=10;n:=10;writeln('x='，x，'n='，n);{语句①}chan(x，n);writeln('x='，x，'n='，n);{语句③}END.运行结果：x=10n=10{语句①的结果}x=15y=15{语句②的结果}x=10n=15{语句③的结果}过程chan中定义了形参x和变量形参y。在调用过程时，形参x接受实参的值10，然后将它加5，但是形参值的改变并不影响主程序中实参的值（数值传递），所以返回主程序后，输出实参x的值仍为10，可见，实参x和形参x是两个不同的变量。y为变量形参，对于变量形参的操作实际上就是对相应实参n的操作（共享存储地址）。y的初值为10，调用过程后，值为15，返回主程序时，值15被带回主程序，故n也为15。例13、将实数x拆分为整数部分n和小数部分p。Programp7_16(input,output);vara1,a2,d1,d2:real;z1,z2:integer;procedurefen(x：real;varn：integer;varp：real);beginn:=trunc(x);{n是整数部分}p:=x-n;{p是小数部分}end;begin{主程序}write('inputa1,a2：');readln(a1,a2);fen(a1,z1,d1);writeln(a1:8:3,z1:8,d1:8:3);fen(a2,z2,d2);writeln(a2:8:3,z2:8,d2:8:3);end.运行结果：inputa1，a2：12.87345.76912.87120.870345.7693450.76950 全国青少年信息学奥赛培训教程小结形参和变量形参的区别：①形参传值：为形参分配存贮单元，将实参的值赋给形参，过程体内对形参的操作不影响实参的值。一旦过程体执行完毕，系统将收回形参所占用的存贮单元，形参的值也就不复存在。②变量形参传地址：将实参的地址传给对应的变量形参，即变量形参与实参共享实参的地址，因此对变量形参的操作就是对实参的操作。一旦过程体执行完毕，系统将收回变量形参所占用的存贮单元，但运算结果已保留在对应的实参中。2.5变量及其作用域全程变量：主程序中被说明的变量。局部变量：在过程或函数中被说明的变量。在程序中，局部变量、全程变量进行存取的适用范围是不一样的，即作用域不一样。局部变量的作用域是它们所在的子程序。因形式参数也只在子程序中有效，因此也属于局部变量。对于局部变量的作用域可以这样理解：当局部变量所在子程序被调用时，局部变量才被分配有效的存储单元；当返回调用程序时，局部变量所占的存储单元就被释放。全程变量的作用域分为两种情况：①在全程变量和局部变量不同名时，其作用域是整个程序。②在全程变量和局部变量同名时，局部变量屏蔽了全程变量。例14、变量作用范围：Programp7_10(input,output);varm:integer;{m为全程变量}proceduretest2;varm:integer;{定义m为局部变量}beginm:=100;end;begin{主程序}m:=5;writeln('Beforethetest2call,themis：',m);{输出过程调用前的m值}test2;{调用过程test2}writeln('Afterthetest2call,themis：',m);{输出过程调用后的m值}end.运行结果：Beforethetest2call，themis：5Afterthetest2call，themis：5主程序开始执行后，全程变量m被赋初值5；调用过程test2后，由于有与全程变量同名的局部变量m，故过程中起作用的是局部变量m，而全程变量m暂时被屏蔽不受影响。过程调用完毕返回主程序后，全程变量m起作用，局部变量m所占用的临时单元被释放。从这个程序可以看出，当过程或函数内包含与全程变量同名的变量时，全程变量的作用域将不包括在此过程或函数中。2.6函数和过程的区别过程和函数都为子程序，但也有区别：1、标识符不同。函数的标识符为FUNCTION，过程为：PROCEDURE。2、函数中一般不用变量形参，用函数名直接返回函数值；而过程如有返回值，则必须用变量形参返回。3、过程无类型，不能给过程名赋值；函数有类型，最终要将函数值传送给函数名。4、函数在定义时一定要进行函数的类型说明，过程则不进行过程的类型说明。5、调用方式不同。函数的调用出现在表达式中，过程调用，由独立的过程调用语句来完成。6、过程一般会被设计成求若干个运算结果，完成一系列的数据处理，或与计算无关的各种操作；而函数往往只为了求得一个函数值。四、过程与函数的综合应用例15、从键盘读取A，B数组的元素，A，B数组均已从小到大排好序（无相同元素），现将A，B合并为数组C，同样要求数组C也是从小到大排好序（有相同元素时只保留一个）。程序中n表示数组A，B的51 全国青少年信息学奥赛培训教程长度，i，j，k分别表示数组A，B，C的取数或存数的指针。programexcp3；constn=8；m=2*n；typearr1=array[1..n]ofinteger；arr2=array[1..m]ofinteger；vara，b:arr1；c:arr2；i，j，k:integer；procedurecopy(x:arr1；vary:arr2；vari，j:integer)；begini:=i+1；y[i]:=x[j]；j:=j+1；end；beginfori:=1tondoread(a[i])；readln；fori:=1tondoread(b[i])；readln；i:=1；j:=1；k:=0;while(I<=n)and(j<=n)doifa[i]=3）Pascal程序：varf0,f1,f2:real;i,n:byte;beginreadln(n);f0:=0;f1:=1;fori:=2ton-1dobeginf2:=f0+f1;f0:=f1;f1:=f2end;writeln(f2:1:0)end.53 全国青少年信息学奥赛培训教程【上机练习7.3】1、猴子吃枣问题：猴子摘了一堆枣，第一天吃了一半，还嫌不过瘾，又吃了一个；第二天，又吃了剩下的一半零一个；以后每天如此。到第十天，猴子一看只剩下一个了。问最初有多少个枣子？2、任何一个自然数的立方都可以写成一串连续奇数之和。如：31=132=3+5=833=7+9+11=2734=13+15+17+19=64……………………….3编程输入N，求N是由哪些奇数之和。3、楼梯有N级台阶，上楼可以一步上一阶，也可以一步上二阶。编一递归程序，计算共有多少种不同走法？4、兔子在出生两个月以后，就具有生殖后代的能力。假设一对兔子，每月都能生一对兔子，生出来的每一对小兔子，在出生两个月后，也每月生一对兔子。那末，由一对刚出生的小兔子开始，连续不断地繁殖下去，在某个指定的月份有多少对兔子？5、骨牌铺法：有1×n的一个长方形，用一个1×1、1×2和1×3的骨牌铺满方格。例如当n=3时为1×3的方格。此时用1×1、1×2和1×3的骨牌铺满方格，共有四种铺法。如下图：递推公式：边界条件：第四节递归算法一、递归概念当过程或函数的定义中，其内部操作又直接或间接地出现对自身程序的引用，则称这样的程序嵌套定义为递归定义。递归算法是把处理问题的方法定义成与原问题处理方法相同的过程，在处理问题的过程中又调用自身定义的函数或过程。例如，在数学上，所有偶数的集合可递归地定义为：①0是一个偶数；②一个偶数和2的和是一个偶数。可见，仅需两句话就能定义一个由无穷多个元素组成的集合。在程序中，递归是通过函数或过程的调用来实现的。函数或过程直接调用其自身，称为直接递归；函数或过程间接调用其自身，称为间接递归。二、函数递归[例1]仍用上例的计算植树棵数问题来说明递归算法分析：把原问题求第一位同学在植树棵数a1，转化为a1=a2+2;即求a2；而求a2又转化为a2=a3+2;a3=a4+2;a4=a5+2;逐层转化为求a2,a3,a4,a5且都采用与求a1相同的方法；最后的a5为已知,则用a5=10返回到上一层并代入计算出a4；又用a4的值代入上一层去求a3;...,如此,直到求出a1。54 全国青少年信息学奥赛培训教程因此：10(x=5)ax={ax+1+2(x<5)其中求ax+1又采用求ax的方法。所以:①定义一个处理问题的函数Num(x)：如果X<5就递归调用函数Num(x+1);②当递归调用到达一定条件(X=5)，就直接执行num:=10，再执行后继语句，遇End返回到调用本函数的地方。③最后返回到开头的原问题，此时所得到的运算结果就是原问题Num(1)的答案。Pascal程序：programexam1_1;vara:integer;functionnum(x:integer):integer;beginifx=5thennum:=10elsenum:=num(x+1)+2;end;BEGINwriteln('TheNumis',num(1));READLN;END.递归方法说明如下：①调用原问题的处理过程时，调用程序应给出具体的过程形参值（数据）;②在处理子问题中，如果又调用原问题的处理过程，但形参值应是不断改变的量(表达式）;③每递归调用一次自身过程，系统就打开一“层”与自身相同的程序系列;④由于调用参数不断改变，将使条件满足（达到一定边界），此时就是最后一“层”，不需再调用（打开新层），而是往下执行后继语句，给出边界值，遇到本过程的END，就返回到上“层”调用此过程的地方并继续往下执行;⑤整个递归过程可视为由往返双向“运动”组成，先是逐层递进，逐层打开新的“篇章”，（有可能无具体计算值）当最终递进达到边界，执行完本“层”的语句，才由最末一“层”逐次返回到上“层”，每次返回均带回新的计算值，直至回到第一次由主程序调用的地方，完成对原问题的处理。n[例2]用递归算法求X。n0分析：把X分解成:X=1(n=0)10X=X*X(n=1)21X=X*X(n>1)32X=X*X(n>1)……(n>1)programex1;varx,n:integer;functioncf(n:integer):integer;beginifn=0thencf:=1elsecf:=x*cf(n-1);end;BEGINwrite('Pleaseinputx,n:');readln(x,n);write(x,'^',n,'is:',cf(n));END.递归算法，常常是把解决原问题按顺序逐次调用同一“子程序”(过程)去处理，最后一次调用得到已知数据，执行完该次调用过程的处理，将结果带回，按“先进后出”原则，依次计算返回。55 全国青少年信息学奥赛培训教程[例3]用递归函数求x!1(x=0)x!={x(x-1)!(x>0)分析：根据数学中的定义把求x!定义为求x*(x-1)!,其中求(x-1)!仍采用求x!的方法，需要定义一个求x！的过程或函数，逐级调用此过程或函数，即：当x=0时x!=1；当x>0时，x!=x*(x-1)！。假设用函数Fac(x)表示x的阶乘，当x=3时，Fac(3)的求解方法可表示为：Fac(3)=3*fac(2)=3*2*Fac(1)=3*2*1*Fac(0)=3*2*1*1=6①定义递归函数：fac(n:integer):integer;如果n=0，则fac:=1;如果n>0，则调用函数fac:=n*fac(n-1);②返回主程序，打印fac(x)的结果。它的执行流程如图4.4.2所示ProgramExam3;Varx:integer;functionfac(n:integer):integer;｛函数fac(n)求n!｝beginifn=0thenfac:=1elsefac:=n*fac(n-1)｛函数fac(n-1)递归求(n-1)!｝end;BEGINwrite(’inputx’);readln(x);writeln(x,’!=’,fac(x));｛主程序调用fac(x)求x!｝END.递归算法表现在处理问题的强大能力。然而，如同循环一样，递归也会带来无终止调用的可能性，因此，在设计递归过程（函数）时，必须考虑递归调用的终止问题，就是递归调用要受限于某一条件，而且要保证这个条件在一定情况下肯定能得到满足。[例4]用递归方法求两个数m和n的最大公约数。(m>0，n>0)求两个数的最大公约数，可以用循环搜索方法，找到能被两个数同时整除且是最大的约数的方法；也可以用辗转相除法，这里采用递归程序设计方法：Programp7_21(input,output);varm,n,g:integer;56 全国青少年信息学奥赛培训教程functiongcd(m,n：integer)：integer;varr:integer;beginr:=mmodn;ifr=0thengcd:=nelsegcd:=gcd(n,r);end;BEGIN{主程序}read(m,n);g:=gcd(m,n);writeln(‘m=’,m,’n=’,n,’gcd=’,g);END.运行：输入12848输出m=128n=48gcd=16输入6794输出m=67n=94gcd=1三、过程递归[例1]仍用上例的计算植树棵数问题来说明递归算法：分析：把原问题求第一位同学在植树棵数a1，转化为a1=a2+2;即求a2；而求a2又转化为a2=a3+2;a3=a4+2;a4=a5+2;逐层转化为求a2,a3,a4,a5且都采用与求a1相同的方法；最后的a5为已知,则用a5=10返回到上一层并代入计算出a4；又用a4的值代入上一层去求a3;...,如此,直到求出a1。因此：10(x=5)ax={ax+1+2(x<5)其中求ax+1又采用求ax的方法。所以:①定义一个处理问题的过程Num(x)：如果X<5就递归调用过程Num(x+1);②当递归调用到达一定条件(X=5)，就直接执行a:=10，再执行后继语句，遇End返回到调用本过程的地方，将带回的计算结果(值)参与此处的后继语句进行运算（a:=a+2）;③最后返回到开头的原问题，此时所得到的运算结果就是原问题Num(1)的答案。ProgramExam1_1;Vara:byte;ProcedureNum(x:integer);{过程Num(x)求x的棵数｝beginifx=5thena:=10elsebeginNum(x+1);｛递归调用过程Num(x+1)｝a:=a+2{求(x+1)的棵数｝endend;BEGINNum(1);｛主程序调用Num(1)求第1个人的棵数｝writeln(’TheNumis’,a);readlnEND.程序中的递归过程图解如下：调用调用调用调用调用Num(x+1);Num(x+1);Num(x+1);Num(x+1);a:=10;Num(1);a=a+2;a=a+2;a=a+2;a=a+2;end;输出aend;end;end;end;Num(1)Num(2)Num(3)Num(4)Num(5)57 全国青少年信息学奥赛培训教程参照图示，递归方法说明如下：①调用原问题的处理过程时，调用程序应给出具体的过程形参值（数据）;②在处理子问题中，如果又调用原问题的处理过程，但形参值应是不断改变的量(表达式）;③每递归调用一次自身过程，系统就打开一“层”与自身相同的程序系列;④由于调用参数不断改变，将使条件满足（达到一定边界），此时就是最后一“层”，不需再调用（打开新层），而是往下执行后继语句，给出边界值，遇到本过程的END，就返回到上“层”调用此过程的地方并继续往下执行;⑤整个递归过程可视为由往返双向“运动”组成，先是逐层递进，逐层打开新的“篇章”，（有可能无具体计算值）当最终递进达到边界，执行完本“层”的语句，才由最末一“层”逐次返回到上“层”，每次返回均带回新的计算值，直至回到第一次由主程序调用的地方，完成对原问题的处理。n[例2]用递归算法求X。n0分析：把X分解成:X=1(n=0)10X=X*X(n=1)21X=X*X(n>1)32X=X*X(n>1)……(n>1)nn-1X=X*X(n>1)n因此将X转化为：n-1n其中求X又用求X的方法进行求解。nn—1①定义过程xn(x,n:integer)求X;如果n>1则递归调用xn(x,n-1)求X;②当递归调用到达n=0，就执行tt:=1,然后执行本“层”的后继语句;③遇到过程的END就结束本次的调用，返回到上一“层”调用语句的地方，并执行其后续语句tt:=tt*x;④继续执行步骤③，从调用中逐“层”返回，最后返回到主程序，输出tt的值。Pascal程序：ProgramExam2;Vartt,a,b:integer;nProcedurexn(x,n:integer);｛过程xn(x,n)求x｝beginifn=0thentt:=1elsebeginn-1xn(x,n-1);｛递归调用过xn(x,n-1)求x｝tt:=tt*xend;end;BEGINwrite(’inputx,n:’);readln(a,b);｛输入a,b｝bxn(a,b);｛主程序调用过程xn(a,b)求a｝writeln(a,’^’,b,’=‘,tt);readlnEND.递归算法，常常是把解决原问题按顺序逐次调用同一“子程序”(过程)去处理，最后一次调用得到已知数据，执行完该次调用过程的处理，将结果带回，按“先进后出”原则，依次计算返回。[例3]用递归过程求x!1(x=0)x!={x(x-1)!(x>0)programex_217;varn:integer;t:longint;58 全国青少年信息学奥赛培训教程procedurejc(x:longint);beginifx=1thent:=1elsebeginjc(x-1);t:=t*x;end;end;BEGINread(n);jc(n);writeln(t);END.[例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.简单地说，递归算法的本质就是自己调用自己，用调用自己的方法去处理问题，可使解决问题变得简洁明了。按正常情况有几次调用，就有几次返回。但有些程序可以只进行递归处理，不一定要返回时才进行所需要的处理。（1）递归程序的执行过程递归程序在执行过程中，一般具有如下模式：①将调用程序的返回地址、相应的调用前变量保存在栈中；②执行被调用的程序或函数；③若满足退出递归的条件，则退出递归，并从栈顶上弹回返回地址、返回变量的值，继续沿着返回地址，向下执行程序；④否则继续递归调用，只是递归调用的参数发生变化：增加一个量或减少一个量，重复执行直到递归调用结束。（2）递归程序设计能够用递归算法解决的问题，一般满足如下要求：①需要求解的问题可以化为子问题求解，其子问题的求解方法与原问题相同，只是数量的增加或减少；②递归调用的次数是有限的；必须有递归结束的条件59 全国青少年信息学奥赛培训教程[深入应用]例5、已知一个一维数组A[1..N]。{N<50}又已知一整数M。如能使数组A中任意几个元素之和等于M，则输出YES，反之则为NO。对于一个已确定的数组a[1]至a[n]和一个确定的数m，判断能否使数组a中任意几个元素之和等于m，等价于判断能否从数组a中取任意数使其和为m。此时若a[n]=m，则可以输出“YES”，否则若n=1，则可以输出“NO”。否则可以按以下规则进行判断：对于a中任意元素a[n]只有取与不取两种情况：(１)取a[n]：则此时问题转化为：对于一个已确定的数组a[1]至a[n-1]和一个确定的数m-a[n]，判断能否使数组a中任意几个元素之和等于m。(２)不取a[n]：则此时问题转化为：对于一个已确定的数组a[1]至a[n-1]和一个确定的数m，判断能否使数组a中任意几个元素之和等于m。若用函数sum(n,m)表示能否从数组a[1]至a[n]中取任意数使其和为m，只要sum(n-1,m-a[n])和sum(n-1,m)当中有一个值为真，则sum(n,m)为真，否则为假。因此，可以用递归来解此题。递归终止条件为：ifa[n]=mthensum:=trueelseifn=1thensum:=false;Programzushu(input,output);Constmax=50;Vara:array[1..max]ofinteger;n,m,i:integer;Functionsum(n,m:integer):boolean;Beginifa[n]=mthensum:=trueelseifn=1thensum:=falseelsesum:=sum(n-1,m-a[n])orsum(n-1,m);End;Beginwrite('n=');readln(n);fori:=1tondobeginwrite('a[',i,']=');readln(a[i]);end;write('m=');readln(m);ifsum(n,m)thenwriteln('YES')elsewriteln('NO');readln;End.【上机练习7.4】1.用递归的方法求1+2+3+……+N的值。2．用递归函数输出斐波那契数列第n项。0,1，1，2，3，5，8，13……3.输入一个非负整数，输出这个数的倒序数。例如输入123，输出321。4.用递归算法将数组A中的N个数倒序输出。5．用递归方法求N个数中的最大数及其位置。6．用递归算法将一个十进制数X转换成任意进制数M（M<=16）。7．用递归算法实现二分查找即：有20个已经从小到大排序好的数据，从键盘输入一个数X，用对半查找方法，判断它是否在这20个数中。60 全国青少年信息学奥赛培训教程第八章集合和记录类型第一节集合类型集合是由具有某些共同特征的元素构成的一个整体。在pascal中,一个集合是由具有同一有序类型的一组数据元素所组成，这一有序类型称为该集合的基类型。一、集合类型的定义和变量的说明集合类型的一般形式为：setof<基类型>;说明:①基类型可以是任意顺序类型,而不能是实型或其它构造类型。同时，基类型的数据的序号不得超过255。例如下列说明是合法的:typeletters=setof'A'..'Z';numbers=setof0..9;s1=setofchar;ss=(sun,mon,tue,wed,thu,fri,sat);s2=setofss;②与其它自定义类型一样,可以将类型说明与变量说明合并在一起.如:typenumbers=setof0..9;vars:numbers;与vars:setof0..9;等价。二、集合的值集合的值是用“［”和“］”括起来，中间为用逗号隔开的若干个集合的元素。如：[]空集[1,2,3]['a','e','i','o','u']都是集合。说明：①集合的值放在一对方括号中，各元素之间用逗号隔开。②在集合中可以没有任何元素，这样的集合称为空集。③在集合中，如果元素的值是连续的，则可用子界型的表示方法表示。例如：［1,2,3,4,5,7,8,9,10,15］可以表示成：［1..5,7..10,15］④集合的值与方括号内元素出现的次序无关。例如，［1,5,8］和［5,1,8］的值相等。⑤在集合中同一元素的重复出现对集合的值没有影响。例如，［1,8,5,1,8］与［1,5,8］的值相等。⑥每个元素可用基类型所允许的表达式来表示。如［1,1+2,4］、［ch］、［succ(ch)］。三、集合的运算⒈赋值运算只能通过赋值语句给集合变量赋值，不能通过读语句赋值，也不能通过write(或writeln)语句直接输出集合变量的值。⒉集合的并、交、差运算可以对集合进行并、交、差三种运算，每种运算都只能有一个运算符、两个运算对象，所得结果仍为集合。三种运算符分别用“＋”、“＊”、“－”表示。注意它们与算术运算的区别。⒊集合的关系运算集合可以进行相等或不相等、包含或被包含的关系运算，还能测试一个元素是否在集合中。所用的运算符分别是：＝、＜＞、＞＝、＜＝、ｉｎ它们都是二目运算，且前４个运算符的运算对象都是相容的集合类型，最后一个运算符的右边为集合，左边为与集合基类型相同的表达式。例1、设有如下说明：typeweekday=(sun,mon,tue,wed,thu,fri,sat);week=setofweekday;subnum=setof1..50;61 全国青少年信息学奥赛培训教程写出下列表达式的值:⑴［sun,sat］+［sun,tue,fri］⑵［sun,fri］*［mon,tue］⑶［wun,sat］*［sun..sat］⑷［sun］-［mon,tue］⑸［mon］-［mon,tue］⑹［sun..sat］-［mon,sun,sat］⑺［1,2,3,5］=［1,5,3,2］⑻［1,2,3,4］<>［1..4］⑼［1,2,3,5］>=［1..3］⑽［1..5］<=［1..4］⑾［1,2,3］<=［1..3］⑿2in［1..10］答:表达式的值分别是:⑴［sun,sat,tue,fri］⑵［］⑶［sat］⑷［sum］⑸［］⑹［tue..fri］⑺TRUE⑻FALSE⑼TRUE⑽FALSE⑾TRUE⑿TRUE例2、输入一系列字符，对其中的数字字符、字母字符和其它字符分别计数。输入‘？’后结束。programex10_2;varid,il,io:integer;ch:char;letter:setofchar;digit:setof'0'..'9';beginletter=['a'..'z','A'..'Z'];digit:=['0'..'9'];id:=0;il:=0;io:=0;repeatread(ch);ifchinletterthenil:=il+1elseifchindigitthenid:=id+1elseio:=io+1;untilch='?';writeln('letter:',il,'digit:',id,'Other:',io);end.例3、调用随机函数产生10个互不相同的随机整数（0<=x<=40）,放入集合中并一起输出（5个一行）。programpx8_1;vara:setof0..40;I,m,n:integer;BeginA:=[];n:=0;Randomize;RepeatM:=random(41);Ifnot(mina)thenbegina:=a+[m];N:=n+1;End;62 全国青少年信息学奥赛培训教程Untiln=10;N:=0;ForI:=0to40doIfIinathenbeginwrite(I:4);N:=n+1;If(nmod5)thenwritelnEnd;End.例4、编程把一个任意十进制正整数转换成二进制数，要求利用集合表示二进制数。如18的二进制数为10010，则集合的值为[2，5]，即倒数地2位和倒数第5位是1，其余位是0。输入样例：18=（10010）2[问题分析]将十进制正整数ten转换成二进制数，只要把ten不停地除以2求余数，每除1次，则num:=num+1,若求得的余数为1则将此时的num存入集合中，最后按要求一起输出。programpx8_5;varten,t,num,I:integer;two:setof1..32;Beginwrite(‘inputainteger:’);readln(ten);t:=ten;two:=[];num:=0;whilet<>0dobeginnum:=num+1;iftmod2=1thentwo:=two+[num];t:=tdiv2;end;iften=0thenwriteln(ten,’=(0)2’)elsebeginwrite(ten,’=(‘);forI:=numdownto1doifIinteothenwrite(‘1’)elsewrite(‘0’);writeln(‘)2’);end;readln;end.【上机练习8.1】1．调用随机函数产生10个互不相同的随机整数（0≤x≤40），放入集合中并一起输出（5个一行）。提示：随机函数使用randomize；{初始化}m:=random(n)；{n，m都是整数，那么0≤m≤n-1}2．编写一个程序读入一系列字符，将它们分别放在英文字母、数字、其他符号三个集合中，统计出各个集合中元素的个数（区分大小写），并输出这三个集合中的元素。3．利用随机函数产生2个整数数列A，B，每个数列包含20个不同数（0到50之间），程序要求：（1）找出在B中出现而在A中没有出现的那些数，并输出；（2）找出在B中出现而在A中也出现的那些数，并输出。4．输入一个大写字母字符串，找出未在此串中出现的所有大写字母。5．编写一个译码程序，将输入的一串字符，（只有小写字母、数字和空格，输入时以句号结束）翻译成原码。译码规则如下：①数字0，1，2，3，…，9分别和字母a，b，c，…，j互换；②字母k，m，p，t，y分别和它们的后继互换；⑶其他字母和空格保持不变。6．口袋中有红、黄、蓝、白、黑5种颜色的5只小球，每次从口袋中取出3只球，问：最多有几种不同颜色的组合，并输出每一种方案。63 全国青少年信息学奥赛培训教程第二节记录类型在程序中对于组织和处理大批量的数据来说，数组是一种十分方便而又灵活的工具，但是数组在使用中有一个基本限制，这就是：一个数组中的所有元素都必须具有相同的类型。但在实际问题中可能会遇到另一类数据，它是由性质各不相同的成份组成的，即它的各个成份可能具有不同的类型。例如，有关一个学生的数据包含下列项目：学号字符串类型姓名字符串类型年龄整型性别字符型成绩实型数组Pascal给我们提供了一种叫做记录的结构类型。在一个记录中，可以包含不同类型的并且互相相关的一些数据。（一）记录类型的定义在pascal中，记录由一组称为“域”的分量组成，每个域可以具有不同的类型。记录类型定义的一般形式：record<域名1>:<类型1>;<域名2>:<类型2>;::<域名n>:<类型n>;end;说明：①域名也称域变量标识符，应符合标识符的语法规则。在同一个记录中类型中，各个域不能取相同的名，但在不同的记录类型中，两个类型中的域名可以相同。②记录类型的定义和记录变量可以合并为一个定义，如：typedate=recordyear:1900..1999;month:1..12;day:1..31end;varx:date;可以合并成:varx:recordyear:1900..1999;month:1..12;day:1..31end;③对记录的操作,除了可以进行整体赋值，还能对记录的分量──域变量进行。④域变量的表示方法如下：记录变量名.域名如前面定义的记录X,其3个分量分别为:x.year，x.month，x.day。⑤域变量的使用和一般的变量一样,即域变量是属于什么数据类型，便可以进行那种数据类型所允许的操作。（二）记录的嵌套当一个记录类型的某一个域类型也是记录类型的时候，我们说发生了记录的嵌套，看下面的例子：例5某人事登记表可用一个记录表示,其中各项数据具有不同的类型，分别命名一个标识符。而其中的“出生年月日”又包括三项数据，还可以用一个嵌套在内层的记录表示。具体定义如下:64 全国青少年信息学奥赛培训教程typesexs=(male,female);date=recordyear:1900..1999;month:1..12;day:1..31;end;personal=recordname:string[15];sex:sexs;birthdate:date;home:string[40];end;例6设计一个函数比较两个dates日期类型记录变量的迟早。设函数名、形参及函数类型定义为：AearlyB(A,B:dates):boolean;函数的形参为两个dates类型的值参数。当函数值为true时表示日期A早于日期B,否则日期A迟于日期B或等于日期B。显然不能对Ａ、Ｂ两个记录变量直接进行比较，而要依具体的意义逐域处理。源程序如下：programex6_7;typedates=recordyear:1900.1999;month:1..12;day:1..31end;varx,y:dates;functionAearlyB(A,B:dates):boolean;varearln:boolean;beginearly:=false;if(A.yeardo<语句>功能:在do后的语句中使用with后的记录的域时,只要直接写出域名即可，即可以省略图10.2.2中的记录变量名和“.”。说明:①一般在with后只使用一个记录变量名。如：write('Inputyear:');readln(x.year);write('Inputmonth:');readln(x.month);write('Inputday:');readln(x.day);65 全国青少年信息学奥赛培训教程可以改写成:withxdobeginwrite('Inputyear:');readln(year);write('Inputmonth:');readln(month);write('Inputday:');readln(day);end;②设x,y是相同类型的记录变量，下列语句是非法的：withx,ydo...;③with后接若干个记录名时,应是嵌套的关系。如有记录说明：varx:recordi:integer;y:recordj:0..5;k:real;end;m:realend;可以使用:withxdobeginread(i);withydoread(j,k);readln(m);end;或简写为:withx,ydoreadln(i,j,k,m);例7读入10个日期，再对每个日期输出第二天的日期。输入日期的格式是月、日、年，如9□30□1993，输出的格式为10/1/1993。分析:可用一个记录变量today表示日期。知道一个日期后要更新为第二天的日期，应判断输入的日期是否为当月的最后一天，或当年的最后一天。programex6_8;typedate=recordmonth:1..12;day:1..31;year:1900..1999;end;vartoday:array[1..10]ofdate;i:integer;maxdays:28..31;beginfori:=1to10do{输入10个日期}withtoday[i]doreadln(month,day,year);fori:=1to10dowithtoday[i]do{求第i个日期中月份最后一天maxdays}begincasemonthof1,3,5,7,8,10,12:maxdays:=31;4,6,9,11:maxdays:=30;66 全国青少年信息学奥赛培训教程2:if(yearmod400=0)or(yearmod4=0)and(yearmod100<>0)thenmaxdays:=29elsemaxdays:=28;end;ifday=maxdaysthenbeginday:=1;ifmonth=12thenbeginmonth:=1;year:=year+1;endelsemonth:=month+1;endelseday:=day+1;writeln(month,'/',day,'/',year);end;end.第三节综合应用实例例8、利用记录类型将N个数由大到小排序，输出排序结果并显示每个数原来的位置序号。ProgramEx59;Typedd=Record{定义DD记录类型}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].ii=string[n];var字符串变量:字符串类型标识符;其中:n是定义的字符串长度,必须是0~255之间的自然整数,第0号单元中存放串的实际长度,程序运行时由系统自动提供,第1~n号单元中存放串的字符。若将string[n]写成string，则默认n值为255。例如：typeman=string[8]；line=string；varname：man；screenline：line；另一种字符类型的定义方式为把类型说明的变量定义合并在一起。78 全国青少年信息学奥赛培训教程例如：VARname：STRING[8]；screenline：STRING；TurboPascal中，一个字符串中的字符可以通过其对应的下标灵活使用。例如：varname：string；beginreadln（nsme）；fori：=1toord（name[0]）dowriteln（name[i]）；end.语句writeln（name[i]）输出name串中第i个字符。例2、求输入英文句子单词的平均长度。programex8_2;varch:string;s,count,j:integer;beginwrite('Thesentenceis:');readln(ch);s:=0;count:=0;j:=0;repeatinc(j);ifnot(ch[j]in[':',',',';','''','!','?','.',''])theninc(s);ifch[j]in['','.','!','?']theninc(count);until(j=ord（ch[0]))or(ch[j]in['.','!','?']);ifch[j]<>'.'thenwriteln('Itisnotasentence.')elsewriteln('Averagelengthis',s/count:10:4);end.分析:程序中，变量s用于存句子中英文字母的总数，变量count用于存放句子中单词的个数，ch[j]表示ch串中的第j个位置上的字符，ord（ch[0]）为ch串的串长度。程序充分利用TurboPascal允许直接通过字符串下标得到串中的字符这一特点，使程序比较简捷。第二节字符串的操作一、字符串的运算和比较由字符串的常量、变量和运算符组成的表达式称为字符串表达式。字符串运算符包括：1．+：连接运算符例如：‘Turbo’+‘PASCAL’的结果是‘TurboPASCAL’。若连接的结果字符串长度超过255，则被截成255个字符。若连接后的字符串存放在定义的字符串变量中，当其长度超过定义的字符串长度时，超过部份字符串被截断。例如：varstr1，str2，str3：string[8]；beginstr1：=‘Turbo’；str2：=‘PASCAL’；str3：=str1+str2；end．则str3的值为：‘TurboPA’。79 全国青少年信息学奥赛培训教程2．=、〈〉、〈、〈=、〉、〉=：关系运算符两个字符串的比较规则为，从左到右按照ASCⅡ码值逐个比较，遇到ASCⅡ码不等时,规定ASCⅡ码值大的字符所在的字符串为大。例如：‘AB’〈‘AC’结果为真；‘12’〈‘2’结果为真；‘PASCAL’=‘PASCAL’结果为假；例3、对给定的10个国家名，按其字母的顺序输出。programex8_3;vari,j,k:integer;t:string[20];cname:array[1..10]ofstring[20];beginfori:=1to10doreadln(cname[i]);fori:=1to9dobegink:=i;forj:=i+1to10doifcname[k]>cname[j]thenk:=j;t:=cname[i];cname[i]:=cname[k];cname[k]:=t;end;fori:=1to10dowriteln(cname[i]);end.分析：程序中，当执行到ifcname[k]>cname[j]时，自动将cname[k]串与cname[j]串中的每一个字符逐个比较，直至遇到不等而决定其大小。这种比较方式是计算机中字符串比较的一般方式。二、字符串的函数和过程TurboPascal提供了八个标准函数和标准过程，见下表，利用这些标准函数与标准过程，一些涉及到字符串的问题可以灵活解决。函数和过程名功能说明copy(s,m,n)取s中第m个字符开始的n个字符若m大于s的长度，则返回空串；否则，若m+n大于s的长度，则截断length(s)求s的动态的长度返回值为整数pos(sub,s)在s中找子串sub返回值为sub在s中的位置，为byte型insert(sour,s,m)在s的第m个字符位置处插入子串sour若返回串超过255，则截断delete(s,m,n)删除s中第m个字符开始的n个字符串若m大于s的长度，则不删除；否则，若m+n大于s的长度，则删除到结尾str(x[:w[:d]],s)将整数或实数x转换成字符串sw和d是整型表达式，意义同带字宽的write语句val(s,x,code)将字符串S转换成整数或实数x若S中有非法字符，则code存放非法字符在S中的下标；否则，code为零。code为整型upcase(ch)将字母ch转换成大写字母若ch不为小写字母，则不转换例4效对输入日期(以标准英语日期,月/日/年)的正确性，若输入正确则以年．月．日的方式输出。programex8_4;constmax:array[1..12]ofbyte=(31,29,31,30,31,30,31,31,30,31,30,31);varst:string;p,w,y,m,d:integer;procedureerr;begin80 全国青少年信息学奥赛培训教程write('InputError!');readln;halt;end;procedureinit(varx:integer);beginp:=pos('/',st);if(p=0)or(p=1)or(p>3)thenerr;val(copy(st,1,p-1),x,w);ifw<>0thenerr;delete(st,1,p);end;beginwrite('TheDateis:');readln(st);init(m);init(d);val(st,y,w);ifnot(length(st)<>4)or(w<>0)or(m>12)or(d>max[m])thenerr;if(m=2)and(d=29)thenifymod100=0thenbeginifymod400<>0thenerr;endelseifymod4<>0thenerr;write('Date:',y,'.',m,'.',d);readln;end.分析：此题的题意很简单，但在程序处理时还需考虑以下几方面的问题。1．判定输入的月和日应是１位或２位的数字，程序中用了一个过程inst，利用串函数pos，求得分隔符/所在的位置而判定输入的月和日是否为１位或２位，利用标准过程val判定输入的月和日是否为数字；2．判定月和日是否规定的日期范围及输入的年是否正确；3．若输入的月是2月份，则还需考虑闰年的情况。例5对输入的一句子实现查找且置换的功能。programex8_5;vars1,s,o:string;i:integer;beginwrite('Thetext:');readln(s1);write('Find:');readln(s);write('Replace:');readln(o);i:=pos(s,s1);whilei<>0dobegindelete(s1,i,length(s));insert(o,s1,i);i:=pos(s,s1);end;writeln(s1);readln;end.分析:程序中,输入要查找的字符串及要置换的字符串,充分用上了字符串处理的标准过程delete、insert及标准函数pos。81 全国青少年信息学奥赛培训教程第三节字符串的综合应用例6、判断从键盘输入的字符串是否为回文（从左到右和从右到左读一串字符的值）是一样的，如ABCDCBA，1234321，11，1），串长<100，且以点号‘．’结束。2000年竞赛题：判断一个数是否为回文数。VARLETTER：ARRAY[1．．100]OFCHAR；I，J：0．．100；CH：CHAR；BEGINWRITELN（‘INPUTASTRING：’）；I：=O；READ（CH）；WHILECH<>‘．’DOBEGINI：=I+1；LETTER[I]：=CH；READ（CH）；END；J：=1；{I指向数组的尾部，J指向数组的头部，逐个比较}WHILE（J=ITHENWRITELN（‘YES’）ELSEWRITELN（‘NO’）；END．例7：统计一个英文句子中有多少英文单词。假设句子中字符数小于80个，单词间用至少一个空格隔开（可以有多个空格），句子头部可以有多个空格，句子以‘*’作为结束标志。如：‘□□□THIS□□IS□A□□GOOD□□□BOOK！*’CONSTN=80；VARSTR：STRING[N]；PREC：CHAR；NUM，IINTEGER；BEGINREADLN（STR）；PREC：=BLANK；NUM：=0；FORI：=1TONDOBEGINIF（STR[I]<>BLANK）AND（PREC=BLANK）THENNUM：=NUM+1；PREC：=STR[I]END；WRITELN（‘NUMOFWORDSIS：’，NUM：3）；END．82 全国青少年信息学奥赛培训教程例8：设姓名最多有15个字符组成，其中姓氏至多5个字符，姓与名之间用空格分隔，输入若干姓名，以‘*’结束，统计各种姓氏的个数。分析：为统计所读姓名中不同姓氏的人数，首先需要把读入的姓氏保存在一张表TABLE中，读入一个姓名时，先要到TABLE中查一下是否已有相同姓氏了，如果有只需将人数加1；如果没有则TABLE的长度加1，将此姓添加到表中，同时将此姓的人数置为1，重复以上过程，直到读到‘*’结束。CONSTN=20；{N要足够大}B5=‘□□□□□’；VARI，SIZE，P：INTEGER；FIND：BOOLEAN；TABLE：ARRAY[1．．N]OFARRAY[1．．5]OFCHAR；NUM：ARRAY[１．．N]OFINTEGER；NAME：ARRAY[１．．15]OFCHAR；XING：ARRAY[１．．5]OFCHAR；BEGINFORI：=1TONDOTABLE[I]：=B5；SIZE：=0；WRITELN（‘INPUTNAMES：’）；READLN（NAME）；WHILENAME[1]<>‘*’DOBEGINXING：=B5；P：=1；WHILE（P<=5）AND（NAME[P]<>‘□’）DOBEGINXING[P]：=NAME[P]；P：=P+1END；FIND：=FALSE；I：=0；WHILE（NOTFIND）AND（I2,1->3,3->1,4->3,5->2,7->4,8…14322马130123456784（a）（b）图184 全国青少年信息学奥赛培训教程【算法分析】如图4（b）,马最多有四个方向，若原来的横坐标为j、纵坐标为i,则四个方向的移动可表示为：1:（i,j）→（i+2,j+1）；(i<3,j<8)2:（i,j）→（i+1,j+2）；(i<4,j<7)3:（i,j）→（i-1,j+2）；(i>0,j<7)4:（i,j）→（i-2,j+1）；(i>1,j<8)搜索策略：S1:Ａ[１]:=(0,0);S2:从Ａ[1]出发，按移动规则依次选定某个方向，如果达到的是（4,8）则转向S3,否则继续搜索下一个到达的顶点；S3:打印路径。【算法设计】proceduretry(i:integer);{搜索}varj:integer;beginforj:=1to4do{试遍4个方向}if新坐标满足条件thenbegin记录新坐标;if到达目的地thenprint{统计方案，输出结果}elsetry(i+1);{试探下一步}退回到上一个坐标，即回溯;end;end;【参考程序】programexam2;constx:array[1..4,1..2]ofinteger=((2,1),(1,2),(-1,2),(-2,1));{四种移动规则}vart:integer;{路径总数}a:array[1..9,1..2]ofinteger;{路径}procedureprint(ii:integer);{打印}vari:integer;begininc(t);{路径总数}fori:=1toii-1dowrite(a[i,1],',',a[i,2],'-->');writeln('4,8',t:5);readln;end;proceduretry(i:integer);{搜索}varj:integer;beginforj:=1to4doif(a[i-1,1]+x[j,1]>=0)and(a[i-1,1]+x[j,1]<=4)and(a[i-1,2]+x[j,2]>=0)and(a[i-1,2]+x[j,2]<=8)thenbegina[i,1]:=a[i-1,1]+x[j,1];a[i,2]:=a[i-1,2]+x[j,2];if(a[i,1]=4)and(a[i,2]=8)thenprint(i)elsetry(i+1);{搜索下一步}a[i,1]:=0;a[i,2]:=0end;end;85 全国青少年信息学奥赛培训教程BEGIN{主程序}try(2);END.【例2】选书学校放寒假时，信息学竞赛辅导老师有A，B，C，D，E五本书，要分给参加培训的张、王、刘、孙、李五位同学，每人只能选一本书。老师事先让每个人将自己喜欢的书填写在如下的表格中。然后根据他们填写的表来分配书本，希望设计一个程序帮助老师求出所有可能的分配方案，使每个学生都满意。ABCDE学生张同学YY王同学YYY刘同学YY孙同学Y李同学YY【算法分析】可用穷举法，先不考虑“每人都满意”这一条件，这样只剩“每人选一本且只能选一本”这一条件。在这个条件下，可行解就是五本书的所有全排列，一共有5！=120种。然后在120种可行解中一一删去不符合“每人都满意”的解，留下的就是本题的解答。为了编程方便，设1，2，3，4，5分别表示这五本书。这五个数的一种全排列就是五本书的一种分发。例如54321就表示第5本书（即E）分给张，第4本书（即D）分给王，……，第1本书（即A）分给李。“喜爱书表”可以用二维数组来表示，1表示喜爱，0表示不喜爱。【算法设计】S1：产生5个数字的一个全排列；S2：检查是否符合“喜爱书表”的条件，如果符合就打印出来；S3：检查是否所有的排列都产生了，如果没有产生完，则返回S1；S4：结束。上述算法有可以改进的地方。比如产生了一个全排列12345，从表中可以看出，选第一本书即给张同学的书，1是不可能的，因为张只喜欢第3、4本书。这就是说，1××××一类的分法都不符合条件。由此想到，如果选定第一本书后，就立即检查一下是否符合条件，发现1是不符合的，后面的四个数字就不必选了，这样就减少了运算量。换句话说，第一个数字只在3、4中选择，这样就可以减少3/5的运算量。同理，选定了第一个数字后，也不应该把其他4个数字一次选定，而是选择了第二个数字后，就立即检查是否符合条件。例如，第一个数选3，第二个数选4后，立即检查，发现不符合条件，就应另选第二个数。这样就把34×××一类的分法在产生前就删去了。又减少了一部分运算量。综上所述，改进后的算法应该是：在产生排列时，每增加一个数，就检查该数是否符合条件，不符合，就立刻换一个，符合条件后，再产生下一个数。因为从第I本书到第I+1本书的寻找过程是相同的，所以可以用递归方法。算法设计如下：proceduretry(i);beginforj:=1to5dobeginif第i个同学分给第j本书符合条件thenbegin记录第i个数ifi=5then打印一个解elsetry(i+1);删去第i个数字end;end;end;86 全国青少年信息学奥赛培训教程【参考程序】programexam3;typefive=1..5;constlike:array[five,five]of0..1=((0,0,1,1,0),(1,1,0,0,1),(0,1,1,0,0),(0,0,0,1,0),(0,1,0,0,1));name:array[five]ofstring[6]=('zhang','wang','liu','sun','li');varbook:array[1..5]of0..5;flag:setoffive;c:integer;procedureprint;vari:integer;begininc(c);writeln('answer',c,':');fori:=1to5dowriteln(name[i]:10,':',chr(64+book[i]));end;proceduretry(i:integer);varj:integer;beginforj:=1to5doifnot(jinflag)and(like[i,j]>0)thenbeginflag:=flag+[j];book[i]:=j;ifi=5thenprintelsetry(i+1);flag:=flag-[j];book[i]:=0;end;end;beginflag:=[];c:=0;try(1);readlnend.输出结果：zhang:Cwang:Aliu:Bsun:Dli:E87 全国青少年信息学奥赛培训教程第二节贪心算法一、贪心法的思想在实际问题中，经常会遇到求一个问题的最优解，这就是所谓的最优化问题。最优化问题往往包含一组限制条件和一个优化函数，符合条件的解决方案称为可行解，使优化函数取得最佳值的可行解称为最优解。贪心法是求解这类问题的一种常用算法，它的思想和做法是这样：从问题的某一个初始解出发，采用逐步构造（迄今为止）最优解的方法向给定的目标前进。在每个局部阶段，都做出一个看上去最优的决策（即某种意义下的、或某个标准下的局部最优解），并期望通过每次所做的局部最优选择，能够产生出一个全局最优解来。做出贪心决策的依据称为贪心准则（策略）。贪心与递推不同的是，推进的每一步不是依据某一固定的递推公式，而是做一个当时看似最佳的贪心选择，从而不断地将问题实例归纳为更小的相似子问题。在有些最优化问题中，采用贪心法求解不能保证一定得到最优解，这时可以采取一些变形的贪心法或其他解决最优化问题的方法(如动态规划方法)。下面我们通过几个应用实例来看看贪心法的应用。二、应用举例【例3】删数问题通过键盘输入一个高精度的正整数n(n的有效位数≤240)，去掉其中任意s个数字后，剩下的数字按原左右次序将组成一个新的正整数。编程对给定的n和s，寻找一种方案，使得剩下的数字组成的新数最小。输入：ns输出：最后剩下的最小数【样例输入】178543S=4【样例输出】13【问题分析】由于正整数n的有效位数最大可达240位，所以可以采用字符串类型来存储n。那么，应如何来确定该删除哪s位呢？是不是只要删掉最大的s个数字就可以了呢？为了尽可能地逼近目标，我们选取的贪心策略为：每一步总是选择一个使剩下的数最小的数字删去，即按高位到低位的顺序搜索，若各位数字递增，则删除最后一个数字，否则删除第一个递减区间的首字符。然后回到串首，按上述规则再删除下一个数字。重复以上过程s次，剩下的数字串便是问题的解了。例如：对n=178543，s=4，删数的过程如下：n=178543{删掉8}n=17543{删掉7}n=1543{删掉5}n=143{删掉4}n=13{解为13}这样，删数问题就与如何寻找递减区间首字符这样一个简单的问题对应起来了。要注意一个细节问题：可能会出现字符串首部有若干个0(甚至整个字符串都是0)的情况。按以上贪88 全国青少年信息学奥赛培训教程心策略编制的程序框架如下：输入s,n;whiles>0dobegini:=1;{从串首开始找}while(i1)and(n[1]=‘0’)dodelete(n,1,1);{删去串首可能产生的无用零}输出n;【例4】0/1背包问题有一个容量为weight的背包，现在要从n件物品中选取若干件装入背包中，每件物品i的重量为w[i]，价值为p[i]。定义一种可行的背包装载为：背包中物品的总重不能超过背包的容量，并且一件物品要么全部选取，要么不选取。定义最佳装载是指所装入的物品价值最高，并且是可行的背包装载。【样例输入】11{weight}4{n}2467{w[i]}6101213{p[i]}【样例输出】010123【问题分析】设有数组chosen[1..n]，若chosen[i]=1，表示物品i被装入了背包中，chosen[i]=0表示物品i不装入背包中。那么，chosen[0,1,0,1]就是一种可行的背包装载方案，也是一种最佳的装载方案，此时的总价值为23。【算法分析】0/1背包问题有好几种贪心策略，每种贪心策略都是采用多步过程来完成背包的装入，在每一步中，都是利用某种固定的贪心准则来选择将某一件物品装入背包。一种贪心准则为：从剩余的物品中，选出可以装入背包的价值最大的物品。这种贪心准则不能保证得到最优解。例如，weight=105，n=3，w=[100,10,10]，p=[20,15,15]，按照以上这种“价值贪心准则”，获得的解为choice=[1,0,0]，这种方案的总价值为20，而最优解为choice=[0,1,1]，其总价值为30。另一种方案是“重量贪心准则”，即从剩下的物品中，选择可以装入背包的重量最小的物品。虽然这种规则对于前面的例子能产生最优解，但在一般情况下，不一定能得到最优解，例如，weight=25，n=2，w=[10,20]，p=[5,100]。获得的解为choice=[1,0]，总价值为5，比最优解choice=[0,1]的总价值100要差。本题还有一种方案，即“单位价值贪心准则”，这种方案是从剩余物品中，选择可装入包的p[i]/w[i]值最大的物品，这种策略也不能保证得到最优解。例如，weight=30，n=3，w=[20,15,15]，p=[40,25,25]。获得的解为choice=[1,0,0]，总价值为40，而最优解为choice=[0,1,1]的总价值为50。其实，0/1背包问题是一个复杂的NP问题。对于这类问题，也许根本就不存在多项式时间的算法。在用贪心法解这类问题时，我们还可以结合其他的一些优化策略，如启发式策略等，使解的结果与最优解相差在一定的范围内，也就是，可以得到原问题的近似最优解。另外，在解本题这样的问题时，还可以采用动态规划方法。89 全国青少年信息学奥赛培训教程第三节分治算法一、分治法的思想与要点为了说明分治法的思想，我们先来看一个问题：如果有16枚硬币，其中有一枚是伪造的，并且那枚伪造硬币的重量和真硬币的重量不同(假设比真币轻)。你能不能用最少的比较次数找出这枚伪造的硬币?为了帮助你完成这一任务，将提供一台可用来比较两组硬币重量的仪器，利用这台仪器，可以知道两组硬币的重量是否相同。要解决这一问题，可以两两比较。或者，也可以这样来找：将全部硬币分成两组，一次比较两组。一次比较后，可以舍弃完全是真币的那一组，只对另一组进行下一步的比较。在这种做法下，问题的规模明显缩小了，而且每一次比较的规模都成倍地减少。在这种方法下，参与比较的硬币越多，处理起来就越快，投机性也大大减少。解决方法的关键在于能将大问题分割成若干小问题，小问题与原有问题是完全类似的。通常，我们将这种大化小的策略称为分治法（“分而治之”）。分治法在设计查找、排序等算法时很有效，最常用的分治法有二分法、归并法、快速排序等。二、应用举例【例5】循环比赛设有N个选手进行循环比赛，其中N=2M，要求每名选手要与其他N-1名选手都赛一次，每名选手每天比赛一次，循环赛共进行N-1天，要求每天没有选手轮空。输入：M输出：表格形式的比赛安排表【样例输入】3【样例输出】1234567821436587341278564321876556781234658721437856341287654321【问题分析】以M=3(即N=23=8)为例，可以根据问题要求，制定出如下图所示的一种方案：第一天第二天第三天第四天第五天第六天第七天123456782143658734127856AB43218765567812346587214378563412CD87654321以表格的中心为拆分点，将表格分成A、B、C、D四个部分，就很容易看出有A=D，B=C，并且，这一规律同样适用于各个更小的部分。90 全国青少年信息学奥赛培训教程这样，对8个队的赛事排列就逐步减化为对4个队的排列，然后又进一步减化为对2个队的排列，最后就成为1个队的排列。因此，这一问题可以采用分治法的思想来解决。在设计程序时，采用由小到大的方法进行扩展，而数组下标的处理是解决该问题的关键。【算法过程】BeginN:=2m;对数组A的第一行赋值;fors:=1tokdo{s表示层数}beginn:=n/2;fort:=1tondofori:=m+1to2*mdoforj:=m+1to2*mdobegina[i,j+(t-1)*m*2]:=a[i-m,j+(t-1)*m*2-m];a[i,j+(t-1)*m*2-m]:=a[i-m,j+(t-1)*m*2];end;m:=m*2;end;end.【例6】快速排序（1）基本思想在当前无序区R[1..H]中任取一个数据元素作为比较的"基准"(不妨记为X)，用此基准将当前无序区划分为左右两个较小的无序区：R[1..I-1]和R[I+1..H]，且左边的无序子区中数据元素均小于等于基准元素，右边的无序子区中数据元素均大于等于基准元素，而基准X则位于最终排序的位置上，即R[1..I-1]≤X.Key≤R[I+1..H](1≤I≤H)，当R[1..I-1]和R[I+1..H]均非空时，分别对它们进行上述的划分过程，直至所有无序子区中的数据元素均已排序为止。（2）排序过程【示例】初始关键字[4938659776132749]第一次交换后［2738659776134949］第二次交换后［2738499776136549］J向左扫描，位置不变，第三次交换后［2738139776496549］I向右扫描，位置不变，第四次交换后［2738134976976549］J向左扫描［2738134976976549］（一次划分过程）初始关键字［4938659776132749］一趟排序之后［273813］49［76976549］二趟排序之后［13］27［38］49［4965］76［97］三趟排序之后1327384949［65］7697最后的排序结果1327384949657697各趟排序之后的状态91 全国青少年信息学奥赛培训教程快速排序算法Constn=10;Vara:array[1..n]ofinteger;k:integer;procedureqsort(low,high:integer);vari,j:integer;x:integer;beginiflow=x)and(ix)and(imiddodec(j);{在右半部分寻找比中间数小的数}ifi<=jthenbegin{若找到一组与排序目标不一致的数对则交换它们}swap(a[i],a[j]);inc(i);dec(j);{继续找}end;untili>j;ifl0这一条件。t:=0form:=1to11doforl:=1to25dobeginn:=100-9*m-lif(n>0)and(2*m+2*n+4*l=100)thenbeginwriteln(m,n,l);t:=t+1;end;end;writeln(t);【方法4】：进一步的优化将式(1)×2再减去(2)，这样就消去N，得到：16M–2L=100整理上式可得：L=8M–50(4)这样就可以将两重循环进一步简化成一重循环。但是，(4)式由M计算出来的L也可能会出现负数，这是不允许的，故在循环体中的语句是：if(l>0)and(n>0)thenbeginwriteln(m,n,l);t:=t+1;end;表达式(4)应写在表达式(3)的前面，即必须先求出l，才能求n。94 全国青少年信息学奥赛培训教程t:=0;form:=1to11dobeginl:=8*m–50;n:=100-9*m-l;if(l>0)and(n>0)thenbeginwriteln(m,n,l);t:=t+1;end;end;writeln(t);上面的四种方法都能给出正确的结果，但所需循环次数分别是100*100*100、11*50*25、11*25、11次，通过一系列优化措施，以及将不必要的循环去掉，使得程序的效率不断地提高。提高穷举法效率的方法1）在步长值不变的情况下，减少循环变量的初值和终值的差距；2）在初值、终值不变的情况下，增大步长值；3）减少循环嵌套的层数。具体使用时，应根据题目的条件，灵活运用。【例8】装箱问题（NOIP2001）【问题描述】有一个箱子的容量为V（V为正整数，且满足0≤V≤20000），同时有n件物品（00)and(v-s0theniff[i,j]>d[i,j,k]+f[i+1,k]thenf[i,j]:=d[i,j,k]+f[i+1,k];writeln(f[1,1]);readln;end.【例10】数塔问题（IOI94）有形如图2所示的数塔，从顶部出发，在每一结点可以选择向左走或是向右走，一起走到底层，要求找出一条路径，使路径上的值最大。图2这道题如果用枚举法，在数塔层数稍大的情况下（如40），则需要列举出的路径条数将是一个非常庞大的数目。如果用贪心法又往往得不到最优解。在用动态规划考虑数塔问题时可以自顶向下的分析，自底向上的计算。从顶点出发时到底向左走还是向右走应取决于是从左走能取到最大值还是从右走能取到最大值，只要左右两道路径上的最大值求出来了才能作出决策。同样的道理下一层的走向又要取决于再下一层上的最大值是否已经求出才能决策。这样一层一层推下去，直到倒数第二层时就非常明了。所以实际求解时，可从底层开始，层层递进，最后得到最大值。实际求解时应掌握其编程的一般规律，通常需要哪几个100 全国青少年信息学奥赛培训教程关键数组来存储变化过程这一点非常重要。一般说来，很多最优化问题都有着对应的计数问题；反过来，很多计数问题也有着对应的最优化问题。因此，我们在遇到这两类问题时，不妨多联系、多发展，举一反三，从比较中更深入地理解动态规划的思想。其实递推和动态规划这两种方法的思想本来就很相似，也不必说是谁借用了谁的思想。关键在于我们要掌握这种思想，这样我们无论在用动态规划法解最优化问题，或是在用递推法解判定型、计数问题时，都能得心应手、游刃有余了。【算法分析】①贪心法往往得不到最优解：本题若采用贪心法则：13-11-12-14-13，其和为63但存在另一条路：13-8-26-15-24，其和为86。贪心法问题所在：眼光短浅。②动态规划求解：动态规划求解问题的过程归纳为：自顶向下的分析，自底向上计算。其基本方法是：划分阶段：按三角形的行，划分阶段，若有n行，则有n-1个阶段，找到问题求解的最优路径。A．从根结点13出发，选取它的两个方向中的一条支路，当到倒数第二层时，每个结点其后继仅有两个结点，可以直接比较，选择最大值为前进方向，从而求得从根结点开始到底端的最大路径。B．自底向上计算：（给出递推式和终止条件）①从底层开始，本身数即为最大数；②倒数第二层的计算，取决于底层的数据：12+6=18，13+14=27，24+15=39，24+8=32；③倒数第三层的计算，取决于底二层计算的数据：27+12=39，39+7=46，39+26=65④倒数第四层的计算，取决于底三层计算的数据：46+11=57，65+8=73⑤最后的路径：13——8——26——15——24C．数据结构及算法设计①图形转化：直角三角形，更于搜索：向下、向右②用三维数组表示数塔：a[x,y,1]表示行、列及结点本身数据,a[x,y,2]能够取得最大值,a[x,y,3]表示前进的方向——0向下，1向右；③算法：数组初始化，输入每个结点值及初始的最大路径、前进方向为0；从倒数第二层开始向上一层求最大路径，共循环N-1次；从顶向下，输出路径：关键是J的值，由于行逐渐递增，表示向下，究竟向下还是向右取决于列的值。若J值比原先多1则向右，否则向下。数塔问题的样例程序如下：vara:array[1..50,1..50,1..3]oflongint;x,y,n:integer;beginwrite('pleaseinputthenumberofrows:');readln(n);forx:=1tondofory:=1toxdobeginread(a[x,y,1]);a[x,y,2]:=a[x,y,1];a[x,y,3]:=0end;101 全国青少年信息学奥赛培训教程forx:=n-1downto1dofory:=1toxdoifa[x+1,y,2]>a[x+1,y+1,2]thenbegina[x,y,2]:=a[x,y,2]+a[x+1,y,2];a[x,y,3]:=0endelsebegina[x,y,2]:=a[x,y,2]+a[x+1,y+1,2];a[x,y,3]:=1end;writeln('max=',a[1,1,2]);y:=1;forx:=1ton-1dobeginwrite(a[x,y,1],'->');y:=y+a[x,y,3]end;writeln(a[n,y,1])end.【输入】：5{数塔层数}1311812726614158127132411【输出】max=8613—8—26—15—24【例11】求最长不下降序列㈠问题描述：设有由n个不相同的整数组成的数列，记为:b(1)、b(2)、……、b(n)且b(i)<>b(j)(i<>j)，若存在i1b(n)则存在长度为1的不下降序列b(n-1)或b(n)。3·一般若从b(i)开始，此时最长不下降序列应该按下列方法求出:在b(i+1),b(i+2),…,b(n)中，找出一个比b(i)大的且最长的不下降序列，作为它的后继。㈢数据结构：为算法上的需要，定义一个数组整数类型二维数组b(N,3)1·b(I,1)表示第I个数的数值本身；2·b(I,2)表示从I位置到达N的最长不下降序列长度3·b(I,3)表示从I位置开始最长不下降序列的下一个位置，若b[I,3]=0则表示后面没有连接项。102 全国青少年信息学奥赛培训教程㈣求解过程：①从倒数第二项开始计算，后面仅有1项，比较一次，因63>15，不符合要求，长度仍为1。②从倒数第三项开始其后有2项，需做两次比较，得到目前最长的不下降序列为2，如下表：11121314……11121314226315……21226315211……32111300……121300㈤一般处理过程是：①在i+1,i+2,…,n项中，找出比b[I,1]大的最长长度L以及位置K;②若L>0，则b[I,2]:=L+1;b[I,3]:=k;最后本题经过计算，其数据存储表如下：123456789101112131413791638243718441921226315787634352432114348979101311121300初始化:fori:=1tondobeginread(b[i,1]);b[i,2]:=1;b[i,3]:=0;end;下面给出求最长不下降序列的算法:fori:=n-1downto1dobeginL:=0;k:=0;forj:=i+1tondoif(b[j,1]>b[i,1])and(b[j,2]>L)thenbeginL:=b[j,2];k:=j;end;ifL>0thenbeginb[i,2]:=L+1;b[i,3]:=k;end;end;下面找出最长不下降序列：L:=1;forj:=2tondoifb[j,2]>b[L,2]thenL:=j;最长不下降序列长度为B(L,2)序列whileL<>0dobeginwrite(b[L,1]:4);L:=b[L,3];end;103 全国青少年信息学奥赛培训教程【参考程序】varn,i,L,k,j:integer;b:array[1..100,1..3]ofinteger;beginwriteln('inputn:');readln(n);fori:=1tondobeginread(b[i,1]);b[i,2]:=1;b[i,3]:=0;end;fori:=n-1downto1dobeginL:=0;k:=0;forj:=i+1tondoif(b[j,1]>b[i,1])and(b[j,2]>L)thenbeginL:=b[j,2];k:=j;end;ifL>0thenbeginb[i,2]:=L+1;b[i,3]:=k;end;end;L:=1;forj:=2tondoifb[j,2]>b[L,2]thenL:=j;writeln('max=',b[L,2]);whileL<>0dobeginwrite(b[L,1]:4);L:=b[L,3];end;writeln;readln;end.程序运行结果：【输入】：13791638243718441921226315【输出】：max=879161819212263104
