简介这是一份面向高校算法课程学习者的完整实验与作业合集覆盖排序、查找、图算法等经典主题并融入递归、动态规划、贪心、分治等核心策略。资源共29个文件包含22份docx报告、6个cpp源码文件和1份pdf实验教程压缩包整体41.72MB。其中docx文档按实验目的、算法介绍、代码实现、性能分析、实验结果与问题讨论等模块展开帮助读者理解算法原理与复杂度评估方法作业报告部分提供算法应用与改进练习cpp文件给出可直接运行的实现代码便于动手验证pdf教程则作为课程配套参考。已有260人学习适合正在修读算法分析与设计课程、需要借鉴实验报告结构或学习算法编程实现的学生使用。通过阅读报告与配套源码读者不仅能掌握快速排序、二分查找、Dijkstra等算法的实际应用还能提升对时间与空间复杂度的分析能力为后续软件开发、数据挖掘等方向打下基础。1. 算法分析与设计报告打包成zip交这份作业前先想明白的几件事算法分析与设计这门课的作业到最后往往卡在一个很琐碎的环节把实验报告、作业报告、源码一起打包成zip交给老师或上传系统。可别小看这个zip它决定了老师在这门课上对你的最后印象。我见过太多人栽在这里文件名是“新建文件夹.zip”目录里套着三层“最终版”装的是上一次没改对的数据解压出来一片乱码甚至提示压缩包损坏。这篇笔记按我实际交作业和帮同学排障的经验把报告怎么写、目录怎么组织、zip怎么压怎么校验讲透适合正在修这门课的本科生也适合带课程的助教照着做模板。2. 把实验报告写成能打分的文档结构、复杂度与实验数据的呈现算法分析与设计的实验报告最常见的误区是当成课程设计报告来写堆一堆背景介绍和需求分析真正关键的算法设计反而两三页带过。按我批改作业和帮同学改报告的经验一份能拿高分的报告通常控制在四段式结构里问题描述、算法设计、复杂度分析、实验结果。这四段各有各的要求下面拆开说。2.1 四段式结构问题描述、算法设计、复杂度分析、实验结果问题描述不要抄题目原文要写“输入是什么、输出是什么、约束条件有哪些”。比如0-1背包问题写成“给定n件物品每件有重量w_i和价值v_i背包容量C求价值最大的装包方案要求每件物品只能取0次或1次”再补一句数据规模n≤1000C≤10000这就够了。数据规模直接影响后续算法选型老师会从这看你是不是真的理解了题目边界。算法设计这一段要写清楚三件事用的什么算法思想分治、动态规划、贪心、回溯、图论算法之一状态或子问题怎么定义递推关系或搜索策略是什么。拿最长公共子序列LCS举例伪代码可以这样给def lcs_len(x, y): m, n len(x), len(y) # dp[i][j] 表示 x 前 i 个字符与 y 前 j 个字符的最长公共子序列长度 dp [[0] * (n 1) for _ in range(m 1)] for i in range(1, m 1): for j in range(1, n 1): if x[i - 1] y[j - 1]: dp[i][j] dp[i - 1][j - 1] 1 else: dp[i][j] max(dp[i - 1][j], dp[i][j - 1]) return dp[m][n]这段代码的核心是两层循环填一个(m1)行、(n1)列的二维表。dp初值为0是边界条件对应空串的LCS长度为0字符相等时从左上角转移不等时取上方和左方的较大值。参数上m和n是输入串长度空间复杂度O(mn)时间也是O(mn)。写报告时建议补一句“当m或n超过10^4时可用滚动数组把空间压到O(min(m,n))”这比只贴代码能多拿不少印象分。复杂度分析是算法分析与设计区别于其他编程课的地方。不能只写“很快”要写清楚最好、最坏、平均情况以及空间开销。分治法一般按主定理T(n)aT(n/b)O(n^d)推动态规划盯状态数和转移代价贪心要说明为什么局部最优能推出全局最优回溯法写最坏情况指数级并说明剪枝带来的实际改进。我在报告里习惯用一行数学式加一句话解释如“T(n)2T(n/2)O(n)由主定理得T(n)O(n log n)空间O(log n)递归栈”。2.2 复杂度推导与伪代码评审老师最看重的两处细节算法设计加复杂度分析是报告的核心区但不少同学在这犯一个错只对了一层循环或者把“平均复杂度”和“最坏复杂度”混着写。比较稳妥的做法是分情况列。比如快速排序最好和平均是O(n log n)最坏是O(n²)每次划分都取到最大/最小元素空间是平均O(log n)、最坏O(n)的递归栈。不要在报告里写“快速排序是O(n log n)”就完了老师一眼就知道你没彻底弄清楚。伪代码也有规范照这个套路写不会错变量先声明类型循环和条件用缩进对齐不使用任何某种语言特有的语法关键操作旁边写一句中文注释说明它的作用。比如归并排序的合并过程伪代码写“MERGE(A, p, q, r)输入数组A和下标p≤qr输出A[p..r]有序”下面用LIBRARY式缩进列出循环最后注明“总共比较次数不超过r-p1”。这套写法在教材里常见照搬它的风格最安全。这里还想提一个容易踩的认知坑不是所有实验都必须上最优化算法。有的题数据范围很小暴力回溯也能过实验报告里一定要说明为什么选择某个算法。我见过有人明明n20的量级非要用状态压缩DP硬写代码改了三天没调对最后实验结论写“算法复杂度太高”自相矛盾。算法选择要和问题规模匹配报告里写清楚“本实验数据规模为…故采用…”这个逻辑链条。2.3 实验数据与图表运行时间要测中位数而不是平均值实验结果是报告里最容易注水的部分也是答辩时老师最爱追问的地方。要求是把理论复杂度和实际运行时间对上。数据要可复现我一般用固定随机种子生成数据比如C里srand(42)或Python里random.seed(42)在报告里注明种子值、数据规模、测试机器配置CPU型号、内存大小即可不用写频率以外的细节。运行时间测量有个血泪经验多次运行取中位数别取平均值。原因很简单机器上会有后台进程、CPU自动降频、缓存预热这些干扰平均值会被偶发的长尾拖高中位数更接近稳定表现。测的时候用同一份数据跑5到7次去掉最快和最慢取剩余数据的中位数。数据规模建议按10倍递增取至少五组比如10^3、10^4、10^5、10^6、10^7这样画出来的曲线才能看出O(n log n)和O(n²)的差距。图表方面报告里放折线图比放表格直观但原始数据表要放到附录或代码包的data目录里。截图注意只截核心输出窗口不要截整个桌面。每组图要有图题、坐标轴标签和一行结论比如“当n10^6时归并排序耗时约为插入排序的1/80与理论复杂度比值吻合”。要是发现实际结果和理论明显不符不要改数据糊弄先检查代码是不是误用了别的算法——这种问题我在排错环节碰到的频率相当高。3. 作业报告的归档规则目录结构、命名与版本管理实验报告写得再好放进一个乱糟糟的zip里印象分也要打折扣。课程作业打包成zip交上去之后老师解压出来面对的就是你的目录结构。按我自己的归档习惯压缩包里的组织方式直接影响对方能否快速找到需要的文件。这一章讲目录、命名、版本管理这三件事都是十分钟内能改完、但能省大量沟通时间的细节。3.1 目录结构按专题建目录而不是按“作业123”建常见做法是按算法专题建目录每个目录里放代码、报告和数据子目录。我自己的模板长这样算法分析与设计/ ├── 01_divide_and_conquer/ │ ├── merge_sort.c │ ├── merge_sort_report.docx │ └── data/ │ ├── input_1e5.txt │ └── input_1e6.txt ├── 02_dynamic_programming/ │ ├── knapsack.cpp │ ├── knapsack_report.docx │ └── data/ ├── 03_greedy_and_backtracking/ │ ├── activity_select.cpp │ ├── n_queens.cpp │ └── README.md └── README.md目录命名用“两位数字下划线英文专题名”排在zip里就是有序的老师按顺序就能看完整门课的实验。每个实验目录里放一个README.md用三五行写明这个文件夹里有什么、哪几个源文件对应哪个实验题、运行命令是什么。不要小看这个文件它相当于给审查者一份地图尤其当课程报告和代码要分文件提交时能省掉回来问你的来回功夫。代码文件不要叫final.cpp、new.cpp这种用题目的核心对象命名比如0_1_knapsack_dp.cpp。数据文件固定放data子目录生成数据的脚本也放进去这是可复现实验的基本要求。压缩时整个“算法分析与设计”目录打成一个zip包内不要有多余的临时文件、__pycache__、编译产物。3.2 文件命名规范学号_姓名_作业次数别带空格和特殊符号zip包的文件名建议用“课程_学号_姓名_内容描述”这种格式例如算法分析与设计_20210001_张三_实验二.zip。这里面有两个细节一是不要用空格二是不要用中文括号、全角符号、#号、号。原因很实际老师把zip传到课程系统或Linux服务器上时空格和中文字符在命令行里要转义遇到脚本批处理解压还会莫名报错。用下划线连接是最稳的。还有一种常见翻车是标题党命名写“最终版”“绝对最终版”“再改一版”。我处理自己文件会这样做每次修改后把后缀编号往上加不覆盖旧文件。这样哪怕改错了也有后悔药。对要交的作业提交前最后看一眼文件名和内容版本是否对应别出现文件名写着实验二、里面打开是实验一的乌龙。这种错误我自己犯过一次老师批改时当场指出后来每回打包前都强制自己跑一遍下文写的校验步骤。还有一点关于内网传输或U盘拷贝文件传过去后先解压一次再删除本地包确认解压出来的文件数和本地一致。不要依赖对方“应该能打开”。这里有个适用的土办法在本地解压后对比统计文件数量即可unzip -l 包名.zip | tail -1看总数再和本地目录里find . -type f | wc -l的结果比一下。3.3 版本管理每次改动留快照提交前打时间戳作业周期短很多人觉得用不上Git。这想法没问题但不做版本管理的代价是“改崩了没法回退”。我推荐一个轻量做法每次大改动前把当前目录复制一份带时间戳的备份。命令如下cp -r 算法分析与设计 算法分析与设计_backup_$(date %Y%m%d_%H%M%S)这行命令把当前工作目录复制成带年月日时分秒后缀的备份目录。$(date %Y%m%d_%H%M%S)是bash里调用系统时间格式化的标准写法23年后缀能精确到秒多个备份不会重名。如果愿意用Git就在作业目录里git init每次改完git commit -m 完成了第几次修改提交历史就是天然的版本脉络。版本管理真正的价值在提交前当你要打包zip时先确认工作目录是你要交的版本。我用一个笨办法打包前在目录里生成一个commit_info.txt内容写上“提交时间、最后一次改动内容、已知未完成事项”然后把它一起打进zip。这样不仅老师能看到你的进度你自己三个月后再看这个包也知道当时做到哪了比空对着一堆代码强。4. Linux与Windows下压缩zip的命令实操从打包到校验写报告是内容问题打包是技术问题。很多人用鼠标右键“压缩为zip”交差了事但遇到文件多、需要排除临时文件、要在服务器上解压时右键就不够用了。这一章给你Linux和Windows两套命令行方案外加分卷压缩这种右键永远做不到的操作。学会之后打包速度会快很多而且每一包都能先自测再交。4.1 Linux下用zip与unzip处理报告包常用参数一次说清Linux服务器的核心命令是zip和unzip如果没有安装Debian/Ubuntu系执行sudo apt install zip unzip即可。打包作业目录最常用的是递归压缩加排除文件zip -r -9 算法分析与设计_学号_姓名.zip 算法分析与设计 -x *.o -x *.tmp -x *__pycache__*参数说明-r表示递归包含子目录缺了它只会压顶层目录骨架-9是压缩率最高档会牺牲一点速度换体积-x指定排除模式这里排除了编译产物.o、临时文件.tmp和Python缓存目录。若想确认包里文件清单用unzip -l列出全部条目检查有没有漏压或误压unzip -l 算法分析与设计_学号_姓名.zip测试压缩包是否完整、有没有坏文件用unzip -t。这个命令会逐个解压每个条目到内存并校验CRC任何文件字节不对都会报错。强烈建议把它作为“提交前的固定动作”比解压出来肉眼抽查靠谱得多unzip -t 算法分析与设计_学号_姓名.zip最后是解压。如果收到别人发来的中文命名zip在Linux下解压乱码常见做法是指定编码解压unzip -O gbk 包名.zip。这个-O参数不是所有发行版的unzip都支持需要安装的是p7zip-full或unzip的最新版若你的unzip不支持-O就用Python脚本处理代码放在5.2节说。4.2 Windows下用PowerShell与7-Zip不装第三方也能压Windows 10以后的系统自带Compress-Archive和Expand-Archive可以不开任何软件。打开PowerShell进入作业目录执行Compress-Archive -Path .\01_divide_and_conquer, .\02_dynamic_programming -DestinationPath .\submit.zip -CompressionLevel Optimal -Force-Path接受一个数组可以一次压多个目录-CompressionLevel Optimal表示最优压缩率默认是Optimal但显式写出来更清楚-Force表示目标zip已存在时直接覆盖不加它会报错。对应解压命令是Expand-Archive -Path .\submit.zip -DestinationPath .\extracted -Force-DestinationPath指定解压目标文件夹不存在会自动创建。PowerShell方案的局限是压缩速度一般且不能精细排除某些文件类型想要排除.tmp得先复制一份干净目录再压比较笨。传文件或放到服务器上我更推荐装7-Zip用它的命令行7z功能上和Linux zip命令对齐而且能处理更多格式。加分项目录打包的写法7z a -tzip submit.zip .\算法分析与设计 -mx5 -xr!*.o -xr!*.tmp-tzip强制输出zip格式-mx5是压缩等级0~95是速度和体积的平衡点-xr!*.o递归排除.o文件。7-Zip在中文环境下的默认行为比系统自带的zip对中文文件名兼容性更好也正是这个原因我在Windows下手动打包基本都用7z而不是右键菜单。4.3 分卷压缩与传输校验邮件网盘限制体积时的应对课程系统或网盘限制单个文件大小常见做法的限制值是10MB或50MB。这时需要分卷压缩Linux zip命令写法是zip -s 10m submit.zip 算法分析与设计-s 10m表示每个分卷10MB生成submit.zip、submit.z01、submit.z02这样的文件。发给对方后对方需要把所有分卷放在同一个目录下执行zip -s 0 submit.zip --out submit_full.zip把分卷合并回完整包再正常解压。不要直接对.z01解压那样会报错。Windows下的7-Zip对应功能是7z a -v10m用法类似。传输完后的完整性校验比解压测试更快的方法是比对校验值。发送方执行生成摘要接收方比对字符串是否一致md5sum submit.zip sha256sum submit.zip这两条命令分别输出MD5和SHA256摘要。网上传输渠道其实无法保证字节不变化尤其是走聊天工具传文件或从网页下载校验值是一致的判断依据。我在交作业时会生成一个checksums.md5文件一起打进去写一句“提交前请运行md5sum -c checksums.md5验证”对方跑一下就放心了。5. 压缩包常见问题排查伪加密、乱码、损坏与密码的坑这段时间帮周围同学处理过至少十几次“压缩包打不开”的求助结论是绝大多数问题集中在五个点上伪加密、中文乱码、压缩包损坏、密码遗忘、解压路径异常。这一章按排查顺序写每条都按“现象、原因、解决”三步说清楚。你可以把它当作一份速查手册遇到问题按图索骥。5.1 zip伪加密明明没设密码解压却弹密码框现象双击zip能看到文件列表和文件名但点解压或提取时弹窗要求输入密码用unzip命令解压时直接提示输入密码。可你很清楚自己没有设过密码。原因zip格式里每个文件都有一组通用标志位位于本地文件头的第6、7字节。其中第0位是加密标志位为1表示文件加密。伪加密就是有人把这个位改成了1但压缩数据实际没有加密纯粹让普通解压工具误以为有密码。网上流传的“base64加密zip”“zip伪加密”都属于这类情形一个是可逆编码伪装一个是标志位伪装本质都不是真正的加密口令保护。解决分两步。第一步是诊断用十六进制查看工具打开zip搜索PK\x03\x04本地文件头签名查看紧随其后的第6字节的第0位是否为1。第二步是修复把该位重新置0。下面的Python脚本能处理常见的简单zip包逐条清理加密标志位import struct def remove_pseudo_encryption(in_path, out_path): data bytearray(open(in_path, rb).read()) i 0 cleaned 0 # zip 本地文件头以 PK\x03\x04 开头长度30字节 while i len(data) - 30: if data[i:i4] bPK\x03\x04: flag struct.unpack_from(H, data, i 6)[0] if flag 0x0001: # 第0位为1 伪加密 flag ~0x0001 # 清除该位 struct.pack_into(H, data, i 6, flag) cleaned 1 # 跳过文件头、文件名区和扩展区继续找下一个本地文件头 name_len struct.unpack_from(H, data, i 26)[0] extra_len struct.unpack_from(H, data, i 28)[0] i 30 name_len extra_len else: i 1 open(out_path, wb).write(data) print(f已检查并修复 {cleaned} 个伪加密条目的标志位) remove_pseudo_encryption(report_fake.zip, report_fixed.zip)代码里struct.unpack_from(H, data, i 6)读取的是小端序无符号短整型正好覆盖第6、7字节的通用标志位。 0x0001取出加密位 ~0x0001把它清零。跳转时用偏移26和28处的文件名长度与扩展区长度一路扫到下一个文件头。注意这个脚本对使用了数据描述符、压缩大小写在文件尾的特殊zip需要额外处理那种情况直接用7-Zip里的“修复压缩文件”或换原始文件更省事。这里补一句如果你收到的是这种伪加密包说明作者本意是防止在线预览或防止小白乱改内容你修复的是自己有权解压的资料不要把脚本用在别人明确要求付费或加密的包上。5.2 中文文件名乱码Windows压的包传到Linux解压全变“浣犲ソ”现象从Windows电脑压缩的zip传到Linux服务器解压后文件名显示成“浣犲ソ”“缂栫爜”一类的乱码文件内容完好或者反过来Linux压缩的zip在Windows老版本系统里解压乱码。原因zip格式规范没有强制统一文件名字符编码。Windows默认用本地代码页GBK/GB18030写文件名Linux的unzip默认按UTF-8解释两种编码对不上就出现乱码。现在较新的Windows 11和macOS Finder都能自动识别但服务器和Win7、老系统仍然会翻车。解决先确认zip里文件名原始编码。最稳的处理是用Python的zipfile模块读原始字节并重新解码代码比命令行更可控import zipfile def fix_zip_encoding(zip_path, output_dir, encgbk): with zipfile.ZipFile(zip_path) as zf: for info in zf.infolist(): # 原始文件名是按 cp437 或 gbk 存入的字节先还原再转成正确编码 raw info.filename.encode(cp437, errorssurrogateescape) name raw.decode(enc, errorsreplace) target f{output_dir}/{name} if info.is_dir(): continue with zf.open(info) as src, open(target, wb) as dst: dst.write(src.read())这段代码的核心是zipfile会把文件名按cp437解码为str这并非原编码我们先用encode(cp437)还原出原始字节再用GBK解码出正确文件名。enc参数可以按实际情况换成utf-8。注意要把target路径里的/替换成os.sepWindows和Linux路径分隔符不同我为了简洁没展开。预防措施也很简单压缩前把中文文件名改成拼音或英文或者统一用7-Zip压缩并设置“使用UTF-8文件名”。5.3 压缩包损坏unzip -t报bad CRC或双击提示格式未知现象解压到一半提示“CRC校验错误”或者连文件列表都刷不出来Windows直接报告“压缩文件夹格式无效或已损坏”。有时候是某个文件解压出来内容缺了几行肉眼不易发现。原因主要有三种。其一网盘或聊天工具传输时文件没下全其二U盘拷贝过程中断或文件系统错误其三FTP传输时没切换到二进制模式把zip当文本传了导致字节被改写。我遇到的案例里九成是第一种。解决第一步用unzip -t定位到底是哪个条目坏了条目标识会打在报错信息里。第二步尝试用zip自带的修复功能zip -FF damaged.zip --out repaired.zip-FF尝试从损坏的包中恢复尽可能多的内容修复结果写进repaired.zip原文件保持不动。修复完必须再做一次unzip -t repaired.zip确认。如果zip -FF说“无法定位中央目录”说明尾部结构损坏严重可以试试zip -F弱修复模式再不行就回到源头重新下载或让发送方重传。这里有个经验不要反复下载同一个可能有问题的源文件先让对方在那边生成md5sum你下载完比对几分钟就能确认是不是传输问题。5.4 密码遗忘自己设的密码自己都解不开现象按要求用zip -e给作业包设了密码交完作业一个月后想打开密码怎么想都不对连试十几次把自己锁在门外。原因没有可靠的密码记录习惯。密码保护本身没问题问题是很多人设密码时用了随手输入的一串符号事后既没写进备忘录也没存到密码管理器。解决先别急着上暴力破解工具那条路对一个包含大量文件的zip来说时间成本很高而且动用高强度破解本身就不可取。按这个顺序排查第一翻聊天记录和邮件压缩前是否发给过别人对方回复里可能带密码第二检查自己浏览器保存的密码库或手机备忘录很多人设密码时会顺手记一下第三如果密码跟常用口令相关列出三五次迭代的变体比如常用口令加年份、加学号后缀做成一个单词表逐个试。真的全部失败只能重新做一遍实验重新生成。预防方案是把密码写进作业目录里的password_hint.txt提示词而非明文或者用密码管理器生成随机密码并保存记录。压缩包密码这件事没有后悔药这是最实诚的结论。5.5 解压路径异常与权限问题zip slip和可执行文件权限现象一从某个来源下载的zip解压后文件跑到了预期目录之外的路径上或者覆盖了磁盘里已有同名文件。现象二Linux解压出来的源码文件权限变成了-rwxr-xr-x甚至-rwxrwxrwx编译执行都正常但看着别扭从Windows压缩再传到Linux所有文件都是-rw-r--r--有人说脚本无法直接执行。原因现象一属于“zip slip”攻击恶意构造的zip条目里带着../../这样的相对路径解压时逐级跳出目标目录。这不是课程作业会遇到的场景但值得知道排查方法。现象二是zip格式本身不保存Unix权限位和可执行位解压时用的是umask默认值不同解压工具生成不同权限纯属正常。解决解压前先unzip -l逐条检查路径凡是出现../开头或者绝对路径的条目一律拒绝解压先隔离再查看。对自己打包的习惯压缩前也不要包含绝对路径在作业目录的上一级执行zip -r且zip命令直接指定目录名而不是全路径。权限问题想要保持可执行位用7-Zip或zip命令的-X、-k等参数处理比较复杂更简单的做法是解压后统一执行chmod x *.sh或者干脆压缩时只放源码运行权限在目标机上自行配置。6. 用一个脚本把“整理压缩校验”一步做完前面几章讲的都是手动操作但人总有赶截止时间的时刻。我现在的习惯是写一个打包脚本放在作业目录的父目录里每次做完实验跑一次整理、压缩、校验全自动完成不会再出现“忘压了某个数据文件”这种事。#!/usr/bin/env bash # 用法./submit_pack.sh 实验名称如 ./submit_pack.sh 实验二_动态规划 set -euo pipefail WORK_DIR算法分析与设计 ASSIGN_NAME$1 STAMP$(date %Y%m%d_%H%M%S) PKG${ASSIGN_NAME}_${STAMP}.zip # 压缩排除编译产物和系统临时文件 zip -r -9 ${PKG} ${WORK_DIR} \ -x *.o -x *.tmp -x *.log \ -x *__pycache__* -x *backup* # 完整性测试任何条目的CRC错误都会让unzip -t返回非0脚本随即退出 unzip -t ${PKG} # 生成校验文件随包一起传给对方 md5sum ${PKG} ${PKG}.md5 echo 打包完成${PKG} ls -lh ${PKG}脚本里set -euo pipefail是三保险-e让任何命令出错就退出-u把未定义变量当错误-o pipefail让管道命令的失败也能被捕获。zip -x *backup*排除我随手复制的备份目录避免把几百MB的旧备份误传上去。unzip -t放在压缩后立刻执行等于给压缩包先做一遍体检任何坏文件都会让脚本停在当前步骤输出报错根本不会生成最终提交的包。我一开始也嫌这步麻烦直到有一次在截止前十分钟把上一版本的实验数据压进了包交上去被老师指出来。现在每次跑完脚本看到“unzip -t”那行通过心里才踏实。打包这件事看起来小但它卡住你的那一次损失的是整份实验报告的分数。希望这套流程能帮到你少踩一个算一个。本文还有配套的精品资源点击获取
 会创建几个对象？)
