惠阳中山中学计算机奥赛培训讲义.doc

惠阳中山中学奥赛培训讲义目录01- 算法和流程图102- PASCAL简介 403- TP70的使用 804-顺序结构1905-顺序结构21106-选择结构11307-选择结构21608-循环结构11909-循环结构22210-循环结构32411-循环综合练习2812-字符类型数据处理3013-枚举类型3414-子界类型3815-一维数组的建立、输入输出、计算4116-一维数组的移动、插入、删除4417-一维数组的查找、排序4718-二维数组的建立、输入输出、计算5019-二维数组的应用、矩阵5320-字符数组与字符串类型5621-函数5922-过程6323-递归6724-集合7025-记录72算法和流程图一、学习目的和学习内容 学习各种软件的使用让计算机按照我们的意图去完成一件事编程序（软件）给别人用；国际信息学（计算机）奥林匹克竞赛全国中学生信息学奥赛广东省中学生信息学奥赛；比赛的内容就是编程比赛；这也是我们的学习目的和内容；计算机程序设计语言：人类语言用程序设计语言（如Pascal语言）表示再翻译成机器语言；二、 计算机解决问题的步骤 做任何一件事都要有一定的的步骤，如求1+2+3+4+5+6+7+8+9+10；计算机解题步骤：分析问题 确定解决问题的方法和步骤（即算法） 选择一种计算机语言，根据算法编写计算机程序 让计算机执行这个程序获得结果三、 算法的概念 1、为解决某一个问题而采取的方法和步骤，称为算法。或者说算法是解决一个问题的方法的精确描述。 如： 已知半径，计算圆的面积的算法。 算法 读入半径R的值计算圆的面积S=*R*R输出圆的面积S。 注意：算法不一定唯一，如求1+2+3+4+5+6+7+8+9+10的算法。2、算法的特点： 有穷性：必须在执行了有穷个计算步骤后终止； 确定性：每一个步骤必须是精确的、无二义性的； 可行性：可以用计算机解决、能在有限步、有限时间内完成； 有输入： 有输出：四、 算法举例例一：交换两个大小相同的杯子中的液体（A水、B酒）。算法1：1、再找一个大小与A相同的空杯子C；2、AC；3、BA；4、CB；结束。或（BC、AB、CA）算法2：1、再找两个空杯子C和D；2、AC、BD；3、CB、DA；结束。注意：一个算法往往具有代表性，能解决一类问题，如例一可以引申为：交换两个变量的值。例二：输入1个数给计算机，若为正数则打印出来。算法：输入1个数X； 判断X0 ？； 若X0，则打印X；结束。例三：分别输入10个数，打印出其中的正数。算法：设T为计数器。 输入第一个数X，1T； 判断X0 ? ； 若X0，则打印输出；判断T10 ？若T10，则表示10个数已经处理完，结束。 否则，再输入下一个数X，且T+1T，然后转继续执行。例四：从10个数中挑选出最大的一个数，打印输出。诱导：以从10个人中挑出最高的人为例，让学生发挥想象。算法1：“打擂台”或“比武招亲”，设MAX为大力士，T为计数器。 先输入1个数MAX，1T； （擂主） 再输入下一个数X，T+1T； （上一个挑战者） 比较XMAX ？； （比武）若XMAX成立，XMAX； （打败擂主，即新的大力士产生） 否则，MAX仍然是最厉害，即值不变；（败下阵来）判断T=10 ？； （看看还有没有挑战者）若T=10成立，则说明10个数已比较玩，最大的数在MAX中，输出MAX即可； （颁奖） 否则，转继续找下一个挑战者比武。 （下一个）算法2：两个两个打（淘汰赛）。23457611098例五：计算1*2*3*4*5*6*7*8*9*10。描述：阶乘10！算法1：找两个容器T和I；T为累乘器，初值为1；I为计数器，初值为1。 1T，1I； T*IT； I+1I； 判断I10 ？ 成立，则输出T，结束。 否则，转继续乘。提问：1、T的初值可不可以为0？不能 2、I的初值可不可以放0？不能 3、I的初值可不可以放2？可以 4、I可不可以放10？可以，怎么改算法？让学生完成。 5、可不可以先判断后执行？ 6、现在要求1+2+3+4+5+6+7+8+9+10，如何办？让学生完成。五、 算法的表示形式1、 文字描述：二义性，如：甲叫乙把他的书拿来；小明连王刚都不认识；2、 伪代码：用符号，不直观；3、 流程图：简洁、直观、无二义性。有很多种，我们学N-S流程图。六、 结构化程序设计和N-S流程图经过证明：任何一个算法都可以用以下3种基本结构表示：1、顺序结构：例一；2、分支结构：例二、例三中的、例四中的；3、循环结构：例三中的、例四中的、例五； 两种循环：直到型和当型。相应的N-S图： 条件成立 不成立 A B当条件成立时做A直到条件成立时为止AABC注意：一个算法往往需要几个简单结构复合在一起才能表示，即复合结构。练习：用N-S图画出以上5个例子的流程图，举例让学生模仿。将第一个数MAX，将1T将下一个数X，T+1T直到T=10为止输出MAX1T，1I直到I10为止输出TT*ITT+1T X MAXY NX MAX 当型循环 例五 例四（算法一）输入第一个数X，1 T当T 0Y N打印X输入下一个数XT+1T输入1个数XX0 Y N打印X找一个CACBACB 例一（算法1） 例二 例三让学生将直到型循环和当型循环相互转换：关键是条件的取反。七、 课后作业1、 求1+1/2+1/3+1/4+1/10。2、 求两个自然数的最大公约数。要求：写出算法，画出相应的N-S流程图。0S ，1T当T ST + 1 T输入M，N当N0 时做输出MM除以N的余数RNMRN 第1题 第2题Pascal程序设计语言简介Pascal语言是学习计算机程序设计首选的语言，它的数据类型丰富、程序结构清晰，对培训逻辑思维能力和结构化程序设计思想很有益。是国际、国内比赛的首选语言，也是大学计算机专业的必修课程。 Pascal种类、版本较多。我们学习的是Turbo Pascal 7.0，即TP7.0。计算机程序是什么：程序是一些计算机能够读懂的命令或指令的有序集合，它的作用是按照编写者的意图完成一定的功能，编写这样的程序叫程序设计。如：下面是一个最简单的Pascal程序，它的作用是在屏幕上显示“HOW DO YOU DO !”PROGRAM EX1 (INPUT,OUTPUT)； BEGIN WRITELN(HOW DO YOU DO !)； END下面我们就开始讲解Pascal程序设计的基础知识。一、 一个完整的PASCAL程序的组成 再看一个简单的例子：PROGRAM EX1 (INPUT,OUTPUT)； const p = 3.1415926； var r：integer； s：real； BEGIN Readln(r)；S：= p * r * r ； Write (s)； END从上面两个简单例子，我们归纳出： PROGRAM表示一个程序 的开始 空格 不能省，但可以有多个 程序首部 程序名 任意，但一般要有意义 （可以省略） （INPUT，OUTPUT） 参数，表示需要从键盘输入数据，在显示器上显示结果 ； 不能省，表示一个语句结束 说明部分：说明程序中用到的标识符（如符号常量、变量）。 标识符必须以字母开头，后跟字母或数字，不许有空格。 PASCAL程序组成 如：B，TWO，X1，MY_1是正确的； 3X，MY FUNCTION，ABC.123是错误的。 用const说明常量；如： const p = 3.1415926；用var 说明变量；如： var r：integer； BEGIN 语句；一个语句一般表示一个动作，语句之间要用“；”分割 程序体 END 句号“.” 表示一个程序的结束，不能省。例二、已知梯形的上底、下底和高，求梯形的面积。PROGRAM AREA（INPUT，OUTPUT）；说明：1、标识符要先定义后使用，并且先说明常量再说明变量；2、数据类型：相同类型可以一起定义，用逗号割开；3、赋值号：不是等于号，是“：=”4、乘号：“*” ，不能省略，如AB一定要写成A*B5、除引号里面的字符外，程序中的字母不分大小写；6、按造格式写，注意对齐。VAR R1，R2，H，S ：REAL；BEGINR1：= 4.5；R2：= 8.1； H：= 6； S：=（R1+R2）*H / 2；WRITEIN（S）；END.二、 关键字又称保留字，是指PASCAL中具有固定意义的一批英文单词或其缩写，有专门的用途，用在固定的位置，不能作为它用。1、 程序的起始符号：PROGRAM、FUNCTION、PROCEDURE2、 说明部分的专用符号：CONST、VAR、ARRAY、FILE、LABEL、TYPE、SET、RECORD、PACKED3、 专用语句：CASE、DO、DOWNTO、ELSE、FOR、GOTO、IF、OF、REPEAT、THEN、TO、UNTIL、WHILE、WITH4、 运算符号：AND、DIV、IN、MOD、NOT、OR5、 分隔符：BEGIN、END6、 空指针变量：NIL注意：单词不要写错，不分大小写。三、 标识符用来标识（表示）程序、符号常量、变量、过程、函数等的名字的符号。分为两类：1、 标准标识符：PASCAL已经预先定义好的，有特定含义。 常量名：FALSE，TRUE，MAXINT(系统中的最大整数，32767)， 类型名：BOOLEAN，CHAR，INTEGER，REAL，TEXT 文件名：INPUT，OUTPUT 函数名：ABS，ARCTAN，CHR，COS，EOF，ELON，EXP，LN，ODD， ORD，PRED，ROUND，SIN，SQR，SQRT，SUCC，TRUNC 过程名：DISPOSE，GET，NEW，PACK，PAGE，PUT，READ，READLN， RESET，REWRITE，UNPACK，WRITE，WRITELN注意：注意：单词不要写错，不分大小写。2、 自定义标识符：在程序中需要，由用户自己定义的，要注意以下几个问题： 禁止使用关键字、标准标识符作标识符； 尽量做到“见名知义”； 标识符要先说明后使用。四、 数据类型1、 计算机处理的对象就是数据，数据的一个重要特征就是它的类型，类型决定了它可以进行的运算、它可能取值的范围、它需要占用的计算机空间。2、 四种简单的标准数据类型： INTEGER：整形，3276832767；占用2个字节； REAL：实形，10-38 1038，-1038 -10-38 ；关于“溢出”； 占用4个字节； CHAR：字符型，能显示和打印输出的字符，如“A”，“=”，“a”； 占用1个字节； BOOLEAN：布尔型（逻辑型），TRUE（真）、FALSE（假）；占用1个字节；五、 常量在程序运行过程中，其值不能被改变的量，称为“常量”。 如：MAXINT（32767），PI=3.1415926，“A”，TRUE，FALSE。1、 整形常量：MAXINT MAXINT12、 实形常量： 表示方法：十进制表示法，如123456.789，7.55，0.012 科学计数法，如120000000，即1.2*108 ,应写成1.2E+8 0.000000012，即1.2*108，应写成1.2E83、 字符常量：ASCII码字符集，256个，记住几个关键的。4、 布尔常量：FALSET 的含义。七、 标准函数PASCAL预先写好的一些有用的小程序，供用户直接调用，称为标准函数。函数的作用：得到一个值；调用方法：函数名（参数）；函数的两个注意问题：自变量的类型，函数值的类型；1、 算术函数：8个 ABS（X）：X可以为INTEGER 或 REAL，作用求X的绝对值； SQR（X）：X可以为INTEGER 或 REAL，作用求X的平方值； SQRT（X）：X可以为非负整数 或非负实数，作用求X的绝对值； SIN（X）：正弦； COS（X）：余弦； ARCTAN（X）：反正切； EXP（X）：指数，X可以为INTEGER 或 REAL，作用求e的X次方； e=2.71828 LN（X）：自然对数，X为正整数或正实数，作用求X的自然对数；2、 转换函数：4个 TRUNC（X）：截尾，X为REAL，作用去掉X的小数部分； ROUND（X）：舍入，X为REAL，作用为小数部分四舍五入； ORD（X）：序号，X为INTEGER、CHAR、BOOLEAN，作用求X的序号； CHR（X）：字符，X为INTEGER，作用求以X为序号的字符，是ORD函数的反函数；ASCII码：见表将字符转换为数字：ORD（X）ORD（0）；记住“A”、“a”、“0”的ASCII码便行，其它可计算出。3、 顺序函数：2个PRED（X）：前驱，X为INTEGER、CHAR、BOOLEAN，作用取X的前一个数据。 SUCC（X）：后继，X为INTEGER、CHAR、BOOLEAN，作用取X的后一个数据。注意：第一个数没有前驱，最后一个数没有后继。4、 逻辑判断函数：3个ODD（X）：奇函数，X为INTEGER，判断X是奇数还是偶数， 若X为奇数则值为TRUE（1），否则值为FALSE（0）；OLN（X）：行结束函数，判断一换是否结束； EOF（X）：文件结束函数，判断文件是否结束；八、 算术运算符加（+）减（-）乘（*）除（/）：运算数都可以是INTEGER或REAL； 结果为INTERGER或REAL（“/”的结果必为REAL）整数除DIV：运算数都是INTEGER，结果也是INTEGER； 如：16 DIV 3 = 5 ；-21 DIV 2 = -10；求 余MOD：运算数都是INTEGER，结果也是INTEGER； 如：16 MOD 3 = 1 ；-21 MOD 2 = -1；九、 表达式1、 数学表达式： 运算顺序：圆括号（）函数*、/、DIV、MOD+、；内层括号优先。（X+2*Y）/（3*X5*Y） X+2Y 3X-5Y（COS（X）+4）/（X*X*X）COSX+4 X3A*X*X+B*X+CAX2+BX+CSQRT（P*（P-A）*（P-B）*（P-C）P（P-A）（P-B）（P-C）ABS（XY）/3） X-Y 32、 关系表达式：两个数据的比较运算，其结果为布尔值（真或假）关系运算符：大于（）、等于（=）、小于（=）、 小于等于（=）、不等于（）如： 156 结果为真（TRUE）； 7.68.9结果为假（FALSE）； AB结果为假； TRUEFALSE 结果为真； 注意：3.1415926=3.1415927 ？不一定，因为实数在计算机内是按照近似值存放的，所以是否相等取决于题目（你）的要求。一般要比较两个实数X，Y是否相等，可假设一个很小的数MIN（根据题目（自己）的要求定），如果ABS（X-Y）0； NOT （A0）：取反； （X0） AND （Y0）：而且； （X0） OR （Y0）：或者；举例：已知X=4，Y=5，Z=6，B1=TRUE，B2=FALSE，B3=TRUE， 求下列表达式的值。 X+3*Y-6*Z ：TRUE； (X6) OR (Y3) AND B1 ：FALSE； (B1=B2) AND NOT (B2 OR B3 )：FALSE； NOT B2 AND NOT ( XY) ：FALSE；TURBO PASCAL 7.0 的使用1、TP7.0的安装：双击tp7.0一直按“Y”+ 回车就会出现Tp目录找到Tp目录“右键单击”Turbo.exe图标选择“属性” 再单击“程序”标签单击“高级”按扭选择“必要时建议MS-DOS方式” 还可以修改“屏幕”的大小全部改好后按“确定”就可以用TP了。注意其它一些选项不要修改。2、启动和退出：双击C：双击TP子目录双击快捷方式图标TURBO进入TP；也可以在桌面上建立一个TURBO快捷方式；退出时单击“FILE”“EXIT”关闭TP窗口；3、TP的使用：输入源程序；存盘：单击“FILE”选择“SAVE”C：文件名（或A：）回车（单击OK）； 或按“F2”键。编译：检查程序有无语法和逻辑上的错误。单击“COMPILE”“COMPILE”出现错误提示就修改光标附近的错误，直至出现“success”的窗口，表示你的程序在语法和逻辑上完全正确，再次保存；但是否满足题目的要求，即功能上是否正确还不知道。或按“ALT”+“F6”。运行：单击“RUN”“RUN”输入数据后回车确认； 或按“CTRL”+“F9”。看结果：单击“DEBUG”“USER SCREEN”，看结果是否正确按任意键返回TP窗口（有错误，则修改源程序再编译、运行、保存，直至结果正确）； 注意：一个输入数据得到的结果正确并不能说明你的程序对任何输入的数据都对，所以要多用一些数据去测试程序的正确性。再编一个新程序：一定要单击“FILE”“NEW”；千万不能把几个程序保存在一个文件中，一个程序就对应着一个文件。或先关闭前程序（WINDOWCLOSE）；打开已有程序：单击“FILE”“OPEN”文件名（路径结合OPEN按钮）；“CTRL”+“C”或“CTRL”+“BREAK”终止程序的运行（因为逻辑错误出现黑屏或死循环），退到编辑状态。增加观察窗口：“DEBUG”“WATCH”；增加输出屏幕窗口：“DEBUGOUTPUT”；改变各个窗口的大小和位置：拖动鼠标（右下角、上端等）；增加跟踪变量：先激活观察窗口（WATCH窗口）：按“INSERT”键输入变量名或数组名等单步跟踪（用F7或F8键，区别是F7连子程序也一起跟踪，而F8只跟踪主程序，把子程序当一个语句调用执行。）出现错误，按F9键回到编辑窗口修改保存后再跟踪。顺序结构（一）一、程序：是由若干条语句组成的。一条语句完成一个动作或功能，若干条语句组合在一起便可以完成一个任务，实现用户的意图。因此，能否正确利用语句的功能来达到预定的要求，是程序设计的关键。二、程序的三种基本结构1、 顺序结构：按照语句的书写顺序，依次执行。2、 选择结构（分支结构）：根据给定的条件，判断成立与否，成立做一件事， 不成立做另外一件事。两件事必须做一件且只能做一件。3、 循环结构（重复结构）：重复做某件事。3种： 计数循环：重复执行的次数确定； 当型循环：当条件成立时，反复做某件事； 直到型循环：反复做某件事，直到条件成立时为止。三、补充介绍TP70系统的使用：以用WRITELN语句打印OK图形为例，也可以让学生自由发挥，调动学生的积极性。* * * * * * * * * * * * * * * * * * * * * * * *四、输出语句：写语句1、命令： WRITE（ 输出项 ）； 或 WRITELN（ 输出项 ）； 2、说明：输出项可以是字符串：用单引号引起来的一串字符，如WRTIE（*）； 数值常量：如WRITE（8）； 变量：输出变量的值，注意变量必须要先定义再赋值，然后才可以输出值，如WRITE（A）； 表达式：输出表达式的值，表达式必须正确，如WRITE（A+B）； 可以有多个不同类型的输出项，之间用逗号隔开。 如WRITE（A=，A）；WRITE（X，X+2，Y，Z）；3、 两者区别：WRITE连续输出；而WRITELN输出完后会自动换行； ：WRITE至少有1个输出项；而WRITELN可以无，表示换一行； ：WRITE（X，Y）=WRITE（X）；WRITE（Y）； 而WRITELN（X，Y）= WRITE（X）；WRITELN（Y）； WRITELN（X）；WRITELN（Y）；五、赋值语句1、 语句格式：变量名 := 表达式 ；2、 语句作用：先计算右边表达式的值，然后赋给左边的变量；赋值号 ：=3、 变量要遵循“先说明后使用”的原则；说明方法：VAR 变量名 ： 类型名；注 意：说明必须在VAR之前，一个程序中只要1个VAR，相同类型的变量可以一起说明，多个变量之间用逗号隔开就行了；4、 右边表达式必须有确定的值，且类型必须与左边的变量一致；例：已知梯形的上底、下底和高，编程求梯形的面积。PROGRAM TIXINGMIANJI（INPUT，OUTPUT）； VAR A，B，H，S：REAL；BEGIN A：=5； B：=8； H：=9； S：=（A+B）*H/2； WRITELN（TI XING MIAN JI WEI ：，S）；END.屏幕显示为：TI XING MIAN JI WEI ：5.8500000000E+01 为什么结果不是58.5呢？因为计算机内部以科学计数法表示实数，要想以小数形式表示，需要用到场宽。场宽：数据输出时所占据的列数，称为场宽；单场宽：对于INTEGER、CHAR、BOOLEAN、字符串，一般用一个数值限定数据输出的场宽，如WRITELN（X：N）；N要不小于数据的长度。N大时左边补空格；双场宽：用来控制REAL数据的输出格式，如WRITELN（X：N1：N2）；N1表示输出X的总列数（包括符号位、整数部分、小数点、小数部分），N2表示小数部分的列数。输出时，先把小数位数右边补0，再在整个数的左边补空格。例：写出下面程序的运行结果VAR A：INTEGER；B：REAL；C：CHAR；D：BOOLEAN；BEGIN A：=1357； B：=1234.5678； C：= % ； D：=TRUE； WRITELN（A，A：5，A：3）； WRITELN（B，B：12：5，B：10：2）； WRITELN（C，C：5）； WRITELN（D，D：5，D：2）； WRITELN（ END. ）；END.屏幕显示为：135713571357 1.2345678000E+031234.56780%TRUETRUETRUEEND.作业：1、已知一个学生的语文成绩为89，数学成绩为96，外语成绩为99，编程求他的总分和平均成绩。 2、已知直角三角形的两个直角边分别为10、15，编程计算它的面积。顺序结构（二）一、 输入语句：读语句 引出：在程序中为了变量获得一个确切的值，可以用赋值语句。但有时候，程序中需要赋值的变量很多或变量的值经常变化。这时，我们往往要修改源程序，这样的程序通用性就不好。一个好的程序应该是在程序运行需要的时候，提示用户从键盘输入原始数据，然后程序继续运行求得结果，而不需要修改源程序。1、 语句格式： READ（输入项）；或READLN（输入项）； 如：READ（A）； READ（A，B，C）； READLN（A）；2、 语义：程序执行到这个语句时，就等待用户从键盘输入数据，并依次赋给相应的变量。 3、 说明：输入的数据个数要与需要的一致；（整型和实型数据之间用空格或回车键隔开， 最后要用回车表示数据输入完毕，让程序继续运行） 输入的数据类型要与需要的相对应；（整数可以给实数） READ和READLN的区别：几个READ语句连续读，中间不换行，只有当一行数据个数不够时才换到下一行继续读；而每个READLN语句读完后都自动换行。而且READ语句一定要有输入，而READLN可以没有输入，表示读入一个回车换行符（换行）。 所以，建议用READLN，输入时一行对应一个READLN语句。并且在READ或READLN语句前最好加上个WRITE或WRITELN提示用户输入数据的名称、个数、类型。4、 举例：例：设程序中有两个语句（ERAD（A，B，C）；READ（D，E，F，G）；），当从键盘分别输入以下两批数据时，各变量的值分别为多少？ 678910 5432 67 8910 54321若语句改为READLN（A，B，C）；READLN（D，E，F，G）；呢？例：设有下列语句：READ（A，B，C）； READLN（D，E）； READLN； READLN（F，G）； 其中变量都是INTEGER，输入数据如下： 12 345678 910 11 1213 问：各变量值为多少？将上一节课的例题全部用读入语句改写：1、已知梯形的上底、下底和高，编程求梯形的面积。2、已知一个学生的语文成绩89，数学成绩96，外语成绩99，编程求他的总分和平均成绩。注意：一定要强调分析题目，找出已知什么，输出什么，如何做，用什么语句，按什么程序。例：读入一个四位数，分别求它的个位、十位、百位、千位。 VAR A，G，S，B，Q：INTEGER；BEGIN WRITELN（PLEASE INPUT A SI WEI INTEGER：）； READLN（A）； G：=A MOD 10； S：=（A G）DIV 10） MOD 10； Q：=A DIV 1000； B：=（A 1000*Q） DIV 100； WRITELN（G：，G，S：，S，B：，B，Q：，Q）；END. （或者：在G，Q，B后面加上S：=（A-G-B*100-Q*1000）DIV 10；也行）例：输入一个三位自然数，把这个数的百位数与个位数对调，输出对调后的数。分析：设输入的数为M，对调后的数为N，则： A：=M DIV 100；（百位） B：=（M DIV 10 ）MOD 10；（十位） C：=M MOD 10；（个位） N：=C*100+B*10+A；作业：完成程序。选择结构的程序设计（一）引言：在日常生活中，我们经常遇到根据具体情况的不同而去做具体的事，比如：若星期天下雨，我就在家看书，否则我就去踢足球。我们可以画出这个语句的N-S图（见图1）：A0星期天下雨YNYN打印A打印A踢足球在家看书 图1 图2在我们的程序设计过程中，我们也会经常遇到这种情况，即判断某一个条件是否成立