计算机科学概论（微课版）· 第7章 算法 · 教学课件

高等学校计算机专业核心课程精品系列教材计算机科学概论（微课版）第7章算法算法基础·递归与分治·动态规划·贪心·回溯算法是计算机科学的灵魂。本章从《九章算术》与约瑟夫环讲起，依次吃透递归分治、动态规划、贪心、回溯四大经典算法思想及其经典案例。图7-3汉诺塔问题的示意（教材第114页）LEARNINGGOALS学习目标与知识导图第7章知识导图（教材第112页）本章学习目标❶了解算法的起源与定义，掌握算法的五大特征；❷理解时间复杂度与空间复杂度，能比较常见复杂度量级；❸掌握递归与分治思想，能用斐波那契、汉诺塔、二分查找说明；❹理解动态规划，掌握01背包与最长公共子序列的状态转移；❺掌握贪心与回溯的适用场景，了解Prim/Kruskal、八皇后、图着色等经典案例。能力落点：从"会编程"走向"会设计"，能针对问题选择合适的算法策略。计算机科学概论（微课版）｜第7章算法02CONTENTS本章目录7.1算法基础算法的定义｜从实例看算法｜复杂度分析7.2递归与分治算法递归的基本思想及案例｜分治的基本思想及案例7.3动态规划算法思想及案例｜递归与迭代实现｜优化策略7.4贪心算法钱币找零｜区间调度｜Prim与Kruskal7.5回溯算法八皇后问题｜图着色问题｜货郎问题章末7.6本章小结｜7.7拓展知识｜7.8课后习题计算机科学概论（微课版）｜第7章算法037.1算法基础·起源从"术"到Algorithm古代中国称为"术"，最早见于《周髀算经》《九章算术》。《九章算术》收录246个例题，分方田、粟米、衰分、少广、商功、均输、盈不足、方程、勾股九章，涵盖四则运算、最大公约数、埃氏筛、线性方程组的高斯消元法等，堪称算法的启蒙书。三国时期，刘徽给出求圆周率的割圆术。此后历代专著不断：唐《一位算法》、宋杨辉《杨辉算法》、明程大位《算法统宗》、清《开平算法》《算法一得》《算法全书》等，是中国古代人民智慧的结晶，影响远传世界各地。图7-1《九章算术》（教材第112页）"Algorithm"的词源与最早的算法英文名"algorithm"源自9世纪波斯数学家花拉子米（al-Khwarizmi的音转），"算法"原为"algorism"，18世纪演变为"algorithm"。公认的最早算法是欧几里得算法（辗转相除法求最大公约数），记载于《几何原本》第VII卷。计算机科学概论（微课版）｜第7章算法047.1算法基础·定义算法的定义与五大特征算法是解决问题的方法，是为解决某类问题而规定的一个有限的操作序列——一组按特定顺序执行的明确指令。有穷性执行有限步后必须终止，不能陷入无限循环。确切性每一步含义明确无歧义，任何人执行结果都一致。输入有零个或多个输入，刻画问题的初始条件。输出至少有一个输出，即问题求解的结果。可行性每一步都可分解为基本可执行的操作。算法≠程序算法是解决问题的思想与步骤，与具体语言无关；程序是算法在计算机上的具体实现。同一个算法可以用Python、C++、Java等不同语言实现——学算法，学的是"怎么想"，其次才是"怎么写"。计算机科学概论（微课版）｜第7章算法057.1算法基础·从实例看算法实例：约瑟夫环问题问题：41名冒险者围成一圈依次报数，报到3的人离开圈子，如此继续，直到只剩2人。求：站在哪两个位置才能幸存？小明与小华没有硬碰硬地干等，而是按规则一步步推演整个报数过程，算出两个安全位置并站了过去，最终成功脱险。启示面对复杂问题，先弄清规则，再按确定步骤推演——这正是算法思维。这类重复推演交给计算机，瞬间即可完成：把规则写成算法，剩下的交给机器。图7-2约瑟夫环问题（教材第113页）计算机科学概论（微课版）｜第7章算法067.1算法基础·复杂度分析时间复杂度与空间复杂度算法的优劣用时间复杂度（操作单元数量随规模变化的函数）与空间复杂度衡量；评估时间复杂度时通常考虑最坏情况。复杂度记法典型算法/场景常数阶O(1)访问数组的第一个元素对数阶O(logn)二分查找线性阶O(n)顺序遍历一维数组多项式阶O(n²)遍历二维数组O(mn)，m=n时常见时间复杂度对应的算法描述（教材第114页）空间复杂度算法运行过程中占用存储空间大小的度量，也是输入规模的函数。如递归算法执行时，调用堆栈会随问题规模不断增大。什么是"好算法"兼顾时间与空间：执行时间不能太久，也不能占用过多额外空间。解决同一问题时，应养成主动分析复杂度的习惯，挑选时间复杂度更小的算法。计算机科学概论（微课版）｜第7章算法077.2递归与分治算法·递归思想递归：自己调用自己核心思想：在函数执行过程中反复调用自身，每调用一次就把问题规模缩小一点，直到可以直接求解，再把结果层层返回、组合出原问题的答案。关键概念①递归式把大问题与同类小问题的关系写成递推公式，如斐波那契数列f(n)=f(n−1)+f(n−2)，汉诺塔f(n)=2f(n−1)+1。关键概念②递归边界递推不能无限进行，必须有终止条件：f(1)=f(2)=1（斐波那契），f(1)=1（汉诺塔）。到达边界即开始逐层返回。课堂提醒没有递归边界的递归=死循环，还会因调用栈不断加深而耗尽内存。写递归函数先问自己两个问题：递归式是什么？边界在哪里？两者齐备，递归才正确。计算机科学概论（微课版）｜第7章算法087.2递归与分治算法·递归案例案例：神兔与斐波那契数列问题：一对神兔出生后，从第3个月起每月再生一对神兔；新生的神兔也按此规律繁殖。第n个月共有多少对？观察：当月的兔对数=上月已有的+上上月已成熟所生。递归式f(n)=f(n−1)+f(n−2)(n≥3)递归边界f(1)=f(2)=1由此得到数列1,1,2,3,5,8,13,21,…，即著名的斐波那契数列。每一项都由前两项递归生成，是理解递归最经典的入口。图7-4斐波那契数列的递归结构（教材第115页）计算机科学概论（微课版）｜第7章算法097.2递归与分治算法·递归案例案例：汉诺塔问题传说：一块黄铜板上有三根宝石柱，一根柱上从下到上按大小穿好64个金盘。要把全部金盘移到另一根柱上，规则是：小盘上不能放大盘，三根柱之间一次只能移动一个圆盘。递归思路：先把上面n−1个盘移到辅助柱→把最大盘移到目标柱→再把n−1个盘移到目标柱。问题规模每次减1。递归式f(n)=2f(n−1)+1边界f(1)=1解f(n)=2ⁿ−164个盘需移动2⁶⁴−1≈1.8×10¹⁹次——即使每秒移一盘，也要约5800亿年。图7-3汉诺塔问题的示意（教材第114页）计算机科学概论（微课版）｜第7章算法107.2递归与分治算法·分治思想分治：化整为零，各个击破历史中的分治：秦灭六国面对"统一天下"这个庞大目标，秦始皇没有与六国同时开战，而是在公元前230年—前221年的十年间，按韩→赵→魏→楚→燕→齐的顺序逐个击破——把大问题拆成一个个可解决的小问题，正是分治思想。①分解Divide把原问题拆成若干规模更小、结构相同的子问题。②解决Conquer子问题足够小则直接求解，否则递归地继续分解求解。③合并Combine把各子问题的解组合成原问题的最终答案。适用条件：子问题相互独立、且求解方法与原问题相同。递归常作为分治的实现手段：分治是"战略"，递归是"战术"。计算机科学概论（微课版）｜第7章算法117.2递归与分治算法·分治案例案例：二分查找猜数字游戏：在1~100中想一个数，怎么猜最快？第一次就猜中间值(1+100)÷2=50——对方回答"大了"或"小了"，范围立刻缩小一半；再取新范围的中间值继续猜。第1次范围1~100猜50，排除一半第2次范围缩至50个数再猜中间值如此反复每猜一次，候选范围减半最多7次log₂100≈7必定猜中为什么快？与顺序查找对比100个数：顺序查找最坏要查100次；二分查找最多7次——时间复杂度O(logn)。数据量越大优势越惊人：10亿个数，二分最多约30次。前提：数据必须有序。这正是"分治"的威力：每一步都扔掉一半不可能的部分。计算机科学概论（微课版）｜第7章算法127.3动态规划算法·基本思想动态规划：记住算过的答案动态规划（DynamicProgramming）是运筹学的一个分支，用于解决多阶段决策过程的优化问题。把问题拆成若干阶段，记录已解子问题的答案，后续阶段直接查表使用，避免重复计算——"聪明地记住，而不是傻乎乎地重算"。两个核心①状态定义：用什么量描述子问题；②状态转移方程：状态之间如何递推。真实案例：1990年，曾赛星、李寿声在内蒙古河套灌区永联试区，把春小麦、玉米、甜菜三个子区的灌溉水量分配建模为多阶段决策，用动态规划逐阶段优化配水。图7-5河套灌区（教材第117页）计算机科学概论（微课版）｜第7章算法137.3动态规划算法·案例案例：01背包问题游戏情境：王者荣耀中预算2500金币、最多购买6件装备，每件要么买要么不买（01背包），怎样使增加的攻击力最大？装备增加攻击力价格（金币）陨星+451080泣血之刃+1001800无尽战刃+1102140风暴巨剑+80910雷鸣刃+40450铁剑+20250表7-1装备属性一览（教材第118页）图7-6装备（教材第118页）状态定义与转移方程状态dp[i][v]：前i件装备、预算v时的最大攻击力。转移dp[i][v]=max(dp[i−1][v],dp[i−1][v−w[i]]+c[i])不买第i件vs买了它计算机科学概论（微课版）｜第7章算法147.3动态规划算法·案例案例：最长公共子序列（LCS）子序列：从原序列中按顺序挑出若干字符（不必连续）。如"ace"是"abcde"的子序列。问题：给定两个序列，求它们最长公共子序列的长度。状态定义与转移方程状态dp[i][j]：串A前i个字符与串B前j个字符的LCS长度。转移·若A[i]=B[j]：dp[i][j]=dp[i−1][j−1]+1·否则：dp[i][j]=max(dp[i−1][j],dp[i][j−1])边界dp[0][j]=dp[i][0]=0

