摘 要：在学习了基本语言和数据结构的基础上，在学校里，学生继续学习算法设计与分析课程，可以参加多项比赛增 强自己的能力，并在找工作时提升自身的竞争力。但算法本身存在难度，采用传统的讲授法会使得很多学生望而却步。因此可 以采用以问题为导向，从实际生活中的例子，按照抽取问题，分析问题，探讨数据结构，实现算法，测试算法的准确性，一步 步引导学生学习算法。在此基础上加深难度，引导学生尝试将所学的算法使用到竞赛中，帮助克服看到竞赛题如看到猛虎的心 理。从而带领学生全面系统深入的学习算法，培养算法学习的兴趣，让他们加强专业学习的信心。
关键词：算法设计与分析 ;问题为导向 ;数据结构
0 引言
在计算机相关专业的学习中，算法设计与分析是区 分学生能力的重要课程，一些学生对这门课程涉及的算 法望而生畏，因此不敢尝试。因此考虑结合学校的优势 专业中的问题，以实际生活中的问题为导向，引导学生理解算法思想，激发学生的兴趣，进而加深课程内容，引入竞赛题目，从而提升学生的算法设计与分析能力。
1 背景
众多高校的本科生在学习了基本编程语言和数据结 构的基础上，会选择一些限选课程提升自己的能力，算 法设计与分析就是其中一门。这门课的理论与实践课时 开设比例是 1:2.如何在较短的理论课中培养学生的学习兴趣，使得他们能在后序的算法实践课上能够主动的完成基本问题，增强自身能力，以便后续参加各种比赛，是值得探讨的问题。
刘伟等 [1-2] 在当前大学课程与思政结合的时机，将 算法的性质、课程内容与学生价值观的引领相结合，在 某些环节加入了爱国主义教育，如地图着色问题和“学 习强国”中的人文地图模板相结合。吴清寿等 [3] 提出使 用三式融合教学法案例解决动态规划问题。田东平 [4] 研 究了面向算法设计与分析课程的信息化教学模式。
以往的以教师讲授为主的方法在当前的形势下，会磨灭学生的学习热情，因此可以从实际生活中的案例出发，抽取出问题，以此为导向，理论联系实际，在培养 学生兴趣的同时，提升他们参加算法竞赛的能力。并在 适当的单元以中药材数据为例，引导学生增强学校的荣誉感。
2 教学及实践内容
算法设计与分析这门课，主要教学内容分为六大部 分，分别是 ：(1)算法概述 ;(2)递归与分治算法 ;(3) 动态规划算法 ;(4)贪心法 ;(5)回溯法 ;(6)分支限 界法。
在实践课程中，对相应的算法进行展开实验，每种算 法对应两次实验，第一次实验是实现课堂上所讲的基本算 法，并出一个算法竞赛附加题，以便能力不同的学生对算 法题进行相应的取舍。第二次实验对应的是竞赛算法题， 要求在自己机器上运行成功，另外提供一道可以在竞赛网 上提交的附加题，要求在竞赛网上提交。使得有兴趣参加 竞赛的同学熟悉竞赛编程环境，并对赛题中会出现的问 题有所了解，便于其后序参加正式算法竞赛 [3]。
3 教学模式
不同的算法对应多个样例，为了引发学生的兴趣， 可以在引入样例的时候贴近生活。这样可以引起学生的 共鸣，有学有所用的意识，培养学生主动学习 [4]。所用 的部分样例如下所示。
3.1 样例 1：算法的复杂度
算法的复杂度是算法概述环节重要的内容。在讲解 该章节的时候可以从日常所用的手机问题引入，手机用 了一段时间经常会出现提示“内存不足”，这是典型的 空间存储问题。而在算法竞赛中，经常也会出现这种情 况 ：在自己的电脑上程序能够运行出结果，但是提交到相应的比赛系统时，代码就会报错。通常所报的错误有3.2 样例 2：旅游行程最优化该样例是动态规划算法中的典型。
(1)问题 ：以在南京旅游为例，假设有两天假期， 但是南京的景点很多，没法在两天的时间里游完所有景 点。但是可以根据网上信息获得不同景点游玩所需要的 时间以及网友对该景点的打分。那么可以使用动态规划 算法找出在两天时间里去哪些景点游玩可以获得最好的 体验。
假设景点和对应的游玩时间如表 1 所示 ：
(2)分析 ：根据动态规划算法的思想，应该建立一 张表格，其中表格的横向区间为 [0.2]，间隔是 0.5.纵 向是每个景点所需要的时间，初始化后，根据每个景点 的游玩情况填写表格。
填写时遵循的规则是 ：
其中，i,j 分别对应的是表格的行号和列号，c[i][j] 表示游览前 i 个景点花费j 时间可以获得的最高得分。 w[i] 和 v[i] 分别表示景点游玩所需要花费的时间和其对 应的得分。
(3)填表 ：经过计算可以得到如表 2 所示 :
最高得分是 24.根据公式可以推断要去的景点有哪些。
当 c(i,j)=c(i-1.j) 时，说明没有选择第 i 个景点，则回到 c(i-1.j) ;当 c(i,j)=c(i-1.j-w(i))+c(i) 时，说明装了第 i 个景点，该景点是最优解组成的一部分，随后我们得回到选择该商品之前，即回到 c(i-1.j-w(i)) ;一直遍历到 i = 0 结束为止，所有解的组成都会找到。最后推导得到应该选择的景点是玄武湖公园、金牛湖野生动物园和雨花台风景区。请同学思考如何将所学的知识应用到已知不同公里不同价格的公交车，怎样可以通过无限次的换车来完成想走的旅程。最后要求费用最少。
(4)代码实现对应的过程如下 ：
1)首先建表并初始化边界条件，c(0.j)=c(i,0)=0 ;如此下去，填到最后一个 ;
2)然后推导出公式，按照公式一行一行的填表，
3)最后分析得出要去的景点有哪些。在学生掌握了基础的动态规划解题思路后，可以进入蓝桥杯题目 1282: 公交汽车的题目。
3.3 样例 3：装药材游戏
南京中医药大学的双一流学科是中药学，将专业知识向强势专业靠拢，可以加强学生的荣誉感和对专业的自信心。所以设置了这个游戏。规则如下 ：
(1)问题 ：假设有若干种药材和一个小袋子，已知药材的种类和其对应的价值，小袋子的承重量也已知。药材可分，现在请大家快速选择药材，使得装入袋中的药材价值最大。
假设现在有四种药材和一个袋子，每种药材的重量( 单位 ：千克 ) 为(2.5.4.2)，价值 ( 单位 ：元 ) 为(600.300.500.400)，如表 3 所示。包装袋的承重量为 10kg，求在不超过袋子承重量的前提下，把哪些药材放入袋子，才能获得最大价值。
(2)分析 ：根据题目，药品可分，因此应该使用贪心算法。此时思考有哪些贪心策略可以选择，比如 ：每次挑选价值最大的药材装入袋子，得到的结果是否最优? ;或者每次挑选重量最小的药材装入，能否得到最优解?还是每次选取单位重量价值最大的药材，能使价值最大?推断发现应该选择第三种。每次选择价值 / 重量最高的药材，在袋子的承重范围内，得到的药材价值就会最大。
(3)代码实现对应的过程如表 4 所示 ：
1)初始化药材的重量和对应的价值，袋子的重量 ;
2)按照性价比降序排序对药材进行排序 ;
3)按照贪心策略每次选择性价比高的药材放入袋子 ; 4)构造最优解，把这些放入袋子的药材组合在一起，就得到了最优解(天麻，山东灵芝，三七，2/5 板蓝根)，获得的价值为 1620 元。其中板蓝根装入的情况是在前面三种药材装入后对袋子的剩余承重量进行分析，发现袋子还可以装 2 千克，因此取了 5 千克板蓝根的 2/5.在药材的总价值上也要加上相应重量板蓝根的价值。这里是为了解题方便，真正的做这个游戏，对应的药材会有很多，在比赛中，盲目选取结果一定不如使用贪心算法。
4 结语
在算法设计与分析教学过程中可以通过身边的实际问题，引导学生联系到算法中，对不同的问题需要采取不同的算法。在此基础上引入竞赛题目，以便于学生在基础打牢的情况下，增强自身的算法能力，在竞赛中能够沉着冷静的解题，而不是望题生畏。且使用相关算法参加竞赛的时候，注意题目中时间和空间复杂度的要求，从而在设计相关算法的时候也注意不要超过题目要求。从而切实提高学生的算法设计与分析能力。
参考文献
[1] 刘伟,胡为,李小智,等.算法分析与设计课程思政教学研究与实践[J].计算机教育,2020(8):70-74.
[2] 何菊,戴彩艳.计算机类专业课程思政教学改革[J].福建电脑,2021.37(2):158-160.
[3] 清寿,郭磊.动态规划算法的三式融合教学法案例研究[J].现代计算机,2020(17):58-61.
[4] 田东平.面向算法设计与分析课程的信息化教学模式研究[J].信息与电脑(理论版),2020.32(12):233-235.
可解释性是一个非常重要的标准。机器学习模型... 详细>>
如何设计有效的环境治理政策, 是学术界和政策... 详细>>
