程序设计第7讲OJ作业：高频题型、常见陷阱与AC自查清单

这门课做到第7讲，正好是很多同学开始觉得“有点意思”的时候。前面几讲还在跟语法、流程控制较劲，到了Lecture(7)，题目忽然从“照着公式写”变成“自己想办法把问题拆开”，OJ作业的通过率也会肉眼可见地往下掉。如果你正卡在这份作业上，或者想提前知道第7讲作业里哪些地方最容易翻车，这篇就聊聊我批改作业和带学生刷OJ时总结出来的实际经验。

先交代一下背景。我见过太多同学把这门课当“背语法”，到了第7讲才发现根本不是那么回事。Lecture(7)的OJ作业，题目量一般不大，三四道居多，但每一道都在逼你把前面的知识点串起来用。它考的已经不单单是“认不认识这个函数”，而是“你拿到一个实际问题，能不能把它翻译成程序逻辑”。这篇文章不会帮你代写任何一道题，但会把这一类作业最常见的题型、解题框架、提交时踩过的坑一次性讲透，你对照着做，应该能少走很多弯路。

1. 第7讲作业到底在考什么

1.1 一次实打实的“半程测验”

按大多数“程序设计与算法”课程的教学进度，前6讲会把C/C++或Java的基本语法、分支循环、数组、字符串、函数这些地基打完。到第7讲，老师默认你已经掌握这些工具，接下来开始进入“算法入门”阶段，而OJ作业就是在这个节骨眼上安排的。

所以这份作业本质上是一次半程测验。它不会直接告诉你“这题考数组”“这题考递归”，而是把知识点藏在题目描述里，让你自己识别。比如题目里出现“对于任意输入的正整数，反复执行某操作直到满足条件”，你就要意识到这多半是循环或递归；出现“判断一个字符串是否满足某种规则”，那就是在考字符串处理和逻辑分支。

很多同学在这里第一次体验到“读题两小时，写代码五分钟”的困惑。不是说题目本身有多难，而是你还不习惯从自然语言里抽取算法。反过来，那些第7讲作业做得顺的同学，普遍在前期就养成了“先想边界条件、再写代码”的习惯。这两种人的差距，往往不是从第7讲才开始拉开的，而是在前6讲练习顺带养成的好习惯，到第7讲集中体现出来了。

1.2 题目风格从“练语法”转向“练思维”

前几讲的OJ作业，很多时候是“题目给了明确的输入输出公式，你照着翻译就行”。比如说“输入两个整数，输出它们的和”，这种题写起来没有思考压力，顶多注意一下数据类型。

第7讲作业不一样。题面会出现更多类似这样的表述：

• “请设计一个算法，使程序在最坏情况下也能在限定时间内完成”
• “你可以使用递归或非递归两种方式实现，但必须保证正确性”
• “输入可能包含多组测试数据，请处理到文件结束”

这些话是什么意思？就是老师不再满足于“你能跑出正确答案”，而是希望你开始思考“为什么这个程序是对的”“为什么这个程序够快”。这是从“编码者”向“算法设计者”过渡的一个关键节点。

我经常跟学生打一个比方：前几讲就像学开车，教练告诉你油门刹车在哪，你踩下去车能动就行；第7讲开始是真正上路，你要会判断路况、会变道、会预判，而不是只会踩油门。题目变难不是坏事，它逼着你把大脑里的“语法知识”变成“解决问题的能力”。

2. 三个高频题型提前摸透

2.1 带边界条件的数学模拟题

这类题看起来是数学题，但本质上考的是“模拟”。题目会给你一个规则，让你把整个过程一步步走完，最后输出结果。

最常见的例子是数字反转、进制转换、最大公约数迭代求解、约瑟夫环（Josephus）这类经典问题。以数字反转为例，题目要求把输入的整数倒序输出，比如输入12345输出54321。大多数同学在一分钟内能写出反转逻辑，但真正上了OJ才发现：

• 负数怎么办？比如-123要输出-321还是-123反转后得到-321？
• 末尾是0怎么办？比如1200反转后应该是21还是0021？
• 反转后会不会超出整数范围？比如输入一个接近int上限的数，反转后很可能直接溢出。

这些就是边界条件（edge case）。一个能在OJ上拿满分的程序，不是“大多数情况下正确”，而是在所有合法输入范围内都正确。老师很喜欢在这种看似简单的题里藏几个边界数据，专门用来筛掉那些“看着能跑”的代码。

