算法竞赛入门经典授课教案第7章_暴力求解法.doc
版权申诉
19 浏览量
2022-05-30
18:16:31
上传
评论
收藏 217KB DOC 举报
第 7 章 暴力求解法
第 7 章 暴力求解法
【教学内容相关章节】
简单枚举 枚举排列 子集生成
回溯法 隐式图搜索
【教学目标】
（）掌握整数、子串等简单对象的枚举方法；
（）熟练掌握排列生成的递归方法；
（）熟练掌握用“下一个排列”枚举全排列的方法；
（）理解解答树，并能估算典型解答树的结点数；
（）熟练掌握子集生成的增量法、位向量法和二进制法；
（）熟练掌握回溯法框架，并能理解为什么它往往比生成测试法高效；
（）熟练掌握解答树的宽度优先搜索和迭代加深搜索；
（）理解倒水问题的状态图与八皇后问题的解答树的本质区别；
（）熟练掌握八数码问题的 实现；
（）熟练掌握集合的两种典型实现—— 表和 集合。
【教学要求】
掌握整数、子串等简单对象的枚举方法；熟练掌握排列生成的递归方法；熟练掌握用
“下一个排列”枚举全排列的方法；理解子集树和排列树；熟练掌握回溯法框架；熟练掌握
解答树的宽度优先搜索和迭代搜索；熟练掌握集合的两种典型实现—— 表和 集
合。
【教学内容提要】
本章主要讨论暴力法（也叫穷举法、蛮力法），它要求调设计者找出所有可能的方法，
然后选择其中的一种方法，若该方法不可行则试探下一种可能的方法。介绍了排列生成的
递归方法；在求解的过程中，提出了解答树的概念（如子集树和排列树）；介绍了回溯法
的基本框架；介绍了集合的两种典型实现—— 表和 集合。
【教学重点、难点】
教学重点：
（）熟练掌握排列生成的递归方法；
（）理解解答树，并能估算典型解答树的结点数；
（）熟练掌握子集生成的增量法、位向量法和二进制法；
（）熟练掌握回溯法框架，并能理解为什么它往往比生成测试法高效；
（）熟练掌握解答树的宽度优先搜索和迭代搜索；
（）熟练掌握集合的两种典型实现—— 表和 集合。
教学难点：
（）熟练掌握子集生成的增量法、位向量法和二进制法；
（）熟练掌握回溯法框架，并能理解为什么它往往比生成测试法高效；
（）熟练掌握解答树的宽度优先搜索和迭代搜索；
（）熟练掌握集合的两种典型实现—— 表和 集合。
【课时安排】
简单枚举 枚举排列 子集生成
回溯法 隐式图搜索
第 页
剩余25页未读，继续阅读
评论0
最新资源