这几道题放在一起其实是有讲究的。先把结论放在前面Day1 我做了三道题——最大公约数GCD、素数判断、结构体排序。题目本身不难网上随便一搜全是答案但我写完一遍之后发现真正值钱的不是“会做”而是“为什么这么做”“边界在哪”“错了怎么查”。这篇帖子就把这三道题从审题到实现再到踩坑完整拆开讲一遍。如果你是刚开算法课的学弟学妹或者正在补算法基础这篇可以帮你少走不少弯路。1. 三道题背后藏着同一个核心循环与边界很多人觉得 Day1 的题“太简单了没什么好总结的”。但我自己的感受恰恰相反——这三道题恰好覆盖了算法入门阶段最核心的三个能力维度数学模型的抽象、循环边界的控制、对语言自带能力的掌握。这三样东西基本决定了你后续学二分、学排序、学搜索时能不能顺利落地。1.1 为什么 Day1 偏偏是这三道题第一题是最大公约数表面上考“辗转相除法”实际上考的是“能不能从问题描述里提炼出递归式或循环式”。第二题是素数判断考的是“循环到底该到哪停”——很多人第一次写都是i n一看就知道没过脑子。第三题是结构体排序表面上考排序其实是考“你会不会用现成的排序工具”以及“自定义比较器怎么写才不出错”。也就是说这三题分别对应数学抽象能力GCD 的欧几里得算法边界控制能力sqrt 边界、奇偶判断工具使用能力qsort 或 sort 的自定义比较器。这三点是后面所有算法题的底层基础设施。哪怕你之后学 KMP、学 Dijkstra、学动态规划最终拼的仍然是“抽象模型 边界处理 代码落地”这三板斧。所以 Day1 这三道题其实是一个“地基检测仪”。1.2 我用到的套路清单在正式写代码之前我习惯先做一遍“套路检查”这题能不能用数学结论简化循环的上下界是什么边界情形n1、n2、数组空有没有覆盖如果是排序题系统库函数能不能直接用这个习惯帮我节省了大量调试时间。下面每一道题我都会先写“审题思考”再给最终代码最后补一段“我当时在这里踩过的坑”。这样你看到的不只是答案而是一个完整的做题路径。2. 第一道题最大公约数与最小公倍数2.1 审题与常规思路题目描述大概是这样输入两个正整数 a 和 b输出它们的最大公约数和最小公倍数。拿到题之后我的第一反应是“这题我初中就会”——用短除法嘛。但真要用代码实现短除法反而有点绕。实际上计算机领域求 GCD 有一套标准解法就是欧几里得算法也叫辗转相除法。它的核心只有一句话gcd(a, b) gcd(b, a % b)当 b 等于 0 时gcd(a, 0) a。这句话背后的原理是a 和 b 的公约数必然也是 b 和 a % b 的公约数。因为 a q * b rq 是商r 是余数如果某个数 d 能同时整除 a 和 b那么它一定能整除 r a - q * b。反过来也一样。所以问题规模不断缩小但公约数集合不变一直缩到余数为 0剩下的那个数就是最大公约数。这个算法不仅好写而且效率极高时间复杂度是 O(log min(a, b))。哪怕 a 和 b 都是 10 的 18 次方量级也只需要几十次取模运算就能出结果。相比之下短除法如果被翻译成“枚举所有可能的因子”时间复杂度是 O(sqrt(n))一旦数字大了就会非常吃力。2.2 辗转相除法的完整实现我用 C 语言写的因为大一课程通常要求先用 C 把逻辑搞明白之后再迁移到 C 或 Java。代码如下#include stdio.h int gcd(int a, int b) { while (b ! 0) { int temp b; b a % b; a temp; } return a; } int lcm(int a, int b) { return a / gcd(a, b) * b; } int main() { int a, b; scanf(%d %d, a, b); printf(%d %d\n, gcd(a, b), lcm(a, b)); return 0; }注意第三行到第六行的循环体千万不要直接写成a b; b a % b;因为第二步用到的a % b里的a已经被覆盖了。必须先存临时变量。这个顺序问题我第一次写的时候就栽了后面会细说。2.3 最小公倍数的一个经典坑最小公倍数很多人直接写a * b / gcd(a, b)表面看没问题。但我建议写成a / gcd(a, b) * b也就是先除再乘。原因很简单如果 a 和 b 都很大比如 a 1000000000b 1000000000那么 a * b 就是 10 的 18 次方如果用 32 位整数int存储直接溢出变成负数答案自然就错了。但如果你先算a / gcd(a, b)这个值一定不超过 a再乘 b 也能控制在合理范围内因为 a/gcd 和 b 是互质的结果就是最小公倍数不会超过 a*b。用 64 位整数long long自然能缓解这个问题但从一开始就养成“先除后乘”的习惯能省掉很多边界问题的排查时间。2.4 边界测试与心得写完代码我习惯立刻做几个边界测试输入“1 1”输出应该是 1 1输入“2 3”输出应该是 1 6输入“100 1000”输出应该是 100 1000再试一个“12 18”输出应该是 6 36。这四个用例全部通过之后我才会提交。我的个人体会算法题第一次写对不算本事难的是每次都形成一套固定的验证路径。就像写作文要检查标点符号一样写算法题要检查边界。后面做的题多了你会发现大量 bug 都藏在“数组长度为 1”“数字为 0”“输入为最大值”这些边角料里。3. 第二道题素数判断3.1 最直接的判断逻辑第二题要求判断一个正整数是不是素数。素数的定义是大于 1且除了 1 和它本身之外没有其他因子。新手通常会这么写#include stdio.h int isPrime(int n) { if (n 1) return 0; for (int i 2; i n; i) { if (n % i 0) return 0; } return 1; }这个写法逻辑上没问题但效率很差。假设 n 1000000循环要跑 999998 次如果题目给 1000 个这样的数字总运算量就是 10 亿级别直接超时。所以必须优化。3.2 优化1循环只到 sqrt(n)关键观察是如果 n 有因子 d那么 n/d 也是 n 的因子。d 和 n/d 中一定有一个不超过 sqrt(n)。因此只要在 [2, sqrt(n)] 范围内没有因子n 后面也不会再有因子。于是循环从i n变成i * i n注意这里用的是i * i避免调用 sqrt 函数导致浮点数误差。这个优化把时间复杂度从 O(n) 降到了 O(sqrt(n))。int isPrime(int n) { if (n 1) return 0; for (int i 2; i * i n; i) { if (n % i 0) return 0; } return 1; }这个版本已经够应对绝大多数入门题了。但如果你追求极致性能还可以继续优化。3.3 优化2先筛偶数因为除了 2 以外所有偶数都不是素数。所以可以先排除 n 是偶数的情况然后循环步长从 1 变成 2只检查奇数因子。代码如下int isPrime(int n) { if (n 1) return 0; if (n 2) return 1; if (n % 2 0) return 0; for (int i 3; i * i n; i 2) { if (n % i 0) return 0; } return 1; }这样循环次数又少了一半。不过说实话对于 Day1 的作业题优化到 sqrt(n) 已经够用了但知道有这一步能让你在面对“判断 10 的 12 次方级别的大数”时心里有底。3.4 为什么判断“1”必须单独处理我当时第一次提交没过就是因为没处理 n 1。题目如果没说 n 的范围1 是必然要测的边界。1 不是素数因为素数定义要求大于 1。所以if (n 1) return 0;这句话必须写而且写在最前面。类似的边界还有 n 2 和 n 3。n 2 是素数n 3 是素数。我的代码里已经通过n 2返回 1 来覆盖 2而 3 会进入循环但3 * 3 3循环直接不执行返回 1。这两个值一定要在本地测一遍。4. 第三道题给结构体排序4.1 题目要求与难点第三题长这样输入 n 个学生的信息每个学生有学号、姓名、成绩要求按成绩从高到低排序如果成绩相同则按学号从小到大排。这个题单独看排序本身不难难的是“多关键字比较”和“怎么把比较规则写对”。很多同学在这种题上会手写冒泡排序这当然也能过但没必要——C 标准库自带 qsortC 自带 sort直接用就好。把时间省下来去理解比较逻辑才是正事。4.2 用 qsort 而不是手写冒泡先看 qsort 的函数原型void qsort(void *base, size_t nmemb, size_t size, int (*compar)(const void *, const void *));四个参数分别是数组首地址、元素个数、单个元素大小、比较函数指针。重点在 compar 函数。它返回负数表示第一个参数排前面返回正数表示第二个参数排前面返回 0 表示相等。返回值用“第一个减第二个”还是“第二个减第一个”决定了升序还是降序。这是最容易搞混的地方我的记忆方法是“升序”return(int)a -(int)b“降序”return(int)b -(int)a。相当于比较器把两个元素“拉出来比大小”a 大就往后升序b 大就往前降序。4.3 比较器函数的写法针对这道多关键字排序题比较器可以这样写#include stdio.h #include stdlib.h #include string.h typedef struct { int id; char name[50]; int score; } Student; int cmp(const void *a, const void *b) { Student *s1 (Student *)a; Student *s2 (Student *)b; if (s1-score ! s2-score) { return s2-score - s1-score; // 成绩降序 } return s1-id - s2-id; // 学号升序 } int main() { int n; scanf(%d, n); Student arr[1005]; for (int i 0; i n; i) { scanf(%d %s %d, arr[i].id, arr[i].name, arr[i].score); } qsort(arr, n, sizeof(Student), cmp); for (int i 0; i n; i) { printf(%d %s %d\n, arr[i].id, arr[i].name, arr[i].score); } return 0; }这里有两个细节。第一比较器参数是const void *必须先强转回Student *否则不能访问结构体成员。第二成绩相同时必须返回按学号升序的比较结果这样才能保证“成绩相同按学号排”。4.4 扩展如果成绩和学号都相同呢可能有同学会问如果学号也相同怎么办理论上学号是唯一的不该重复。但为了稳妥你可以在比较器里再加一层判断比如按姓名字典序排。这在实际工程中很常见——多关键字排序就是一层一层比较下去直到有字段能分出先后。另外qsort 的底层是快速排序平均时间复杂度 O(n log n)。多数情况下这是最优泛用选择。如果你用的是 C直接用 sort 更顺手比较器写法类似但不用强转 void 指针类型安全更好。这一步算是把“排序”从“会写冒泡”升级到“会用系统工具 自定义规则”对后面学 STL、学 Python sort 的 key 函数都非常有帮助。5. 当天提交时踩过的三个坑这一节单独拎出来是因为我觉得比题目本身更值得记住。三道题我前前后后提交了八次有三次是因为低级错误被罚时写下来给大家提个醒。5.1 坑点一scanf 格式串写错我第一次做结构体排序题时把scanf(%d %s %d, arr[i].id, arr[i].name, arr[i].score);写成了scanf(%d %s %s, ...)导致第三个参数读到了一个乱七八糟的值。当时还很困惑为什么成绩打印出来是负数。后来逐行检查才发现格式串和参数没对齐。这个错误非常经典。C 语言不像 Python 那样会自动识别类型格式串写错就是内存错乱而且编译器不会报错。我的经验是每次写完 scanf立刻回头数一遍“有几个转换说明就对应几个取地址或数组名参数”。5.2 坑点二比较器返回值越界另一个容易忽略的问题是s2-score - s1-score可能溢出。如果 score 是 int两个极端值相减可能超过 int 范围。虽然在这个题里成绩一般是 0 到 100不会有问题但万一字段是很大的数建议用更稳妥的写法if (s1-score s2-score) return -1; if (s1-score s2-score) return 1; return 0;这种写法的好处是语义清晰绝对不会溢出也方便扩展多关键字。我在后来的工程代码里几乎都是用这种结构而不是直接相减。5.3 坑点三变量命名太随意导致逻辑混乱我当时给 GCD 函数里的变量起名叫t给取模结果起名叫r结果临时代码一多自己都分不清谁是旧值谁是新值。后来我强制自己用完整单词做变量名比如temp、remainder、next读起来舒服很多。这看起来像风格问题但在调试时真的很要命。算法题打到一半乱了思路大多数时候不是思路错了而是代码里的变量名在误导你。保持命名清晰是在给未来的自己省时间。5.4 三次踩坑后的自检清单经过这几轮罚时我给自己定了一个提交前自检清单输入格式串和参数是否一一对应所有除法运算是否可能除零所有数组访问是否可能越界循环终止条件是否覆盖了最小/最大边界比较器返回值的符号是否和题目要求一致是否用了 long long 替代 int 以避免溢出本地是否测过最简单和最极端的样例。这套清单后来陪我过了很多次算法作业和比赛比任何“技巧”都管用。如果你做作业也总是稀里糊涂被罚时强烈建议建一个自己的清单。6. 一些额外想对新手的建议如果这三道题你已经能顺利写出来那我建议你趁热打铁把几个衍生问题也想一想会让收获翻倍。第一个衍生问题如果要求输出 1 到 n 之间所有素数你会怎么做最直接的方案是对每个数调用一次 isPrime整体复杂度 O(n * sqrt(n))。但当 n 达到 10 的 6 次方时就会有点慢了。这时候可以引入“埃氏筛”用一个布尔数组标记所有合数整体复杂度 O(n log log n)代码也没多长。这个优化算是素数相关题目里最经典的分水岭建议你至少在编辑器里敲一遍。第二个衍生问题如果把最大公约数扩展成求三个数的最大公约数你会怎么写其实很简单先求前两个的 gcd再用结果和第三个数再求一次 gcd。但用“递归”还是“循环”来实现会牵扯到你后面学习分治和动态规划时的代码习惯。我建议两种写法都练一遍。第三个衍生问题结构体排序如果再按照姓名字典序排序字典序和数字排序有什么本质差异这涉及到字符串比较的实现思路——逐字符比 ASCII 码。理解了这一点后面的字符串排序题就不会卡壳了。做算法题不是“会了就完”而是“会不会变通”。这三个衍生问题我在 Day2 的时候会继续写总结到时候可以对比一下思路有没有升级。7. 收尾我觉得 Day1 最大的收获不是 AC 了三道题而是明确了一件事写题的第一步不是敲键盘而是先在草稿纸上把边界写清楚。最大公约数题让我记住了“先除后乘”素数题让我理解了“为什么循环到 sqrt(n) 就够”排序题让我体会到“熟悉标准库函数能让你少写一半代码”。这些经验课本上不会直白地写但以后每一道题都会用到。最后再分享一个实用小技巧我平常练习的时候会专门建一个“错误笔记本”每次提交报错就把报错点、原因、修法记下来。这个习惯在 Day1 就已经救了我两次。如果你也是那种“平时写题全靠 IDE 调试考试时一紧张就手忙脚乱”的人强烈建议试试。积累到一个月你会发现自己的 bug 率明显降下来而且再遇到相似问题时能秒定位。