刷OJ基础题刷到一定阶段你会发现很多题目其实都在反复考察同一种能力把数学描述翻译成代码逻辑。东华OJ的第48题《数列1》就是这么一道非常典型的C基础题表面上只是输出某个数列的第n项实际却在考察你对递推思想、数组边界和输入输出格式的掌握程度。这篇文章我就从这道题出发把“数列1”背后的考点、解题方案、代码实现和常见坑位一次讲透给正在刷东华OJ或者准备打基础的初学者一个可以直接照抄的参考。这道题适合谁一是刚学完C语法、想在OJ上找点题目练手的新手二是已经刷了一部分简单题、想系统理解递推数列写法的人。如果你已经能轻松拿下这类题这篇文章也可以当作一个查漏补缺的速查手册——尤其是后面讲到的边界条件和溢出问题很多人写代码时没注意等到提交报错才回头排查。1. 题目到底在考什么先别急着写代码1.1 “数列1”这类题的真实面目东华OJ的基础题里凡是叫“数列1”“数列2”“数列3”的基本都是同一个套路给你一个递推关系让你输出第n项。有的题目直接写明f(1)1f(2)1f(n)f(n-1)f(n-2)这其实就是斐波那契数列有的会把初始项改一改比如f(1)1f(2)2f(n)f(n-1)2*f(n-2)之类但你仔细一看本质还是“当前项由前几项推导出来”的递推结构。我个人的习惯是拿到题目后先不急着写代码而是把题目里的数学关系抄在草稿纸上写成纯数学的递推公式。这一步看起来多余但对理清思路特别有帮助。比如题目如果写成“给定正整数n输出数列的第n项”你就要先确认三点第一数列的第一项是从1开始还是从0开始第二递推公式里依赖的是前一项还是前两项第三n的取值范围有多大会不会超出int类型能表示的极限。很多初学者栽跟头不是不会写代码而是没有把题目条件读透最后在边界case上报错。比如题目要求n1时输出什么n2时又输出什么这些特殊值如果没处理数组下标就可能变成负数程序直接崩溃。1.2 为什么这类题被归为“基础题”“基础题”三个字听着简单但它的分量并不低。东华OJ把《数列1》放进基础题序列目的很明确检验你对数组、循环、函数这几块基础语法的掌握程度同时让你提前接触“递推”这个在后续算法题里反复出现的核心思想。递推思想有多重要后面的动态规划、状态转移方程本质上都是递推的升级版。你在基础题里把f(n)f(n-1)f(n-2)这种关系写顺了以后遇到二维数组递推、带条件的状态转移思路迁移就很快。所以刷这道题的时候别只满足于“能过”我建议你多想想为什么用数组存中间结果为什么不能用递归如果n变成100000这个代码还跑得动吗带着这些问题去写代码一道基础题就能吃出三四道题的收获。2. 解题思路与方案选型2.1 第一种思路递归看起来最直观但不是最优看到f(n)f(n-1)f(n-2)这种递推式很多人第一反应是写递归int fib(int n) { if (n 1 || n 2) return 1; return fib(n - 1) fib(n - 2); }这段代码逻辑上没错在n比较小的时候也能跑出正确答案但这恰恰是这道题最容易埋坑的地方。递归版的时间复杂度是O(2^n)n稍微大一点比如n40程序就会明显卡顿n到了45以上基本就跑不动了。原因很简单递归会反复计算大量重复的子问题fib(5)被算了不知道多少遍。我在实际刷题中就遇到过这种情况本地测试输出了一个数还觉得挺快结果放到OJ上直接超时。所以递归虽然“看起来最像递推公式”但它绝不是这道题的最佳解法。除非题目明确要求用递归实现否则我不建议你在OJ题里用它尤其是涉及多次查询的题目递归的重复计算问题会被瞬间放大。2.2 第二种思路递推数组最推荐既然递归会重复计算那就把算过的结果存下来。这就是递推数组的做法核心思想是“从前往后推”int f[50]; f[1] 1; f[2] 1; for (int i 3; i n; i) { f[i] f[i - 1] f[i - 2]; } cout f[n] endl;这段代码的时间复杂度是O(n)空间复杂度是O(n)已经可以轻松应对n在几千甚至几万范围内的题目。为什么会快因为每个f[i]只被计算一次算完之后存进数组后面要用的时候直接取不用再递归回去算一遍。为什么数组大小要开50而不是刚好开到n因为OJ题里n的最大值往往不会明说你也不敢赌它一定很小。多开一点空间没有任何代价但开小了就可能导致数组越界所以在基础题里养成“数组稍放宽”的习惯非常值当。实际操作中如果输入范围明确说n40或n45int型数组就够用如果n可能超过46建议直接用long long因为斐波那契数列在第47项左右就会超过int范围。2.3 第三种思路滚动变量省空间版如果更进一步其实你会发现算f[n]的时候不需要整个数组只需要保留前两项就行。这就是滚动变量的思路int a 1, b 1, c; if (n 1 || n 2) cout 1 endl; else { for (int i 3; i n; i) { c a b; a b; b c; } cout b endl; }这种写法的空间复杂度降到了O(1)在n很大的时候依然很快。它的原理是每次循环只需要知道前两项的值算完新的值之后旧值就没用了可以被覆盖。这个思路有点像排队打饭——你只需要知道前面两个人的位置不需要记住整条队伍所有人的位置。不过对于东华OJ这道基础题数组递推版已经绰绰有余了滚动变量属于锦上添花。我建议新手先把数组递推写熟练再尝试滚动变量优化这样对“状态转移”的理解会更扎实。3. C代码实现与关键细节3.1 完整代码数组递推版说了这么多思路直接上代码。这是我最常用的写法简洁、清晰、不容易出错#include iostream using namespace std; int main() { int n; cin n; long long f[55] {0}; f[1] 1; f[2] 1; for (int i 3; i n; i) { f[i] f[i - 1] f[i - 2]; } cout f[n] endl; return 0; }几个细节我展开说一下。首先数组f我直接开成55这个大小应付n在1到50之间的数据绰绰有余。其次我用long long而不是int虽然基础题里n通常不大但long long能覆盖的情况更多也省得以后在数据范围上栽跟头。再就是f数组初始化成0这样即使某次输入了非法值程序也不会读到完全不可预测的垃圾数据。如果你不确定题目是“输出第n项”还是“输出前n项”要注意区分。第n项就是上面的写法输出前n项只需要在循环结束后把f[1]到f[n]全部打印一遍。东华OJ的这道“数列1”据我做题的经验多数版本是输出第n项但你在考场或OJ上遇到类似题时务必读清楚output部分到底写的是什么别想当然。3.2 输入输出与边界处理边界处理是基础题里最容易丢分的地方。以这个数列为例n1和n2是特殊情况因为递推公式f(n)f(n-1)f(n-2)在n为1和2的时候并不适用。上面的代码通过预先给f[1]和f[2]赋值来绕过这个问题循环从3开始这样n1或n2时就直接输出预置值不会出错。还有一种边界情况是n等于0。如果题目范围里出现了n0你的代码就必须处理。常见的做法是判断一下如果n0就直接输出0并结束否则再走递推。虽然东华OJ这道题多半不会给你n0但养成“逢输入必考虑边界”的习惯绝对不亏。输出格式上也要留意。OJ的判题系统通常对空白字符不敏感行尾有没有多余空格、最后有没有换行一般都能过。但千万别在每行末尾多打一个空格——有些题目的Special Judge会容忍但有些不会。最稳妥的方案就是一条输出语句输出完直接换行不多不少。3.3 关于循环写法的一个容易踩坑的点我见过不少初学者把循环写成这样for (int i 3; i n; i) { f[i] f[i - 1] f[i - 2]; }看着没问题但如果n1或者n2循环一次都不会执行直接输出f[n]结果正好是1也算歪打正着。真正容易出问题的写法是循环从1开始for (int i 1; i n; i) { f[i] f[i - 1] f[i - 2]; }f[1]和f[2]就会被莫名覆盖f[0]和f[-1]直指垃圾值程序直接崩。为什么会出现这种低级错误本质上是“推着推着就忘了自己已经初始化过了”。所以我的建议是初始化和递推循环的职责分开初始化就是给f[1]、f[2]赋值循环只负责“从3开始一直推到n”代码读起来一眼就能看出逻辑。调试这个阶段的时候可以利用cout打印中间结果比如在循环里每次算完f[i]都输出一行观察数列是否符合预期。确认无误后再把这行打印代码删掉或注释掉。这个调试思路对任何OJ题都通用毕竟本地能看见的过程越多定位问题就越快。4. 常见问题与排查技巧4.1 数组越界问题数组越界是这类题里最典型的运行时错误表现就是提交后返回Runtime Error但本地可能一切正常。为什么本地正常因为数组越界读取的往往是相邻内存里的旧值有时候碰巧是你想要的值有时候不是属于典型的“薛定谔的bug”。要避免越界核心原则只有一条永远保证循环里的下标范围在数组定义范围内。比如数组开的f[55]你最多只能访问f[0]到f[54]循环条件就必须让i的上限不超过54。如果n可能到60数组就开65可能到100就开105。宁大勿小这是基础题的护身符。还要注意一个隐藏越界当n特别大比如n1000000时f数组里存的值早就超了long long的范围虽然下标不越界但数据溢出的问题又出来了。这种情况就得考虑取模输出题目如果说“结果对1000000007取模”你在每次加法运算后就做一次取模。4.2 整数溢出问题斐波那契数列增长非常快f(47)就已经超过20亿超出int的表示范围f(90)左右就超出unsigned long long。所以写这类递推题之前一定先看一眼题目给的数据范围。如果n在40以内int够用n在90以内long long够用n更大要么用高精度要么题目会要求取模。我自己的经验是递推题里涉及到加乘运算的默认用long long只有确认数据范围很小才退回int。为什么因为OJ题的数据范围往往写得很模糊而且你做对了也看不到测试数据不如从源头上把类型放宽。有的同学担心long long比int慢消耗内存多实际上在基础题这个体量下完全不用担心现代的评测机处理这点数据量都是毫秒级的。如果题目要求结果取模注意模运算和递推运算的混用。常规写法是f[i] (f[i - 1] f[i - 2]) % MOD;一定先相加再取模不要让中间的临时值超过数据类型上限。如果你用的是intf[i-1]f[i-2]就可能先溢出再取模结果就不对了。4.3 提交结果与本地不一致很多刚接触OJ的同学都会遇到“本地运行正确提交却Wrong Answer”的诡异情况。排除代码本身的逻辑错误最常见的原因是题目可能有多组测试输入你的程序只处理了一组。东华OJ的基础题不少是单组输入的但也有多组输入的情况。判断方法很简单看题目描述里是否出现“多组测试”“EOF结束”之类的字眼。如果是多组输入要用while循环读常见写法是while (cin n) { // 处理每一组数据 }注意这段代码的位置数组定义、初始化和递推计算都要放在while循环内部否则第二组数据进来时f数组里存的还是上一组的老数据直接污染计算结果。这一点非常关键我见过很多人在多组输入的问题上出错就是因为f数组只初始化了一次。4.4 常见问题速查表症状可能的根因解决方案Runtime Error数组下标越界比如f[-1]或f[n5]扩大数组容量检查循环边界Wrong Answer多组输入只处理了一组或初始化位置不对使用while(cinn)把init和计算放进循环Time Limit Exceeded递归写法导致重复计算改用数组递推或滚动变量结果异常大/负数int溢出换成long long必要时取模本地正确OJ错误输入输出格式不符仔细核对题目输出样例检查多余空格和换行n1/2时输出错边界情况没处理先给f[1]、f[2]初始化为1循环从3开始这张表是基础题通用排查思路不止适用于《数列1》任何递推类题目都能照着走一遍。5. 同类型题目扩展与举一反三5.1 变式输出前n项有的数列题不让你只输出第n项而是要求输出前n项每项之间用空格隔开。这种变式特别适合用来检验你是不是真的理解了数组存中间结果的意义。核心代码几乎不用改只要在递推完成后加一个输出循环for (int i 1; i n; i) { if (i 1) cout ; cout f[i]; } cout endl;注意输出格式里每行末尾不能有多余空格。什么时候会因为这个挂掉有些OJ的判题很严格对比字符串时连空格差异都算错。你可以在输出每一项之前判断一下当前是不是第一项不是第一项就先输出一个空格这样最后一个元素后面不会多出空格。5.2 变式从第0项开始有些数列题会把f(0)定义为0f(1)定义为1然后让你输出f(n)。这种情况代码的边界条件和前面就完全不同了。你得先把f[0]0、f[1]1指定好再让循环从2开始推。实战中我经常被这种“下标平移”坑到所以现在做题的第一步就是确认第一个有效项到底是第0项还是第1项然后立刻对应着改数组初始化代码。处理这种变式的技巧是不管下标从0开始还是从1开始统一把数组多开几个空间并做一个“空一位”的操作也就是f[0]不用或者留作0循环从第一个需要递推的位置开始。这样即使题目换个方式描述代码也不容易翻车。5.3 变式取模输出“对1000000007取模”这类条件在算法题里非常常见。乍一看只是多了个取模操作实际上对思维的转变还是挺大的——因为取模之后你不能再凭直觉判断“这个数是不是太大了”所有中间结果都被压缩在模数的范围内。实现上要注意每一步加法都取模而不是等最后结果算完再取模。为什么因为中间结果可能早就溢出了最后取模已经来不及。写成f[i] (f[i-1] f[i-2]) % MOD是安全的写法这也是我在上一节强调过的点。5.4 从“数列1”到“动态规划思维”如果你把这道题往深了想一层就会发现递推数组和动态规划其实是一家人。动态规划的状态转移方程本质上就是你写在循环里的那行“f[i] f[i-1] f[i-2]”。只不过动态规划的状态定义更复杂、转移条件更多样。我的建议是刷完这道《数列1》之后可以马上去找几道同类的递推题目巩固比如爬楼梯问题、不同路径问题。你会发现它们的套路几乎一样定义状态、确定初始值、写出递推式、遍历填充。这套四步法用熟了以后的算法学习会顺很多。6. 这道题值得多刷几遍的原因很多人觉得基础题一遍过了就完事其实换个思路再写一遍收获完全不同。第一遍用数组递推第二遍改成滚动变量第三遍再想想能不能用矩阵快速幂虽然这道题用不上这种“一题多解”的刷法比闷头刷十道新题更有利于内化能力。我个人在实际操作中还有一个小习惯把每道题的n1、n2、n3这几个小数据用手算一遍再跟程序跑出来的结果对一下。如果没有问题基本就是稳的。这个习惯帮我避免了很多次因为边界条件导致的返工也让我在OJ上提交时更有底气。最后再分享一个小技巧代码里多用有意义的变量名别偷懒写a、b、c这种。这道题可能很简单但如果你养成了写注释、理清变量含义的习惯等到刷更复杂的题目时debug的效率会高出不少。希望这篇关于东华OJ第48题《数列1》的拆解能帮你少踩几个坑把递推这个基础真正吃透。