Pascal字符串的过程.ppt

2019/12/5,信息学竞赛培训提高班,1,第三-四讲字符串处理,PASCAL基本教程,2019/12/5,信息学竞赛培训提高班,2,回顾知识点,字符类型的概念回顾字符是一个有序类型,字符的大小顺序按其ASC代码的大小而定。函数succ、pred、ord适用于字符类型。例如：后继函数：succ(a)=b前继函数：pred（B）=A序号函数：ord（A）=65字符函数：chr(65)=A注意：AZ的ASCII码是连续的；az的ASCII码是连续的；,2019/12/5,信息学竞赛培训提高班,3,例1按字母表顺序和逆序每隔一个字母打印。即打印出：acegIkmoqsuwyzxrvtpnljhfdb,程序如下：programex8_1;varletter:char;beginforletter:=atozdoif(ord(letter)-ord(a)mod2=0thenwrite(letter:3);writeln;forletter:=zdowntoadoif(ord(letter)-ord(z)mod2=0thenwrite(letter:3);writeln;end.分析：程序中，我们利用了字符类型是顺序类型这一特性，直接将字符类型变量作为循环变量，使程序处理起来比较直观。,2019/12/5,信息学竞赛培训提高班,4,数组类型运用回顾输入十个正整数,把这十个数按由小到大的顺序排列。（冒泡法排序）下面对5个进行排序，这个五个数分别为829105。按选择排序方法，过程如下：初始数据：829105第一次排序：829105928105102895102895第二次排序：108295109285109285第三次排序：109825109825第四次排序：109852对于十个数，则排序要进行9次，一共要比较N2。,2019/12/5,信息学竞赛培训提高班,5,源程序如下：programex5_2;vara:array1.10ofinteger;i,j,t:integer;beginwriteln(Input10integers:);fori:=1to10doread(ai);读入10个初始数据readln;fori:=1to9do进行9次排序beginforj:=i+1to10do将第i个数与其后所有数比较ifaicnamejthenk:=j;t:=cnamei;cnamei:=cnamek;cnamek:=t;end;fori:=1to10dowriteln(cnamei);end.分析：程序中，当执行到ifcnamekcnamej时，自动将cnamek串与cnamej串中的每一个字符逐个比较，直至遇到不等而决定其大小。这种比较方式是计算机中字符串比较的一般方式。,2019/12/5,信息学竞赛培训提高班,11,三、字符串的函数和过程,TurboPascal提供了八个标准函数和标准过程，见下表，利用这些标准函数与标准过程，一些涉及到字符串的问题可以灵活解决。,2019/12/5,信息学竞赛培训提高班,12,经典运用之“最长公共子字符串”,题目：我们把一个字符串中在两个字符串中找到最长公共子串；题目分析：若存在公共子串，则子串肯定存在在两个字符串st1,st2中,所以1.两个字符串的公共自字符串的长度肯定l=min(length(st1),length(st2);2.因为我们要求最长公共子串，所以我们可以先设子串=st1(较短)，然后利用pos函数在st2中查找子串pos(st,st2),如果我们找到了则既为所求。否则我们将尝试长度为l:=l-1的st1的子字符串（利用函数str:=copy(st1,1,l),copy(st1,2,l)直到找到为止。,2019/12/5,信息学竞赛培训提高班,13,programsearch(input,output);varstr1,str2,str:string;l1,l2,l,a,:integer;flag:boolean;布鲁形变量它的值只有TRUE，FALSEbeginflag:=false;标识有没有找到最大公共子字符串writeln(pleaseinputstring1);readln(str1);writeln(pleaseinputstring2);readln(str2);输入两个字符串l1:=length(str1);l2:=length(str2);用length函数求两个字符串的长度ifl1l2thenbeginstr:=str2;str2:=str1;str1:=strend;l:=length(str1);将较短的字符串-str1,较长的字符串-str2,l:=min(l1,l2);fora:=Ldownto1do公共子字符串的长度依次减少forb:=1toLdo起始位置1-Lbeginstr:=copy(str1,b,a);取长度为a,第b个位置开始的字符串为假定的公共子字符串ifpos(str,str2)0then用POS函数来找str2中有没有此字符串beginwrite(str1);flag:=true;exit;end如果有既为所求，输出，退出循环end;ifflag=falsethenwriteln(nomatch);如果始终没有找到，则输出没有end.,2019/12/5,信息学竞赛培训提高班,14,看程序写答案,programprogram2;vari,j:integer;str1,str2:string;beginstr1:=pig-is-stupid;str2:=clever;str11:=d;str12:=o;i:=8;forj:=1to6dobeginstr1i:=str2j;inc(i);end;writeln(str1);end.,2019/12/5,信息学竞赛培训提高班,15,思考题,Context1:统计字符数字【题目】读入一字符串，请输出大写英文字母数、小写英文字母数，和数字字母的数量和其他字符数。例：输入字符串abc$deAD38H输出：3522context2:统计单词数【题目】读入一英文句子，单词之间用空格或逗号隔开，统计其中单词个数，并输出各个字母出现的频率。(句子末尾不一定用.结束)【算法分析】要注意连续两个空格或逗号与空格连在一起时的误判断。例如输入以下字符串:“abc_abc_abc,_abc_,_abc_,_.”(_代表空格),2019/12/5,信息学竞赛培训提高班,16,提高思考题,CONTEXT：在键盘中输入两个位数不超过200位的正整数A和B，求A-B的差和和A+B；求N个字符串的最长公共子串，n20,字符串的长度不超过255；例如N=3,由键盘依次输入三个字符串为：Whatislocalbus?Namesomelocalbus?LocalbusishighspeedI/0busclosetotheprocessor.则最大公共子字符串是：“localbus”;,2019/12/5,信息学竞赛培训提高班,17,测试题一,一、拆分整数输入一个正整数N（不超过一百位），如果N是偶数，则拆分N的各个数字相加求和；如果N是奇数，则拆分N的各个数字相乘求积。输入输出样例：输入：输出：H输入：输出：J数据范围：30%的数据在二十位以内；100%的数据在一百位以内,2019/