蓝桥杯2019年省赛这道Fibonacci数列与黄金分割题目编号2311表面看是一道斐波那契数列的送分题给你一个n输出F(n)/F(n1)保留8位小数。可真上了考场你会发现数据范围根本不给你“老老实实算”的机会。我第一次见到这道题时第一反应是写个大数库直接莽结果当然是超时。后来把前几十项比值打出来才意识到这道题考的不是大数而是你有没有发现这个比值在数学上会收敛到黄金分割比例。如果你正好在备赛蓝桥杯或者对算法题里“什么时候可以偷懒”这件事感兴趣这道题非常值得拆开来看。1. 先把题目读懂这题到底在卡什么1.1 原题还原与常规思路原题的要求很简洁定义F(1)F(2)1F(n)F(n-1)F(n-2)输入n求F(n)/F(n1)的值保留8位小数。题目给出的n可以非常大在很多常见版本里达到10^9级别。看到题大多数人的第一反应是递推开一个数组F[1]1F[2]1for一遍把前n1项全部算出来最后输出F[n]/F[n1]。这个思路本身没有错但n10^9时数组需要10^9个long long也就是8GB内存直接爆掉就算优化到只用两个变量滚动更新10^9次循环的计算量在多数OJ上也扛不住更别提递归实现——n稍微大一点就会栈溢出。所以第一步就应该意识到这道题的正解不是“用更强的算力硬算”而是“找出一个可以不硬算的理由”。也有人会想到矩阵快速幂毕竟斐波那契数列的第n项可以用2x2矩阵的n次幂配合快速幂在O(log n)时间内求出来。这个方案能不能做能做但属于“用大炮打蚊子”。因为题目要的是比值不是某一项的精确值而且数据范围大到不合理的程度命题人显然另有意图。我在实际比赛中也见过有选手真的写了矩阵快速幂代码一百多行最后还因为取模和浮点输出的细节浪费了好多时间——不是方案错是方向偏了。1.2 出题人真正希望你发现的数学性质这个“不硬算的理由”就是极限。斐波那契数列有一个非常重要的性质相邻两项的比值F(n)/F(n1)会随着n的增大幅荡收敛到(√5-1)/2大约等于0.6180339887。这个数的几何意义就是黄金分割。换句话说当n足够大之后F(n)/F(n1)和黄金分割之间的差值会小到在输出精度范围内看不出来。题目要求保留8位小数这其实是一个非常强的信号。既然结果只关心小数点后8位而比值已经在无限逼近一个常数那么当n大到某个临界值以后四舍五入的结果就会固定为0.61803399。此时继续往下算没有任何意义——直接输出这个常数即可。这就是这道题最核心的解题思路用极限性质把问题规模压缩到常数级。2. 数学推导与临界点到底算到第几项才算够2.1 比值收敛的严格推导很多文章直接告诉你“斐波那契比值收敛到黄金分割”但为什么这里用递推式就能推出来不需要动用特征方程这种看着吓人的工具。设R(n)F(n1)/F(n)那么题目要求的F(n)/F(n1)其实就是1/R(n)。由递推式F(n1)F(n)F(n-1)两边同时除以F(n)得到R(n) 1 F(n-1)/F(n) 1 1/R(n-1)如果R(n)存在极限r那么对等式两边取极限就有r 1 1/r整理得到r² - r - 1 0解出正根r(1√5)/2≈1.618。于是F(n)/F(n1)1/r(√5-1)/2≈0.6180339887。这个推导同样解释了为什么比值会“震荡”而不是单调逼近因为R(n)和1/R(n-1)之间是倒数的关系奇偶项会分别从两侧靠近极限但差距会越来越小。实际打印前几十项也能直观看到0.6、0.666、0.615、0.619、0.617、0.618这样来回摆动但摆动的幅度在逐渐缩小。2.2 收敛速度与截断点估算知道了会收敛下一步就是确定“从第几项开始可以截断”。这里需要估算误差的大小。相邻项比值与黄金分割的差值和斐波那契通项公式有关粗略来说误差会按φ^(-2n)的级别缩小其中φ≈1.618。也就是说n每增加1误差大约缩小到原来的0.382倍每增加两步误差下降一个数量级。实际列几项就能看到nF(n)F(n1)F(n)/F(n1)1111.000000005580.625000001055890.61797753156109870.61803445206765109460.6180339925750251213930.61803399注意看第20项6765/10946保留8位小数已经得到0.61803399和第25项的结果完全一致。也就是说在8位小数的精度约束下n20就已经达到稳定。代码里为了安全通常把截断边界做成n25再大的n直接输出0.61803399。这不是严谨的数学定理式证明但作为竞赛解法它完全够用因为你可以用程序实测验证。2.3 为什么不直接对黄金分割开根号有人可能会想既然极限是(√5-1)/2那我直接算这个值不就行了也可以但没必要。用sqrt(5)算黄金分割本质上也是在用浮点近似精度同样受限于double。更重要的是题目考的其实是“发现极限并截断”这个思路而不是真的让你去求一个黄金分割常数。我见过有人直接把黄金分割算到8位小数写在代码里然后n比较小时也输出这个值结果在小数据点就挂掉了。因为n1时F(1)/F(2)1.0不是0.618。所以无论如何n较小的时候必须真实计算。3. 代码实现双保险方案与格式细节3.1 稳过的C参考实现这个方案的代码非常短。核心逻辑就是n超过25直接输出常数n不超过25时用迭代算出F(n)和F(n1)再做一次浮点除法。#include cstdio int main() { int n; scanf(%d, n); if (n 25) { printf(0.61803399\n); return 0; } long long a 1, b 1; for (int i 2; i n; i) { long long c a b; a b; b c; } double ans (double)a / b; printf(%.8lf\n, ans); return 0; }这段代码里有几个地方值得说一下。循环从i2开始循环体里干的事是把a更新为F(2)、b更新为F(3)以此类推。当循环结束时aF(n)bF(n1)。如果n1循环一次都不跑a1b1正好是F(1)/F(2)1.0不会错。这个边界处理是这类题的常见坑点务必想清楚。n25时F(25)75025F(26)121393都远小于long long的上限用long long没有任何风险。如果n再大比如93F(93)就已经超过long long范围了但因为我们提前用if截断了完全不需要担心。3.2 Python参考实现Python写起来更短思路一样n int(input()) if n 25: print(0.61803399) exit() a, b 1, 1 for _ in range(2, n 1): a, b b, a b print(f{a / b:.8f})这里Python的a, b b, a b是同时赋值不会出现“a被覆盖后影响b的计算”这种问题算是Python的一个语法糖。n25时a/b得到的浮点数在double精度范围内输出8位小数没有任何问题。3.3 为什么不用矩阵快速幂和高精度我见过很多题解上来就写矩阵快速幂看得人头皮发麻。但冷静想一下矩阵快速幂解决的是“我要精确得到第n项的值”这个问题而本题要的是“一个最多8位小数的比值”。这个需求之间的差距非常大。高精度更不用说。如果老老实实写大数加法把F(10^9)算出来再去做高精度除法时间、代码量、出错概率全部爆炸属于典型的“正确但没必要”。选方案的标准永远是在满足题目精度约束的前提下选最简单的。宁可多花两分钟思考数学性质也不要多花两小时调试大数板子。4. 常见错误与调试实录4.1 错误一递归暴力与数组越界递归实现斐波那契是教学里的经典但在这里是灾难。n50时递归调用次数已经是指数级别跑多久都算不完即使侥幸运行系统栈也可能溢出。滚动数组虽然避免了内存爆炸但10^9次循环仍然是不可接受的。我在调试时试过直接循环到10^9本地跑了十几秒没出结果果断放弃。还有一个隐蔽问题如果用数组存储所有斐波那契项并且n很大数组长度本身就是瓶颈。有些选手把数组开成全局的long long f[1000005]一看n10^9就傻了——数组根本开不出来。这些都是对题目数据范围不敏感造成的。4.2 错误二忽略了n较小时的边界这是最容易丢分的地方。很多人想清楚“比值收敛到黄金分割”之后就直接写printf(0.61803399\n);然后提交发现只过了部分测试点。原因就是n1输出1.00000000、n3输出0.66666667这些和0.61803399完全不是一回事。所以双保险方案不是锦上添花而是必须的小n老老实实算大n才截断。这个临界值通常取20到30之间我习惯取25留出足够的安全余量。4.3 错误三浮点精度的坑double的有效数字大约15到16位算n25的比值绰绰有余。但如果你用的是float有效数字只有7位左右输出8位小数时末尾几位很可能已经出现偏差。这个题精度要求不算苛刻但能避开就避开直接用double不要在临界点上赌运气。另外还要注意printf(%.8lf)中的格式控制符是四舍五入不是截断。有些同学自己写乘10^8再强转int再除以10^8的手动四舍五入很容易在正负数边界或者进位时出错完全没有必要。4.4 错误四格式化输出的细节C里除了printf还可以用cout fixed setprecision(8)但记得包含iomanip头文件并且fixed一定要写——如果不写fixedsetprecision(8)会变成控制有效数字位数而不是小数点后位数输出结果大相径庭。Python里用f{ans:.8f}即可:.8f同样表示小数点后8位。我在本地跑过几次发现一个有意思的现象有些选手在测试n10时正常测试n1e9时也正常唯独n20附近出错多是因为手写四舍五入时边界判断差了一位。建议直接用语言的格式化输出机制不要自己造轮子。4.5 一段自检脚本打印前30项如果你不确定自己的临界值取在哪可以在本地跑一段小脚本把前30项的比值都打印出来a, b 1, 1 for i in range(1, 31): print(i, f{a / b:.8f}) a, b b, a b跑完你会看到从第20项开始输出结果一直停留在0.61803399。这样你就知道截断点选在20以上是安全的。5. 从这道题延伸出去的思维模型5.1 变式如果题目改成保留100位小数怎么办双保险方案之所以能成立是因为8位小数的精度约束给了一个宽松的截断空间。如果某道变式题要求保留100位小数答案就没这么简单了——你可能需要分析收敛速度估算误差到底在哪个n时小于10^(-100)甚至可能需要用高精度浮点库来计算极限值。这个思考过程其实暴露了题目背后的通用逻辑截断点的位置完全取决于精度要求。竞赛里还有一种常见变式不输出比值而是输出F(n)的末几位。这种题的核心就完全不同了需要用矩阵快速幂或者循环节来处理。如果只记住“看到斐波那契就输出黄金分割”遇到这类变式就会翻车。学习一道题更重要的是掌握它背后的判断方法而不是背下一个结论。5.2 通用套路看到“保留k位小数”先想三件事我做题做多了以后总结出一个非常实用的套路。只要题目里出现“保留几位小数”这类字样先问自己三个问题第一这个结果有没有极限或规律如果遇到类似比值收敛、级数求和、迭代逼近这类结构极可能存在一个不用算到底就能拿到的近似值。第二数据范围是否大到必须利用这个规律如果n只有100老老实实算完全没问题如果n是10^9那几乎可以肯定出题人在暗示你找数学性质。第三截断后误差是否满足要求保留8位小数意味着绝对误差只要控制在5×10^(-9)以内就行这是一个相当宽松的条件很多收敛序列很早就达到了这个精度。这三个问题放在这道题里答案分别是有极限、数据范围巨大、误差条件宽松。于是解法水到渠成。换到其他题目比如圆周率近似、根号2逼近、调和级数求和这套思路同样适用。我在实际写题的过程中最大的体会是算法竞赛里很多题并不是在比谁的算力强而是在比谁更能抓住问题的数学本质。这个题目2311的解法把“精确计算”变成“近似截断”把O(n)甚至O(log n)的复杂度变成O(1)靠的就是提前想清楚了“保留8位小数”这句话背后的含义。以后再遇到类似题别急着写循环先盯着数据范围看十秒——很多时候答案就藏在题目给你的精度信号里。
蓝桥杯2019年省赛这道Fibonacci数列与黄金分割题目编号2311表面看是一道斐波那契数列的送分题给你一个n输出F(n)/F(n1)保留8位小数。可真上了考场你会发现数据范围根本不给你“老老实实算”的机会。我第一次见到这道题时第一反应是写个大数库直接莽结果当然是超时。后来把前几十项比值打出来才意识到这道题考的不是大数而是你有没有发现这个比值在数学上会收敛到黄金分割比例。如果你正好在备赛蓝桥杯或者对算法题里“什么时候可以偷懒”这件事感兴趣这道题非常值得拆开来看。1. 先把题目读懂这题到底在卡什么1.1 原题还原与常规思路原题的要求很简洁定义F(1)F(2)1F(n)F(n-1)F(n-2)输入n求F(n)/F(n1)的值保留8位小数。题目给出的n可以非常大在很多常见版本里达到10^9级别。看到题大多数人的第一反应是递推开一个数组F[1]1F[2]1for一遍把前n1项全部算出来最后输出F[n]/F[n1]。这个思路本身没有错但n10^9时数组需要10^9个long long也就是8GB内存直接爆掉就算优化到只用两个变量滚动更新10^9次循环的计算量在多数OJ上也扛不住更别提递归实现——n稍微大一点就会栈溢出。所以第一步就应该意识到这道题的正解不是“用更强的算力硬算”而是“找出一个可以不硬算的理由”。也有人会想到矩阵快速幂毕竟斐波那契数列的第n项可以用2x2矩阵的n次幂配合快速幂在O(log n)时间内求出来。这个方案能不能做能做但属于“用大炮打蚊子”。因为题目要的是比值不是某一项的精确值而且数据范围大到不合理的程度命题人显然另有意图。我在实际比赛中也见过有选手真的写了矩阵快速幂代码一百多行最后还因为取模和浮点输出的细节浪费了好多时间——不是方案错是方向偏了。1.2 出题人真正希望你发现的数学性质这个“不硬算的理由”就是极限。斐波那契数列有一个非常重要的性质相邻两项的比值F(n)/F(n1)会随着n的增大幅荡收敛到(√5-1)/2大约等于0.6180339887。这个数的几何意义就是黄金分割。换句话说当n足够大之后F(n)/F(n1)和黄金分割之间的差值会小到在输出精度范围内看不出来。题目要求保留8位小数这其实是一个非常强的信号。既然结果只关心小数点后8位而比值已经在无限逼近一个常数那么当n大到某个临界值以后四舍五入的结果就会固定为0.61803399。此时继续往下算没有任何意义——直接输出这个常数即可。这就是这道题最核心的解题思路用极限性质把问题规模压缩到常数级。2. 数学推导与临界点到底算到第几项才算够2.1 比值收敛的严格推导很多文章直接告诉你“斐波那契比值收敛到黄金分割”但为什么这里用递推式就能推出来不需要动用特征方程这种看着吓人的工具。设R(n)F(n1)/F(n)那么题目要求的F(n)/F(n1)其实就是1/R(n)。由递推式F(n1)F(n)F(n-1)两边同时除以F(n)得到R(n) 1 F(n-1)/F(n) 1 1/R(n-1)如果R(n)存在极限r那么对等式两边取极限就有r 1 1/r整理得到r² - r - 1 0解出正根r(1√5)/2≈1.618。于是F(n)/F(n1)1/r(√5-1)/2≈0.6180339887。这个推导同样解释了为什么比值会“震荡”而不是单调逼近因为R(n)和1/R(n-1)之间是倒数的关系奇偶项会分别从两侧靠近极限但差距会越来越小。实际打印前几十项也能直观看到0.6、0.666、0.615、0.619、0.617、0.618这样来回摆动但摆动的幅度在逐渐缩小。2.2 收敛速度与截断点估算知道了会收敛下一步就是确定“从第几项开始可以截断”。这里需要估算误差的大小。相邻项比值与黄金分割的差值和斐波那契通项公式有关粗略来说误差会按φ^(-2n)的级别缩小其中φ≈1.618。也就是说n每增加1误差大约缩小到原来的0.382倍每增加两步误差下降一个数量级。实际列几项就能看到nF(n)F(n1)F(n)/F(n1)1111.000000005580.625000001055890.61797753156109870.61803445206765109460.6180339925750251213930.61803399注意看第20项6765/10946保留8位小数已经得到0.61803399和第25项的结果完全一致。也就是说在8位小数的精度约束下n20就已经达到稳定。代码里为了安全通常把截断边界做成n25再大的n直接输出0.61803399。这不是严谨的数学定理式证明但作为竞赛解法它完全够用因为你可以用程序实测验证。2.3 为什么不直接对黄金分割开根号有人可能会想既然极限是(√5-1)/2那我直接算这个值不就行了也可以但没必要。用sqrt(5)算黄金分割本质上也是在用浮点近似精度同样受限于double。更重要的是题目考的其实是“发现极限并截断”这个思路而不是真的让你去求一个黄金分割常数。我见过有人直接把黄金分割算到8位小数写在代码里然后n比较小时也输出这个值结果在小数据点就挂掉了。因为n1时F(1)/F(2)1.0不是0.618。所以无论如何n较小的时候必须真实计算。3. 代码实现双保险方案与格式细节3.1 稳过的C参考实现这个方案的代码非常短。核心逻辑就是n超过25直接输出常数n不超过25时用迭代算出F(n)和F(n1)再做一次浮点除法。#include cstdio int main() { int n; scanf(%d, n); if (n 25) { printf(0.61803399\n); return 0; } long long a 1, b 1; for (int i 2; i n; i) { long long c a b; a b; b c; } double ans (double)a / b; printf(%.8lf\n, ans); return 0; }这段代码里有几个地方值得说一下。循环从i2开始循环体里干的事是把a更新为F(2)、b更新为F(3)以此类推。当循环结束时aF(n)bF(n1)。如果n1循环一次都不跑a1b1正好是F(1)/F(2)1.0不会错。这个边界处理是这类题的常见坑点务必想清楚。n25时F(25)75025F(26)121393都远小于long long的上限用long long没有任何风险。如果n再大比如93F(93)就已经超过long long范围了但因为我们提前用if截断了完全不需要担心。3.2 Python参考实现Python写起来更短思路一样n int(input()) if n 25: print(0.61803399) exit() a, b 1, 1 for _ in range(2, n 1): a, b b, a b print(f{a / b:.8f})这里Python的a, b b, a b是同时赋值不会出现“a被覆盖后影响b的计算”这种问题算是Python的一个语法糖。n25时a/b得到的浮点数在double精度范围内输出8位小数没有任何问题。3.3 为什么不用矩阵快速幂和高精度我见过很多题解上来就写矩阵快速幂看得人头皮发麻。但冷静想一下矩阵快速幂解决的是“我要精确得到第n项的值”这个问题而本题要的是“一个最多8位小数的比值”。这个需求之间的差距非常大。高精度更不用说。如果老老实实写大数加法把F(10^9)算出来再去做高精度除法时间、代码量、出错概率全部爆炸属于典型的“正确但没必要”。选方案的标准永远是在满足题目精度约束的前提下选最简单的。宁可多花两分钟思考数学性质也不要多花两小时调试大数板子。4. 常见错误与调试实录4.1 错误一递归暴力与数组越界递归实现斐波那契是教学里的经典但在这里是灾难。n50时递归调用次数已经是指数级别跑多久都算不完即使侥幸运行系统栈也可能溢出。滚动数组虽然避免了内存爆炸但10^9次循环仍然是不可接受的。我在调试时试过直接循环到10^9本地跑了十几秒没出结果果断放弃。还有一个隐蔽问题如果用数组存储所有斐波那契项并且n很大数组长度本身就是瓶颈。有些选手把数组开成全局的long long f[1000005]一看n10^9就傻了——数组根本开不出来。这些都是对题目数据范围不敏感造成的。4.2 错误二忽略了n较小时的边界这是最容易丢分的地方。很多人想清楚“比值收敛到黄金分割”之后就直接写printf(0.61803399\n);然后提交发现只过了部分测试点。原因就是n1输出1.00000000、n3输出0.66666667这些和0.61803399完全不是一回事。所以双保险方案不是锦上添花而是必须的小n老老实实算大n才截断。这个临界值通常取20到30之间我习惯取25留出足够的安全余量。4.3 错误三浮点精度的坑double的有效数字大约15到16位算n25的比值绰绰有余。但如果你用的是float有效数字只有7位左右输出8位小数时末尾几位很可能已经出现偏差。这个题精度要求不算苛刻但能避开就避开直接用double不要在临界点上赌运气。另外还要注意printf(%.8lf)中的格式控制符是四舍五入不是截断。有些同学自己写乘10^8再强转int再除以10^8的手动四舍五入很容易在正负数边界或者进位时出错完全没有必要。4.4 错误四格式化输出的细节C里除了printf还可以用cout fixed setprecision(8)但记得包含iomanip头文件并且fixed一定要写——如果不写fixedsetprecision(8)会变成控制有效数字位数而不是小数点后位数输出结果大相径庭。Python里用f{ans:.8f}即可:.8f同样表示小数点后8位。我在本地跑过几次发现一个有意思的现象有些选手在测试n10时正常测试n1e9时也正常唯独n20附近出错多是因为手写四舍五入时边界判断差了一位。建议直接用语言的格式化输出机制不要自己造轮子。4.5 一段自检脚本打印前30项如果你不确定自己的临界值取在哪可以在本地跑一段小脚本把前30项的比值都打印出来a, b 1, 1 for i in range(1, 31): print(i, f{a / b:.8f}) a, b b, a b跑完你会看到从第20项开始输出结果一直停留在0.61803399。这样你就知道截断点选在20以上是安全的。5. 从这道题延伸出去的思维模型5.1 变式如果题目改成保留100位小数怎么办双保险方案之所以能成立是因为8位小数的精度约束给了一个宽松的截断空间。如果某道变式题要求保留100位小数答案就没这么简单了——你可能需要分析收敛速度估算误差到底在哪个n时小于10^(-100)甚至可能需要用高精度浮点库来计算极限值。这个思考过程其实暴露了题目背后的通用逻辑截断点的位置完全取决于精度要求。竞赛里还有一种常见变式不输出比值而是输出F(n)的末几位。这种题的核心就完全不同了需要用矩阵快速幂或者循环节来处理。如果只记住“看到斐波那契就输出黄金分割”遇到这类变式就会翻车。学习一道题更重要的是掌握它背后的判断方法而不是背下一个结论。5.2 通用套路看到“保留k位小数”先想三件事我做题做多了以后总结出一个非常实用的套路。只要题目里出现“保留几位小数”这类字样先问自己三个问题第一这个结果有没有极限或规律如果遇到类似比值收敛、级数求和、迭代逼近这类结构极可能存在一个不用算到底就能拿到的近似值。第二数据范围是否大到必须利用这个规律如果n只有100老老实实算完全没问题如果n是10^9那几乎可以肯定出题人在暗示你找数学性质。第三截断后误差是否满足要求保留8位小数意味着绝对误差只要控制在5×10^(-9)以内就行这是一个相当宽松的条件很多收敛序列很早就达到了这个精度。这三个问题放在这道题里答案分别是有极限、数据范围巨大、误差条件宽松。于是解法水到渠成。换到其他题目比如圆周率近似、根号2逼近、调和级数求和这套思路同样适用。我在实际写题的过程中最大的体会是算法竞赛里很多题并不是在比谁的算力强而是在比谁更能抓住问题的数学本质。这个题目2311的解法把“精确计算”变成“近似截断”把O(n)甚至O(log n)的复杂度变成O(1)靠的就是提前想清楚了“保留8位小数”这句话背后的含义。以后再遇到类似题别急着写循环先盯着数据范围看十秒——很多时候答案就藏在题目给你的精度信号里。
