聪明人的游戏教材.doc

第二章 字符串处理和进制转换 在程序设计时，如果输入数据一行包含多种信息，以字符串的形式出现，这时就需要用到字符串处理 第1课 贝贝的交通指挥系统(jqr.pas) 【问题描述】 贝贝所居住的城市有很多个交通路口，其中有26个交通路口在上下班高峰期总是塞车，严重影响市民的出行。于是交通管理部门研制了一批机器人交通警察，用它们来专门指挥这26个交通路口，但需要一个自动化的指挥系统来指挥机器人的运作。这个任务交给了贝贝，贝贝的设计如下。 分别用大写英文字母A、B、…、Z表示这26个路口，并按如下的规则派出这些机器人到交通路口协助指挥交通： 1．每次派出两名机器人； 2．当两名机器人的名字中存在一个相同的字母时，这两有多个字母相同时，两名机器人需要按字母的字典顺序到这些路口上巡逻； 3．当两名机器人的名字中不存在相同的字母时，交警部门的派出指令无效( WuXiao)。 假设这些机器人的名字全由大写字母组成，请你编一个程序，帮贝贝完成这个交通指挥系统。 【输入格式】jqr 第1行输入第一个机器人的名字（长度不超过250）； 第2行输入第二个机器人的名字（长度不超过250）。 【输出格式】jqr 1．当不能派出机器人时，在第一行输出“WuXiao； 2．当两名机器人在路口上指挥交通时，在第一行输出“ZhiHui，第二行输出路口编号； 3．当两名机器人在路口上巡逻时，在第一行输出“XLuo，第二行输出巡逻的路口数，第三行输出巡逻线路。 【输入输出样例】 题目意思：输入两个机器人的名字，统计他们的名字中出现相同字母的个数，由相同字母的个数决定 解决问题 1．方法一 因为输入的机器人名长度不超过250，可用字符串方式读入数据。用两个字符串保存数据，使用双重total记录相同字母的 如果total=0，则输出“WuXiao； 如果total=，则输出“ZhiHui； 如果total，则输出“XLuo。 参考程序如下： 上述程序未考虑题目中隐含的条件，即机器人名字中可能会出现重复的相同字母。上面①处双重循环total上，最终total的结果是错误的，导致输 for i:=A to Z do b[i]:=true; for i:=1 to length(str1) do for j:=1 to length(str2) do if (str1[il=str2[j])and b[str1[i]] then begin inc(total) ; a[total]:=strl[i]; b[str1[i]]: =false; end; 算法效率：程序中统计相同字母个数和使用简单排序对字母进行排序时，用了双重循环，因此时间复(n2)，而n的值为机器人名字长度，最长为250个字符，即n2=250×250=62500 108，程序不会超10000，程序将会超时。 2．方法二 设置ab两个数组，数组下标范围：AZ，初始值为false，分别用来记录两个机器人名字中出现true。然后再用下面的代码统计相同字母个数： for j=A to Z do if(a[j]) and (b[j]) then 统计相同字母的个数(total)。 参考程序如下：算法效率：①②③④处都是单循环，①②的循环次数最多才250次，③④的循环次数为26次，因此(n)，效率比方法一高。 算法比较：方法一，很多同学会容易想到，只要用枚举查找法和简单排序法便可以解决，是比较直观 可见，我们做题时要审清题目，仔细分析题目中隐含的信息，只有这样才能避免漏洞，保证测试全部 活学活用 1．贝贝的车牌问题(car) 【问题描述】 广州市车管所为每一辆入户的汽车都发放一块车牌，车牌的号码由六个字符组成，如A99452、B88888等，这个字符串从左边数起的第一个字符为大写英文字母，如A、B、C等，表示这辆车是属于广州市区内的汽车还是郊区的汽车，后面的五位由数字组成。假定以字母A、B、C、DE、F、G、R、S、T开头的表示是市区车牌，而以其他字母开头的表示郊区车牌。 车管所把这个任务交给贝贝。请你帮贝贝找出所给出的车牌中有多少辆是广州郊 【输入格式】 第1行是一个正整数N(1≤N≤105)，表示共有N个车牌。接下来的N行，每行是一个车牌号。题目保证给出的车牌不会重复。 【输出格式】 只有1行，即广州郊区车牌的数量。 【输入样例】 3 G54672