1. 从一道“病历单”题聊聊信息学奥赛里的“逆向思维”大家好我是老张一个在信息学奥赛圈子里摸爬滚打了十来年的老选手兼教练。今天咱们不聊那些高深莫测的算法就聊聊一道特别有意思、也特别能锻炼“程序员思维”的经典题目——OpenJudge NOI 1.7的第12题“加密的病历单”。这道题在信息学奥赛的入门阶段尤其是字符串处理这个关卡里堪称一块绝佳的“试金石”。它看起来就是个简单的字符串变换但里面藏着的“逆向思维”和“工序拆解”的智慧对初学者来说价值远超题目本身。很多刚接触编程的同学一看到“加密”、“解密”这样的字眼可能下意识就觉得复杂脑子里立刻蹦出什么RSA、AES这些高级词汇。其实不然信息学奥赛的很多题目恰恰喜欢用生活中常见的、易于理解的场景来包装核心的编程思想。这道题就是典型。它模拟了一个非常简单的加密过程医生写了一份病历单为了保密先对每个字母循环左移3位比如‘a’变成‘d’然后把整句话倒过来写逆序存储最后再把所有字母的大小写互换大写变小写小写变大写。现在你拿到的是这份经过“加工”的病历单你的任务就是把它还原成原文。你看题目描述是不是一下子就亲切了它没有复杂的数学公式就是一个清晰的、分步骤的操作流程。但解题的关键恰恰在这里题目告诉你的是“加密”的步骤而你需要实现的是“解密”。这就要求你不能顺着题目的描述直接写代码而是必须倒过来想。加密是“左移-逆序-大小写翻转”那解密就应该是它的逆过程也就是“大小写翻转-逆序-右移”。这种“逆序操作”的思维在编程中极其重要无论是解决数学方程、回溯算法还是后来的栈、递归等概念都离不开这种“原路返回”的思考方式。所以别小看这道题它是在为你未来更复杂的算法学习打下一个非常重要的思维基础。2. 庖丁解牛三步拆解解密算法拿到加密后的字符串我们知道了需要三步操作来还原它。但具体每一步在代码里怎么实现里面有不少细节和技巧。咱们就像拆解一台精密仪器一样把这三个工序一个一个掰开揉碎了讲清楚。我会用最直白的语言配合代码示例让你不仅知道要这么做更明白为什么要这么做以及有哪些容易踩的“坑”。2.1 第一步大小写反转——最直接的“开关”解密的第一步是先把字符串里所有字母的大小写状态给翻转回来。为什么先做这一步因为加密的最后一步是大小写翻转那么解密的第一步自然就是把它再翻回去。这就像你最后关上的门得最先打开。在C里实现大小写翻转有几种方法。最“原始”但最能体现原理的方法就是利用字符在ASCII码表中的规律。我们知道同一个字母的大小写它们的ASCII码值相差32。比如‘A’是65‘a’是97。所以判断一个字符c如果它是大写字母c A c Z那么把它变成小写就是c c 32或者更优雅地写成c c - A a。后面这种写法不依赖具体的ASCII码值可读性更好。如果它是小写字母c a c z那么把它变成大写就是c c - 32或者c c - a A。当然C的标准库cctype为我们提供了更便捷的工具函数islower()判断是否小写isupper()判断是否大写tolower()转小写toupper()转大写。用这些函数写出来的代码更简洁意图也更清晰。我建议初学者在理解原理的基础上可以多用这些库函数它们能让你避免很多边界判断的错误。这里有个小坑需要注意字符串里可能包含非字母字符吗从题目描述看加密对象是“字符串”但通常这种字母移位操作默认只处理字母。不过为了代码的健壮性我们在做大小写转换前最好用isalpha()函数判断一下当前字符是不是字母。只对字母进行转换对于空格、标点等字符则保持原样。这是一个很好的编程习惯。2.2 第二步逆序存储——对称交换的艺术大小写翻回来之后第二步就是把字符串的顺序再倒回来。加密时是正序变逆序解密时自然要把逆序变回正序。实现字符串逆序最经典、效率也最高的方法就是“双指针交换法”。想象一下你有一排格子里面放着字符。要逆序其实就是把第1个和最后1个交换第2个和倒数第2个交换以此类推直到走到中间位置。用代码来实现就是用一个for循环循环变量i从0开始到字符串长度len的一半len/2结束。在循环体内交换s[i]和s[len-1-i]这两个位置的字符。这里的关键点在于循环的终止条件i len/2。为什么是小于len/2而不是小于等于我们举个例子如果字符串长度是5比如hellolen/2在整数除法下等于2。我们需要交换的位置是(0,4)、(1,3)。当i2时len-1-i也等于2自己和自己交换多此一举而且循环到中间就足够了。如果字符串长度是4如testlen/2等于2需要交换(0,3)和(1,2)。当i2时循环条件i2已经不满足正好结束。所以这个条件对于奇数和偶数长度都是完美适用的。另外你也可以使用C标准库的reverse()函数需要包含algorithm头文件一行代码reverse(s, slen)就能搞定。但在信息学奥赛的初级阶段我强烈建议你亲手实现一遍这个交换过程这能加深你对数组下标操作和循环控制的理解这是基本功中的基本功。2.3 第三步循环右移3位——模运算的巧妙应用这是整个解密过程最核心、也最具技巧性的一步。加密时字母是循环左移3位那么解密时就需要循环右移3位。什么叫“循环”呢就是说‘z’右移3位不是跑到字母表外面去而是回到‘w’‘a’右移3位也不是跑到前面去而是变成‘x’。这就像一个圆环首尾相连。如何用数学和代码来描述这个“圆环”呢这里就要请出编程中一个极其重要的概念模运算。我们可以把26个字母想象成0到25的数字a0, b1, ..., z25。对于一个字母对应的数字x右移3位直观上就是x3。但直接加3可能会超过25比如‘x’对应23加3得26这时我们就需要它“绕回来”。模运算%26正好能实现这个效果(x3) % 26。这个式子的意思是先计算x3然后除以26取余数。结果一定落在0到25之间完美对应回字母表。因此对于一个小写字母c解密右移3位的步骤就是将其转换为数字int num c - a;数字加3后模26num (num 3) % 26;将数字转换回字母c num a;合并成一行就是c (c - a 3) % 26 a;对于大写字母同理c (c - A 3) % 26 A;这里有一个非常精妙的点为什么是(c - a 3) % 26而不是(c - a - 3) % 26因为我们要的是右移从加密状态左移后的结果还原。假设原字母是p数字15加密左移3位后变成s数字18。现在拿到s18要还原成p15相当于要把s右移3位。在0-25的环上从18向右走3步就是(183)%2621不对这反而走更远了。实际上在环上“右移3位”等价于“左移23位”。因为右移1位等于左移25位右移3位等于左移23位。而(1823)%26正好等于15。但我们用(183)%26为什么也对呢奥秘在于我们解密时处理的字符串是已经经过前两步大小写翻转和逆序处理过的此时字符对应的“移位关系”已经发生了改变。按照解密流程大小写翻转-逆序-右移推导最终公式就是(c - a 3) % 26。如果你从数学上严格推导加密和解密的逆运算也会得到这个结果。所以记住这个公式就好它是经过验证的正确形式。3. 两种实战代码思路从“过程模拟”到“结果构造”理解了每一步的原理我们就可以动手写代码了。这里我提供两种风格迥异的解题思路它们代表了解决这类问题两种非常重要的编程范式。第一种是直观的“过程模拟”第二种是高效的“结果构造”。掌握这两种思路对你未来解题大有裨益。3.1 思路一模块化函数清晰模拟解密过程这种思路最直接也最符合人类的思维习惯既然解密分三步那我就写三个函数分别完成“大小写翻转”、“逆序存储”和“循环右移”的功能。然后在主函数里按顺序调用这三个函数来处理输入的字符串。#include iostream #include cstring #include cctype using namespace std; // 函数1循环右移3位 void moveRight(char s[]) { int len strlen(s); for (int i 0; i len; i) { if (isupper(s[i])) { s[i] (s[i] - A 3) % 26 A; } else if (islower(s[i])) { s[i] (s[i] - a 3) % 26 a; } // 非字母字符原样保留 } } // 函数2大小写翻转 void changeCase(char s[]) { int len strlen(s); for (int i 0; i len; i) { if (isupper(s[i])) { s[i] tolower(s[i]); } else if (islower(s[i])) { s[i] toupper(s[i]); } } } // 函数3字符串逆序 void reverseStr(char s[]) { int len strlen(s); for (int i 0; i len / 2; i) { swap(s[i], s[len - 1 - i]); // 使用swap函数交换 } } int main() { char secret[55]; // 题目说长度小于50留一点余量 cin secret; // 读入加密后的字符串 // 注意解密步骤是加密步骤的逆序 changeCase(secret); // 第一步翻转大小写 reverseStr(secret); // 第二步逆序 moveRight(secret); // 第三步循环右移 cout secret endl; return 0; }这种写法的优点非常明显结构清晰易于调试。每个函数只负责一个明确的任务如果某一步结果不对你可以很快地定位到是哪个函数出了问题。比如你可以先注释掉后面两步只调用changeCase看看大小写翻转是否正确。这对于初学者培养调试能力、理解程序执行流程非常有帮助。而且这三个函数都是非常基础的字符串操作函数你在其他题目里也完全可能用到这次写好以后就是你的代码库里的现成工具了。3.2 思路二单次遍历边解密边构造新字符串第二种思路更巧妙效率也通常更高一些。它不需要修改原字符串而是通过单次遍历加密字符串直接计算出解密后每个字符应该是什么并放入一个新的结果字符串中。怎么做到呢我们再来分析一下解密步骤翻转大小写 - 逆序 - 循环右移。如果我们从加密字符串的最后一位开始向前遍历这就是“逆序”的体现对于遍历到的每个字符先对其应用“循环右移3位”的规则。然后立即进行“大小写翻转”。将这个处理好的字符按顺序放入结果数组中。这样当我们从后往前遍历完原字符串时结果数组里顺序存放的字符恰好就是完全解密后的字符串了。因为从后往前遍历实现了“逆序”而对每个字符先右移再翻转整体效果就等价于“翻转-逆序-右移”。#include iostream #include cstring #include cctype using namespace std; int main() { char secret[55], result[55]; // secret存加密串result存解密结果 cin secret; int len strlen(secret); int index 0; // 指向result数组的当前位置 // 从加密字符串的末尾开始向前遍历 for (int i len - 1; i 0; --i) { char c secret[i]; // 处理循环右移3位 和 大小写翻转 if (c a c z) { // 小写字母右移3位后转换为大写 c (c - a 3) % 26 A; } else if (c A c Z) { // 大写字母右移3位后转换为小写 c (c - A 3) % 26 a; } // 非字母字符保持不变但根据题意可能不存在非字母 result[index] c; } result[index] \0; // 千万不要忘记在结果字符串末尾加上结束符 cout result endl; return 0; }这种方法的优点是只需要遍历字符串一次并且避免了在原字符串上频繁修改可能带来的下标错乱问题。它更侧重于对问题的整体理解和转化将多步操作融合在一步里体现了算法设计中的“优化”思想。缺点是理解起来稍微绕一点需要你在大脑里清晰地模拟整个转换过程。我建议你先彻底理解第一种方法再来看第二种你会有一种“原来还可以这样”的豁然开朗感。4. 举一反三字符串处理题的通用心法通过“加密的病历单”这道题我们其实可以提炼出解决一大类信息学奥赛字符串处理题目的通用方法和心法。这些经验是我带学生这么多年看他们一次次调试、一次次踩坑总结出来的希望能帮你少走弯路。心法一明确“加密”与“解密”的互逆关系。这是本题最核心的考点。以后遇到任何带有变换规则的问题首先要问自己题目给的是编码规则还是解码规则我需要实现的是正向过程还是逆向过程就像解一道数学题已知yf(x)和y求x你的代码实现的是f(x)还是f^{-1}(y)务必保持清醒。心法二复杂操作分而治之。一个复杂的字符串处理流程往往由多个简单操作组合而成比如本题的移位、逆序、翻转。最好的策略就是为每一个简单操作编写一个独立的函数。这样做不仅让主程序逻辑清晰就像一份烹饪食谱一步步来更重要的是便于测试。你可以单独测试每个函数是否正确大大降低了调试难度。记住模块化是应对复杂性的不二法门。心法三善用字符的算术运算。在C/C中字符本质上是整数ASCII码。‘a’ 1得到‘b’‘Z’ - ‘A’得到25。利用这个特性我们可以非常方便地在字母和数字0-25之间进行转换从而实现移位、替换等操作。关键是找到那个“基准”比如c - ‘a’就把小写字母映射到了0-25。心法四警惕边界和循环。本题的“循环移位”是边界处理的经典案例。当移位可能超出字母表范围时必须通过模运算(%26)让它“绕回来”。在其他题目中边界可能是数组的起点和终点、字符串的结束符‘\0’、或者各种特殊字符的判断。处理边界情况是程序是否健壮、能否拿满分的决定性因素。心法五选择合适的数据结构。本题使用字符数组C风格字符串是合适的。但在更复杂的问题中你可能需要用到C的string类型它提供了reverse、find等大量现成方法能极大简化代码。不过信息学奥赛的早期题目往往鼓励你从底层实现这些功能以夯实基础。我的建议是理解原理用数组追求效率用string。最后我再分享一个我学生常踩的“坑”忘记字符串结束符‘\0’。当你像第二种思路那样自己构建一个字符数组作为结果时一定要在最后手动加上result[index] ‘\0’;。没有这个结束符后续用cout输出或者用strlen计算长度都会出错因为程序不知道你的字符串在哪里结束。这个错误隐蔽但致命一定要养成习惯。字符串处理是信息学竞赛的基石从简单的字母变换到复杂的模式匹配、文本解析都离不开这些基本功。希望“加密的病历单”这道题不仅能让你学会循环、模运算和逆序更能帮你建立起拆解问题、模拟过程、优化代码的思维模式。多练多思考多总结你会发现再复杂的“病历单”你也能轻松“解密”。