abcdea11111c11222e11223A=ace，B=abcde的dp表（右下角3即答案）填表过程自左向右、自上向下，每个格子只依赖上方、左方、左上方三个已知格子——这就是"记住已解子问题"的具体体现。计算机科学概论（微课版）｜第7章算法157.3动态规划算法·实现方式递归实现vs迭代实现#递归求斐波那契deffib(n):ifn<=2:#递归边界return1returnfib(n-1)+fib(n-2)

print(fib(10))#55递归实现代码直观、与递归式一一对应；但存在大量重复计算（如fib(3)被反复求解），且调用栈开销大，规模稍大就慢得难以接受。#迭代求斐波那契deffib(n):a,b=1,1for_inrange(n-2):a,b=b,a+breturnb

print(fib(10))#55迭代实现按状态转移顺序自底向上计算，每个状态只算一次，时间与空间表现都更好；动态规划实践中通常采用迭代（填表）方式。计算机科学概论（微课版）｜第7章算法167.4贪心算法·基本思想贪心：每步都选当前最优阿里巴巴与四十大盗：阿里巴巴进入藏宝洞，宝物可以分割装袋。想让背走的价值最大，策略很简单——优先装单位重量价值最高的宝物。这种"只看眼前最优"的策略就是贪心：不从整体最优出发，而是每一步都做出当前看来最好的选择。贪心算法的一般步骤①设定初始条件（如背包为空）；②迭代：每次选出局部最优，问题规模随之缩小；③把各步的选择综合为全局（近似）最优解。图7-7阿里巴巴与四十大盗（教材第121页）计算机科学概论（微课版）｜第7章算法177.4贪心算法·案例案例：钱币找零问题问题：要找零41分，面额有25分、10分、5分、1分，怎样使用最少的硬币？贪心策略：每次都选不超过剩余金额的最大面额。41分选25分剩余41−25=16分16分选10分剩余16−10=6分6分选5分剩余6−5=1分1分选1分剩余0，完成✓结果：41=25+10+5+1，共4枚硬币。注意：贪心不保证处处最优标准面额体系下贪心恰好最优；但若面额为1、3、4分要找6分，贪心给出4+1+1（3枚），而最优是3+3（2枚）。使用贪心前，先论证问题具备"贪心选择性质"，否则应改用动态规划。计算机科学概论（微课版）｜第7章算法187.4贪心算法·案例案例：区间调度问题问题：数轴上有N个开区间，要从中选出尽可能多的区间，使它们互不相交。例如多门课程时间冲突时，如何安排才能上最多的课？贪心策略：每次选择左端点最大（开始最晚）的区间，选中后把与之相交的区间全部排除，再在剩余区间中重复——从右向左一步步"贪"出最多的不相交区间。为什么这样"贪"是对的？开始得越晚，给左侧留下的可用空间就越大，后续能容纳的区间就越多——局部最优选择恰好不破坏全局最优，因此贪心成立。图7-8区间调度问题（教材第121页）计算机科学概论（微课版）｜第7章算法197.4贪心算法·案例案例：最小生成树Prim与Kruskal情境：斯巴达克斯率军行军，要用最少的"代价"把所有据点连通——即求连通图的最小生成树。两种经典算法都是贪心。Prim算法：点贪心把顶点分为已入选集合A与未入选集合B。①每步在A、B之间找权值最小的边；②把该边在B端的顶点并入A；③重复，直到所有顶点进入A。Kruskal算法：边贪心把所有边按权值从小到大排序。①依次考察每条边：两端点若不在同一连通块，就加入该边；②在同一连通块则跳过（避免成环）；③选够顶点数−1条边即完成。图7-9斯巴达克斯行军（教材第122页）两种算法贪心对象不同（点vs边），但都能得到同一棵最小生成树——条条大路通罗马。计算机科学概论（微课版）｜第7章算法207.5回溯算法·基本思想回溯：碰壁就回头回溯法是一种试探性的算法：沿一个方向向前走，每步都做一种选择；发现当前选择走不通时，就退回到上一步，换另一种选择重新尝试。好比走迷宫：一路尝试不同方向，碰壁之后退回来，再选别的路，直到找到出口。经典问题：八皇后——在8×8棋盘上放置8个皇后，使任意两个皇后都不在同一行、同一列、同一对角线上（互不攻击）。回溯vs暴力枚举回溯不是傻枚举：一旦发现当前方案已不可能成功，立即放弃整条分支（剪枝），不必走到最后才回头——效率远高于穷举。图7-10八皇后问题的棋盘（教材第123页）计算机科学概论（微课版）｜第7章算法217.5回溯算法·案例四皇后问题的回溯过程把棋盘缩小为4×4、只放4个皇后。皇后放在(1,1)后，其同行、同列、同对角线位置（黑色标识）都不能再放；第二行只能放(2,3)，但第三行随即无解——退回重选(2,4)仍不行，继续回溯，第一行改放(1,2)重新尝试。图7-11四皇后问题的棋盘（教材第123页）图7-12解决过程（一）（教材第124页）图7-13解决过程（二）（教材第124页）核心思想一句话：当前方案走不通，就回溯并重新选择。理解四皇后，八皇后只是规模放大。计算机科学概论（微课版）｜第7章算法227.5回溯算法·案例图着色问题与货郎问题图着色问题（著名的NP完全问题之一）给定无向图G=(V,E)，V为顶点集合、E为边集合。要求把V划分为K个颜色组，每组形成一个独立集——组内没有相邻顶点，即相邻顶点不同色。判定版：K种颜色够不够用（回溯逐点试色，冲突即回退）；优化版：求所需的最小K值。图7-14图着色问题与一种着色方案（教材第124页）货郎问题（TSP）问题：货郎要到若干城市卖货，每个城市恰好经过一次，最后回到起点，要求总路程最小。回溯思路：把路径看作逐城市的选择序列，一边走一边累加路程；若当前部分路径已超过已知最优，立即剪枝回退。城市一多，组合爆炸，即便回溯也很吃力——这正是NP难问题的特点。计算机科学概论（微课版）｜第7章算法23章末·本章小结第7章小结：算法❶算法基础——算法是解决问题的有限操作序列，具备有穷、确切、输入、输出、可行五特征；优劣用时间/空间复杂度衡量，评估看最坏情况。❷递归与分治——递归=递归式+递归边界（斐波那契、汉诺塔）；分治三步"分解—解决—合并"（秦灭六国），二分查找每次减半，仅O(logn)。❸动态规划——面向多阶段决策，记录已解子问题的答案；关键是状态定义与状态转移方程（01背包、LCS）；迭代实现优于朴素递归。❹贪心算法——每步取局