csp信奥赛c++中的递归和递推研究

csp信奥赛c中的递归和递推研究通过斐波那契数列理解递归与递推题目描述斐波那契数列是指这样的数列数列的第一个和第二个数都为1 11接下来每个数都等于前面2 22个数之和。给出一个正整数a aa要求斐波那契数列中第a aa个数是多少。输入格式第1 11行是测试数据的组数n nn后面跟着n nn行输入。每组测试数据占1 11行包括一个正整数a aa1 ≤ a ≤ 30 1 \le a \le 301≤a≤30。输出格式输出有n nn行每行输出对应一个输入。输出应是一个正整数为斐波那契数列中第a aa个数的大小。输入输出样例 1输入 14 5 2 19 1输出 15 1 4181 1通过本题来深入研究递归和递推的思想斐波那契数列的定义是F(1)1, F(2)1, F(n)F(n-1)F(n-2) (n ≥ 3 n\ge 3n≥3) 。这个定义本身就是递归的——用自身更小的实例来定义自身。而递推则是从已知的基础值出发一步步推出更大的值。下面通过这道题来深入理解两种思想。一、递归递归是一种直接或间接调用自身的函数设计方法。它把一个大型复杂问题层层转化为一个规模较小的同类问题直到达到可以直接求解的“基础情况”递归基。对应代码递归版intfib(inta){if(a1||a2)return1;// 递归基returnfib(a-1)fib(a-2);// 递归调用}执行过程以fib(5)为例递归树fib(5) / \ fib(4) fib(3) / \ / \ fib(3) fib(2) fib(2) fib(1) / \ | | | fib(2) fib(1) 1 1 1 | | 1 1树的说明每个结点代表一次函数调用结点下的两个子结点是它递归调用的两个子问题。叶子结点是递归基fib(1)或fib(2)直接返回 1。从叶子开始向上逐层返回fib(2)1,fib(1)1→fib(3)112→fib(4)fib(3)fib(2)213→fib(5)fib(4)fib(3)325。重复计算问题观察树中fib(3)被计算了2 次分别在fib(5)的左子树和右子树中fib(2)被计算了3 次。当a增大时重复计算的结点数呈指数增长导致总调用次数约为O ( 2 n ) O(2^n)O(2n)。例如a30时调用次数超过 270 万次效率极低。特点思路自然直接翻译数学定义代码简洁易写。缺点明显大量重复计算效率低下且递归深度过大可能导致栈溢出。适用场景问题规模很小或者配合记忆化优化见后文记忆化搜索。二、递推递推是从已知的初始条件出发按照某种规则逐步推导出后续所有结果。它通常使用循环迭代实现是一种自底向上的计算方法。对应代码递推预存储版intf[31];f[1]f[2]1;// 初始条件for(inti3;i30;i){f[i]f[i-1]f[i-2];// 递推公式}// 查询时直接返回 f[a]执行过程计算f[3]到f[5]f[3] f[2] f[1] 11 2 f[4] f[3] f[2] 21 3 f[5] f[4] f[3] 32 5每一步只用前面已经算好的值没有重复计算。特点效率高计算f[n]只需 O(n) 时间查询只需 O(1)若预存。空间可控可以只保留最近两项空间 O(1)也可以预存整个表空间 O(n) 但查询更快。无函数调用开销纯循环实现不会栈溢出。思路要求需要找到“如何从已知推未知”的规则不如递归直观。适用场景问题具有明确的阶段性和递推关系如动态规划、数列计算。需要反复查询不同 n 的结果预存后 O(1) 查询。大规模数据如 n10 6 10^6106甚至更大。三、递归 vs 递推 对比表对比维度递归递推实现方式函数调用自身循环迭代方向自顶向下从大问题分解到小问题自底向上从小问题构建大问题重复计算严重未优化时无时间复杂度指数级O ( 2 n ) O(2^n)O(2n)多项式级O(n)空间复杂度调用栈深度 O(n)通常 O(1) 或 O(n)代码可读性贴近数学定义直观需要设计迭代顺序稍不直观风险栈溢出风险n 大时基本无风险四、本题方法思路本题中a ≤ 30三种方法递归、记忆化搜索、递推都能在时限内通过。纯粹递归虽然能 AC但效率最低仅适合理解定义或极小的 n。递推预存储代码清晰、查询最快适合工程实践。记忆化搜索是递归的优化版保留了递归的直观形式同时消除了重复计算适合那些“不好直接写出递推顺序但容易递归”的问题如图论中的 DAG 记忆化搜索。总结一句话递归是“自己调用自己”分解问题递推是“从已知推未知”迭代求解。递归自然但低效递推高效但需思考顺序。解法一递归思路直接按照斐波那契的数学定义编写递归函数终止条件a 1 || a 2返回 1否则返回fib(a-1) fib(a-2)时间复杂度 O(2 n 2^n2n)空间复杂度 O(n)调用栈深度。代码实现#includebits/stdc.husingnamespacestd;// 递归计算斐波那契数列的第 a 项intfib(inta){if(a1||a2)return1;// 边界returnfib(a-1)fib(a-2);// 递归调用}intmain(){intn,a;cinn;while(n--){cina;coutfib(a)endl;// 直接输出递归结果}return0;}解法二记忆化搜索思路使用一个全局数组memo保存已计算过的值。在fib函数中如果memo[a] ! 0直接返回否则递归计算并存入memo[a]时间复杂度 O(n)空间复杂度 O(n)。对多组测试数据memo复用效率高。代码#includebits/stdc.hconstintMAXN31;intmemo[MAXN];//记忆化数组0表示未计算// 记忆化搜索计算斐波那契数列的第 a 项intfib(inta){if(a1||a2)return1;// 边界if(memo[a]!0)returnmemo[a];// 已计算直接返回memo[a]fib(a-1)fib(a-2);// 计算并保存returnmemo[a];}intmain(){memset(memo,0,sizeof(memo));// 初始化记忆数组intn,a;cinn;while(n--){cina;coutfib(a)endl;}return0;}解法三递推思路提前计算出所有可能用到的斐波那契数因为 a≤30所以计算到 30 即可。用一个全局数组f存储f[1] f[2] 1然后for i 3 to 30: f[i] f[i-1] f[i-2]。函数fib(int a)直接返回f[a]。这样对于每个查询只需 O(1) 时间预处理 O(n)。代码#includebits/stdc.husingnamespacestd;constintMAXN31;intf[MAXN];// 存储斐波那契数列的数组intmain(){// 预处理计算 f[1] 到 f[30]f[1]f[2]1;for(inti3;iMAXN;i){f[i]f[i-1]f[i-2];}intn,a;cinn;while(n--){cina;coutf[a]endl;// O(1) 输出}return0;}三种解法对比总结方法时间复杂度单次查询空间复杂度优点缺点递归O(2 n 2^n2n)O(n)代码极简与数学定义完全一致重复计算极多n30 时调用次数约 270 万次效率低记忆化搜索O(n)O(n)保留递归的直观性避免重复计算可复用中间结果递归深度仍为 nn≤30 安全需要额外数组递推预存储O(1)O(n)查询最快预处理后直接数组访问适合多组查询需要事先知道最大范围本题已知无影响针对本题多组查询a ≤ 30 a \le 30a≤30递推预存储是最优选择查询时间复杂度最低代码也简洁。记忆化搜索在本题也能高效运行且不需要提前预知最大 n但每次查询仍可能触发递归调用。纯递归效率最低。推荐在实际编程中对于固定小范围的多组查询预存储法最佳。各种学习资料助力大家一站式学习和提升#includebits/stdc.husingnamespacestd;intmain(){cout########## 一站式掌握信奥赛知识! ##########;cout############# 冲刺信奥赛拿奖! #############;cout###### 课程购买后永久学习不受限制! ######;return0;}【秘籍汇总】完整csp信奥赛C学习资料1、csp/信奥赛C完整信奥赛系列课程永久学习https://edu.csdn.net/lecturer/7901 点击跳转2、CSP信奥赛C竞赛拿奖视频课https://edu.csdn.net/course/detail/40437 点击跳转https://edu.csdn.net/course/detail/41081 点击跳转3、csp信奥赛高频考点知识详解及案例实践CSP信奥赛C动态规划https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转CSP信奥赛C标准模板库STLhttps://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转信奥赛C提高组csp-s知识详解及案例实践https://blog.csdn.net/weixin_66461496/category_13113932.html 点击跳转4、csp信奥赛冲刺一等奖有效刷题题解CSP信奥赛C初赛及复赛高频考点真题解析持续更新https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转信奥赛C提高组csp-s初赛复赛真题题解持续更新https://blog.csdn.net/weixin_66461496/category_13125089.html 点击跳转5、GESP C考级真题题解GESP(C 一级二级三级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转GESP(C 四级五级六级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转GESP(C 七级八级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_13117178.html 点击跳转· 文末祝福 ·#includebits/stdc.husingnamespacestd;intmain(){cout跟着王老师一起学习信奥赛C;cout 成就更好的自己 ;cout csp信奥赛一等奖属于你! ;return0;}