algorithm chapter 3

《algorithm chapter 3》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、算法分析与设计AnalysisandDesignofComputerAlgorithms第三章蛮力法BruteForce软件设计实践（ACM程序设计）教学内容选择排序和冒泡排序顺序查找和蛮力字符串匹配最近对核凸包问题的蛮力算法穷举查找要求掌握蛮力法的基本思想，了解排序和查找问题的蛮力算法。蛮力法就像宝剑不是撬棍一样，科学也很少使用蛮力。——EdwardLytton认真做事常常是浪费时间。——RobertByrne蛮力法是一种简单直接地解决问题的方法，常常直接基于问题的描述和所涉及的概念定义。蛮力法——一种最简单、最直接的算法设计方法（

2、直接基于问题本身）——直接干吧！（最容易想到）一个简例已知：数字a和非负整数n，要求：设计计算an值的算法蛮力算法：策略：直接基于问题定义来设计算法——把a和a相乘n次其他例子——计算gcd(m,n)的连续整数检测算法（效率不如欧几里德算法）蛮力法的优点可以用来解决广阔领域的问题对于一些重要的问题，它可以产生一些合理的算法解决问题的实例很少时，它让你花费较少的代价可以解决一些小规模的问题可以作为其他高效算法的衡量标准【例百钱百鸡问题。中国古代数学家张丘建在《算经》中提出了著名的“百钱百鸡问题”：鸡翁一，值钱五；鸡母一，值钱三；鸡雏三，

3、值钱一；百钱买百鸡，翁、母、雏各几何?算法设计1：通过对问题的理解，可能会想到列出两个三元一次方程，去解这个不定解方程，就能找出问题的解。这确实是一种办法，但这里我们要用“懒惰”的枚举策略进行算法设计：设x，y，z分别为公鸡、母鸡、小鸡的数量。尝试范围：由题意给定共100钱要买百鸡，若全买公鸡最多买100/5=20只，显然x的取值范围1~20之间；同理，y的取值范围在1~33之间，z的取值范围在1~100之间。约束条件：x+y+z=100且5*x+3*y+z/3=100算法1如下：main(){intx,y,z; for(x=1;

4、x<=20;x=x+1)  for(y=1;y<=34;y=y+1)   for(z=1;z<=100;z=z+1)     if(100=x+y+zand100=5*x+3*y+z/3)   {print("thecocknumberis",x)；print("thehennumberis",y)；print("thechicknumberis",z);}}算法分析：此算法需要枚举尝试20*34*100=68000次。算法的效率显然太低。选择排序思考：解决排序问题最直接的方法？选择排序——依序挑出各个元素（设小→大）1.扫

5、描整个元素列表，找最小元素，并与第1个元素交换位置2.从第2个元素开始找余下元素中的最小元素，与第2个元素交换3.如此继续，直到全部元素已排好序——找n-1遍选择排序的时间效率分析输入规模：元素个数n基本操作：比较次数A[j]

6、.第2轮将第2大元素沉到下面去。如此n-1轮，排序完毕。想一想：j循环的含义？冒泡排序的时间效率分析输入规模：元素个数n基本操作：比较次数A[j]>A[j+1]效率类别：比较次数与输入顺序无关，没最佳、最差、平均效率之分增长函数：结果讨论：1.冒泡排序算法效率属于类型—与选择排序相同2.元素的交换次数在最坏情况下（逆序输入，每次比较后需交换）与比较次数相同——比选择排序差（线性）“如不是因为它有一个好记的名字，我们很可能对它不会有任何了解”顺序查找——下两节讨论蛮力法在查找问题上的应用：顺序查找、字符串匹配查找在给定列表中查找某一个给

7、定值——查找键顺序查找的蛮力法查找键与表中元素从头至尾逐个比较。结果：找到或失败限位器：把查找键添加到列表末尾——一定成功，避免每次循环时对检查是否越界（边界检查）最佳效率：Tbest(n)=1最差效率：Tworst(n)=n+1问：为何定义A数组为n+1维？答：有一个位置放限位器问：若输入有序，算法可改进？答：遇到≤或≥查找键元素，立即停止查找。蛮力字符串匹配蛮力字符串匹配Θ(n+m)=Θ(n)最近对(ClosestPair)描述：在一个包含n个点的点集中，找到距离最近的两个点简化：二维平面上两点Pi(xi,yi)和Pj(xj,yj

8、)的欧氏距离蛮力法：穷举计算每一对点的距离，然后找出距离最小的那对点。点对总数：最近对蛮力算法改进与效率分析算法改进基本操作：计算两点的欧氏距离，需要计算平方根避免开方：欧氏平方距离替代欧氏距离，所得结论相同数学依据：平