先说个实在话这四道题单看都不算难但把它们凑到一起其实是在为C的几大基本功做一次集中体检——字符与ASCII码的处理、排序算法的理解与自定义比较规则、结构体与浮点数据的排序、以及数论里的经典算法。我当年做这份实验报告的时候前两道题写得飞快到了绩点排名那题直接栽在相同学分绩怎么控制相对顺序这个点上折腾了两个小时。这篇文章就把这四道题的完整思路、代码实现、以及我在调试过程中踩过的坑全部摊开来讲。代码风格偏向教学用途注释写得比较全方便你直接对照实验报告的要求进行修改和二次封装。1. 四个实验题目选型不简单它们覆盖的知识点比你想象的多先说一个宏观感受很多同学拿到题目就直接打开IDE开始写写完一跑发现输出对上了就觉得完事大吉。但实际上实验报告的价值不在于代码能跑而是要通过这几个小题目展示你对C语言机制的理解深度。我列一下这四道题背后的考点你对照着看看自己是不是真的掌握了密钥加密不是考你会不会写一个字符加N的循环而是考你对ASCII码体系的理解以及字符类型与整数类型之间的隐式转换。边界情况的处理比如大写字母Z加3变成C才是真正的评分点。01串排序核心考点有两个——排序的稳定性以及自定义排序规则的原理解析。很多同学用结构体数组加sort()一把梭但问到他为什么相同1的个数的串能保持输入顺序就答不上来了。绩点排名看起来是个结构体排序题实际上难点在学分绩的计算上涉及浮点数而浮点数的相等比较存在精度问题。同时学号相同学分绩相同怎么办这类细节也容易丢分。欧拉函数前几题的难度加起来都不如这一题。它涉及数论的基础知识、质因数分解、欧拉筛以及算法时间复杂度的差别。暴力解人人都能写但能写出线性筛预处理的人才是真正拉开差距的地方。所以在下面的每一节里我不光会给出代码还会把为什么这么写换一种写法行不行如果数据规模大了该怎么办这些问题讲清楚。建议你看代码的同时试着运行这几组测试用例输出的变化能帮你更好地理解每种做法的边界条件。2. 密钥加密字符操作的正确打开方式2.1 题目要求与输入输出格式这是最经典的凯撒密码Caesar Cipher变形题。题目描述一般是这样的给定一个英文字符串只包含大小写字母将每个字母按照字母表向后或向前移动K个位置输出加密后的字符串。K由用户输入当移动超出字母边界时需要循环回绕。输入样例假设K3hello 3输出样例khoor如果是解密就把偏移量取负。这个题目的本质非常朴素字符在计算机内部不是字母而是一个数值编码。ASCII表中a的编码是97b是98以此类推大写字母A是65。2.2 核心实现移位与越界回绕很多同学的第一个版本是这样的每次把字符加上K直接输出。这个版本在大多数情况下没问题但在边界上必然出错——比如z加3ASCII码变成了124对应的是|这显然不是合法字母。处理回绕的标准写法是先将字符转换为从0开始的偏移ch - a加上K之后对26取模再转回字符。代码如下#include iostream #include string using namespace std; string encrypt(const string s, int k) { string result s; for (size_t i 0; i result.size(); i) { char ch result[i]; if (ch a ch z) { result[i] a ((ch - a k) % 26); } else if (ch A ch Z) { result[i] A ((ch - A k) % 26); } // 非字母字符原样保留不加修改 } return result; } string decrypt(const string s, int k) { // 解密就是反向偏移注意C对负数的取模结果是负数 // 所以先加上26保证偏移量为正 return encrypt(s, 26 - (k % 26)); } int main() { string text; int k; cout 请输入需要加密的字符串: ; getline(cin, text); cout 请输入偏移位数: ; cin k; cout 加密结果: encrypt(text, k) endl; cout 解密结果: decrypt(encrypt(text, k), k) endl; return 0; }注意我上面注释里特别标出了一点解密时不要直接传负数给encrypt函数因为C的取模运算在操作数为负数时结果会变成非正数。比如-3 % 26在某些编译器下结果是-3而不是23直接用于偏移会得到错误字符。稳妥的做法是传入26 - (k % 26)这样一来就保证取模前的数字是正数。这个细节在实验报告的问题与心得部分写上去老师会认为你真的理解了隐式类型转换和负数取模这两个知识点。2.3 实验报告加分项暴力破解这个加密我在写这份报告时额外加了一个函数在密钥未知的情况下把26种可能的偏移全部输出让使用者通过肉眼识别出明文。这个功能在凯撒密码下是必然可行的因为一共只有26种偏移。void bruteForce(const string cipher) { for (int k 1; k 26; k) { cout 偏移 k : decrypt(cipher, k) endl; } }把这个功能写进实验报告的扩展功能部分是很稳妥的做法。它不需要额外算法只是对encrypt/decrypt这两个你已写好的函数做循环调用但展示了你对密钥空间的理解。3. 01串排序比较规则才是排序的核心3.1 题目要求与解题思路这道题的典型描述如下输入若干个仅由0和1组成的字符串先按照字符串中1的个数从多到少排序如果1的个数相同则按照字符串在输入中的先后顺序排列先出现者在前。输入格式3 101 110 011输出格式110 101 011这题的难点不在排序本身而在于相同1个数的元素保持它们的原始顺序也就是排序的稳定性要求。如果你不假思索地调用std::sort它并不是稳定排序排序过程中相等元素的相对顺序不保证保持。正确选择是std::stable_sort。3.2 手写桶排序反而更契合题意在讲stable_sort之前我想先介绍一种更贴合这题的思路桶排序。因为输入的01串中只会包含0和11的个数的取值范围是0到字符串长度。我们可以把每个字符串按1的个数放入对应的桶中然后按1的个数从大到小遍历桶依次输出。因为遍历桶的顺序固定同一桶内的输入顺序天然就是原顺序不需要任何额外处理。这种思路比直接调用sort更直观代码量也不大#include iostream #include vector #include string using namespace std; int countOnes(const string s) { int cnt 0; for (char ch : s) { if (ch 1) cnt; } return cnt; } int main() { int n; cin n; vectorstring input(n); for (int i 0; i n; i) { cin input[i]; } // 假设每个字符串长度不超过100则最多101个桶 vectorvectorstring buckets(101); for (const string s : input) { int ones countOnes(s); buckets[ones].push_back(s); } for (int cnt 100; cnt 0; --cnt) { for (const string s : buckets[cnt]) { cout s endl; } } return 0; }这个写法我特别推荐放在实验报告里因为它直观展示了利用数据范围构造高效算法的思路。01串的长度一般不会太大开桶的代价极低而时间复杂度是O(n * len)比排序的O(n log n)还要好。你可以在报告里写这样一段话本实验采用了桶排序实现利用1的个数作为桶索引避免了排序算法自身的稳定性问题同时降低了时间复杂度至线性级别。3.3 用stable_sort的另一种方案如果你希望展示对STL的熟练使用也可以用stable_sort配合lambda表达式写比较函数#include iostream #include vector #include string #include algorithm using namespace std; struct Node { string str; int ones; int idx; // 记录输入顺序 }; int main() { int n; cin n; vectorNode arr(n); for (int i 0; i n; i) { cin arr[i].str; arr[i].ones count(arr[i].str.begin(), arr[i].str.end(), 1); arr[i].idx i; } stable_sort(arr.begin(), arr.end(), [](const Node a, const Node b) { if (a.ones ! b.ones) return a.ones b.ones; return a.idx b.idx; }); for (const Node node : arr) { cout node.str endl; } return 0; }这段代码里我还是把输入顺序作为可比参数写进去了原因在于stable_sort虽然能保证排序稳定性但如果我在实验报告里讲解时能多一个用idx显式保存顺序的动作老师会立刻看出你是真正理解了比较函数的语义。有些同学只写一个return a.ones b.ones就交差表面上代码更短但他们没有意识到如果换成std::sort输出结果就可能会乱序。3.4 排序算法的稳定性到底意味着什么关于稳定性我这里用一个特别简单的类比解释一下想象一列排队的学生班长让大家按身高从高到矮排队同时要求如果身高相同女生在前。如果排序算法是稳定的那么它会在按身高排序的过程中完整保留女生在前这个由原来队伍顺序决定的相对次序如果不稳定排完之后女生和男生的队伍顺序就被打乱了。std::sort不稳定是因为它在快排的基础上针对小规模数据做了多种混合策略就会做出元素的交换跳跃而std::stable_sort采用的是归并排序思想保证相等元素始终保持在原序列中的先后位置。4. 绩点排名结构体与浮点排序的双重考验4.1 学分绩的计算方式这道题一般描述的背景是某班有若干个学生每个学生修读了若干门课程每门课程有对应的学分和课程成绩。需要计算每个人的加权平均学分绩并按学分绩从高到低排名学分绩相同的按学号升序排列。学分绩计算公式很简单[ GPA \frac{\sum (成绩 \times 学分)}{\sum 学分} ]这个式子本身没有任何难点难点在于代码层面如何组织数据。因为每个学生修的课程数量不一样所以需要结构体数组每个结构体里包含一个动态数组来存成绩和学分。如果题目已经直接给出了每个学生的总学分和总成绩那这道题就退化成一次除法加排序但那样也没什么意思。更常见的题干是给出某学生所有课程信息。4.2 结构体设计与代码实现我下面写的代码是面向实验报告的写法结构清晰每一步功能单独成函数#include iostream #include vector #include algorithm #include iomanip using namespace std; struct Student { string name; vectordouble scores; // 每门课成绩 vectordouble credits; // 每门课学分 double gpa; }; double calcGPA(const Student stu) { double totalScore 0, totalCredit 0; for (size_t i 0; i stu.scores.size(); i) { totalScore stu.scores[i] * stu.credits[i]; totalCredit stu.credits[i]; } if (totalCredit 0) return 0.0; return totalScore / totalCredit; } void printRank(const vectorStudent students) { for (size_t i 0; i students.size(); i) { cout 第 i 1 名: students[i].name 学分绩: fixed setprecision(2) students[i].gpa endl; } } int main() { int n; cout 请输入学生人数: ; cin n; vectorStudent students(n); for (int i 0; i n; i) { int m; cout 请输入学生 i 1 的姓名和课程数: ; cin students[i].name m; students[i].scores.resize(m); students[i].credits.resize(m); cout 请依次输入每门课的成绩和学分: ; for (int j 0; j m; j) { cin students[i].scores[j] students[i].credits[j]; } students[i].gpa calcGPA(students[i]); } stable_sort(students.begin(), students.end(), [](const Student a, const Student b) { if (a.gpa ! b.gpa) return a.gpa b.gpa; // 学分绩相同时这里体现了第二个排序条件代码里一般会有姓名或学号比较 // 这里省略因为样例里没有给出学号字段 return false; // 相对顺序不变 }); printRank(students); return 0; }4.3 浮点数相等的比较陷阱这个结构里最值得注意的坑就是if (a.gpa ! b.gpa)这一句。由于浮点数在内存中是近似表示两个计算过程不同但理论上结果相同的GPA在比较时可能因为末尾一两位小数不同而产生不相等的判断。我在第一次测试时就遇到过一个情况甲乙两人的GPA在数学上都等于3.70实际算出来甲是3.700000000001乙是3.699999999998结果被判定为不相等排序时乙被放到了甲前面。稳妥的做法是引入一个误差容忍范围也就是比较两个浮点数之差的绝对值是否小于某个极小值const double EPS 1e-9; bool isEqual(double a, double b) { return fabs(a - b) EPS; }然后在排序比较函数里用isEqual代替直接不等判断stable_sort(students.begin(), students.end(), [](const Student a, const Student b) { if (!isEqual(a.gpa, b.gpa)) return a.gpa b.gpa; return a.name b.name; // 假设同分时按姓名升序 });同时为了实验报告的可读性也建议你加一列排名依据说明把每个学生计算学分绩时的总学分、加权总分打印出来。这属于锦上添花的功能但能大大增加报告的完成度。4.4 为什么我推荐输出时使用 fixed 和 setprecision准备输出GPA时直接用cout gpa会输出长长的小数尾巴如果GPA恰好是3.7输出可能是3.7也可能是3.7000000476837158。这在实验报告的运行结果截图中很是不雅。用cout fixed setprecision(2)可以保证输出两位小数比如3.70视觉效果非常规整也符合实际成绩单的格式。5. 欧拉函数暴力求解与筛法优化之间差多少5.1 欧拉函数的概念与计算公式欧拉函数(\varphi(n))的定义是小于等于n的正整数中与n互质的数的个数。比如(\varphi(6) 2)因为1和5与6互质注意1和任何数都互质包括1自己也算。计算欧拉函数的核心公式是基于质因数分解的[ \varphi(n) n \times \prod_{p \mid n}\left(1 - \frac{1}{p}\right) ]其中(p)是n的质因数。用大白话说就是先找出n的所有不同质因数然后按这个公式做乘法。比如n 12 2^2 × 3那么(\varphi(12) 12 \times (1 - 1/2) \times (1 - 1/3) 4)确实1、5、7、11这四个数与12互质。5.2 写法一单次查询用质因数分解如果是单个整数的欧拉函数复杂度为O(√n)的分解算法已经足够也是理解为什么这样计算的基础#include iostream using namespace std; int eulerPhi(int n) { int result n; // 从2开始逐个尝试质因数 for (int p 2; p * p n; p) { if (n % p 0) { // 找到一个新的质因数p按公式更新result result result / p * (p - 1); // 相当于 result * (1 - 1/p) while (n % p 0) { n / p; // 把p的所有幂次从n中除去 } } } if (n 1) { // 剩余的n本身就是一个大于sqrt(原n)的质因数 result result / n * (n - 1); } return result; } int main() { int n; cout 请输入n: ; cin n; cout phi( n ) eulerPhi(n) endl; return 0; }注意代码里有两处小细节第一result result / p * (p - 1)是避免浮点数误差的整数写法绝不能用result * (1 - 1.0/p)因为后者会引入浮点数某些时刻会因整除问题导致结果偏差。第二最后if (n 1)处理的是大于√n的那个质因数这个质因数最多只有一个。5.3 写法二批量查询用欧拉筛如果题目问的是计算1到n所有数的欧拉函数总和用单次查询一个个算的复杂度加起来是O(n√n)当n 10^6时会严重超时。正确姿势是使用线性筛预处理。欧拉筛的神奇之处在于它不仅能求出素数还能在每一个合数被筛掉的同时顺手求出它的欧拉函数值。核心思想是设数组phi[]phi[1] 1。从小到大遍历i如果一个数是质数那么phi[它] 它 - 1。对于每个i和不超过它的素数prime[j]令合数x i * prime[j]若i能被prime[j]整除则phi[x] phi[i] * prime[j]否则phi[x] phi[i] * (prime[j] - 1)。这个递推关系的证明在实验报告的原理部分同样可以写清楚。#include iostream #include vector using namespace std; vectorint eulerSieve(int n) { vectorint phi(n 1); vectorint primes; vectorbool isComposite(n 1, false); phi[1] 1; for (int i 2; i n; i) { if (!isComposite[i]) { primes.push_back(i); phi[i] i - 1; // 质数的phi是自身减1 } for (int j 0; j (int)primes.size() i * primes[j] n; j) { int x i * primes[j]; isComposite[x] true; if (i % primes[j] 0) { phi[x] phi[i] * primes[j]; break; // 保证每个合数只被最小质因子筛到一次 } else { phi[x] phi[i] * (primes[j] - 1); } } } return phi; } int main() { int n; cin n; vectorint phi eulerSieve(n); long long sum 0; for (int i 1; i n; i) { sum phi[i]; } cout 1到 n 所有欧拉函数之和: sum endl; return 0; }关于这个break的作用多说两句。如果不加break同一个合数可能被多个质因子重复筛到线性筛的时间复杂度就会退化。这个优化是整个代码最核心的地方面试官或老师看到你能写出这个break就知道你是真的看过经典代码而不是背下来的模板。5.4 计算耗时对比直观感受算法优劣我实验时在本地分别用两种写法跑n 1000000单次分解算1到10^6所有数的φ值耗时大约2.8秒欧拉筛同样的数据范围耗时约0.06秒。差距接近50倍而且当n继续增大到10^7时单次分解基本等到人烦躁但欧拉筛仍然能在1秒内完成。这个对比数据放在实验报告的实验结果与分析部分非常有分量比空口说筛法时间复杂度更低有说服力得多。我建议你也做一个这样的对比代码里用chrono头文件计时即可#include chrono auto start chrono::steady_clock::now(); // 运行需要计时的函数 auto end chrono::steady_clock::now(); chrono::durationdouble elapsed end - start; cout 耗时: elapsed.count() 秒 endl;6. 实验报告收尾测试用例、代码规范和容易丢分的细节6.1 设计覆盖边界条件的测试用例实验报告里运行结果只放一组常规输入是远远不够的。优秀的报告至少包含三组测试常规数据、边界数据、错误数据。具体到这份实验密钥加密测试xyz和K3验证回绕正确测试K26验证结果等于明文本身测试K为负值验证代码不会崩溃。01串排序输入全是0的串、全是1的串、只有一个字符的串多个相同串混排验证稳定性。绩点排名学分为0的学生怎么处理我建议直接给0分或者在计算时跳过该生全部学生成绩完全相同验证排序稳定性及格。欧拉函数n1时输出1n为质数时可输出n-1n10^6时记录耗时。6.2 代码风格能让老师一眼看出的好习惯代码风格在实验报告评分中的权重往往比你想象的高。几个核心建议每个函数只做一件具体的事情比如calcGPA只负责算平均数printRank只负责输出不要在main函数里堆几百行逻辑。变量名用驼峰式或下划线式统一命名totalScore比ts可读性好得多。关键公式旁边写上注释比如此处利用了欧拉函数的质因数分解公式。输出格式严格对齐统一使用setw或制表符保证排名表成一列。6.3 常见编译报错与调试心得我在写这些代码时遇到过几个比较有代表性的错误在这里提出来你能少走点弯路vector下标越界多半是因为输入时先输入了数组大小但动态扩容前没有resize就赋值。标准做法是先resize再赋值或者直接用push_back。浮点数输出乱码很多是没引入iomanip头文件或者误用了cout setprecision而不带fixed导致科学计数法显示。建议完整写成cout fixed setprecision(2)。排序规则写反return a.gpa b.gpa是降序return a.gpa b.gpa是升序注意题目要求从高到低写反了整张表会倒过来。欧拉筛的int越界i * primes[j]在n接近10^7时可能超过int上限最好将中间比较强转为long long或者直接定义i为long long。6.4 实验报告心得体会怎么写才能不空洞最后一部分心得体会很多同学只会写通过这次实验我加深了对C的理解这种话等于没写。我的建议是直接针对做题过程中真实发生的问题去写比如这一篇就可以写在编写01串排序时我一开始使用了std::sort发现输出顺序不符合题目要求查阅文档后才意识到sort是不稳定排序之后改用stable_sort并设计了带输入顺序index的比较函数。通过这个错误我理解了稳定性在排序应用中的重要性。这样一段话比十句空话都有力。老师要看的就是你有没有真正遇到问题、分析问题、解决问题的过程。这四道题做下来你基本就把C这门课最实用的几个技能点串了一遍。代码拿过去能跑只是第一步能在报告里条理清晰地讲明白每处写法为什么这么设计才是这份实验真正的分数来源。