2.2 需要函数拆分的递归结构题

递归是第7讲的重头戏。几乎可以断定，OJ作业里至少有一道题跟递归相关，最典型的就是汉诺塔（Hanoi Tower）、斐波那契数列、全排列生成这类。

有同学觉得递归难，是因为脑子一时转不过“函数自己调自己”这个弯。我用一个通俗的说法帮大家理解：递归不是你无限循环地调用自己，而是把一个大规模问题，拆成一个“小规模问题”加上“当前这一步”的操作。只要子问题能被同样规则继续拆，最终拆到一个不用再拆的“出口”，整个问题就解决了。

在OJ作业里，递归题的丢分点往往不是“递归思路想不出来”，而是：

• 没有设置或没有写对递归终止条件
• 递归调用时传入的参数没有简化，导致永远无法收敛
• 忽略了递归层数过深导致栈溢出（比如递归百万层）

所以看到“递归”标签的题，你先别急着写函数，先问自己三个问题：什么时候停？当前这一层做什么？传给下一层的参数是什么？把这三个问题想清楚，递归代码基本不会写错。

2.3 算穷举也算搜索的枚举题

有些题就算你一时没有最优解法，也可以靠“暴力”过关。比如数据量小的时候，枚举所有可能情况，逐个判断，照样能在OJ的时限内通过。

枚举题在第7讲作业里出场率也很高，因为老师想让你体验“算法设计”的完整过程：先写一个能解决问题的暴力版本，再考虑能不能优化。例如有几道搜索迷宫路径的题，数据范围小的时候，直接做深度优先搜索（DFS）或广度优先搜索（BFS）就能过。这类题本身不难，但它会检测两件事：第一，你二维数组下标到底会不会用；第二，你访问过的位置有没有标记，会不会死循环。

很多同学第一次写迷宫题，一跑就卡死或者栈溢出，十有八九是没有标记“已访问”。这个问题我在第4节会展开说，这里先提个醒：枚举和搜索类的题目，最重要的不是怎么写循环，而是怎么保证状态不重不漏。

3. 三道代表性问题的拆解全过程

3.1 反转整数：不要被“简单”误导

我先用一个大家最熟的题作为例子，把做题思路完整走一遍。

题面可以这样描述：输入一个整数，输出它的反转结果。例如输入123，输出321；输入-120，输出-21（负数保持符号，忽略反转后前导的零）。

这个题我见到太多版本了。最简单直观的思路是把整数转成字符串，逆序后转回整数。但如果我们想写得既简洁又稳，直接用数学方法更优雅。核心思路是：每次取出原数的最后一位，加到结果上，同时原数除以10。

#include <stdio.h> #include <limits.h> int reverse(int x) { long result = 0; while (x != 0) { result = result * 10 + x % 10; x = x / 10; } return result; } int main() { int n; scanf("%d", &n); printf("%d\n", reverse(n)); return 0; }

为什么这里用long保存result而不是直接用int？因为反转后可能溢出。比如输入接近INT_MAX，反转后极可能超过int能表示的范围。如果题目没明说“输入在int范围内，输出也在int范围内”，你用long是更稳妥的做法。

另外注意负数。C语言的取模运算在x为负数时，x % 10得到的是负数，比如-123 % 10结果是-3，这样所有位数的符号都是负的，最终反转结果也自然带负号，正好符合题意。所以前面代码对负数是天然正确的，不需要单独写if。

这道题告诉我们一个很重要的道理：OJ作业里最简单的题，也值得花3分钟写下来检查。你每多想一个边界，就多一分把握。

3.2 汉诺塔计数：递归调用的本质

汉诺塔问题几乎是算法课的保留节目。题面大概是：有三根柱子A、B、C，初始时A柱上有n个大小不等的圆盘，按上小下大叠放。要求把全部圆盘移到C柱，每次只能移动一个圆盘，且任何时候都不能把大盘放到小盘上面。输出移动过程，或输出最少移动次数。

先说结论：最少移动次数是2^n - 1。这个公式可以直接算，但OJ往往要求你输出具体的移动步骤，比如“A -> C”。所以真正要写的是递归过程本身。

