《数据结构与算法（C语言） 教案 第07章经典算法.docx》由会员分享，可在线阅读，更多相关《数据结构与算法（C语言） 教案 第07章经典算法.docx（7页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、千锋教育数据结构与算法（C语言篇）教学设计课程名称：数据结构与算法（C语言篇）授语年级：授课学期：教师娓名：2020年03月01日课程名称第7章经典算法计划 学时4学时内容分析本章主要介绍约瑟夫问题、球钟问题、八皇后问题、背包问题、地图着 色问题、旅行商问题教学目标 与教学要求要求学生理解各种经典算法的设计思想与操作原理、熟练操作算法中涉 及的数据结构、掌握具体算法实例的代码编写方法教学重点约瑟夫问题、球钟问题、八皇后问题、背包问题、地图着色问题、旅行 商问题教学难点约瑟夫问题、球钟问题、八皇后问题、背包问题、地图着色问题、旅行 商问题教学方式课堂讲解及ppt演示教学过程第一课时(约瑟夫问题、
2、球钟问题、八皇后问题)0内容回顾1 .回顾上节内容，引出本课时主题。上节已经介绍了查找与排序，本章将主要介绍一些经典算法的实例。经 典算法涉及到很多解决问题的方法，如回溯法、贪心算法、分治法、动态规 划法、分支界限法等。前面的章节中，本书已经介绍了利用贪心算法与分治 法解决问题的实例，如赫夫曼树、快速排序等。本章将主要介绍使用回溯法 与动态规划法解决问题的实例，其中也涉及一些数据结构的操作，望读者理 解算法的设计思想，熟练编写操作代码。2 .明确学习目标(1)能够掌握算法概述(2)能够掌握算法实现(3)能够掌握算法概述(4)能够掌握算法实现(5)能够掌握算法概述(6)能够掌握算法实现0知识讲解
3、算法概述约瑟夫问题又称为约瑟夫斯置换，是一个在计算机科学和数学中出现的 问题。在计算机编程中，类似问题又可以称为约瑟夫环。约瑟夫问题有很多 版本，其一般的形式如下所示。假设编号分别为(1,2,n)的n个人围坐成一圈。其中，约定序号为 k(lWkWn)的人从1开始报数，数到m的那个人出列，然后下一位继续从 1开始报数，数到m的那个人再次出列，以此类推，直到所有人出列为止。如下图，设k等于3, n等于8, m等于4,那么出列的序列为6- 2-7-4-3-5-l-8o算法实现L链表实现由节中对约瑟夫问题的简单描述可知，每个待出列的人都可以 被视为一个数据元素，这些元素形成一个封闭环。因此，可以使用单
4、向循环 链表来解决约瑟夫问题。使用单向循环链表解决约瑟夫问题的代码参考教材7.1. 2节。例中，joseph()函数将数据元素个数设定为8,然后从第3个元素开 始计数，每当计数到第4个元素时，将该元素删除。Joseph()函数首先采用循环的方式对单向循环链表进行遍历，然后寻找 需要删除的元素的上一个元素与下一个元素，最后将这两个元素进行连接， 即可实现指定元素的删除。每一次删除元素后，单向循环链表都会重新连接 为一个新的环，因此无须考虑环中数据元素减少的问题。程序运行结果如下 所示。linuxubuntu:/1000phone/data/chap7$ ./a.out1 2 3 4 5 6 7
5、8/*去掉头结点前的所有数据元素*/12345678/*去掉头结点后的所有数据元素*/62743518/*按照规那么输出数据元素*/2 .循环实现在单向循环链表中，每删除一个数据元素(结点)后，链表都会重新形 成新的循环。因此，无论第几次删除数据元素，其删除过程都与第一次相同, 即计数到k时，删除对应数据。而如果采用数学的思想处理约瑟夫问题， 就需要考虑删除数据产生的空位对后续计数的影响。例如，假设当前环中的 数据元素为10个，从第0个元素开始，每次计数到4时，将对应的数据 元素删除，如下图。3 .递归实现采用递归的编程方式同样可以解决约瑟夫问题，递归操作与循环操作类 似，都是循环执行推理公式
6、。不同的是，循环实现是直接逐级计算被删除元 素在新环中对应的编号，而递归实现是先按轮次向下调用，然后逐级计算被 删除元素在新环中对应的编号。采用递归的方式解决约瑟夫问题代码参考教 材节。 算法概述球钟问题是一个需要借助于栈和队列来解决的问题。球钟是一种利用球 的移动来记录时间的简单装置。它有3个可以容纳假设干个球的指示器：小 时指示器、五分钟指示器、分钟指示器。例如，分钟指示器中有3个球， 五分钟指示器中有4个球，小时指示器中有8个球，那么表示当前时间为8 点23分。球钟问题的工作原理如下。（1）每过一分钟，球钟就会从球队列的队首取出一个球放入分钟指示 器（分钟指示器中最多可容纳4个球）。当放
7、入第5个球时，在分钟指示 器中的4个球就会按照它们被放入时的相反顺序加入球队列的队尾，第5 个球那么会进入五分钟指示器。（2）五分钟指示器最多可放11个球，当放入第12个球时，在五分 钟指示器中的11个球就会按照它们被放入时的相反顺序加入球队列的队 尾，第12个球那么会进入小时指示器。（3）小时指示器最多可放11个球，当小时指示器放入第12个球时, 原来的11个球就会按照它们被放入时的相反顺序加入球队列的队尾，然后 第12个球也加入队尾。此时三个指示器均为空，回到初始状态。算法实现由节的分析可知，球钟问题需要借助队列与栈来解决，因此，下面将展 示使用链式队列实现球队列和使用顺序栈实现指示器。自
8、定义头文件实现链式队列的数据定义以及基本操作，例如代码参考教 材7. 2.2节。例在头文件中实现了链式队列的创立、入队、出队以及队列的判断。自定义头文件实现顺序栈的数据定义以及基本操作，例如代码参考教材 7.2.2 节。例在头文件中实现了顺序栈的创立、入栈、出栈以及输出栈中的数据。测试程序需要借助于例7-4与例7-5中的函数接口，例如代码参考教 材7. 2. 2节。例中，程序利用球钟的计时规那么，计算从球出队开始到球全部回到队列 （同时保证球在队列中的顺序与初始出队时一致）的时间。程序运行结果如 下。linuxubuntu: / 1000phone/data/chap7/7-4$ . /a.o
9、ut33120 min - 552 hour 23 day由运行结果可知，按照球钟的计时规那么，从球开始出队到全部入队（入 队后球的顺序与初始出队时一致）的时间为23天。 算法概述八皇后问题是一个利用回溯法的典型案例，该问题是由国际西洋棋棋手 马克斯贝瑟尔于1848年提出的。其具体形式为：在8格义8格的国际 象棋棋盘上摆放八个皇后，使其不能互相攻击（即任意两个皇后都不能处于 同一行、同一列或同一斜线上），计算有多少种摆法。棋盘中的任意两个皇后都不在同一行、同一列或同一斜线上，满足摆放规那么，如下图。QQQQQQQQ 算法实现由7. 3.1节算法分析可知，在棋盘中摆放皇后，需要考虑下一个皇后 是
10、否有位置可以摆放，如果没有，那么返回到上一步，重新摆放皇后。因此， 在设计代码时，需要采用回溯的思想，例如代码参考教材节。第二课时(背包问题、地图着色问题、旅行商问题)Q内容回顾1 .回顾上节内容，引出本课时主题。上节已经介绍了约瑟夫问题、球钟问题、八皇后问题，下面将介绍背包 问题、地图着色问题、旅行商问题。2 .明确学习目标(1)能够掌握算法概述(2)能够掌握算法实现(3)能够掌握算法概述(4)能够掌握算法实现(5)能够掌握算法概述(6)能够掌握算法实现八飞知识讲解 算法概述背包问题可以描述为：假设有n个物品与一个背包，物品i的质量为 Wi ,价值为Vi ,背包的最大载重为c,求如何装载可使
11、背包中物品的总 价值最大。本次只讨论“0-1”的情况，即物品不可拆分，只能装入或不装入, 且不能将同一个物品装入屡次。解决背包问题的方法有很多，如回溯法、动态规划法、分支界限法等。 本节将主要介绍通过回溯法解决背包问题，即采用探测的方式。接下来通过 一个具体的例如展示探测的过程。例如，一个背包只能载重8kg,荔枝4kg的价格为45元，樱桃 5kg的价格为57元，香蕉1kg的价格为11元，草莓2kg的价格为22.5 元，菠萝6kg的价格为67元，如表所示。荔枝樱桃香蕉草莓菠萝序号12345重量45126价格45571122.567 算法实现采用回溯法解决背包问题，例如代码参考教材742节。 算法
12、概述地图着色问题是著名的NP完全问题（多项式复杂程度的非确定性问 题）之一。该问题可以详细分为以下3种模式。（1）图的着色问题，即给定无向连通图G与n种不同的颜色，计算 所有不同的着色方法，使得任意相邻的2个顶点具有不同的颜色。（2）图的着色判定问题，即给定无向连通图G与n种不同的颜色， 使用这些颜色为图G中的各顶点着色，判断是否存在一着色法使图G中 任意相邻顶点具有不同的颜色。（3）图的着色优化问题，即计算无向联通图G中，至少需要多少种颜 色使得任意相邻的2个顶点具有不同的颜色。 算法实现下面通过代码展示地图着色问题以及地图着色优化问题。1 .地图着色问题地图着色问题的解决方法与八皇后问题、
13、背包问题类似，都是利用深度 优先搜索的方式进行递归并回溯，找到所有问题的子集。具体代码参考教材 7.5.2 Tio2 .地图着色优化问题地图着色优化问题即计算地图的最小色数，该问题只需要求出可行着色 方案中的一种，要求使用的颜色数量最少，不需要考虑顶点之间的颜色调换。 具体代码参考教材752节。 算法概述旅行商问题是一个经典的组合优化问题。具体的问题描述为：一个推销 员必须访问n个城市，且所有城市只访问一次，然后回到起始的城市（城市 与城市之间有旅行费用，且推销员希望旅行费用之和最小）。也可以换一种 描述：给定一系列城市和每对城市之间的距离，求访问每一座城市一次并回 到起始城市的最短回路。算法实现采用动态规划法解决旅行商问题参考教材节。第三课时上机练习（总结、练习题）L总结本章内容。.2.通过题库发送相关测试题，检查学生掌握情况。上机练习主要针对本章中需要重点掌握的知识点，以及在程序中容易出 错的内容进行练习，通过上机练习可以考察同学对知识点的掌握情况，对代 码的熟练程度。第四课时上机练习（总结、练习题）1 .总结本章内容2 .通过题库发送相关测试题，检查学生掌握情况。上机练习主要针对本章中需要重点掌握的知识点，以及在程序中容易出 错的内容进行练习，通过上机练习可以考察同学对知识点的掌握情况，对代 码的熟练程度。习题教材第7章习题