PASCAL提高教程.docx
《PASCAL提高教程.docx》由会员分享，可在线阅读，更多相关《PASCAL提高教程.docx（26页珍藏版）》请在冰点文库上搜索。
PASCAL提高教程
PASCAL提高教程
第一讲素数及其应用
一、什么是素数
素数，也叫质数，例如：
2、3、5、7、11、13等等。
素数是这样定义的：
若正整数p恰好只有1及本身p两个正因数，则p称为素数。
若正整数p有多于两个正因数，则p称为合数。
依定义，全体正整数按其正因数的多少可分成三类：
1、只有一个正因数；
2、全体素数：
只有两个正因数；
3、全体合数：
有多于两个的正因数。
所以1既不是素数，也不是合数。
二、素数的求法
1、根据定义的常规求法：
如果要判断数p是否是素数，可将2到p-1之间的数与p进行试除，只要p除以其中某个数k的余数为0，那么说明k是p的另一个因数，因此p不是素数；反之，如果2到p-1之间所有的数都不能被p整除，那么可以判断p是一个素数。
程序：
ProgramLt1_1;
Begin
Write（'p='）;
ReadLn（p）;
Fork:
=2top-1do
Ifpmodk=0Then
Begin
WriteLn（p,'isnotaprimenumber!
'）;
Halt;
End;
WriteLn（p,'isaprimenumber!
'）;
End.
2、一种改进的快速方法－筛法
给定正整数p后，我们可以提供一种可以求不大于p的所有的素数的方法。
假定p=50，将2到50之间的整数按顺序排列如下：
234567891011121415161718
19202122232425262728293031323334
35363738394041424344454647484950
依次划去2、3、5、7的倍数，数表中没有被划去的数即为不大于50的素数。
程序：
ProgramLt1_2;
Constp=50;
Vara:
Array[1..p]ofBoolean;
i,j,k:
Integer;
Begin
Fillchar（a,Sizeof（a）,True）;
Fori:
=2toTrunc（Sqrt（p））do
Ifa[i]Then
Forj:
=2topdivido
a[i*j]:
=False;
Fori:
=2topdo
Ifa[i]ThenWrite（i:
5）;
End.
三、应用举例
1.从小到大找出5个素数,使后面的数比前面的数都大12.（答案:
5,17,29,41,53）
2.哥德巴赫猜想：
任何大于2的偶数，都可以写成两个素数的和的形式，例如：
18=5+13。
满足条件的表达式不一定是唯一的，例如：
10=3+7=5+5=7+3。
其中我们将3+7与7+3两种写法认为是重复的，因此10有2种不重复的分解方法。
请你编一个程序，对于键盘输入的一个大于2小于1000的偶数，输出所有满足要求的不重复的表达式。
3.分解质因数：
任意一个合数，均可唯一表示为素数的乘积，例如：
6=2*3，100=2*2*5*5。
现在由键盘输入一个不超过5000的合数p，请编一个程序，将p表示成为素数的乘积的形式。
4.“漂亮数”：
一个自然数，若它的质因数至少是两重的（相同质因数的个数至少两个，如36=22*3２），则称该数为“漂亮数”，请编程序找出100以内的“漂亮数”。
第二讲字符串及其应用
字符串是TurboPascal中有效的,应用广泛的数据类型,下面我们将通过例题学习关于字符串的一些标准过程和函数.
常用的字符串标准函数和过程
〖例3.1〗编一个程序,从键盘上输入一个算术表达式,判别该表达式中,左圆括号与右圆括号是否正确配对,如正确,打印"YES",否则打印"NO".
①由于算术表达式中可以包含有数字,运算符,括号等,所以可以将它们作为字符串看待,用一个字符串变量来存储.同时,可以将字符串当成一个一维的字符型数组进行处理.
②算术表达式中括号匹配的检测方法:
设一个计数器T为0,将表达式串从向右扫描,当遇到左括号'（'时将T加1,遇到右括号时将T减1,直到结束,若期间T小于0或扫描结束后T不为0,都表明括号不匹配.
〖例3.2〗回文数:
一个两位以上的整数,如果左右对称就称回文数,7491947和3883都是回文数.编程序找出不超过40000的且是完全平方数的回文数.
习题:
1.有一个各位数字都不相同的三位数,如果将此数码重新排列,必可得到一个最大数和一个最小数,些两数之差正好就是原来的三位数,求这个三位数.
2.求所有不超过1000的这样的整数,它的平方的末两位数字相同,但不为0.
3.统计一个句子中单词的平均长度.以'IcomefromBeijing.'为例,测试程序.
4.在小于10N的全部自然数中,找出含奇数个5的自然数,并统计个数,N由键盘输入（N<6）.
5.回文数猜想:
左右对称的自然数称为回文数.如121,4224,13731等,有人猜想:
从任意一个两位或两位以上的自然数开始,将该数与它的逆序数（如1999的逆序数是9991）相加,得到一个新数,再用这个新数与它的逆序数相加.不断重复上述操作,经过若干步的逆序相加后,总可以得到一个回文数.例如:
从1992开始:
1992+2991=4983
4983+3894=8877
8877+7788=16665
16665+56661=73326
73326+62337=135663
135663+366531=502194
502194+491205=993399
经过七步就得到回文数.
利用上述方法,对键盘输入的某个自然数,验证该回文数猜想.
名字过程或函数含义
Copy函数返回主串中的一个子串
Length函数返回字符串的长度
Pos函数返回子串在主串中的起始位置
Delete过程从主串中删除一个子串
Str过程把一个数值转换成相应的字符串
Val过程把一个字符串转换成相应的数值
第二讲数字的截取与合成
在程序设计中经常碰到需要将一个多位数的各位数码分离出来的应用问题。
如下例：
〖例2.1〗在自然数中，各位数字之和的11倍正好等于自身的数只有一个，请找出这个数。
分析：
为了求出数p的各位数字之和，需要对p进行数字分离，处理的方法通常有两种：
（1）求商取余法
如a:
=384mod10,由于是对10求余数,其效果等于将384的个位数取出,
然后令b:
=384div10,相当于将384的个位数字去掉,保留前两位.因些将整数y的各位数字取出,可用以下程序段实现.
Whiley>0DoRepeat
Begina:
=ymod10;
a:
=ymod10;y:
=ydiv10;
y:
=ydiv10;Untily=0;
End;
（2）字符串分离法
将数值量转化为字符串,再用字符串的相应操作实现,具体方法在下讲中讨论.
〖例2.2〗.有一个两位数,加6后再把个位数与十位数互换,得到一个新的两位数,这样加6再互换共三次后,又得到了原来的两位数,求原来的两位数.
分析:
若某两个位数为ab（其中a是第一个数码,b是第二个数码）,则可以用a*10+b合成它们的数值.
习题:
1.有一个各位数字都不相同的三位数,如果将此数码重新排列,必可得到一个最大数和一个最小数,些两数之差正好就是原来的三位数,求这个三位数.
2.回文数:
一个两位以上的整数,如果左右对称就称回文数,7491947和3883都是回文数.编程序找出不超过40000的且是完全平方数的回文数.
3.把一个两位素数写在另一个两位素数之后,得到一个四位数,它能被这两个素数之和的一半整除,求出所有这样的素数对.
4.把一个六位的平方数截成两个三位数时,这两个三位数之差的绝对值是1（如5732=328329）.问这样的六位平方数共有哪些?
5.求所有不超过1000的这样的整数,它的平方的末两位数字相同,但不为0.
第四讲逻辑判断
逻辑判断是一种常见的题型,计算机解题时的主要策略是穷举各种可能的情况,其中的关键在于怎样描述条件.
〖例4.1〗四大湖问题:
上地理课时,四个学生回答我国四大淡水湖的大小时说:
A学生:
洞庭湖最大,洪泽湖最小,鄱阳湖第三.
B学生:
洪泽湖最大,洞庭湖最小,鄱阳湖第二,太湖第三.
C学生:
洪泽湖最小,洞庭湖第三.
D学生:
鄱阳湖最大,太湖最小,洪泽湖第二,洞庭湖第三.
对于每个湖的大小,每人仅答对一个,请计算机帮助判断四个湖的大小.
分析:
如何判断每人仅答对一个是个棘手的问题,程序中给出了一种巧妙的方法.
〖例4.2〗配备侦察员问题：
某侦察队长接到一项紧急任务,要他在代号为A,B,C,D,E,F的六个队员中选出若干人去侦破一件案子.人选的配备必须注意到下列各点:
（1）A,B两人中至少去一人.
（2）A,D不能一起去.
（3）A,E,F三人中要派两人去.
（4）B,C两人都去或都不去.
（5）C,D两人中去一人
（6）如D不去，则E也不去.
请问应该让谁去?
习题:
1.有一块金属,三人对它进行判断:
A说:
它不是铁,也不是钢.
B说:
它不是铁,而是铜.
C说:
它不是铜,而是铁.
结果有一个人全说错了,一个人全说对了,一个人对一句错一句.请你判断这块金属到底是什么?
2.X,Y,Z三名观众对田径场上100米决赛进行预测:
X:
A能得金牌,B能得银牌.
Y:
C能得金牌,D能得第四.
Z:
D能得金牌,B能得铜牌.
结果每个人都只猜对了一半,求A,B,C,D四名选手的名次.
第九讲杂题应用
本讲通过一些问题对上阶段学习的知识进行巩固.
〖例9.1〗澳门回归:
1953年,葡萄牙人借口曝晒水浸货物,进入澳门.1957年他们又通过贿赂守澳中国官员,得以在澳门半岛定居.鸦片战争以后,葡萄牙不断扩大其侵略地盘,至此,澳门沦为葡萄牙的殖民地.为了收复澳门,我国政府同葡萄牙政府进行多次谈判,于1987年4月13日签署了《关于澳门问题的联合声明》.两国政府声明:
澳门是中国的领土,中国政府将于1999年12月20日对澳门恢复行使主权.毫无疑问,澳门的回归将成为香港回归后又一件举世瞩目的大事.
你的任务是编写一个倒计时程序,计算1999年的某一日期距澳门回归还剩多少天.
日期通过键盘输入,输入日期的格式为mm/dd,其中mm表示月,dd表示日.
例如输入:
12/04时,你的程序应输出:
16.
〖例9.2〗奇偶校验
当一个布尔矩阵每行与每列的和都是偶数时,那它就有奇偶校验的功能.下面是一个有奇偶校验的4*4矩阵:
1010
0000
1111
0101
每行的和分别为:
2,0,4和2.每列的和分别为2,2,2和2.
你的任务是写一程序读入一个矩阵,并检查它是否具有奇偶校验的功能.如果没有,你的程序应再检查是否能只改变矩阵中的某一位使之具有奇偶校验的功能.如果还是没有,这个矩阵将被指明不再作为奇偶校验使用.
输入:
输入数据由文本文件input.txt读入,文件中可以有多个等处理矩阵,对每个矩阵的描述是这样的:
第一行包含一个整数n（n<100）,表示矩阵的大小.接下来的n行,每行有n个非0即1的整数,表示矩阵的元素.同一行相邻的两个整数之间用一个空格分隔.输入数据以n的值为0时表示结束.
输出:
对每组输入数据只输出一行.如果矩阵已经具有奇偶校验的功能,则输出"OK";如果改变某一位后矩阵具有奇偶校验功能,输出"Changebit（i,j）",其中i和j表示被改变的元素在矩阵中的行和列;如果还是不行,则应输出"Corrupt".
输入样例:
输出样例:
4OK
1010Changebit（2,3）
0000Corrupt
1111
0101
4
1010
0010
1111
0101
4
1010
0110
1111
0101
0
〖例9.3〗编码问题:
设有一个数组A:
ARRAY[0..N-1]OFINTEGER;数组中存放的元素为0~N-1之间的整数,且A[I]<>A[J]（当I<>J）时.例如:
N=6时,有:
A=（4,3,0,5,1,2）,此时数组编码的定义如下:
A[0]的编码为0,
A[I]的编码为:
在A[0],A[1],...,A[I-1]中比A[I]小的值的个数（I=1,2,...,N-1）.
因此例子所组的数组的编码为:
B=（0,0,0,3,1,2）
请编一个程序解决以下问题:
（1）给出数组A后,求出其编码B,
（2）给出数组A的编码后,求出A中的原数据.
〖例9.4〗有一个自然数,它的最末一个数是2,将2移到这个数的最前面后得到一个新数,此是新数恰好是原数的2倍,求原数是多少?
第十讲数制转换
我们日常生活中使用的大多是十进制计数法,而在计算机科学中,还经常会出现二进制,八进制和十六进制计数法.这一讲我们将学习一些常用的进位计数制和它们之间相互转换的方法.
一.进位计数制
1.十进制数
十进制数有十个基数,即0,1,2,3,4,5,6,7,8,9.十进制数是逢十进位.
2.二进制数
二进制数有两个基数,即0,1.二进制数是逢二进位.
3.八进制数
八进制数有八个基数,即0,1,2,3,4,5,6,7.八进制数是逢八进位.
4.十六进制数
十六进制数有十六个基数,即0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F.十六进制数是逢十六进位.
以下是二进制,十进制和十六进制数码转换表:
二.各种数制之间的转换
1.R进制数转化成十进制数.
把任意R进制数转化成十进制数的方法是:
将这个R进制数按权展开求和,所得的结果即为对应的R进制数.
（11011）2=1*24+1*23+0*22+1*21+1*20=16+8+2+1=（27）10
（123）8=1*82+2*81+3*80=64+16+3=（83）10
（1AB）16=1*162+10*161+11*160=256+160+11=（427）10
2.十进制数转换成R进制数
将十进制数转换成R进制数的一种常用方法是:
除以R取余法.
例如,将（123）10转换成二进制数.
余数
2|123......1转换后的低位数
---------
2|61.....1
------
2|30.....0
-----
2|15.....1
-----
2|7......1
-----
2|3......1
-----
1转换后的高位数
结果:
（123）10=（1111011）2
十进制十六进制二进制
000
111
2210
3311
44100
55101
66110
77111
881000
十进制十六进制二进制
991001
10A1010
11B1011
12C1100
13D1101
14E1110
15F1111
161010000
二.各种数制之间的转换
1.R进制数转化成十进制数.
把任意R进制数转化成十进制数的方法是:
将这个R进制数按权展开求和,所得的结果即为对应的R进制数.
（11011）2=1*24+1*23+0*22+1*21+1*20=16+8+2+1=（27）10
（123）8=1*82+2*81+3*80=64+16+3=（83）10
（1AB）16=1*162+10*161+11*160=256+160+11=（427）10
2.十进制数转换成R进制数
将十进制数转换成R进制数的一种常用方法是:
除以R取余法.
例如,将（123）10转换成二进制数.
余数
2|1231转换后的低位数
2|611
2|300
2|151
2|71
2|31
1转换后的高位数
结果:
（123）10=（1111011）2
习题:
1.归并有序表：
A和B是两个已经按从小到大排列好的有序表，编程由这两个子表中的元素归并得到一个新的有序表C。
2.1987乘幂的尾数：
M和N是自然数，N>M>=1，而1987^.M与1987^.N的末三位数相同，求最小的M和N。
分析：
（1）本题只须记录1987的乘幂的末三位数，故不必高精度计算；
（2）用数组a[1..n]存储1987的1至n次幂的末三位数；
（3）n的初始值为2，计算1987的n次幂的末三位数，并和1987的1至n-1次幂进行比较，若无相等的，则n=n+1，重复（3）；否则，第一次找到相等的，即是所求的m，n值。
3.求序列的第300项：
把所有3的方幂及互不相等的3的方幂和排列成一个递增序列：
1，3，4，9，10，12，13，...，求这个序列的第300项。
分析：
本题可以用一个线性表来记录这个递增的序列，通过递推可以将整个序列构造出来。
方法如下：
（1）数组a存放线性表，t为尾指针，b存放3的幂，初始时t=1，b=1；
（2）将b放入表尾，尾指针加1；a[t]←b；t←t+1；
（3）将b依次与1至t-1的元素相加，按顺序放入表尾；
（4）重复
（2），（3），直至第300项放入表中。
4.迷宫问题:
下图是一个6*8的迷宫,其中阴影部分表示不能通行的中径,要求寻找从从上角的起点到右下角终点的一条最短的路径.
第十二讲图及图的最短路算法
一.图及其存储结构
图是另一种有层次关系的非线性的数据结构.在日常生活中有图的许多实例,如铁路交通网,客运航空线示意图,化学结构式,比赛安排表等.下面的几个例子都可称为图.在实际运用中,我们可以用图来表示事物间相互的关系,从而根据需要灵活地构建数学模型.例如:
图（A）,可以用点来表示人,如果两个人相互认识,则在表示这两个人的点之间连一条线.这样从图中我们就可以清楚地看到,这些人之间相互认识的关系.图（B）:
可以用点表示城市,若两城市间有连线则表示可在这两城市架设通信线路,线旁的数字表示架设这条线路的费用.图（C）:
4个点表示4支足球队,它们进行循环比赛,若甲队胜乙队,则连一条由甲队指向乙队的有向线段.在上面三个例子中,（A）,（B）又可称为无向图,（C）称为有向图,其中（B）是一个有权图.
图的一种常用存储方式是邻接矩阵法.
邻接矩阵是用一个二维数组表示图的有关信息,比如图A的邻接矩阵为:
在邻接矩阵中,第i行第j表示图中点i和点j之间是否有连线,若有则值为1,否则为0.比如说:
点v1和v2之间有连线,则矩阵的第一行第二列的值为1.而矩阵的第四行行三列的值为0说明图中点v4和v3之间没有连线.图A是一个无向图,它的邻接矩阵是一个关于主对角线对称的矩阵.而有向图的邻接矩阵则不一定是对称的.比如图C的邻接矩阵为:
二.图的最短路算法
〖例12.1〗下图是一个铁路交通图的例子.图中的顶点表示车站,分别用1,2,...,6编号,两个点之间的连线则表示铁路线路,而线旁的数字则表示该条线路的长度.要求编一个程序,求出任意两个车站之间的最短路径.
这里介绍一种编程简单的算法－Floyd算法,算法中应用了动态规划的思想.
令Dk（i,j）表示将第1,2,...,k个点作为中间点考虑进来后点i到点j的最短路径的长度,而A（i,j）表示点i与点j之间直接通路的路长,我们有以下关系成立:
Dk（i,j）=Min{Dk-1（i,j）,Dk-1（i,k）+A（k,j）}
当k取到N时,DN（i,j）即为点i到点j之间的最短路的长度.
〖例12.2〗流动书店:
某市的几所学校联合起来,准备合资兴建一间流动书店,当某学校需要购书时,流动书店的流动售书车可以马上出发开往该校.为了节约开支,这几所学校决定把流动书店建在某所学校内,并且为了使书以尽快运到其他学校,流动书店所在的学校距最远的一所学校的距离要尽可能地短.
你的任务是编写一个程序,对于给出的某些学校间的距离,把适合建流动书店的学校找出来.
输入:
学校间的距离通过一个文本文件H08.DAT读入.文件的第一行是一个正整数N（1输出:
请将程序运行结果输出在屏幕上,只需要一个数,即为你所选的建流动书店的学校编号.
当有多所学校可供选择时,编号小的学校优先考虑
贪吃的九头龙
【问题描述】
传说中的九头龙是一种特别贪吃的动物。
虽然名字叫“九头龙”，但这只是说它出生的时候有九个头，而在成长的过程中，它有时会长出很多的新头，头的总数会远大于九，当然也会有旧头因衰老而自己脱落。
有一天，有M个脑袋的九头龙看到一棵长有N个果子的果树，喜出望外，恨不得一口把它全部吃掉。
可是必须照顾到每个头，因此它需要把N个果子分成M组，每组至少有一个果子，让每个头吃一组。
这M个脑袋中有一个最大，称为“大头”，是众头之首，它要吃掉恰好K个果子，而且K个果子中理所当然地应该包括唯一的一个最大的果子。
果子由N-1根树枝连接起来，由于果树是一个整体，因此可以从任意一个果子出发沿着树枝“走到”任何一个其他的果子。
对于每段树枝，如果它所连接的两个果子需要由不同的头来吃掉，那么两个头会共同把树枝弄断而把果子分开；如果这两个果子是由同一个头来吃掉，那么这个头会懒得把它弄断而直接把果子连同树枝一起吃掉。
当然，吃树枝并不是很舒服的，因此每段树枝都有一个吃下去的“难受值”，而九头龙的难受值就是所有头吃掉的树枝的“难受值”之和。
九头龙希望它的“难受值”尽量小，你能帮它算算吗？
例如图1所示的例子中，果树包含8个果子，7段树枝，各段树枝的“难受值”标记在了树枝的旁边。
九头龙有两个脑袋，大头需要吃掉4个果子，其中必须包含最大的果子。
即N=8，M=2，K=4：
图一描述了果树的形态，图二描述了最优策略。
【输入文件】
输入文件dragon.in的第1行包含三个整数N（1≤N≤300），M（2≤M≤N），K（1≤K≤N）。
N个果子依次编号1，2，...，N，且最大的果子的编号总是1。
第2行到第N行描述了果树的形态，每行包含三个整数a（1≤a≤N），b（1≤b≤N），c（0≤c≤105），表示存在一段难受值为c的树枝连接果子a和果子b。
【输出文件】
输出文件dragon.out仅有一行，包含一个整数，表示在满足“大头”的要求的前提下，九头龙的难受值的最小值。
如果无法满足要求，输出-1。
【样例输入】
824
1220
134
1413
2510
2612
3715
385
【样例输出】
4
【样例说明】
该样例对应于题目描述中的例子。
算法分析
按照题意，“大头”必须吃掉k个果子，其余每一组至少吃掉一个果子。
显然，k+m-1>n时，要么“大头”吃的果子数小于k，要么有的组未吃到果子。
反之，如果k+m-1≤n，九龙头必能按照题意要求吃尽n个果子。
由于“大头”吃的果子
升级会员 