简介共享一份哈工大2023春季高级算法课程实验的完整配套压缩包涵盖Lab1至Lab5共5个递进式实验适合计算机相关专业学生、准备课程设计或自学进阶算法的读者使用实验安排由浅入深便于循序渐进地掌握算法核心思想。整个资源共30个文件压缩后约18.87MB以23个Python源码文件为主体辅以4个txt数据文件、2个pickle预处理数据集和1份README说明分别用于实验输入、加载向量化数据与阅读实验指导。各Lab围绕高级算法主题展开涉及minHash、lazySelect、Bloom Filter、图算法、局部敏感哈希LSH等典型模型代码与数据集一一对应便于按阶段逐项调试和验证。该项目目前已有109人学习或下载具有一定参考价值。通过对照说明文档阅读源码读者可深入理解每种算法的实现脉络并基于自身需求修改参数或扩展应用场景从而提升算法设计、编码调试和工程落地能力。1. 拿到高级算法课程实验压缩包先把它当工程看别当作业抄我是那种拿到“哈工大2023春高级算法课程实验”这类压缩包会先紧张一下的人它确实省事源码和说明书都是现成的但“可自己修改”四个字才是这门课真正的坑。实验能不能过不看代码能不能编译而看老师随机挑一个算法问你“为什么正确、换一组数据会怎样”时你答不答得上。这个包的价值不是给你一份能交的作业而是给你一套能拆开重组的样例说明书写清环境、输入输出约定和提交物源码给出能跑的起点。适合三类人要交实验的学生、想补算法功底的考研党、需要完整实验样例做方案验证的从业者。你拿到的是参考实现不是免检答案。2. 解压与目录结构先读懂说明书再动源码很多人拿到实验包的第一反应是直接双击main.cpp。我劝你反着来先把说明书当图纸看一遍再碰代码。因为实验包里的源码能不能跑取决于说明书里写清的环境和约定能不能改取决于你对目录结构里哪些文件承担什么职责的判断。这一步做扎实了后面就省事。2.1 从.zip到实验根目录解压命令与压缩包完整性检查先不要双击解压。我有一次直接在Windows上右键解压结果压缩包里自带一层嵌套目录所有相对引用路径全乱了。后来养成了先列目录再解压的习惯。拿到哈工大2023春高级算法课程实验-内含源码和说明书(可自己修改).zip之后我一般用命令行做三件事确认文件完整、列出压缩包内容、解压到独立目录。# 先看文件大小是否合理 ls -lh 哈工大2023春高级算法课程实验-内含源码和说明书(可自己修改).zip # 列出压缩包内部结构不解压 unzip -l 哈工大2023春高级算法课程实验-内含源码和说明书(可自己修改).zip # 解压到独立目录-n 表示不覆盖已有文件 unzip -n 哈工大2023春高级算法课程实验-内含源码和说明书(可自己修改).zip -d hlg_alg_2023 # 测试解压后的文件完整性 unzip -t 哈工大2023春高级算法课程实验-内含源码和说明书(可自己修改).zip逻辑说明ls -lh先看文件大小一个声称含源码和说明书的课程包大小太异常多半是下载半截unzip -l只列内容不改动文件用来确认里面确实有说明文档和源码目录。-d指定解压目录避免把大量文件散落当前目录-n防止你之前解压过、旧文件被新文件覆盖。unzip -t是对解压结果的完整性测试说明书如果是 PDF 或文档文件损坏后读不出内容后面的流程全白搭。注意解压路径不要带中文和空格部分实验里的Makefile或批处理脚本不会处理带空格的路径这一点在 Windows 上尤其常见。如果你遇到unzip直接报invalid zip archive: could not find eocd这不是权限问题而是文件没有下载完整或者它根本不是标准 zip 结构重新下载再做一次。还有一种情况双击压缩包弹出一个“输入密码”的对话框但标题栏又说没有加密这大概率是 zip 伪加密——文件头写了需要密码实际数据没有加密。常见做法是改用 7zip 解压或者用zip -F修复一次不要信网上的所谓付费处理工具。压缩包里如果有中文文件名Linux 下解压还可能出现乱码判断实际编码后给unzip加-O GBK或-O UTF-8即可。解压后立刻把原始src复制一份起名src_origin。这一步就是后悔药后面不管改成什么样都能随时和原始实现做对拍。没有这份备份你写“我改进了 XXX”都是没有根据的。2.2 说明书里必看的四个字段环境要求、输入格式、输出格式、提交物实验包里的说明书可能叫README.md、说明.docx或实验指导.pdf。名字不重要重要的是一致扫这四个字段字段常见写法看漏的后果环境要求“在 Visual Studio / g 9 / JDK 11 下完成”到验收机器编译失败输入格式“第一行为整数 T接下来 T 组数据”程序把第一行当数据读直接崩输出格式“每个结果占一行浮点数保留 6 位”评测判错肉眼却看不出来提交物“源码 实验报告 可执行文件”只交了代码没交报告扣分环境要求决定你用什么编译器、要不要读Makefile输入格式决定你的读入代码怎么写尤其注意是“先读 T 再读 N”还是“读到 EOF 结束”输出格式决定你用printf还是cout、要不要输出Case #:前缀、浮点保留几位提交物决定你要不要保留中间文件。很多课程把“可执行文件”也列为提交物意味着你要能在验收机器的环境上重新编译出来而不是只在自己 IDE 里点一下运行。提示说明书和源码不一致时以源码里的实际输入输出为准。我遇到过说明书写“浮点保留两位”源码里却用printf(%.10lf)最后按说明改了反而判错。2.3 源码文件分类哪些是算法核心哪些是框架代码打开源码目录后先按“算法核心、框架、脚本、残留”四类把文件分清楚。算法核心文件命名通常很直白比如kmp.cpp、min_cost_flow.cpp、dp_solution.cpp框架文件是main.cpp、io_helper.cpp、Makefile脚本一般是gen_data.py、run_all.sh残留文件是.o、.obj、__pycache__、.vscode这类。文件类别识别信号修改影响算法核心文件名即算法名有状态转移、搜索、排序逻辑决定时间和空间复杂度框架 / IOmain 函数、cin/cout、参数解析影响输入输出格式与评测结果数据脚本gen_*.py / *.sh不参与评测只帮你构造用例残留文件.o / .obj /pycache提交前应删除不留绝对路径分清楚这些才知道修改的边界在哪。改算法核心会改变复杂度改框架会改变输入输出行为删残留文件则是让提交更干净。如果说明书写得含糊看源码头注释作者一般会写编译方式和输入输出约定如果注释也是空的就看main函数里先读了什么、最后打印了什么这是最后的手段但能解决问题。3. 在本地跑通源码三个高频实验的最小验证路径跑通不是玄学是流程。不管包里是什么算法第一步永远是先让它吃进一个输入、吐出一个输出再谈正确性和性能。高级算法课程实验最常见的三类题型是字符串匹配、图算法、动态规划我按这三类各给一条最小验证路径你拿到包后可以对号入座。3.1 通用编译、运行套路不同语言实验包的启动命令先看包里有没有Makefile、CMakeLists.txt、build.sh。有就用包自带的没有就按语言兜底。高级算法实验最常见的是 C、Java、Python 三种。# C 实验包 g -stdc17 -O2 -Wall -o lab main.cpp kmp.cpp dp_solution.cpp ./lab in.txt out.txt # Java 实验包注意编码避免中文注释乱码 javac -encoding UTF-8 -d . *.java java -cp . Lab in.txt out.txt # Python 实验包 python3 main.py in.txt out.txt逻辑说明-stdc17是常见默认标准-O2是让大规模测试不因常数而超时-Wall打开警告很多隐蔽问题比如有符号数和无符号数比较能在警告里提前暴露。Java 那行的-encoding UTF-8是给源码里的中文注释用的不指定的话 Windows 默认按 GBK 解码注释就可能乱码甚至编译报错。Python 用python3而不是python避免机器上同时装两个版本时选错解释器。参数说明输入输出重定向和让程序从文件读、往文件写而不是在终端手工敲数据这样反复跑同一份输入结果可复现。第一次跑完用wc -l out.txt看输出行数是否和输入组数一致这是最便宜的 sanity check。如果编译时出现-Werror把警告当错误先临时去掉把逻辑跑通再处理警告。3.2 字符串匹配类实验构造随机输入用对拍验证实现字符串匹配类实验出现频率很高常见点是 KMP、AC 自动机、后缀数组。最容易翻车的地方不是算法本身而是样例太小看不出“偏移量差一”这种低级错误。我会用固定随机种子生成一组短文本先跑一个朴素匹配再去跟你改写的算法程序做对拍。# 生成随机测试数据固定随机种子保证可复现 import random def naive_match(p, t): res [] for i in range(len(t) - len(p) 1): if t[i:i len(p)] p: res.append(i) return res random.seed(2023) t .join(random.choice(abc) for _ in range(12)) p .join(random.choice(abc) for _ in range(3)) print(p) # 模式串 print(t) # 文本 print(naive_match(p, t)) # 所有命中位置逻辑说明random.seed(2023)固定种子每次生成同样的p和t同一个 bug 可以反复复现字符集只取abc重复子串出现快更容易暴露“多算一个位置、少算一个位置”的问题。naive_match返回所有命中位置这个输出会和你的 KMP 程序输出逐行比对。参数说明如果实验要求的是“第一次出现的下标”输出只要一个整数如果要求“输出所有出现次数”输出往往是一个列表。两种语义经常被搞混。把print(naive_match(p, t))换成print(len(naive_match(p, t)))答案就完全不同所以读输出格式时要看清是下标还是次数。3.3 图算法类实验用稀疏图和稠密图分别观察复杂度图算法实验常见最短路、最小生成树、最大流。验收点往往不是“能不能算出结果”而是“在什么数据规模下能限时算完”。我会构造一稀疏一稠密两组输入跑同一份源码观察耗时和输出规模。# 分别为 1000 节点构造稀疏图和稠密图 python3 gen_graph.py --nodes 1000 --edges 3000 --seed 1 sparse.in python3 gen_graph.py --nodes 1000 --edges 300000 --seed 1 dense.in time ./lab sparse.in sparse.out time ./lab dense.in dense.out逻辑说明time输出的real是墙钟时间user是程序占用 CPU 的时间数据规模不大时两者几乎一样数据上到百万级后user更能代表算法本身开销。生成器gen_graph.py课程包通常自带没有的话自己写一个用random.randint生成边表的脚本几十行就够。参数说明稀疏图 3000 条边平均到 1000 个节点每个节点出度约 3邻接表和邻接矩阵差距不明显稠密图 30 万条边接近完全图邻接矩阵的初始化和遍历时间会明显上升。如果源码用邻接矩阵而输入规模到 5000 节点这就是“源码能跑但数据一大就挂”的典型场景后面大概率要改成邻接表。3.4 动态规划类实验拿边界用例把数组下标逼出来DP 类实验代码通常短但数组越界和初始化问题是重灾区。以 0/1 背包为例容量为 0、物品重量为 0、物品数只有 1这三组小数据能把 dp 数组开多大、下标从哪开始逼出来。# 三组边界用例第一行是物品数和容量后面每行是 重量 价值 printf 1 0\n1 1\n case1.in printf 1 1\n0 5\n case2.in printf 0 5\n case3.in ./lab case1.in ./lab case2.in ./lab case3.in逻辑说明case1.in容量为 0正确输出应为 0如果 dp 初始化写错会越界case2.in物品重量 0、价值 5如果代码里用if (j - w[i] 0)判断通常没问题但循环边界写得糙就会漏掉case3.in没有物品看程序会不会读空输入后崩溃。参数说明这三组数据不是为了验证正确性是为了逼数组下界。如果实验要求“每个物品只能取一次”和“可以取无限次”边界行为完全不一样。改源码前最好把这两种差别的判断条件写进注释答辩时老师经常从这里切入。4. 按自己的理解修改源码改算法、改输入输出、改出可解释性“可自己修改”是标题里最值钱的五个字但许多人拿到包后第一件事是把注释改成自己名字。这没有用。修改的核心目标是让代码的复杂度、数据结构和你的实验报告保持一致而不是让代码看起来不一样。4.1 先确定修改边界什么能改什么不该动我一般把改动分成三层能改、谨慎改、不该动。能改的是算法实现比如暴力替换成 DP、贪心换成搜索以及数据结构比如数组换 vector、map 换 unordered_map。谨慎改的是main函数入口、参数解析方式和文件读取方式因为课程评测往往用批处理脚本调用可执行文件启动参数改了脚本就失配。不该动的是输入格式约定、输出格式约定和包内已有的 Makefile 目标名动了就和验收环境对不上。改之前先复制一份原始包。解压后的src_origin就是干这个用的。后面不管改成什么样都能拿原始实现和新实现做对拍。没有这个基线你写的“我改进了复杂度”无从证明。4.2 实例把 O(n^2) 的 LIS 替换成 O(n log n)并验证等价高级算法课最常见的修改动机是“原实现复杂度不够”。以最长上升子序列LIS为例原生实现是两层循环数据到 1e5 就会超时。修改时我会把两份算法同时留在代码里输出两行结果直接对拍。#include bits/stdc.h using namespace std; int main() { int n; scanf(%d, n); vectorint arr(n); for (int i 0; i n; i) scanf(%d, arr[i]); // 修改前O(n^2) 动态规划保留用来对拍 vectorint dp(n, 1); for (int i 0; i n; i) for (int j 0; j i; j) if (arr[j] arr[i]) dp[i] max(dp[i], dp[j] 1); printf(%d\n, *max_element(dp.begin(), dp.end())); // 修改后O(n log n) 耐心排序 vectorint tails; for (int x : arr) { auto it lower_bound(tails.begin(), tails.end(), x); if (it tails.end()) tails.push_back(x); else *it x; } printf(%d\n, (int)tails.size()); return 0; }逻辑说明dp部分先输出 O(n^2) 的 LIS 长度tails部分再输出 O(n log n) 的长度。tails保存的是“当前长度下最小的末尾元素”每个x二分查找第一个不小于它的位置并替换最终tails.size()就是 LIS 长度。两份结果逐行比对一致说明改写正确再删掉dp分支。参数说明如果题目要的是“不下降子序列”允许相等lower_bound要换成upper_bound。因为相等元素应当接在已有序列后面而不是替换掉。这个细节在高级算法实验里很常考。验证时用diff对比两行输出若不一致说明你对“上升/不下降”的定义和题目不一致。提示改完算法后保留旧输出一行作为对拍基线确认全部一致后再删除不要提前删。4.3 修改输入输出层对准课程要求的三个细节算法改完了最容易被扣分的往往在输入输出层。我总结三个必须检查的细节// 输出浮点结果时不要用 cout 默认精度 printf(%.6lf\n, ans); // 多组样例时确认输出是否有空行分隔 if (case_id 1) printf(\n); printf(Case #%d: %d\n, case_id, ans); // 读入不要混用 scanf 和 cin否则可能顺序错乱 ios::sync_with_stdio(false); // 如果决定用 cin/cout统一走 iostream逻辑说明评测脚本比对的是字节不是人眼。printf输出0.500000cout默认可能输出0.5严格对比就是错。Case #X:前缀是部分课程实验的固定格式缺了前缀程序逻辑再对也判错。scanf和cin混用时不写ios::sync_with_stdio(false)两个输入流各自带缓冲读取顺序可能不符合输入文本顺序这是很多隐藏 bug 的来源。参数说明浮点保留位数以说明书为准常见6位或2位如果要求相对误差1e-9不要写死小数位改成printf(%.10lf)留足精度。改输出格式时把样例输出的空行、大小写、前缀一起对齐不要只读文字描述。4.4 修改后的自测矩阵小数据、随机数据、极限数据都跑改完不要只跑样例。我一般准备三个输入桶小数据桶验证正确性随机数据桶验证稳定性极限数据桶验证性能。#!/usr/bin/env bash # 对拍小脚本每个用例生成输入跑程序和标准答案 diff for i in $(seq 1 50); do python3 gen_case.py --seed $i --type small in.txt ./lab in.txt my.txt python3 judge.py in.txt expected.txt diff my.txt expected.txt /dev/null || echo small case $i failed done # 极限数据观察耗时和内存 python3 gen_case.py --type large --nodes 100000 big.in time ./lab big.in big.out wc -l big.out逻辑说明judge.py如果实验包里没有就自己写一个朴素算法生成标准答案。对拍原理很简单用实现简单但低效的程序生成正确答案再跑你优化过的程序结果一致说明你没改坏。这个动作比看十个样例都有说服力。参数说明--type large --nodes 100000是制造极限数据。题目要求 1e5 规模你就跑 1e5要求 1e6就再翻倍。time看user是否在可接受范围wc -l看输出行数是否符合预期。矩阵跑完你对修改后的程序才有底气说“能交”。5. 实验验收避坑源码能跑却在答辩翻车的5个原因以下五条是我在验收现场见过最多的情况每一条按“现象、原因、解决”写。它们有一个共同点都和“源码能不能跑”无关都和“别人能不能复现你的结果”有关。老师的验收流程通常是换台机器解压、重新编译、按说明书输入格式跑样例再对着源码随机改一个参数问你结果会怎样。5.1 环境不一致编译失败本地通过验收机器报错现象本地 IDE 一键运行很流畅到验收机器用命令行编译报未声明的标识符、不支持发行版本 17之类的错误。原因本机 GCC 12、JDK 17验收机器 GCC 8、JDK 8。源码里用了新标准特性旧编译器不认。很多人只在 IDE 里点运行没做过命令行编译。解决用说明书标明的环境重新编译说明书没有标明就按最低兼容写法去掉新特性。提交前在一台干净机器或虚拟机上用命令行编译一次不要只在 IDE 里运行。编译命令保持简单g -stdc17 -O2 -Wall不行就降标准运行时再补齐优化。5.2 肉眼一致评测判错输出格式差一个空格现象你对着样例输出看了半天数据一模一样评测脚本却判“答案错误”。原因输出包含行末空格、空行数不对、浮点位数不足、Case #:前缀缺失。这些差异人眼容易忽略但评测按字节比对。解决先用diff -w忽略空白对比内容一致说明逻辑没坏再严格diff看格式差异。diff -w out.txt expected.txt echo 逻辑一致 diff out.txt expected.txt echo 字节一致逻辑说明-w忽略所有空白字符如果这步通过说明算法结果对问题只在格式。再跑严格比对定位是空格、换行还是大小写。浮点输出统一用printf控制精度不要交给cout默认格式。参数说明如果diff -w能过而严格diff过不了优先检查每个输出行的末尾是不是多了空格以及最后一题后面是否多了一个空行。这些在样例上不明显在批处理脚本里就是硬伤。5.3 中文注释乱码导致源码无法编译现象源码里作者写了不少中文注释在 Windows 下打开是乱码某些编译器处理到乱码注释直接报错。原因源码文件编码是 UTF-8Windows 中文系统默认用 GBK 打开注释里的“最大流”变成乱码序列编译器解析到特殊字节就失败。解决Java 编译加-encoding UTF-8C 在编辑器中另存为 UTF-8更保险的做法是提交前把大段中文注释改成 ASCII 英文从根上避开编码问题。如果压缩包里的 README 也是 UTF-8一并确认另存编码再打包。注意不要依赖 IDE 自动识别编码命令行编译一次让编译器告诉你真相。5.4 答辩被问“为什么这个贪心是对的”答不上来现象程序跑通了报告也写了老师问“为什么这步贪心选择是正确的”直接卡住。原因只改了代码、跑通了样例但没有把算法证明梳理成自己的话。贪心算法尤其容易暴露这个问题因为“每一步选当前最优”看起来理所当然证明却需要说明贪心选择性质。解决改源码时把每个关键决策点写成注释为什么选当前最大值、为什么可以提前终止、为什么状态转移是单调的。答辩前用十五分钟写一段“三句话证明”第一句说问题的最优子结构第二句说贪心选择性质第三句说反例为什么不成立。这个动作是你从“能跑代码的人”变成“能讲代码的人”的转折。5.5 提交包里残留中间文件和硬编码绝对路径现象老师解压你的提交包编译前先看到一堆.o、.obj、__pycache__代码里还写着D:\user\lab\data.txt这种绝对路径换台机器直接打不开文件。原因直接对解压出来的整个目录做压缩把编译中间产物和 IDE 配置一起打了包代码里读取输入用的是本机绝对路径没有改成相对路径。解决提交前重新建一个干净目录只复制源码、说明书、报告删除中间文件和编辑器配置。代码里读文件统一用相对路径或者在main里先判断文件是否存在再打开。老师拿到包的第一件事就是解压、编译、跑样例硬编码路径导致跑不起来报告写得再好也白搭。6. 进阶把单次实验沉淀成可复用的高级算法模板实验通过只是开始。同一套代码整理成模板后以后做同类题、准备面试、写技术方案都能直接用。整理的核心是让“算法逻辑”和“输入输出”解耦。6.1 模板化的三个落点第一输入统一走重定向或统一参数不改main的入口。第二把算法核心抽成独立函数或类输入是数据和配置输出是结果结构体main只负责读和写。第三把构造数据和验证正确性的脚本留下变成以后做同类题目的脚手架。落点改什么以后的价值输入规范main 只做读入和输出换题只换算法函数算法接口把 solve(data) 独立出来可以对拍、可以单元测试脚本保留保留 gen_case.py / judge.py新实验直接复用对拍流程6.2 用对拍器和随机数据验证修改后的正确性模板化之后最有价值的配套工具是一个对拍脚本。它拿你的新实现和原始实现跑同一份输入结果不一致就停下来报出随机种子。# 对拍器同一份输入分别跑旧实现和新实现不一致即停 for i in $(seq 1 1000); do python3 gen_case.py --seed $i in.txt ./lab_origin in.txt a.txt ./lab_new in.txt b.txt cmp -s a.txt b.txt || { echo seed $i mismatch; break; } done echo all matched逻辑说明这个对拍器在验收前跑一千组随机数据能把“样例恰好通过、随机数据挂掉”的情况压到最低。cmp -s静默比对不相等时打印第一个翻车的随机种子。因为种子固定错误可以复现不用每次重新找数据。参数说明--seed $i是关键seed 从 1 到 1000 每组数据都不一样但每个 seed 对应唯一的数据。如果lab_origin已经被你删了就让新实现和judge.py对拍原理一样。这套脚本留着下次做字符串题、图论题都能用。6.3 留一份你能讲清楚的设计说明模板化最后一步是写说明。不要写“本程序实现了 KMP 算法”这种空话要写“为什么选 KMP在总长度 1e5 的文本上朴素匹配最坏 O(n*m) 会超时KMP 的 O(nm) 在题目数据下足够”。这段文字会帮你把实验从“能跑”变成“能讲”。我自己的习惯是每次实验收尾时留一份 200 字左右的“答辩备忘”三个问题一个是“你改了什么”、一个是“为什么这么改”、一个是“坏数据长什么样”。这份备忘比代码本身更能应对随机提问也让我以后复习时不用重新读代码。希望帮到你。本文还有配套的精品资源点击获取