#include <stdio.h> void hanoi(int n, char from, char to, char aux) { if (n == 1) { printf("%c -> %c\n", from, to); return; } hanoi(n - 1, from, aux, to); printf("%c -> %c\n", from, to); hanoi(n - 1, aux, to, from); } int main() { int n; scanf("%d", &n); hanoi(n, 'A', 'C', 'B'); return 0; }

这段代码的核心在于“把n个圆盘从A移到C”这个问题，被拆成了三步：

1. 把上面n-1个圆盘从A移到B（借助C）；
2. 把最下面最大的圆盘从A直接移到C；
3. 把B上的n-1个圆盘从B移到C（借助A）。

每一步都是在做同一件模式的事，只是参数换了。这就是递归的“递归”之处。

我在批改时发现，很多同学写递归时最怕“中间过程想不清楚”，总想在脑子里模拟每一步。我建议你不要去模拟整个调用栈，只要相信“如果n-1的问题能被正确解决，那么n的问题按这个步骤也一定能被正确解决”。这叫递归的“信任”。学会了信任，递归题就过了一半。

但要注意一点：如果题目只是让你输出次数而不是过程，千万别真的去递归算，直接输出2^n - 1就好，不然n稍微大一点，程序就会慢到超时。

3.3 迷宫寻路之最小步数：二维数组加队列

第7讲阶段，如果老师已经讲过最简单的图遍历，那作业里很可能出现一道“从起点走到终点，求最少步数”的题。下面这个例子可以代表一类很常见的作业题。

题面：给定一个n行m列的二维网格，其中0表示可走，1表示障碍。起点在(0,0)，终点在(n-1,m-1)，每一步可以向上、下、左、右四个方向移动，求最少需要多少步能走到终点。如果走不到，输出-1。

这类题最优解是广搜（BFS）而不是深搜（DFS），因为BFS第一次搜到终点时的步数一定是最少的。实现上，用队列逐层扩展状态。

#include <stdio.h> #include <string.h> #define MAXN 105 int grid[MAXN][MAXN]; int dist[MAXN][MAXN]; int dirX[4] = {-1, 1, 0, 0}; int dirY[4] = {0, 0, -1, 1}; int main() { int n, m; scanf("%d%d", &n, &m); for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) scanf("%d", &grid[i][j]); memset(dist, -1, sizeof(dist)); int queue[MAXN * MAXN][2]; int head = 0, tail = 0; dist[0][0] = 0; queue[tail][0] = 0; queue[tail][1] = 0; tail++; while (head < tail) { int x = queue[head][0]; int y = queue[head][1]; head++; if (x == n - 1 && y == m - 1) break; for (int i = 0; i < 4; i++) { int nx = x + dirX[i]; int ny = y + dirY[i]; if (nx >= 0 && nx < n && ny >= 0 && ny < m && grid[nx][ny] == 0 && dist[nx][ny] == -1) { dist[nx][ny] = dist[x][y] + 1; queue[tail][0] = nx; queue[tail][1] = ny; tail++; } } } printf("%d\n", dist[n - 1][m - 1]); return 0; }

我用一维数组模拟队列，当然也可以用C++的queue，原理一样。dist数组初始化为-1，既表示“还没访问过”，又可以在最后直接判断出终点是否可达。如果dist[n-1][m-1]仍为-1，说明走不到，按题意输出-1。

很多第一次写这种题的同学会问：“为什么不用DFS？” 原因是DFS在图上搜索时，找到终点并不保证路径最短。如果你非要用DFS把所有路径都走一遍再比较，那时间复杂度会爆炸。所以在“最少步数”这类问题里，BFS是常识性选择。第7讲作业如果考到搜索，它往往不要求你掌握多么高级的剪枝技巧，但至少要知道：最短路径首选BFS。

4. OJ提交现场的真实事故

4.1 TLE不一定是算法太慢

OJ返回Time Limit Exceeded，字面意思“超时”，但很多情况下跟算法复杂度一点关系都没有。我见过最多的一种情况是：while循环条件写错了，导致程序根本没退出循环。比如用while(scanf("%d", &n))读入多组数据，却没在文件结束时终止，程序就会一直读下去，自然TLE。

还有一种是递归题。前面汉诺塔的例子，如果n比较大，而题目只要求输出次数，你还在傻傻地递归输出每一步，当然超时。这种TLE是“用错了方法”，不是“程序写得慢”，属于能通过思考避免的低级失误。

4.2 Runtime Error背后的数组边界

