第三章-蛮力法课件_第1页
第三章-蛮力法课件_第2页
第三章-蛮力法课件_第3页
第三章-蛮力法课件_第4页
第三章-蛮力法课件_第5页
已阅读5页，还剩17页未读， 继续免费阅读

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

算法分析与设计

AnalysisandDesignofComputerAlgorithms第三章蛮力法BruteForce.蛮力法就像宝剑不是撬棍一样，科学也很少使用蛮力。——EdwardLytton认真做事常常是浪费时间。——RobertByrne蛮力法是一种简单直接地解决问题的方法，常常直接基于问题的描述和所涉及的概念定义。

2.蛮力法的优点可以用来解决广阔领域的问题对于一些重要的问题，它可以产生一些合理的算法解决问题的实例很少时，它让你花费较少的代价可以解决一些小规模的问题可以作为其他高效算法的衡量标准3.教学内容选择排序和冒泡排序顺序查找和蛮力字符串匹配最近对核凸包问题的蛮力算法穷举查找要求掌握蛮力法的基本思想，了解排序和查找问题的蛮力算法。

4.选择排序A[min]

5.冒泡排序算法BubbleSort(A[0..n-1])//该算法用冒泡排序对数组A[0..n-1]排序//输入：一个可排序的数组A//输出：非降序排列的数组fori0ton-2doforj0ton-2-idoifA[j+1]<A[j]swapA[j]andA[j+1]

6.顺序查找

7.蛮力字符串匹配

8.蛮力字符串匹配Θ(n+m)=Θ(n)

9.最近对问题

10.凸包问题定义对于平面上的一个点集合（有限或无限），如果以集合中任意两点P和Q为端点的线段都属于这个集合，则这个集合是凸的。定义一个点集合S的凸包是包含S的最小凸集合。

11.凸包问题定理任意包含n>2个点（不共线）的集合S的凸包是以S中的某些点为顶点的凸多边形。凸包问题是为一个n个点的集合构造凸包的问题。极点：对于任何一集合中的点为端点的线段来说，它们不是这种线段的中点。对于一个n个点集合中的两个点Pi和Pj，当且仅当该集合中的其他点都位于穿过这两点的直线的同一边时它们的连线是该集合凸包边界的一部分。直线方程：ax+by=ca=y2-y1,b=x1-x2,c=x1y2-y1x2

12.穷举查找旅行商问题

13.穷举查找背包问题

14.穷举查找分配问题N个任务分配给n个人，任务j分配给人i的成本是C[I,j]

15.小结蛮力法是一种简单直接地解决问题的方法，通常直接基于问题的描述和所涉及的概念定义。蛮力法的主要优点是它广泛的适用性和简单性；它的主要缺点是大多数蛮力算法的效率都不高。除了相关问题的一些规模非常小的实例，穷举查找法几乎是不实用的。

16.习题3.2-10找词游戏.习题3.2-11海战游戏.习题3.4-9幻方幻方是我国古代的一种智力游戏，它是在N×N的矩阵方格中填入1...N2

的正整数，使得其每行每列及对角线的和相等。很明显，这个和对某一阶幻方是一个定值。设此值为SN，则不难解出：SN=

N2·(N2+1)/2N=N·(N2+1)/2。.外延法(由巴谢提出)构造奇阶幻方.H·Coxeter构造幻方的方法首先在正方形最上面一行的正中间的小方格内填写1，然后到它的左上方的小格内填写下一个数(

人人文库> 全部分类> 应用文书 > 作业报告

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论