算法设计与分析课程标准
一、课程概况
课程名称 算法设计与分析 课程代码 20106503
适用专业 信息与计算科学 开课学期 第5或第6或第7学期
课程性质 专业选修 学时/学分 51/3
预修课程 面向对象程序设计，数据结构
二、课程目标
课程目标1:掌握递归与分治策略、动态规划法、贪心算法、回溯法与分支限界法
的基本原理和算法框架，熟悉使用这些方法解决经典问题的算法。
课程目标2：掌握使用高级语言实现算法的的方法。
课程目标3：掌握算法的笈杂性分析方法。
三、课程目标与毕业要求的关系
1、课程目标与毕业要求的对应关系
毕业要求 指标点 课程目标
2.1具有扎实的数学基础，掌握分析学、代数学等主干数学课程的 课程目标1
2.数学基础 基本原理、基本技巧和结论，受到比较严格的数学思维训练 课程目标3
2.2具备运用数学知识解决实际问题的能力，了解数学的历史概况 课程目标I
和广泛应用 课程目标3
3.软件开发 3.1具有熟练的计算机算法设计与软件开发能力，能够熟练掌握高级程序设计语言的语法，并设计适当的数据结构和算法，编程解决实际问题。 课程目标1
课程目标2
4.数据分
析 4.1掌握数学建模和数据挖掘的常用方法，具备较强的数据分析与处理能力，能综合运用所学知识分析和解决问题。 课程目标1
2、课程目标与毕业要求的矩阵关系图
思想政治 数学基础 软件开发 数据分析 外语体育 人文劳动
1.1 1.2 1.3 2.1 2.2 2.3 3.1 3.2 3.3 4.1 4.2 4.3 5.1 5.2 5.3 6.1 6.2
课程目标1
1 1
H
M
序
号 课程内容框架 教学要求 教学重点 教学难点
1 算法概述 (1)了解算法与程序的概念；
(2)掌握算法复杂性分析及其有关概念。 算法复杂性分析。 算法复杂
性分析
2 递归与分治策略 (1)理解递归的概念；
(2)掌握分治法的基本思想；
教学单元 计算与问题解决 教学主题 非数值计算
教学目标
知识与技能
・ 能够理解分治思想和递归方法；
・ 能够利用递归方法设计相应程序；
・ 能够基于不同场景分析编写程序。
过程与方法
・ 通过在练习活动中不断将问题与大概念相结合，促进和提升问题解决能力。
情感态度价值观
・ 通过在游戏中体验程序设计的乐趣和逻辑思维的严谨。
核心素养培养
能够分析问题时将其理解为数学问题，并通过合理、严谨的算法进行程序设计，提升问题解决能力和计算思维。
教学内容
二分查找；分治思想；递归思想
教学媒体
电子白板、PPT
教学过程
教学环节 教师活动 学生活动 设计意图
游戏导入 【寻找假币游戏一一在IOO个硬币中找出伪币】
有100个硬币，其中有1个伪币，它除了质量比真币轻一点之外，没有别的区别，如何通过天平快速找到这个伪币。 学生讨论并说明寻找假币的
关键点：
1、如何判断假币；
2、如何找到假币。
如何判断假币？
• 厚薄不均匀
• 色泽不光滑
• 重要不一致 通过游戏让学生从问题解决中学会如何抓住问题的关键问题，解决关键问题便是解决问题。
在教师的引
大家自己查找资料并讨论。
引入二分查找 如何找到假币？
•分治思想 导下了解引入二分查找方法。激发学习兴趣。
I100个碑币，1个轻的|
Ξ向
叵］ ≡
以重量判断为例，重量轻就是假币。
首先是将IOO个硬币分成 回回国θ叵I
SS000
两个50,使用天平进行衡量，然后确定伪币在比较轻的那50个里,接着再将50分成2个25,将25分成两个12和1个1,将12分成2个6,将6分成2个3,将3分成3个1,这样6次就可以找到伪币，比50次少很多。
活动探究 【知识点一、二分查找】
请总结说出如何查找单词“book”的算法。
1、从字典本的中间开始翻找，找到字母b的所在页码区域：
2、从字母b的区域中间翻找，找到。的所在页码区域：
3、重复上述翻找，直到查找到字母ko 学生尝试说明如何去查找单词，并在教师引导下总结步骤：
第 1 页 共 2 页 leetcode cookbook-算法题解
欢迎来到LEETCODE COOKBOOK，这里为你提供一系列解决各种算法问题的技巧和方法。我们的目标是帮助你提升编程技巧，增强逻辑思维能力，并通过实践加深对算法的理解。
**目录**
1. **递归题解**
2. **动态规划题解**
3. **贪心算法题解**
4. **分治算法题解**
5. **剪枝与搜索优化题解**
**递归**
递归是一种强大的算法设计工具，适用于解决具有自相似性或分层结构的问题。下面我们通过几个例子来探讨如何使用递归解决算法问题。
**问题：斐波那契数列**
递归解法简单易懂，但需要注意优化，以避免大量的重复计算。
* 解法一：直接递归，适用于较小规模的题目。
* 解法二：使用记忆化搜索，将历史计算结果保存，避免重复计算。
**动态规划**
动态规划是解决规模较大问题时的优选方法，它通过将问题分解为更小的子问题，并保存子问题的解以避免重复计算，从而达到优化算法的目的。
**问题：最长上升子序列** 第 2 页 共 2 页 通过动态规划，我们可以将问题转化为一个存储问题，通过记忆化搜索进一步提高效率。
**贪心算法**
贪心算法是一种在每一步选择中都采取在当前状态下最好或最优（即局部最优）的选择，从而希望导致结果是全局最优的算法。在某些情况下，贪心算法能得到正确的解答，但在其他情况下，贪心算法可能会导致并非最优的解答。
**问题：最短路径问题（带有权重）**
对于具有权重的情况，贪心算法可能无法得到最优解，但可以提供一个可行解。
**分治策略**
分治策略常用于解决涉及分解和组合的问题。这种策略将一个问题分解为更小的子问题，直到达到基本操作单元，然后通过组合这些基本操作单元来解决问题。
**问题：合并排序数组**
通过分治法，我们可以将问题分解为两个排序数组的合并操作，然后再通过递归合并子数组，最终得到合并后的有序数组。
- 1 - 基本算法策略的比较及应用
姓名：****
学号：************
摘要：基本的算法策略主要有贪婪策略、递推策略、递归策略、枚举策略、递归回溯策略、分治策略和动态规划策略等。各算法策略特点不同，适合的问题类型不同，但各算法策略间也有着紧密的联系。
关键词：算法策略、特点、比较、应用
1. 概述
算法是指在解决问题时，按照某种机械步骤一定可以得到问题结果的处理过程。现在计算机能解决的实际问题种类繁多，解决问题的算法更是不胜枚举。但是还是有一些基本方法、策略是可以遵循的。算法策略和算法是有区别的，他们是算法设计中的两个方面。算法策略是面向问题的，算法是面向实现的，但是二者又是不可分的，只有通过一定的算法策略才能找出解决问题的具体算法。基本的算法策略主要有贪婪策略、递推策略、递归策略、枚举策略、递归回溯策略、分治策略和动态规划策略等。
2. 不同算法策略的特点
2.1 贪婪策略
贪婪策略是对问题要求比较严格的算法策略。贪婪策略解决问题是按一定顺序，在只需考虑当前局部信息的情况下，就做出一定的决策，最终得出问题的解，即贪婪策略针对的是“通过局部最优决策就能得到全局最优决策”的问题。
2.2 递推策略
递推策略和贪婪策略一样也是由当前问题的逐步解决从而得到整个问题的解，它依赖的是信息间本身的递推关系，每一步不需要决策参与到算法中，递推策略更多地用于计算。
2.3 递归策略
和递推策略类似，递归策略是利用大问题与其子问题的递推关系来解决问题。能采用递归描述的算法，通常有如下特征：为求解规模为n的问题，设法将- 2 - 它分解成规模较小的问题，然后从这些小问题的解方便地构造出大问题的解，并且这些规模较小的问题也能采用同样的分解和综合方法，分解成规模更小的问题，并从这些更小问题的解构造出规模较大问题的解。特别地，当规模n=1时，能直接得解。
2.4 枚举策略
枚举既是一个策略，也是一个算法，还是一种分析问题的手段。枚举策略的求解思路很简单，就是对问题的所有可能的解逐一尝试，从而找出问题的真正解。当然，这就要求所解问题的可能解是有限的、固定的、容易枚举的。枚举策略多用于决策类问题，这类问题往往不易找出大、小规模间问题的关系，也不易对问题进行分解，因此用尝试的方法对整体求解。
