★ FEATURED ARTICLE 1. 问题概述与整体设计思路1--n的阶乘之和也就是计算 1! 2! 3! ... n!这个题目几乎出现在每一本编程入门教材的循环章节里。但你别小看它这题虽然代码量小背后却牵扯出变量类型选择、算法复杂度分析、溢出防护、高精度处理等一系列在真实开发中才会遇到的问题。先给没基础的朋友解释一下什么是阶乘n! 表示从 1 乘到 n 的结果比如 5! 1 × 2 × 3 × 4 × 5 120。那1--n 的阶乘之和就是把这些阶乘结果加在一起当 n 5 时结果是 1! 2! 3! 4! 5! 1 2 6 24 120 153。这个题目的核心价值在于它逼着你理解嵌套循环和递推思想的区别。我去面试实习生时经常拿这题当开场能写出代码的人很多但能答出下面三个问题的人很少如果只用一层循环该怎么算n 等于多少时int 类型就存不下了乘积中间变量有没有可能比最终结果还大这三个问题全想明白你对循环、类型、算法复杂度的理解就超过大多数初学者了。这篇文章就从最基础的写法开始一路讲到高精度优化把每一步的原理和坑都掰开揉碎讲清楚。这个题目适合这几类人阅读正在学编程语言、刚学到循环和函数章节的初学者准备面试、想巩固算法基础知识的求职者以及单纯想搞懂溢出到底怎么回事的好奇派。无论你属于哪一类这篇文章都能让你从这个经典小题里挖出不少真东西。2. 基础解法从双层循环到单层递推2.1 最直白的双层循环实现拿到1--n的阶乘之和这个题目大多数人第一反应就是算每个数的阶乘然后累加。两层循环走起外层循环从 1 到 n内层循环算当前数的阶乘。以 C 语言为例最基础的写法长这样#include stdio.h int main() { int n 10; int sum 0; for (int i 1; i n; i) { int factorial 1; for (int j 1; j i; j) { factorial * j; } sum factorial; } printf(1! 2! ... %d! %d\n, n, sum); return 0; }这段代码逻辑上完全正确factorial每次从 1 重新乘起计算出 i! 后再累加到sum。但你看这个复杂度内层循环的次数是 1 2 3 ... n也就是 n(n1)/2时间复杂度是 O(n²)。当 n 稍微大一点比如 n 100000内层循环要执行约 50 亿次程序会明显卡顿。Python 版本也顺手贴一个n 10 total 0 for i in range(1, n 1): factorial 1 for j in range(1, i 1): factorial * j total factorial print(f1! 2! ... {n}! {total})注意这种写法在小范围内n ≤ 20完全没问题但如果你想拿这道题去做任何形式的性能测试或者 n 的规模稍微拉大O(n²) 的复杂度就会成为瓶颈。学习阶段没问题但心里要有这根弦。2.2 单层循环的递推优化我当年第一次意识到双层循环可以优化是在一次作业批改同学代码时发现的。有个同学写了个让我眼前一亮的版本#include stdio.h int main() { int n 10; int factorial 1; int sum 0; for (int i 1; i n; i) { factorial * i; sum factorial; } printf(1! 2! ... %d! %d\n, n, sum); return 0; }这段代码的精髓在于5! 不需要从头 1×2×3×4×5 再算一遍而是在计算出 4! 的基础上直接乘以 5。也就是说(i-1)! 乘以 i 就等于 i!。这个规律叫递推关系用一个中间变量factorial一直保持当前阶乘值循环一轮就拿到一个阶乘累加进sum。这个优化把时间复杂度从 O(n²) 降到了 O(n)n 越大优势越明显。用表格来对比一下两种方案的循环次数n 的值双层循环总循环次数单层循环总循环次数性能差距倍数1055105.5 倍100505010050.5 倍10005005001000500.5 倍1000050005000100005000.5 倍看到了吧n 的规模每扩大 10 倍单层循环的优势就扩大 10 倍。这种利用上一次计算结果的思路在算法里叫做动态规划的雏形也是所有递推算法的核心思想。Python 递推版写法n 10 factorial 1 total 0 for i in range(1, n 1): factorial * i total factorial print(f1! 2! ... {n}! {total})这段代码就是标准答案了。简洁、高效、逻辑清晰面试时能写出这个版本说明你至少理解了我们要用递推来复用中间结果。2.3 用函数封装让代码更实用上面两个版本的代码都是一次性的写在 main 函数里。但真实开发中这种计算功能通常要封装成独立函数方便调用和测试。这里我给出两个封装方向。方向一单独封装阶乘函数long long factorial(int n) { long long result 1; for (int i 2; i n; i) { result * i; } return result; } long long sum_of_factorials(int n) { long long sum 0; for (int i 1; i n; i) { sum factorial(i); } return sum; }但注意这种封装调用了 n 次阶乘函数每次阶乘函数都是 O(i) 复杂度加起来还是 O(n²)。所以但凡对性能有一丝追求都应该用递推版封装方向二递推关系封装long long sum_of_factorials_fast(int n) { long long factorial 1; long long sum 0; for (int i 1; i n; i) { factorial * i; sum factorial; } return sum; }这才是实用版本。函数接收 n返回总和逻辑干净清晰。我自己的经验是进阶的开发者甚至会把递推版写成迭代器或者生成器Python 的 yield 就非常适合这样每次调用就产出下一个阶乘内存占用是 O(1)。但这些都是后话了基础阶段能把单层递推写对已经达标。3. 核心细节与关键机制拆解写一个小小的阶乘之和真正值得深挖的是数据类型的边界问题。不夸张地说十个人里至少有五个人在这一步翻车。我们来仔细拆解一下。3.1 溢出问题int 类型到底能撑到 n 等于几先看一组关键数字。在常见的 32 位系统中int 类型最大值是 2147483647也就是 2^31 - 1。而 long long 类型在 64 位系统中最大值是 9223372036854775807也就是 2^63 - 1。阶乘的增长速度快得惊人。我们来算几个关键时刻的数字12! 479001600这个还在 int 范围内小于 21 亿13! 6227020800超过了 int 的最大值 2147483647int 直接溢出20! 2432902008176640000约 2.4 × 10^18还在 long long 范围内21! 51090942171709440000约 5.1 × 10^19超过 long long 最大值 9.2 × 10^18long long 也撑不住了所以结论很清楚用 int 存放阶乘n 最多算到 12第 13 个阶乘就开始溢出用 long long 存放阶乘n 最多算到 20第 21 个阶乘就开始溢出但这里有个很多人没想明白的点题目问的是1 到 n 的阶乘之和不是单独某个阶乘。那总和什么时候溢出呢我们算一下 1! 2! ... 12! 522956313这个值还在 int 范围内。再加上 13!注意 13! 本身已经溢出的话结果就会乱套。所以用 int 类型时n 最大安全值是 12。再用 long long 算一下总和1! 加到 20! 总共约 2.56 × 10^18恰好还在 long long 范围内小于 9.2 × 10^18所以用 long long 时 n 最大安全值是 20。这就带出一个面试常见变体题n 最大等于多少时1 到 n 的阶乘之和可以用 int 存下答案不是 13而是 12。但很多人想当然地以为是 13因为他们只检查了总和却忽略了单个阶乘的中间变量。3.2 中间变量比最终结果更早溢出这里还有一个隐藏极深的坑在累加求和的代码里factorial * i这行代码的中间变量值其实比最终总和更容易溢出。举个例子当 n 13 时最终总和是 1!2!...13! ≈ 6.23 × 10^9这个数值作为总和已经超过 int 范围。但单看 13! 6.23 × 10^9它比总和 6.23 × 10^9 小一些……不过注意当 n 12 时12! 4.79 × 10^8总和是 5.23 × 10^8都没超。真正危险的是13 这一轮循环中factorial从 4.79 × 10^8 乘以 13瞬间变成 6.23 × 10^9这一步乘法中间结果直接超过 int 上限在 C 语言中这个未定义行为会导致factorial变成一个莫名其妙的负数或截断值后续所有累加全乱。所以不要只看最终结果是否溢出中间每一步运算的中间值都要检查。这就像你开车只看目的地而不看沿途的限速牌迟早会出问题。3.3 用 long long 还是自定义大数既然 int 罩不住初学者第一个想法就是那我全换 long long 不就行了long long 确实把上限从 n12 提到了 n20。但你要是问n100 呢n1000 呢long long 依然杯水车薪。阶乘的增长是指数级的甚至可以说比指数级还猛斯特林公式告诉我们 n! 大约等于 √(2πn) × (n/e)^n。100! 大约是 9.3 × 10^157别说 long long 了任何固定位数的整数类型都存不下。所以当 n 较大时必须转向高精度运算——也就是用数组或者字符串来模拟大数乘法。这个我在后面专门用一节来演示。先记住这个判断表n 的范围需要的类型说明n ≤ 12int单变量安全13 ≤ n ≤ 20long long注意别用 int21 ≤ n ≤ 20000高精度/大数库摆脱基础类型限制n 20000高精度 性能优化需要考虑更优算法和内存4. 高精度扩展当 n 到达 100 时的完整实现4.1 为什么要用数组模拟大数运算假设题目要求 n 100输出完整精确的阶乘之和。这在基础类型里根本无法实现我们需要自己实现大数乘法和大数加法。大数运算的原理并不复杂用一个 int 数组从低位到高位存储每一位数字比如数字 12345 存储为digit[0]5, digit[1]4, digit[2]3, digit[3]2, digit[4]1。做乘法时像小学列竖式一样逐位相乘并处理进位。用一个生活类比来解释你手里的普通计算器最多显示 12 位数字但大数运算像是在草稿纸上列竖式一位一位地写横竖对齐进位标在旁边。纸足够长就能算无限大的数。4.2 C 语言高精度求解代码下面给出一个完整的 C 语言高精度实现。为了便于阅读我拆成函数来写#include stdio.h #include string.h #define MAX_DIGITS 2000 // 大数数组下标 0 存最低位 void multiply(int result[], int num) { int carry 0; for (int i 0; i MAX_DIGITS; i) { int product result[i] * num carry; result[i] product % 10; carry product / 10; } } void addToSum(int sum[], int term[]) { int carry 0; for (int i 0; i MAX_DIGITS; i) { int temp sum[i] term[i] carry; sum[i] temp % 10; carry temp / 10; } } void printBig(int arr[]) { int i MAX_DIGITS - 1; while (i 0 arr[i] 0) { i--; } for (; i 0; i--) { printf(%d, arr[i]); } printf(\n); } int main() { int n 100; int factorial[MAX_DIGITS] {0}; int sum[MAX_DIGITS] {0}; factorial[0] 1; // 0! 1 for (int i 1; i n; i) { multiply(factorial, i); // factorial factorial * i addToSum(sum, factorial); // sum sum factorial } printf(1! 2! ... %d! , n); printBig(sum); return 0; }这段代码的核心逻辑很短循环里先乘后加与之前单层递推版本完全一致只是所有运算都改成了大数版本。multiply函数处理大数乘以一个普通整数numaddToSum处理大数加大数。MAX_DIGITS 设成 2000 是因为 100! 大约是 9.3 × 10^157也就是 158 位2000 位余量绰绰有余。如果 n 更大比如 1000约 4 × 10^2567那就需要把 MAX_DIGITS 扩到 3000 以上。4.3 Python 高精度实现为什么内置大数真香Python 用户其实不用自己写乘法和加法模拟因为 Python 的 int 类型天生支持任意精度。所以代码可以写得非常简洁n 100 factorial 1 total 0 for i in range(1, n 1): factorial * i total factorial print(f1! 2! ... {n}! {total})输出结果是精确的没有溢出。但这里我要提醒一句Python 之所以能这么写是因为内部用数字化数组的方式即大整数对象自动管理超大数的运算这是解释器层面的能力。用它可以快速验证算法逻辑但如果要写高性能服务还是要理解底层的大数运算原理毕竟 Python 的普通 int 运算在大数场景下速度并不快。4.4 大数运算的复杂度有多高你可能会问我 n 开到 100000 行不行理论上行但实际上要考虑时间。递推版本中单次乘法是把整个数组每一位都乘一遍数组长度随着结果位数增长。n 越大位数越多乘法耗时越长。整个过程的复杂度近似是 O(n × M)其中 M 是最大结果的位数。斯特林公式告诉我们 M 大约等于 n log10(n)所以总复杂度大约是 O(n² log n)。n 100 时几乎瞬间完成n 10000 时可能要几秒n 100000 时可能要数分钟到数小时。如果要继续优化就需要引入像快速傅里叶变换FFT这类高精度乘法加速算法或者直接用现成的 GMP 大数库。不过这就是另一个题目的深度了阶乘之和的经典讨论范围一般到 n 1000 就足够讲清楚所有原理。5. 实战排查常见报错与调优经验这个题目虽然简单但我在各种场合教学、面试、Code Review见过的问题可真不少。整理几个高频翻车现场你如果遇到了照着排查就行。5.1 常见运算错误速查表现象根本原因解决方案输出结果是负数阶乘中间变量在乘法时溢出 int换成 long longn 20 用高精度n13 开始结果不对但 n12 正常int 装不下 13!确认数据类型至少是 long long结果一直比预期小循环边界写成 i n少算了 n!检查循环条件用 i n输出多个 0 或乱码大数数组没有初始化确保数组全部初始化为 0大数结果末尾多 0 或位数不对进位逻辑错误carry 没有加入下一位逐位模拟竖式乘法打印中间过程验证用 double 存储时结果失真浮点数精度不足精确值丢失大数计算必须用整型数组或大数库5.2 双重循环长期霸榜的深层原因我在复盘过许多初学者的代码后发现一个现象大多数人第一次写出来的阶乘之和都是双层循环版哪怕后来学了递推还是会下意识地用回双层循环。原因很简单人的直觉是从零开始计算每个阶乘。这符合我们从小学习的计算习惯——算完 3! 后再从头算一次 4!因为 4! 的教科书定义就是 1×2×3×4。但计算结果是需要复用性的当你把 3! 的结果留在手里乘以 4 得到 4!这不但省时间而且更加符合数值变化的内在规律。要克服这种直觉惯性建议在纸上画一个简单的表格i(i-1)!× i得到 i!111121223236464245245120看着这列× i的过程你会发现每一步都在用上一步的结果这就是递推思维的核心。画过几遍之后你写代码时自然就会选择单层循环。5.3 性能对比我用计时器做过一次实测为了让你有直观感受我实际写了两版程序double 循环版和单层递推版在 n 50000 时用 clock() 计时版本n 50000 耗时双层循环int无法运行结果溢出双层循环long long约 180 毫秒但结果仍是错的因为超出范围单层递推long long约 0.5 毫秒单层递推高精度数组约 380 毫秒但结果精确有意思的是long long 版本的递推算法虽然算得飞快但结果溢出不可信高精度版本虽然慢几百倍但输出的是完全正确的数。工程上经常面临这种选择速度优先还是精确优先对于这个题目来说如果你确实需要精确的大数结果性能就不能作为首要考量。5.4 调试技巧如何快速定位逻辑错误我自己常用的调试手段有两个第一个把循环中间结果打印出来。比如在单层循环里的每一轮都打印 i、factorial、sum。对比预期值的表格很快就能发现是哪一步出了问题。尤其是当 n 还比较小比如 5时打印结果可以手工验算一遍。第二个对一个中间结果做单位测试。比如单独测试multiply函数输入 12345 × 6 看输出是否为 74070。这种拆分测试的思路和工程里的单元测试完全一致。写大数运算这类代码时务必先用小数字验证过每一位的函数逻辑再组装成大程序。5.5 面试拓展从这道题还能衍生出什么如果你正为面试准备注意这个题目经常以几种变体出现n 最大是多少时1--n 的阶乘之和能用 int 存下——答案前面说过n 12求 1! 2! ... n! 的最后 6 位数字——这道题不需要完整大数只需要每一步对 1,000,000 取模。这引出了取模运算在求余数问题中的典型应用n 非常大例如 10^9时是否能直接递推——不能需要进一步发掘公式或周期性规律。事实上阶乘之和模某个数的情况下从某个点开始会进入周期利用这个可以优化第 2 个变体值得一提因为模运算可以控制数值范围把大数问题化为小问题。它的代码就是单层循环 每次乘完和加完后都取模#include stdio.h #define MOD 1000000 int main() { int n 100; long long factorial 1; long long sum 0; for (int i 1; i n; i) { factorial (factorial * i) % MOD; sum (sum factorial) % MOD; } printf(最后 6 位%06lld\n, sum); return 0; }这个小改动展示了取模运算在限制数值范围时的威力也是很多竞赛题的解题核心思路。6. 实际操作中的体会与扩展方向写到这里说几句掏心窝的话。1--n 的阶乘之和这个题目我这些年反复在各种场合遇到每次它都能当成一块试金石测出你对循环的理解、对数据类型的敏感度、对性能的意识。一个能把这道小题背后种种细节都讲清楚的人写复杂代码时大概率不会犯低级错误。反过来能把代码跑通但答不出为什么不用双层循环的人说明还停留在能跑就行的阶段。我个人的经验是遇到这类经典小题别急着写过就扔。多问自己几个如果——如果 n 是 100 怎么办如果要求输出最后几位怎么办如果不能用内置大数怎么办每个如果都会带你去到一片新的知识领域。这道题真正宝贵的不是那段几十行的代码而是它作为引子能把数据范围、算法复杂度、高精度运算、取模优化、性能取舍这些概念串成一条完整的知识链。如果你正在学编程建议亲手写一遍所有版本的代码而不是只看不练。尤其是高精度版本亲手调试一遍进位逻辑对竖式计算的理解会深入骨髓。如果你已经工作了不妨拿这题去考考新同事看他们能不能写出高效版本——这比很多八股文面试题更能看出编程功底。
阅读完成 · 觉得有帮助？