Runtime Error（运行时错误）是新手最容易慌的错误。它最常见的两个原因：数组越界和除零错误。

数组越界往往不是因为你写了a[100]却访问了a[1000]，而是循环的边界条件差了一个。比如n行m列的矩阵，下标范围是0到n-1和0到m-1，结果写循环时用了for(i=0; i<=n; i++)，多访问了一行，数组越界，运行时就崩了。

排查这类问题，最有效的办法是自查下表：

4.3 Presentation Error：比Wrong Answer更可惜

很多OJ用Presentation Error这个状态表示“你的输出和标准答案几乎一样，但格式不对”。比如多了个空格、少了个换行、结尾多输出了一行空行。这种错误真的很亏——算法全对，只因为输出细节扣分。

解决办法是养成“严格按题面复制输出格式”的习惯。题里说输出两个数之间用空格分隔，就不要自己加逗号；说每个结果占一行，就不要多输出空行。如果你不确定，可以把自己程序的输出和样例输出逐字节对比，装一个能显示不可见字符的编辑器或直接程序比对。

我自己的土办法是：把样例输出保存成文件，再把自己的输出保存成文件，在终端用diff命令比较。这能一眼看出多了哪些看不见的空格。

5. 交作业前必做的查验步骤

5.1 三组数据自查

在点击“Submit”之前，我强烈建议你至少用三组数据做本地测试：

第一组，题面给的样例。它能帮你确认基本逻辑是否跑通。 第二组，边界数据。比如数组长度取最小值1或最大值，数值取0、负数、INT_MAX。这些数据最容易暴露问题。 第三组，自己设计一个稍大数据量的测试。目的是看程序跑起来会不会卡顿，有没有明显的性能问题。

很多同学觉得OJ作业只要“样例通过就行了”，但OJ判定用的测试点远不止样例。样例会通，恰恰因为那是最温和的情况。你主动去试边界，相当于提前把老师可能埋的雷拆掉。

5.2 局部变量和数组大小的常识

用C/C++写OJ题，有一个容易被忽视的点：不要在函数内部开一个特别大的数组。因为函数内的局部变量存储在栈区，栈空间通常只有几MB，你开一个10000x10000的int二维数组，直接就栈溢出了。

解决办法是：全局数组放在静态区，空间限制宽松得多，默认初始化为0，也不需要手动memset清零。另外，用memset或fill时，要注意需要的头文件和参数含义，别把长度参数写成元素个数，结果只清了一半内存，导致后续判断出错。

5.3 复杂度估算方法

最后，交作业前花一分钟估算一下自己程序的时间复杂度。假设OJ时限是1秒，简单估算程序操作数不要超过10^7，尽量控制在10^6到10^7之间。

如果题目输入规模n最大是10^5，你的程序是O(n^2)，那最坏就是10^10次操作，必然超时。这时你需要思考：能不能用O(n log n)或者O(n)的算法？第7讲阶段的OJ题，通常数据范围都算好了，不会故意让你写超难的优化，但要从小养成估算复杂度的习惯。

6. 我踩过几次坑之后的真心体会

说句实话，第7讲这份作业，分数本身并不该是你最在乎的东西。我在实际批改中见过一种很可惜的现象：有人为了追求AC，把题目从网上抄来一段能过的代码，提交上去拿到满分，但后来讲到图、树、动态规划时，这一批人很快跟不上，因为基础没打牢。

我自己当年做类似作业时，最深刻的教训是“不看题就写代码”。有一次自以为是地觉得题目是“反转字符串”，结果审题后发现输入有多组，每组还带长度限制，完全不是我想的那样。老老实实把题读三遍，把输入输出规则用笔画下来，再动手写，这个习惯让我后续少走了很多弯路。

按照Lecture(7)的定位，这次作业是你从“语法入门”迈向“算法思维”的第一道台阶。你会开始体会到“原来同一个问题可以有不同的解法”“原来数据规模会决定你的算法选择”。这些体会，比AC几道题更宝贵。

如果你这次有一两道题没有全过，别灰心，也别急着看答案。先把错误测试点跑出来，想想自己遗漏了什么边界条件，再重新提交。OJ的乐趣和折磨都在同一个地方：它会用你没想到的数据教会你，什么叫“考虑周全”。把这次作业当成一个锤炼思维的机会，你会发现后面那些看起来更难的概念，其实也没那么吓人。