聪明人的游戏教材

1第二章字符串处理和进制转换在程序设计时，如果输入数据一行包含多种信息，以字符串的形式出现，这时就需要用到字符串处理的知识来进行操作。在计算机领域中，有时需要将十进制数转换成二进制、八进制和十六进制的数，有时又需要逆向转换，即将二进制、八进制和十六进制的数转换成十进制的数，或它们相互间进行转换。因此，本章主要介绍字符串处理和进制转换的相关知识。第1课贝贝的交通指挥系统(jqr.pas)【问题描述】贝贝所居住的城市有很多个交通路口，其中有26个交通路口在上下班高峰期总是塞车，严重影响市民的出行。于是交通管理部门研制了一批机器人交通警察，用它们来专门指挥这26个交通路口，但需要一个自动化的指挥系统来指挥机器人的运作。这个任务交给了贝贝，贝贝的设计如下。分别用大写英文字母A、B、…、Z表示这26个路口，并按如下的规则派出这些机器人到交通路口协助指挥交通：1．每次派出两名机器人；2．当两名机器人的名字中存在一个相同的字母时，这两名机器人便到对应的交通路口上指挥交通；有多个字母相同时，两名机器人需要按字母的字典顺序到这些路口上巡逻；3．当两名机器人的名字中不存在相同的字母时，交警部门的派出指令无效(WuXiao)。假设这些机器人的名字全由大写字母组成，请你编一个程序，帮贝贝完成这个交通指挥系统。【输入格式】jqr.in第1行输入第一个机器人的名字（长度不超过250）；第2行输入第二个机器人的名字（长度不超过250）。【输出格式】jqr.out1．当不能派出机器人时，在第一行输出“WuXiao”；2．当两名机器人在路口上指挥交通时，在第一行输出“ZhiHui”，第二行输出路口编号；3．当两名机器人在路口上巡逻时，在第一行输出“XLuo，第二行输出巡逻的路口数，第三行输出巡逻线路。【输入输出样例】输入输出样例1OPENCLOSEXLuo2E-O样例2EPSONSENPUMXLuo4E-N-P-S分析问题题目意思：输入两个机器人的名字，统计他们的名字中出现相同字母的个数，由相同字母的个数决定他们巡逻的路线。当两名机器人的名字中存在一个相同的字母时，这两名机器人便到对应的交通路口上指挥交通；有多个相同的字母时，两名机器人需要按字母的字典顺序到这些路口上巡逻；当两名机器人的名字中不存在相同的字母时，交警部门的派出指令无效。2解决问题1．方法一因为输入的机器人名长度不超过250，可用字符串方式读入数据。用两个字符串保存数据，使用双重循环，用枚举法查找相同的字母，用一个数组保存这些相同的字母，并用一个变量total记录相同字母的个数，然后按字母顺序排序，最后根据相同字母的个数分下面三种情况输出结果：如果total=0，则输出“WuXiao；如果total=1，则输出“ZhiHui；如果total1，则输出“XLuo。最后按题目要求输出巡逻路线。参考程序如下：上述程序未考虑题目中隐含的条件，即机器人名字中可能会出现重复的相同字母。上面①处双重循环的代码，由于忽略题目隐含信息，把重复字母也重复计算在total上，最终total的结果是错误的，导致输出路线的错误。应怎么解决呢？我们可以设置一个数组标识出现过的相同字母，实现如下：fori:='A'to'Z'dob[i]:=true;fori:=1tolength(str1)doforj:=1tolength(str2)doif(str1[il=str2[j])andb[str1[i]]thenbegininc(total);a[total]:=strl[i];b[str1[i]]:=false;end;算法效率：程序中统计相同字母个数和使用简单排序对字母进行排序时，用了双重循环，因此时间复杂度为O(n2)，而n的值为机器人名字长度，最长为250个字符，即n2=250×250=62500108，程序不会超时。如果机器人名字长度超过10000，程序将会超时。2．方法二设置a,b两个数组，数组下标范围：A..Z，初始值为false，分别用来记录两个机器人varstr1,str2:string;total,i,j,temp:longint;a:array[0..1000]ofinteger;beginreadln(str1);readln(str2);//读入两个机器人的名字total:=0;//记录相同字母个数，清零fori:=1tolength(str1)do//①forj:=1tolength(str2)doifstr1[i]=str2[j]thenbegininc(total);a[total]:=str1[i];end;iftotal=0thenwriteln('WuXiao');iftotal=1thenbeginwriteln('ZhiHui');writeln(a[total]);end;fori:=1tototal-1doforj:=i+1tototaldoifa[i]a[j]thenbegintemp:=a[i];a[i]:=a[j];a[j]:=temp;end;iftotal1thenbeginwrite(a[1]);fori:=2tototaldowrite('-',a[i])end;end.3名字中出现的字母，如果某个字母出现过则对应数组值为true。然后再用下面的代码统计相同字母个数：forj:='A'to'Z'doif(a[j])and(b[j])then统计相同字母的个数(total)。参考程序如下：算法效率：①②③④处都是单循环，①②的循环次数最多才250次，③④的循环次数为26次，因此其时间复杂度为O(n)，效率比方法一高。算法比较：方法一，很多同学会容易想到，只要用枚举查找法和简单排序法便可以解决，是比较直观的想法，容易出现漏洞，程序的算法效率不高，如果机器人的名字长度更长，则容易超时；方法二，采用类似计数排序的方法，节约运行时间，算法效率高。可见，我们做题时要审清题目，仔细分析题目中隐含的信息，只有这样才能避免漏洞，保证测试全部通过。同时根据题目的特点，尽量从不同角度分析，可能存在多种算法，要对各种算法进行比较，采用最优的算法。活学活用1．贝贝的车牌问题(car)【问题描述】广州市车管所为每一辆入户的汽车都发放一块车牌，车牌的号码由六个字符组成，如vars:string;j:char;i,total:longint;a,b:array['A'..'Z']ofboolean;beginreadln(s);forj:='A'to'Z'doa[j]:=false;//初始化为falsefori:=1tolength(s)doa[s[i]]:=true;//①标记第一个机器人名字中出现的字母readln(s);fori:=1tolength(s)dob[s[i]]:=true;//②标记第二个机器人名字中出现的字母forj:='A'to'Z'do//③统计两个机器人名字出现的相同字母个数if(a[j])and(b[j])theninc(total);iftotal1then//如果total1,则输出“XLuo”beginwriteln('XLuo');writeln(total);end;iftotal=1thenwriteln('ZhiHui');iftotal=0thenwriteln('WuXiao');total:=0;//计数器清零forj:='A'to'Z'do//④按字母顺序输出巡逻路线if(a[j])and(b[j])thenbegininc(total);iftotal=1thenwrite(j)//只有一个路口，则输出相应的字母elsewrite('-',j);end;end.4A99452、B88888等，这个字符串从左边数起的第一个字符为大写英文字母，如A、B、C等，表示这辆车是属于广州市区内的汽车还是郊区的汽车，后面的五位由数字组成。假定以字母A、B、C、D、E、F、G、R、S、T开头的表示是市区车牌，而以其他字母开头的表示郊区车牌。车管所把这个任务交给贝贝。请你帮贝贝找出所给出的车牌中有多少辆是广州郊区的汽车。【输入格式】第1行是一个正整数N(1≤N≤105)，表示共有N个车牌。接下来的N行，每行是一个车牌号。题目保证给出的车牌不会重复。【输出格式】只有1行，即广州郊区车牌的数量。【输入样例】3G54672Q87680P77771【输出样例】22．贝贝的ISBN号码(isbn)【问题描述】每一本书都有一个ISBN号码，包括9位数字、1位识别码和3位分隔符，其规定格式如“X-XXX-XXXXX-X”，其中符号“-”是分隔符（减号），最后一位是识别码，例如0-670-82162-4就是一个标准的ISBN码。ISBN码的首位数字表示书籍的出版语言，例如O代表英语；第一个分隔符“-”之后的三位数字代表出版社，例如670代表出版社；第二个分隔符之后的五位数字代表该书在出版社的编号；最后一位为识别码。出版社想开发一套自动化识别系统，判断输入的ISBN号码中识别码是否正确，如果正确，则仅输出“Right”；如果错误，则输出你认为是正确的ISBN号码。于是，出版社把这个任务交给了贝贝。识别码的计算方法如下：首位数字乘以1加上次位数字乘以2……以此类推，用所得的结果mod11，所得的余数即为识别码，如果余数为10，则识别码为大写字母X。例如ISBN号码0-670-82162-4中的识别码4是这样得到的：对067082162这9个数字，从左至右，分别乘以1，2，…，9，再求和，即O×1+6×2+…+2×9=158，然后取158mod11的结果4作为识别码。请你帮贝贝完成这个任务。【输入格式】只有1行，是一个字符序列，表示一本书的ISBN号码（保证输入符合ISBN号码的格式要求）。【输出格式】假如ISBN识别码正确，那么输出“Right”，否则输出正确的ISBN号码（包括分隔符“一”）。【输入输出样例】输入输出样例10-670-82162-4Right样例20-670-82162-00-670-82162-45第2课贝贝的图形(vhist)【问题描述】贝贝最近玩起了字符游戏，规则是这样的：读入四行字符串，其中的字母都是大写的，乐乐想打印一个柱状图显示每个大写字母的频率。你能帮助他吗？【输入格式】输入文件共有4行：每行为一串字符，不超过72个字符。【输出格式】与样例的格式保持严格一致。【输入样例】THEQUICKBROWNFOXJUMPEDOVERTHELAZYDOG.THISISANEXAMPLETOTESTFORYOURHISTOGRAMPROGRAM．HELLO!【输出样例】说明：1．输出的相邻字符间有一个空格。2．最后一行的26个大写字母每次必须输出。3．大写字母A所在的第一列前没有空格。分析问题题目意思：输入四行字符串，长度都不超过72，统计大写字母的个数，输出结果时，用“*”表示字母出现的频率，并按样例说明的要求输出。解决此问题的难点在于输出格式的控制，细看样例可知，输出的内容就只有空格、星号和大写字母，除最后一行为大写字母外，上面输出的每行都有空格和星号，那么，问题就成了如何控制空格和星号的输出。只要解决此问题，本题就解决了。通过问题分析，我们应怎么样控制空格和星号的输出呢？我们先把题目的输出样例转化成如下表：表2.2-1字母ABCDEFGHIJKLMN0PQRSTUVWXYZ星号个数5l1282354114421031747311221由表中的数据可以知，出现频率最多的是字母“O”，为10次，也就是说，这个数值决*************************************************************************************ABCDEFGHIJKLMNOPQRSTUVWXYZ图2.2-16定了你输出的图形有10行，并都是由空格和星号组成，我们就倒过来为这些图形定义一个行号，从最上面第一行开始，行号为10、9、8……10如下面图2.2-2所示。图2.2-2行数定了，我们再看看，