椰程信奥 · 教案
搜索1（DFS） · 教案 课件共 18 页
一、教学目标
| 维度 | 具体目标 |
|---|
| 知识与技能 | ① 说出 DFS 四步法；② 独立写迷宫可达性、连通块、全排列、填涂颜色、组合；
③ 区分 vis 永久/临时；④ 掌握 %5d / %3d 场宽输出。 |
| 过程与方法 | 通过 6 个可单步动画把递归栈、回溯、泛洪、递增去重外显化。 |
| 情感态度价值观 | 建立"不漏的笨办法也是正确办法"与"求补集换角度"的工程判断。 |
二、重点难点
| 类别 | 内容 | 突破方式 |
|---|
| 重点 | DFS 四步法 + 回溯取消标记 | 第 3、6 页动画 |
| 重点 | 全排列盒子放数字模板 | 第 10–11 页动画④ + 代码 |
| 难点 | vis 永久 vs 临时 | 第 5–6 页对比 |
| 难点 | 组合递增去重 / 填色反向搜索 | 第 12–13 页动画⑤⑥ |
三、教学过程
| 环节 | 教师活动 | 学生活动 | 设计意图 |
|---|
| ① 本质 6′ | 第 2–3 页 | 答"回溯=递归返回" | 本质认知 |
| ② 迷宫 8′ | 第 4–5 页动画① | 猜方向看栈 | 栈可视化 |
| ③ 回溯 4′ | 第 6 页动画② | 说理由 | 永久/临时 |
| ④ 连通块 6′ | 第 7–8 页动画③ | 数块数 | 多起点 |
| ⑤ 代码 5′ | 第 9 页 | 跟读判否 | 框架 |
| ⑥ 全排列 7′ | 第 10–11 页 | 看 used | 标记模板 |
| ⑦ 填色 5′ | 第 12 页动画⑤ | 预测变 2 | 反向搜索 |
| ⑧ 组合 3′ | 第 13 页动画⑥ | 解释去重 | 双参数 |
| ⑨ 检测 1′ | 第 14–15 页 | 完成 | 评价 |
四、当堂检测标准
| 题号 | 正确答案 | 达标说明 |
|---|
| ① | 组合循环要 i 从 x 起，否则同组合多种顺序重复 | 能说出递增去重 |
| ② | 连通块起点必须选未访问黑格 | 能说每个块恰数一次 |
| ③ | printf("%5d", x) | 能说清 5 个场宽 |
五、板书设计
四步法：定状态 → 找边界 → 列选择 → 写回溯
迷宫/连通块：三判否先写（越界/不可通行/已访问）；可达性 vis 可永久
全排列：used 临时标记，%5d；填色：边界 0 泛洪→未标记 0 改 2
组合：dfs(x,k) 循环 i 从 x 起 → 递增 → 天然去重，setw(3)
六、易错预警清单
① 全排列漏 used[i]=false → 只输出一个排列；
② 方向数组写错 / 漏写三判否 → 漏走或越界 RE；
③ 连通块起点选错 → 块数算错（重或漏）；
④ 组合循环写成 i=1..n → 同一组合重复输出；
⑤ 填色正向找圈内 → 无从下手（应反向搜索）；
⑥ 场宽写错（%5d / %3d）或漏掉 iomanip。