信息学奥赛一本通 1162 题：4 种解法对比与递归思维训练（含复杂度分析）

字符串逆序是信息学竞赛中的经典问题，看似简单却蕴含丰富的算法思想。本文将深入解析《信息学奥赛一本通》1162题的四种实现方案，通过对比递归、迭代、双指针和STL库函数的不同解法，帮助选手建立多维解题视角。每种方法都配有完整可运行的C++代码示例、详细的时间/空间复杂度分析，以及适用场景建议。

1. 问题重述与基础解法

题目要求输入一个以感叹号结尾的字符串，输出其逆序形式（不包含结尾的感叹号）。例如输入"Hello!"，输出应为"olleH"。

1.1 字符数组递归解法

#include <bits/stdc++.h> using namespace std; void reversePrint(char s[], int len) { if(len == 0) return; cout << s[len-1]; reversePrint(s, len-1); } int main() { char s[1005]; cin.getline(s, 1005); int len = strlen(s); s[--len] = '\0'; // 移除末尾'!' reversePrint(s, len); return 0; }

核心分析：

• 递归基：当字符串长度为0时终止
• 递归关系：先输出最后一个字符，再递归处理前n-1个字符
• 时间复杂度：O(n) 每个字符访问一次
• 空间复杂度：O(n) 递归调用栈深度

1.2 迭代解法对比

#include <bits/stdc++.h> using namespace std; int main() { string s; getline(cin, s); s.pop_back(); // 移除末尾'!' for(int i = s.length()-1; i >= 0; --i) cout << s[i]; return 0; }

性能对比：

2. 进阶解法与优化策略

2.1 双指针原地逆序

#include <bits/stdc++.h> using namespace std; void reverseString(string &s) { int left = 0, right = s.length()-1; while(left < right) { swap(s[left], s[right]); left++; right--; } } int main() { string s; getline(cin, s); s.pop_back(); reverseString(s); cout << s; return 0; }

优势分析：

• 空间效率最优：O(1)额外空间
• 适合内存敏感场景
• 可扩展性强（可轻松改为处理字符数组）

2.2 STL算法实现

#include <bits/stdc++.h> using namespace std; int main() { string s; getline(cin, s); s.pop_back(); reverse(s.begin(), s.end()); cout << s; return 0; }

工程实践建议：

• 竞赛中推荐使用，代码简洁
• 需包含 头文件
• 实际性能与编译器优化相关

3. 递归思维深度训练

3.1 递归调用过程可视化

以输入"abc!"为例，递归执行流程：

reversePrint("abc", 3) │ ├─ 输出'c' │ └─ reversePrint("ab", 2) │ ├─ 输出'b' │ │ └─ reversePrint("a", 1) │ │ ├─ 输出'a' │ │ └─ reversePrint("", 0) → 返回 │ └─ 返回 └─ 返回

3.2 递归转非递归通用方法

使用显式栈模拟递归过程：

#include <bits/stdc++.h> using namespace std; void reverseWithStack(char s[], int len) { stack<char> st; for(int i=0; i<len; i++) st.push(s[i]); while(!st.empty()) { cout << st.top(); st.pop(); } } int main() { char s[1005]; cin.getline(s, 1005); int len = strlen(s); s[--len] = '\0'; reverseWithStack(s, len); return 0; }

递归思维要点：

1. 明确递归终止条件
2. 确定问题分解方式
3. 设计递归调用参数传递
4. 分析栈空间使用情况

4. 综合对比与实战建议

4.1 解法特性对比表

4.2 竞赛应用策略

1. 常规题目：优先使用STL reverse，节省编码时间
2. 特殊限制：
   • 禁用STL时采用双指针法
   • 内存严格限制使用迭代法
3. 递归训练：专门练习递归写法，培养分治思维
4. 调试技巧：
   • 递归版本可添加调用深度打印
   • 双指针法注意边界条件测试

// 带调试信息的递归版本 void reverseDebug(char s[], int len, int depth=0) { cout << "Depth " << depth << ": "; for(int i=0; i<len; i++) cout << s[i]; cout << endl; if(len == 0) return; cout << s[len-1]; reverseDebug(s, len-1, depth+1); }

4.3 复杂度分析进阶

考虑不同场景下的实际性能差异：

1. 小字符串（n<100）：

   • 各种方法差异不大
   • 递归调用开销约0.5μs/次

2. 大字符串（n>1e6）：

   • 递归可能栈溢出
   • 迭代法CPU缓存命中率更高
   • STL实现可能有SIMD优化

3. 极端情况（n≈1e7）：

   • 双指针法表现最优
   • 需考虑虚拟内存分页影响

在实际项目中选择解法时，除了考虑时间复杂度，还需要注意：

• 代码可维护性
• 团队熟悉程度
• 平台特性（如嵌入式系统慎用递归）
• 后续功能扩展需求