没有合适的资源?快使用搜索试试~ 我知道了~
算法竞赛入门经典授课教案第7章 暴力求解法.doc
1.该资源内容由用户上传,如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
版权申诉
0 下载量 69 浏览量
2022-05-08
12:15:39
上传
评论
收藏 305KB DOC 举报
温馨提示
试读
26页
算法竞赛入门经典授课教案第7章 暴力求解法.doc
资源推荐
资源详情
资源评论
第 7 章 暴力求解法
第 7 章 暴力求解法
【教学内容相关章节】
简单枚举 枚举排列 子集生成
回溯法 隐式图搜索
【教学目标】
()掌握整数、子串等简单对象的枚举方法;
()熟练掌握排列生成的递归方法;
()熟练掌握用“下一个排列”枚举全排列的方法;
()理解解答树,并能估算典型解答树的结点数;
()熟练掌握子集生成的增量法、位向量法和二进制法;
()熟练掌握回溯法框架,并能理解为什么它往往比生成测试法高效;
()熟练掌握解答树的宽度优先搜索和迭代加深搜索;
()理解倒水问题的状态图与八皇后问题的解答树的本质区别;
()熟练掌握八数码问题的 实现;
()熟练掌握集合的两种典型实现—— 表和 集合。
【教学要求】
掌握整数、子串等简单对象的枚举方法;熟练掌握排列生成的递归方法;熟练掌握用
“下一个排列”枚举全排列的方法;理解子集树和排列树;熟练掌握回溯法框架;熟练掌握
解答树的宽度优先搜索和迭代搜索;熟练掌握集合的两种典型实现—— 表和 集
合。
【教学内容提要】
本章主要讨论暴力法(也叫穷举法、蛮力法),它要求调设计者找出所有可能的方法,
然后选择其中的一种方法,若该方法不可行则试探下一种可能的方法。介绍了排列生成的
递归方法;在求解的过程中,提出了解答树的概念(如子集树和排列树);介绍了回溯法
的基本框架;介绍了集合的两种典型实现—— 表和 集合。
【教学重点、难点】
教学重点:
()熟练掌握排列生成的递归方法;
()理解解答树,并能估算典型解答树的结点数;
()熟练掌握子集生成的增量法、位向量法和二进制法;
()熟练掌握回溯法框架,并能理解为什么它往往比生成测试法高效;
()熟练掌握解答树的宽度优先搜索和迭代搜索;
()熟练掌握集合的两种典型实现—— 表和 集合。
教学难点:
()熟练掌握子集生成的增量法、位向量法和二进制法;
()熟练掌握回溯法框架,并能理解为什么它往往比生成测试法高效;
()熟练掌握解答树的宽度优先搜索和迭代搜索;
()熟练掌握集合的两种典型实现—— 表和 集合。
【课时安排】
简单枚举 枚举排列 子集生成
回溯法 隐式图搜索
第 页
第 7 章 暴力求解法
引 言
暴力法也称为穷举法、蛮力法,它要求调设计者找出所有可能的方法,然后选择其中
的一种方法,若该方法不可行则试探下一种可能的方法。
暴力法也是一种直接解决问题的方法,常常直接基于问题的描述和所涉及的概念定义。
暴力法不是一个最好的算法,但当我们想不出更好的办法时,它也是一种有效的解决
问题的方法。
暴力法的优点是逻辑清晰,编写程序简洁。在程序设计竞赛时,时间紧张,相对于高
效的、巧妙的算法,暴力法编写的程序简单,能更快地解决问题。同时蛮力法也是很多算
法的基础,可以在蛮力法的基础上加以优化,得到更高效的算法。
而且,某些情况下,算法规模不大,使用优化的算法没有必要,而且某些优化算法本
身较复杂,在规模不在时可能因为复杂的算法浪费时间,反而不如简单的暴力搜索。
使用暴力法常用如下几种情况:
()搜索所有的解空间;
()搜索所有的路径;
()直接计算;
()模拟和仿真。
7.1 简 单 枚 举
在枚举复杂对象之前,先尝试着枚举一些相对简单的东西,如整数、子串等。暴力枚
举对问题进行一定的分析往往会让算法更加简洁、高效。
7.1.1 除法
输入正整数 ,按从小到大的顺序输出所有形如 的表达式,其中 ~
恰好为数字 ~ 的一个排列, 。
样例输入:
样例输出:
【分析】
只需要枚举 就可以计算出 ,然后判断是否所有数字都不相同即可。不仅
程序简单,而枚举量也从 ! 降低至不到 万。由此可见,即使采用暴力枚举,
也是需要认真分析问题。
完整的程序如下:
"#$%&'()*+
$%*,%(-
第 页
第 7 章 暴力求解法
''#%((.(%/(%01%%用数组 ( 存放 , 的各位数字
2%%(%(3415-%%初始化数组 (,使得各位数字为 ,好处是使得 & 时
位置为
2%%(%%%-
26#.021%%取 中各位数字存放在数组 ( 中
22%%%%(3774%%%8%-
22%%%%%%%%-
2%%5
6#.021%%取 中各位数字存放在数组 ( 中
22%%%%(3774%%%8%-
22%%%%%%%%%-
2%%5
判断 ~ 是否恰好为数字的 ~ 的一个排列
2%%').(%*%%-%*%&%-%77*0
22%%%%').(%%%*7-%%&%-%770
222%%%%%%.(34%%(3*40%%%)($)%#-
2%)($)%()$-
5
(%*.01
2%%(%-
2%%(%9-
2%%6#.%++%%::%%+%::%%&%021
%%%%%%9%%-
22%%%%6#.9%&%021
222%%%%%(%%%9%;%-
222%%%%%.%&%021%若 &,满足题目的条件, 位置输出
2222%%%%%%%.((./90021
22222%%%%%%%%%'$(%&&%%&&%<<%-
22222%%%%%%%%%.9%&%0%%'$(%&&<<-
22222%%%%%%%%%'$(%&&%9%&&%<<%&&%%&&#-
2222%%%%%%%5
222%%%%%5
222%%%%%779-
22%%%%5
2%%5
%%%)($)%-
5
7.1.2 最大乘积
输入 个元素组成的序列 ,你需要找出一个乘积最大的连续子序列。如果这个最大
的乘积不是正整,应输出(表示无解)。 ,
。
样例输入:
第 页
第 7 章 暴力求解法
%%
%%%%
样例输出:
【分析】
连续子序列有两个要素:起点和终点,因此只需要枚举起点和终点即可。由于每个元
素的绝对值不超过 ,一共又不超过 个元素,最大可能的乘积示会超过
,可以用
#'%#' 存下。
完整的程序如下:
"#$%&('+
(%*.01
%%%%(%34-%%%%%%%%存放输入序列的每一个元素
%==(%%%-%%存放最大的乘积
%%%%(%-%%%%%%%%%%%%输入元素的个数
==(%(*,; 存放乘积的中间结果
%%%%6#..<8</:0!>?01%%%%%%输入序列中元素的个数
%%%%%%%%').(%%%-%&%-%770%%%%输入序列中的元素
%%%%%%%%%%%.<8</:340-
%%%%%%%%').%%-%%&%-%770%1%
从序列中的第 个元素开始,枚举最大连续乘积,并用 存储
%%%%%%%%%%%(*,%%-
%%%%%%%%%%%').(%%%-%%&%-%770%1
%%%%%%%%%%%%%%%(*,%;%34-
%%%%%%%%%%%%%%%.(*,%+%0%%%%%%(*,-
%%%%%%%5
%%%%5
%%%%%%%%.+0
%%%%%%%%%%%%,)(.<8@A</0-
%%%%%%%%#
%%%%%%%%%%%%,)(.<8A</0-
%%%%%5
%%%%%)($)%-
5
7.1.3 分数拆分
输入正整数 9,找到所有的正整数 BCD,使得 。
样例输入:
样例输出:
第 页
第 7 章 暴力求解法
7
7
7
7
7
7
7
7
7
7
【分析】
找出所有有 B,D,枚举完成了就行了。但是从 7 可以看出,B 可
以比 D 大很多。由于 BCD,有 ,因此 ,即 D 9。这样,只需要在 9
范围内枚举 D,然后根据 D 尝试计算出 B 即可。
完整的程序如下:
"#$%&('+
(%*.01
%(%9-
%(%B/%D/%'$(%%-变量 '$( 统计等式的个数
%6#..<8</%:90%!%>?0%1
%').D%%97-D%&%%;%9-%D7701%判断 9B7D 等式的个数,
%B.9%;%D0%%.D%%90-
%.B%;%.D90%%9%;%D01
%'$(77-
%5
%5
%,)(.<8A</'$(0-%%%%输出满足条件的等式的个数
%').D%%97-%D%&%%;%9-%D7701%输出满足条件的等式
%B.9%;%D0%%.D%%90-
%.B%;%.D%%90%%9%;%D01
%,)(.<8878A</9/B/D0-%%
%5
%5
%%5
%%)($)%-
5
7.1.4 双基回文数
如果一个正整数 至少有两个不同的进位制 和 下都是回文数
(
/
),则称 是双基回文数(注意,回文数不以包含前导零)。输入正整数
&,输出比 大的最小双基回文数。
样例输入:
第 页
剩余25页未读,继续阅读
资源评论
老帽爬新坡
- 粉丝: 81
- 资源: 2万+
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功