深度优先搜索在编程中的应用学习任务单-2025-2026学年浙教版高中信息技术一轮复习

信息技术一轮复习拓展——深度优先搜索在编程中的应用 班级（ ）姓名（ ）学号（ ） 【情景展示】战争情报的加密与解密。在某次战争中，甲方欲传达几组长度不等的仅由数字0到9构成的情报，为防止情报泄露给乙方，甲方采用了一种加密方式：针对每一位数字，若该数字为奇数，则把该位数字编译成1；若该数字为偶数，则把该为数字编译成0，例如，数字“29085”编译成“01001”。在甲方将加密好的情报传递给某一较远基地时，由于突发情况，情报及加密方法泄露给了乙方，现乙方想根据该加密方式对情报进行解密，并列举出所有可能性。现要编写一段Python代码，辅助完成情报的加密工作和解密工作。 【课前热身】下面给出的代码是甲方为完成情报加密工作所使用的代码。请在横线处填写合适的代码。 sm=input('请输入需要加密的情报：') sd='' for i in range(len(sm)): if ▲ : sd=sd+'0' else: sd=sd+'1' print(sd) 【课上探索】【方案构思】乙方想根据该加密方式对情报进行解密，并列举出所有可能性。他们应该编写什么样的代码快速高效地列举所有可能性？尝试用已有的知识帮助他们构思几个方案。 （提示：可以考虑枚举、解析等方式提供多样化的方案） 【经验运用】某小组尝试用枚举的方式编写代码，其编写的完整代码如下。 s=input('请输入需要解密的情报：') list1,list2=[],[] for i in range(len(s)): if s[i]=='1': x=1 elif s[i]=='0': x=0 for m in range(1,5**len(s)+1,1): if m%(5**(len(s)-i-1))==0: list2.append(x) x=(x+2)%10 else: list2.append(x) list1.append(list2) list2=[] for n in range(len(list1[0])): ans='' for m in range(len(list1)): ans=ans+str(list1[m][n]) print(ans) 阅读上述代码，讲讲这段代码背后的运行逻辑。 【回顾思考】仔细阅读代码，思考上述代码是否存在一定的缺陷。如有，倾泻在下面的横线上。 如果要修改上面的代码，你觉得可以从哪些方面入手，进行一定程度的修改？ 【创新探索】在进行研究时，小组意外了解到“深度优先搜索”和“宽度优先搜索”概念。 资料：深度优先搜索 深度优先搜索是一种在开发爬虫早期使用较多的方法。它的目的是要达到被搜索结构的叶结点（即那些不包含任何超链的HTML文件）。在一个HTML文件中，当一个超链被选择后，被链接的HTML文件将执行深度优先搜索，即在搜索其余的超链结果之前必须先完整地搜索单独的一条链。深度优先搜索沿着HTML文件上的超链走到不能再深入为止，然后返回到某一个HTML文件，再继续选择该HTML文件中的其他超链。当不再有其他超链可选择时，说明搜索已经结束。 事实上，深度优先搜索属于图算法的一种，英文缩写为DFS即Depth First Search.其过程简要来说是对每一个可能的分支路径深入到不能再深入为止，而且每个节点只能访问一次。 举例说明之：下图是一个无向图，如果我们从A点发起深度优先搜索（以下的访问次序并不是唯一的，第二个点既可以是B也可以是C、D），则我们可能得到如下的一个访问过程:A->B->E（没有路，回溯到A）->C->F->H->G->D（没有路，最终回溯到A，A也没有未访问的相邻节点，本次搜索结束）。 图简要说明深度优先搜索的特点：每次深度优先搜索的结果必然是图的一个连通分量。深度优先搜索可以从多点发起，如果将每个节点在深度优先搜索过程中的“结束时间”排序（具体做法是创建一个list，然后在每个节点的相邻节点都已被访问的情况下，将该节点加入list结尾，然后逆转整个链表），则我们可以得到所谓的“拓扑排序”，即topological sort。 深度优先遍历图的方法是，从图中某顶点v出发: （1）访问顶点v； （2）依次从v的未被访问的邻接点出发，对图进行深度优先遍历；直至图中和v有路径相通的顶点都被访问； （3）若此时图中尚有顶点未被访问，则从一个未被访问的顶点出发，重新进行深度优先遍历，直到图中所有顶点均被访问过为止。 资料：宽度优先搜索 宽度优先搜索算法（又称广度优先搜索）是最简便的图论搜索算法之一，这一算法也是很多重要的图论算法的原型。Dijkstra单源最短路径算法和Prim最小生成树算法都采用了和宽度优先搜索类似的思想。其别名又叫BFS，属于一种盲目搜寻法，目的是系统地展开并检查图中的所有节点，以找寻结果。换句话说，它并不考虑结果的可能位置，彻底地搜索整张图，直到找到结果为止。一般可以用于边的权值相等的最短路搜索。 BFS，其英文全称是Breadth First Search。 BFS并不使用经验法则算法。从算法的观点，所有因为展开节点而得到的子节点都会被加进一个先进先出的队列中。一般的实验里，其邻居节点尚未被检验过的节点会被放置在一个被称为 open 的容器中（例如队列或是链表），而被检验过的节点则被放置在被称为 closed 的容器中。 已知图G=(V,E)和一个源顶点s，宽度优先搜索以一种系统的方式探寻G的边，从而“发现”s所能到达的所有顶点，并计算s到所有这些顶点的距离(最少边数)，该算法同时能生成一棵根为s且包括所有可达顶点的宽度优先树。对从s可达的任意顶点v，宽度优先树中从s到v的路径对应于图G中从s到v的最短路径，即包含最小边数的路径。该算法对有向图和无向图同样适用。 之所以称之为宽度优先算法，是因为算法自始至终一直通过已找到和未找到顶点之间的边界向外扩展，就是说，算法首先搜索和s距离为k的所有顶点，然后再去搜索和S距离为k+l的其他顶点。 为了保持搜索的轨迹，宽度优先搜索为每个顶点着色：白色、灰色或黑色。算法开始前所有顶点都是白色，随着搜索的进行，各顶点会逐渐变成灰色，然后成为黑色。在搜索中第一次碰到一顶点时，我们说该顶点被发现，此时该顶点变为非白色顶点。因此，灰色和黑色顶点都已被发现，但是，宽度优先搜索算法对它们加以区分以保证搜索以宽度优先的方式执行。若(u,v)∈E且顶点u为黑色，那么顶点v要么是灰色，要么是黑色，就是说，所有和黑色顶点邻接的顶点都已被发现。灰色顶点可以与一些白色顶点相邻接，它们代表着已找到和未找到顶点之间的边界。 在宽度优先搜索过程中建立了一棵宽度优先树，起始时只包含根节点，即源顶点s.在扫描已发现顶点u的邻接表的过程中每发现一个白色顶点v，该顶点v及边(u,v)就被添加到树中。在宽度优先树中，我们称结点u 是结点v的先辈或父母结点。因为一个结点至多只能被发现一次，因此它最多只能有--个父母结点。相对根结点来说祖先和后裔关系的定义和通常一样：如果u处于树中从根s到结点v的路径中，那么u称为v的祖先，v是u的后裔。 该小组进行研究发现，该解密问题可以用深度优先搜索进行解决。通过几次尝试，该小组写出以下代码： def change(x): a=[] for i in range(len(x)): if '0'<=x[i]<='9': a.append(int(x[i])) return a def sdc(data): ans='' for i in range(len(data)): ans=ans+str(data[i]) print(ans) def pos(data,start): st1=[1,3,5,7,9] st2=[0,2,4,6,8] if start==len(data): sdc(data) return original_value=data[start] if data[start]==1: for j in range(len(st1)): data[start]=st1[j] pos(data,start+1) elif data[start]==0: for j in range(len(st2)): data[start]=st2[j] pos(data,start+1) data[start]=original_value x=input('请输入要解密的情报：') data=change(x) pos(data,0) 阅读代码，尝试解释这段代码背后的运行逻辑。 【课后总结】本次课堂学习了深度优先搜索在算法中的应用，请进行总结，并提出自己留存的疑惑。 参考答案： 【课前热身】空格中应填的代码为：int(sm[i])%2==0 【经验运用】（1）可采用以下三种思路实现解密并列举全部可能： 枚举法：按位生成符合奇偶规则的数字，通过多层循环或数学规律组合出全部可能结果。 递归回溯法：逐位确定数字，遇到分支递归深入，生成完整结果后回溯，继续生成其他组合。 深度优先搜索（DFS）：从第一位开始，沿着某一分支一直深入到最后一位，得到一组结果后返回，遍历所有合法分支，输出全部组合。 （2）代码运行逻辑 （i）输入加密字符串，按位判断是0（偶数）或1（奇数），确定每一位起始数字。 （ii）利用5 的幂次控制循环次数与切换时机，枚举生成每一位所有可能的数字序列。 （iii）按列读取每一位的数字，拼接成完整数字串，最终输出所有符合奇偶规则的解密结果。 （iv）整体通过数学枚举方式，不使用递归，逐位生成并组合所有可能。 【回顾思考】 （1）代码缺陷 逻辑复杂，依赖数学计算，可读性与可维护性差，不易理解与修改。 当输入字符串较长时，5**len(s)会快速增大，占用大量内存，运行效率低。 代码无注释，结构混乱，不利于调试与扩展。 未对输入做合法性校验，若输入非 0/1 字符会直接出错。 （2）修改方向 增加输入判断，仅允许0和1组成的字符串。 简化逻辑，改用递归或深度优先搜索，结构更清晰。 添加注释，优化变量命名，提升代码可读性。 优化存储方式，避免一次性生成大量数据占用内存。 【创新探索】 （1）代码运行逻辑 change 函数：将输入的字符串逐位转为整数列表，方便后续修改与处理。 sdc 函数：将整数列表转回字符串，用于输出完整解密结果。 pos 函数（核心 DFS）： 判断是否已处理到最后一位，若是则输出当前结果。 若当前位为1，依次替换为所有奇数1、3、5、7、9，递归处理下一位。 若当前位为0，依次替换为所有偶数0、2、4、6、8，递归处理下一位。 递归返回后恢复原值，实现回溯，继续遍历其他可能数字。 整体通过深度优先搜索，逐位枚举、递归深入、回溯重试，输出全部合法解密结果。 【课后总结】 本次课以战争情报加密与解密为场景，学习了数字奇偶加密规则，掌握了加密代码编写；重点理解 ** 深度优先搜索（DFS）** 的核心思想：沿着一条路径深入到底，无法继续则回溯，遍历所有分支。对比了枚举法与 DFS 的优缺点，学会用 DFS 实现情报解密，能枚举所有符合规则的结果，体会到 DFS 在组合枚举、分支遍历问题中的简洁与高效。 留存疑惑： （i）DFS 与广度优先搜索（BFS）的区别与适用场景。 （ii）如何对 DFS 进行优化，避免过长输入导致效率下降。 （iii）除情报解密外，DFS 还可解决哪些典型编程问题。 学科网（北京）股份有限公司 $