计算机程序设计能力考试（PAT）备考通 | PAT模拟样题（进阶题）

1.题目名称：英语老师小助手（ 15分）

题目描述

英语老师要求学生按照如下规则写一串字母。

规则 1：如果写了某个大写字母，则下一个必须写同一个字母的小写或者字母表中前一个字母的大写。

规则 2：如果写了某个小写字母，则下一个必须写同一个字母的大写或者字母表中下一个字母的小写。

例如， “zZzZYXWwxyYX”就是一个合法的字母串；而“ wVUuvUTsR”就是非法的。

现在面对全班学生交上来的作业，老师请你写一个程序自动批改。

输入格式

第一行给出一个不超过 100的正整数 N。随后的 N行，每行给出一位学生的作业，即仅由英文字母组成的非空字母串，长度不超过 2×10⁶。

输出格式

对于每位学生的作业，如果正确，则在一行中输出 Y，否则输出 N。

输入样例

输出样例 

解题思路

事实上，输入格式中给出的学生作业字符串的最大长度是多余的。本题只需要检查当前字母和下一个字母之间的关系是否满足规则，检查后就可以丢弃，所以没有必要记录整个字符串，更不需要把所有学生的作业都存下来后进行分析。额外的空间复杂度应该是 O(1)。

因为输入给出了学生作业的总条数 N，我们明确地知道循环次数，所以应该用一个 for循环处理每一条作业。而在处理每一条作业时，我们不知道学生作业字符串的长度，所以当使用循环处理每个字母时，使用 while循环比较合适。

在处理每条作业时，只需要两个字符，即 thisc存储当前的字母， nextc存储 thisc的下一个字母。可以用一个函数 check(thisc, nextc)检查这两个字母是否满足规则。如果满足规则，则将 thisc更新为 nextc，然后继续读下一个 nextc。这里需要注意的是，一旦有一对字母不满足规则，那么整个作业就错了，但不能立刻跳出 while循环，而是应该继续把剩下的字母读完。

规则检查函数比较简单，它就是对两个规则的直接翻译。首先默认判断结果为正常，然后判断规则 1或 2是否有哪个没有满足，从而改变了状态。所以这里考查的是逆命题的逻辑实现是否正确，即当 thisc为大写字母时，规则 1的逆命题是“ nextc既不是 thisc的小写，也不是 thisc的前一个字母的大写”；当 thisc为小写字母时，规则 2的逆命题是“ nextc既不是 thisc的大写，也不是 thisc的后一个字母的小写”。

测试要点

测试数据首先要覆盖大写和小写的全部英文字母。其次，对于大写和小写两种情况，都要测试其后跟随正确的大写和小写字母，以及跟随错误 的大写和小写字母的情况。另外， A和 z是两个特殊的字母，其中， A后面不可能跟随“前一个字母”，z后面不可能跟随“后一个字母”。最后，最小规模和最大规模的随机数据都应该包含在测试数据中。

源代码 (C)

■ 代码 4.6“英语老师小助手”源代码

2.题目名称：相生相克（ 15分）

题目描述

古代先民认为天下万物皆由五类元素组成，分别是金、木、水、火、土，

它们彼此之间存在相生相克的关系。

相生关系为：木生火，火生土，土生金，金生水，水生木。

相克关系为：金克木，木克土，土克水，水克火，火克金。

本题就请你编写程序，判断任意一对给定的元素之间的关系。

输入格式

在一行中给出一个正整数 N（N≤10），随后的 N行，每行给出两个正整数 A和 B，即两种元素的编号。假设金、木、水、火、土的编号依次为 1、 2、3、4、5。

输出格式

对输入的每一对 A和 B，如果 A生 B，则输出 “A sheng B”；如果 A克 B，则输出“ A ke B”；反之亦然。 

输入样例

输出样例

解题思路

本题考查利用数组进行关系映射的技巧。因为金木水火土是从 1开始顺序编号的，而数组下标是从 0开始顺序编号的，所以正好可以用两个数组映射“生”与“克”的关系，只要把金木水火土的编号分别减 1，就可以把金木水火土和数组的下标一一对应起来了。

把记录相生关系的数组命名为 S，S[A]=B表示“ A生 B”。例如“木生火”，因为木的编号是 2，火的编号是 4，分别减 1后对应的数组下标为 1和 3，所以就对应 S[1]=3。于是给出的 5个相生关系就可以翻译为代码 4.7中 S初始化的值。理解了相生关系后，相克关系就可以完全类似地用另一个数组 K记录。

解决了关系的存储问题后，剩下的事情就很简单了。只要注意一下细节处理，即 A和 B读入后要分别先减 1，用于对应数组下标，但是在输出关系时，要把减去的 1加回来。输出一共有 4种可能，即“A生 B”“B生 A”克 B”“B克 A”，枚举输出即可。

测试要点

样例数据测试了 “B生 A”和“A克 B”。测试数据还应该包含对 “A生 B”和“ B克 A”的测试。当然， N取最小值 1和最大值 10的数据也要包含。

源代码 (C)

■ 代码 4.2“恭喜你”源代码

实例讲解

下期预告