1. 从PTA实战出发聊聊C语言算法学习的那些“坎儿”很多刚开始学C语言的同学一看到“算法”两个字就头疼感觉它像一座大山又抽象又难懂。特别是面对PTA程序设计类实验辅助教学平台上那些题目比如计算组合数、验证哥德巴赫猜想、递归输出整数明明每个单词都认识合在一起就成了“天书”。我刚开始学的时候也这样对着题目发呆半天不知道从哪里下手。其实啊算法没那么神秘。你可以把它想象成做菜的食谱。你要做一道“西红柿炒鸡蛋”算法就是告诉你先打鸡蛋再切西红柿然后热锅下油……每一步的顺序和操作方法就是算法。C语言的核心算法就是解决编程问题的一套标准“烹饪步骤”。PTA上的题目就是给你设定好了要做的“菜名”和“食材”输入数据让你用C语言这把“厨具”按照正确的步骤算法炒出正确的“菜品”输出结果。所以咱们今天不整那些虚头巴脑的理论就紧扣PTA上这几个经典题目像拆解玩具一样把里面的算法核心掰开揉碎了讲。我会结合我当年踩过的坑和总结的技巧让你看到题目就知道该怎么想、怎么写。你会发现一旦掌握了这几个核心套路很多题目都是换汤不换药上手会快很多。2. 函数与递归理解“自己调用自己”的魔法2.1 函数的基石从“计算组合数”说起咱们看PTA里的第一道典型题计算组合数 C(n, m)。题目给的公式看起来有点绕但核心就是那个递推公式C(n, m) C(n-1, m-1) C(n-1, m)并且给了几个特殊情况比如m0时结果为1。很多新手一上来就想用阶乘公式去算但题目明确要求用这个递推关系其实是在引导我们使用递归函数。我先给你写个最直接的递归版本就是题目参考答案的那种int fun(int n, int m) { if (m 0 || n 1 || m n) { return 1; } else { return fun(n - 1, m - 1) fun(n - 1, m); } }这段代码完美体现了递归的思想把大问题分解成结构相同的小问题。计算C(5,2)它会去计算C(4,1)和C(4,2)而C(4,1)又会去计算C(3,0)和C(3,1)……直到触碰到m0或n1或mn这些可以直接得出结果1的“基础情况”然后逐层返回结果。这里有个实战坑点直接这么写在n和m比较大比如接近题目上限20时效率会非常低因为存在大量的重复计算。比如计算fun(20,10)时fun(15,5)这个值可能会被计算成千上万次。这在PTA上可能还能过因为限制了n20但理解这个缺陷很重要。解决方法是使用“记忆化搜索”或直接使用阶乘公式但这就超出本题要求了。我们首先要理解递归这种“自顶向下”的思考方式。2.2 递归的经典应用斐波那契数列与顺序输出整数理解了组合数的递归再看斐波那契数列就轻松多了。题目定义f1f21, fnf(n-1)f(n-2) (n3)。这简直就是为递归量身定做的。int fib(int n) { if (n 1 || n 2) { return 1; } else { return fib(n-1) fib(n-2); } }是不是和组合数的结构很像都是“如果到达基础情况返回确定值否则调用自身解决更小的问题”。同样这个朴素递归也有重复计算的效率问题。我初学时就曾用这个函数去算fib(40)结果程序“卡死”了好一会儿。后来才知道对于这种问题用循环递推往往更高效int fib_iterative(int n) { if (n 2) return 1; int a 1, b 1, c; for (int i 3; i n; i) { c a b; a b; b c; } return b; }这个循环版本只计算n次加法速度快得多。所以递归是一种优美的思想但实际使用时一定要考虑其性能开销。另一个巧妙运用递归的题目是递归实现顺序输出整数。要求把一个整数像12345按位输出成1 2 3 4 5每个数字占一行。如果用循环我们需要先知道这个数有多少位或者用数组把每位存下来再逆序输出有点麻烦。递归提供了一个非常清晰的思路void printdigits(int n) { if (n 10) { // 基础情况只剩一位数 printf(%d\n, n); return; } printdigits(n / 10); // 递归处理“去掉最后一位”的数 printf(%d\n, n % 10); // 最后输出这最后一位 }这个函数的执行过程就像“剥洋葱”。输入12345它先递归调用printdigits(1234)printdigits(123)……直到printdigits(1)此时满足n10打印1并返回。然后回到上一层打印1234%10也就是4再回到上一层打印3……最终顺序是1 2 3 4 5。这种“先深入再返回”的过程是理解递归执行顺序的绝佳例子。3. 数组与循环驾驭数据的“容器”与“流水线”3.1 二维数组与矩阵操作求下三角元素之和离开了函数我们来看看如何操作一批数据。矩阵下三角元素之和这道题就是一个典型的二维数组遍历问题。题目给你一个n*n的矩阵让你求下三角包括主对角线所有元素的和。关键就在于理解“下三角”在二维数组下标中的特征。我们定义一个二维数组a[10][10]行索引是i列索引是j。下三角的元素其列索引j总是小于等于行索引i。换句话说在第i行我们只需要累加从j0到ji的这些元素。int f(int (*p)[10], int n) { int sum 0; for (int i 0; i n; i) { for (int j 0; j i; j) { // 注意这里是 j i sum p[i][j]; } } return sum; }这里函数参数int (*p)[10]是个重点。它不是一个普通的指针而是一个指向长度为10的整型数组的指针。这允许函数接收一个二维数组确切说是数组的首地址并能以p[i][j]的形式正确访问元素。如果写成int *p或者int p[][10]在访问时编译器就无法正确计算元素位置了。这是我当初容易混淆的地方记住传递二维数组列的大小必须指明。3.2 循环与迭代求数列的和循环的另一类经典应用是处理具有迭代关系的数据序列。比如求数列的和数列第一项是n以后每一项都是前一项的平方根求前m项和。这道题思路很直接就是用一个循环重复m次每次把当前项n加到总和sum里然后把n更新为它的平方根sqrt(n)作为下一项。double s(double n, int m) { double sum 0.0; for (int i 0; i m; i) { sum n; n sqrt(n); // 更新为下一项 } return sum; }这里要注意两个细节第一n和sum要用double类型因为平方根运算会产生小数。第二需要包含头文件#include math.h来使用sqrt()函数。这种“循环-累加-更新”的模式在计算数列、级数求和等问题中非常普遍比如计算1 1/2 1/4 1/8 ...这样的等比数列和模式几乎一模一样只是更新规则变成了n n / 2。4. 数学问题与算法优化从暴力到巧思4.1 素数判断与哥德巴赫猜想使用函数验证哥德巴赫猜想这道题综合了函数编写和基础算法优化。题目要求任何一个不小于6的偶数都可以写成两个奇素数之和。我们需要先写一个判断素数的函数isPrime再用它来验证猜想。最朴素的素数判断思路是对于一个数x看它能否被2到x-1之间的任何整数整除。如果能就不是素数。int isPrime_naive(int x) { if (x 1) return 0; // 1不是素数 for (int i 2; i x; i) { if (x % i 0) return 0; } return 1; }但这个效率太低了。我们可以立刻做两个优化第一偶数除了2都不是素数可以先判断。第二实际上只需要检查到sqrt(x)就够了。因为如果x有一个大于sqrt(x)的因子a那么必然有一个小于sqrt(x)的因子bb x / a。所以优化后的版本如下int isPrime(int x) { if (x 1) return 0; if (x 2) return 1; // 2是素数 if (x % 2 0) return 0; // 排除其他偶数 // 只检查奇数因子到 sqrt(x) 为止 for (int i 3; i * i x; i 2) { if (x % i 0) return 0; } return 1; }有了高效的isPrime函数Goldbach函数就简单了从最小的奇素数3开始遍历i如果i和n-i都是素数就找到了解。题目要求输出p最小的解所以我们从小到大遍历找到第一个就break跳出循环。void Goldbach(int n) { for (int i 3; i n; i 2) { // 只遍历奇数 if (isPrime(i) isPrime(n - i)) { printf(%d%d%d, n, i, n - i); break; } } }4.2 阶乘、组合数与数值计算精度另一类常见的数学问题是计算阶乘和组合数。比如求组合数和求算式的和这两题。计算阶乘本身很简单一个循环连乘即可double fact(int n) { double result 1.0; for (int i 1; i n; i) { result * i; } return result; }但这里有个大坑阶乘增长极快20!的结果已经是一个19位数超出了int甚至long long的表示范围20!约为2.43e18刚好在long long上限附近。所以题目建议函数类型用double。用double虽然可能有精度损失但表示范围大对于PTA的测试点通常是够用的。更严谨的做法是使用大整数库但那是后话了。在**求算式的和[1]**这道题里我们不仅要算阶乘还要算一个连乘f(n) n * (n1) * ... * (2n-1)然后计算sum 1/f(1) 1/f(2) ... 1/f(n)。这里f(n)增长比阶乘还快所以也必须用double。写代码时要注意循环边界i从n开始到2n-1结束。double f(int n) { double out 1.0; for (int i n; i 2 * n - 1; i) { out * i; } return out; } // 主函数中求和 double sum 0.0; for (int i 1; i n; i) { sum 1.0 / f(i); // 注意用1.0做除法保证结果是浮点数 }5. 综合应用与细节打磨写出健壮的代码5.1 模拟与逻辑分析“出生年”问题PTA上有些题目更像小型模拟题比如出生年。这道题要求给定出生年份y和一个数字n2、3或4找出从y年开始至少需要多少年x岁才能遇到一个年份4位数不足补零中恰好有n个不同数字。这道题的关键在于如何判断一个4位数中不同数字的个数。一个直观但稍显繁琐的方法是把年份的四个数字拆开到数组里然后两两比较。int count_diff_digits(int year) { int digits[4]; int temp year; // 拆解数字不足4位前面补的0也会被算作0 for (int i 0; i 4; i) { digits[i] temp % 10; temp / 10; } // 计算不同数字的个数 int count 1; // 第一个数字先算一个 // 检查第二个数字是否与第一个不同 if (digits[1] ! digits[0]) count; // 检查第三个数字是否与前两个都不同 if (digits[2] ! digits[0] digits[2] ! digits[1]) count; // 检查第四个数字是否与前三个都不同 if (digits[3] ! digits[0] digits[3] ! digits[1] digits[3] ! digits[2]) count; return count; }主循环就从y年开始逐年检查直到count_diff_digits(i) n为止。这里注意题目要求“不足4位的年份在前面补零”所以我们判断的是4位数年份1就是0001。在拆解数字时year1会被拆成digits {1, 0, 0, 0}正好符合要求。输出时用%04d格式化就能保证输出4位宽度不足补零。5.2 细节决定成败输入输出、格式与边界最后我想强调一些在PTA做题时容易忽略但会导致“答案错误”的细节。第一输入输出格式。PTA是机器判题对格式要求极其严格。比如计算圆柱体的体积这题要求输出Volume 282.743你多一个空格或少一个标点都不行。务必复制题目中的输出样例进行对照。对于浮点数要特别注意保留小数位数用printf(“%.3lf”, volume)来控制。第二变量初始化。在求算式的和题目解析里作者特别注释了“局部变量如果没有初始化默认值是随机值”。这是一个非常重要的好习惯。特别是用于累加的sum、用于计数的count一定要在声明时初始化为0。用于连乘的result一般初始化为1。第三数据类型的选择。这是算法题目的一大核心。看到阶乘、组合数要立刻想到int可能不够用long long或double。看到带小数点的运算比如数列求和、体积计算就用double。同时注意用scanf读取double时用%lf读取float时用%f用printf输出时float和double都用%f或%.xf指定小数位。第四循环边界条件。这是最容易出错的地方之一。在求下三角和的循环里内层循环是j i还是j i这需要根据“下三角是否包含对角线”来定。题目说“下三角元素之和”通常包含主对角线所以是j i。在判断素数的循环里终止条件是i * i x还是i sqrt(x)前者通常更好因为它避免了每次循环都调用sqrt函数。这些细微之处需要结合题目描述和数学定义仔细推敲。把这些核心算法和细节都掌握了再面对PTA上那些形形色色的题目你心里就有了一张“地图”。看到题目先想它属于哪一类问题递归、数组遍历、数学计算、模拟然后套用对应的思维模式注意好数据范围和格式细节代码自然就能流畅地写出来。编程就像搭积木这些题目就是一块块标准的积木零件练熟了以后就能用它们搭建更复杂的程序大厦。