河海大学 · 2026年秋季

计算思维导论

Introduction to Computational Thinking

专题讲座：算法与算法类问题求解
怎样把一个问题变成计算机可以执行的步骤？

授课教师：谢在鹏（河海大学计算机系）
本讲安排：4课时，每课时45分钟 · 面向已学过C语言的大一学生

从遍历四个校门的配送任务出发，学习如何提出算法、组织数据、描述执行步骤，并判断结果是否可靠。本页提供本讲的教学安排与学习资料。

这一讲，我们在学算法

第1课时 · 45分钟

校园配送的目标与约束；用节点和边建立模型；穷举法与组合爆炸；贪心策略及其反例；七桥问题与边的遍历。

课堂活动：比较不同配送路线，说明“走得完”与“走得最短”的区别。

第2课时 · 45分钟

输入、状态与输出；变量和指针的基本回顾；数组、距离矩阵、树与父节点表；三种控制结构；流程图与伪代码；欧几里德算法与配送过程的状态变化。

课堂活动：读图查表，手动跟踪每一步的当前位置、访问记录与累计路程。

第3课时 · 45分钟

算法如何成为程序；编译与运行；边界情况；AI辅助编程中的任务描述和验证；可行性与最优性；时间和空间成本；大O记法及P、NP的直观认识。

课堂活动：解释为什么程序跑通一次，不能证明它总是正确或总能找到最优解。

第4课时 · 45分钟

活动安排的贪心策略；目标改变后重新检查规则；用贪心和穷举比较背包方案；十道概念复习题；总结算法设计与评价的方法。

课堂活动：用自然语言说明选择规则、重复步骤、结束条件及结果依据。

学习要求：重点是算法思路、数据关系与结果解释。复习题不考代码阅读、编写或运行；下载C示例并在本地运行属于选做体验。AI辅助编程部分强调先建立独立思考与编程的基本功。

活动安排与算法选择为必做作业，五个海盗分金币为独立必做题。各项作业的题目、示例和提交要求见作业总览页。

以下文件均可直接下载，无需GitHub账号。CSV文件可用电子表格软件或文本编辑器打开。

文件	用途与说明
贪心算法C示例 `nearest_neighbor.c`	每次选择最近的未访问校门，完成后返回起点。等距时按A、B、C、D的顺序选择。供下载后在自己的C语言环境中运行。
四门距离矩阵（CSV）	与讲义及C示例使用同一组距离，行与列均为A、B、C、D。
校园所属关系（CSV）	七个地点及父节点编号，用于理解树的逻辑关系与表格存储。
活动安排数据（CSV）	六场活动的开始、结束时间，用于思考怎样安排更多不冲突的活动。
背包练习数据（CSV）	三件物品的重量与价值，背包容量为6千克，每件最多选一次。
数据与示例说明（TXT）	校门编号、字段含义、单位、约束和运行结果对照。

运行后观察什么？从A出发得到A→B→C→D→A，总路程13；从C出发得到C→D→B→A→C，总路程14，而该起点存在总路程13的路线。想一想：同一个贪心规则，为什么不能保证每次都最优？

C程序已内置距离矩阵，不会自动读取CSV文件。CSV用于对照、手动推演或自行扩展。

A为东门，B为南门，C为西门，D为北门。任务是从指定校门出发，访问其余三个校门各一次，最后返回起点，比较完整路线的总路程。

校门间距离（教学千米）
出发／到达	A	B	C	D
A	0	2	6	5
B	2	0	4	4
C	6	4	0	2
D	5	4	2	0

这组数值用于算法比较，不用于实际导航。树数据中的地点编号是另一套编号，与校门A、B、C、D无关。

课程教材：《大学计算机——计算思维导论》
战德臣、聂兰顺等著，陈国良主审。配合课堂讲义学习。
优先推荐：《算法设计》
Jon Kleinberg、Éva Tardos著，张立昂、屈婉玲译。清华大学出版社，2007。ISBN：9787302143352。
从具体问题出发，学习如何提出算法、说明正确性并分析效率。建议先读第4.1节“区间调度”，联系本讲的活动安排问题。
内容简介（出版社） · 目录预览
进阶参考：《算法导论（核心篇）（原书第4版）》
Cormen等著。机械工业出版社，2026。ISBN：9787111800026。
内容简介（出版社）

推荐读物可先查询学校图书馆馆藏，优先借阅。不要求购买或通读，先读与课堂问题相关的部分。