算法设计与分析 课件 第2、3章 蛮力法；分治法.pptx

计算机算法设计与分析第二章蛮力法

学习目标了解蛮力法的适用场景掌握蛮力法的设计思想掌握蛮力法解决实际问题。

2.1蛮力法概述蛮力法（BruteForce），又称暴力法、穷举法，它遍历解空间的所有可能解，然后一一验证，直到找到问题的解或所有可能解都验证完毕。该方法是一种简单直接地解决问题的方法，常常直接基于问题的描述和所涉及的概念定义。它完全依靠计算机的算力来直接对问题进行求解。随着计算机硬件技术的不断进步，计算机的算力也在不断提高。蛮力法借助于计算机强大的计算能力就能够解决很大一部分问题。虽然它显得过于愚笨，但往往却能以最简单直接的方式来解决问题，甚至有些问题只能用蛮力法求解。

2.1蛮力法概述虽然巧妙和高效的算法很少来自于蛮力法，但不应该忽略它作为一种重要的算法设计策略的地位。主要体现在以下几个方面：（1）蛮力法的使用范围广，几乎没什么限制，可以解决广阔领域的各种问题。实际上，它可能是唯一一种几乎什么问题都能解决的一般性方法。（2）对于一些重要的问题（如排序、查找、字符串匹配等）来说，规模不大时，蛮力法可以产生一些合理的算法。

2.1蛮力法概述虽然巧妙和高效的算法很少来自于蛮力法，但不应该忽略它作为一种重要的算法设计策略的地位。主要体现在以下几个方面：（3）如果要解决的问题规模不大，从某种意义上说蛮力法是最划算的一种算法。（4）即使计算效率通常较低，但仍可使用蛮力法解决一些小规模的问题实例。（5）蛮力法可作为研究或教学目的服务，比如可以以它作为参照标准，来衡量解决相同问题的其他算法是否更为高效，如把蛮力法作为计算最坏时间复杂度。

2.2蛮力法的设计思想蛮力法本质是先有策略地进行穷举，然后一一验证。蛮力法的设计的需要从三个方面进行：问题解的表示形式及范围；使用何种方法将其穷举，要求不能重复也不能遗漏；将每个列举的可能解代入具体问题的各个条件进行比对。这三个方面中最为核心的是第二个，也就是穷举方法。

为了避免陷入重复验证，应保证验证过的可能解不再被验证。对于线性问题来说，处理次序依次即可，而对于非线性问题，就需要用到一些特定的方法，比如树形结构的前序遍历、中序遍历和后序遍历；图结构的宽度优先有哪些信誉好的足球投注网站和深度优先有哪些信誉好的足球投注网站等。在设计时一般都是用循环语句和判断语句来实现。使用循环是枚举所有的情况，使用判断是验证当前的状态是否满足问题的所有条件。若满足，则找到问题的一个解，可以结束，如需要求其他解，则继续循环；若不满足，则继续循环验证其他状态。2.2蛮力法的设计思想

2.2蛮力法的设计思想基本格式：for(循环变量x取所有可能的值){┇if(x满足指定的条件)输出x;┇}

2.2蛮力法的设计思想使用蛮力法通常有如下几种情况：有哪些信誉好的足球投注网站所有的解空间：问题的解存在于规模不大的解空间中。有哪些信誉好的足球投注网站所有的路径：这类问题中不同的路径对应不同的解。直接计算：按照基于问题的描述和所涉及的概念定义，直接进行计算。往往是一些简单的题，不需要算法技巧的。模拟和仿真：按照求解问题的要求直接模拟或仿真即可。

2.2蛮力法的设计思想编写一个程序，输出2～1000之间的所有完全数。完全数定义：该数的各因子（除该数本身外）之和正好等于该数本身，例如：6=1+2+3，28=1+2+4+7+14分析：解的范围：2～1000，范围小，适合采用蛮力法穷举方法：依次即可条件比对：1到n/2中依次验证是否为n的约数，如是则累加，最终判断是否和n相等

2.2蛮力法的设计思想伪代码：PerfectNum(N)输入：整数N，表示寻找2～N之间所有的完全数。输出：2～N中所有的完全数forn←2toNdo //解空间的范围sum←1fori←2ton/2doifi整除nthensum←sum+i //若是约数，则累加endifendforifsum=nthen //若约数之和与原数相等，则是完全数输出nendifendfor

2.2蛮力法的设计思想C源代码：#includestdio.h#includemath.hvoidPerfectNum(intN){intsum,n,i; for(n=2;n=N;n++){ sum=1; for(i=2;isqrt(n);i++){ if(n%i==0){ sum+=i; if(n/i!=i)sum+=n/i; }} if(sum==n){ printf(%d\t,n); } }}voidmain(){ PerfectNum(1000);}

2.3蛮力法的典型实例蛮力法适用于很多场景，具体来说，