数据结构与算法-ch10Algorithmdesigntechniquesppt课件.ppt

《数据结构与算法-ch10Algorithmdesigntechniquesppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、Ch10算法设计技术(AlgorithmDesignTechniques)10.1穷举法（ExhaustiveAlgorithm）10.2递推法与迭代法（RecurrenceandIterativeAlgorithm）10.3递归（RecursiveAlgorithm）10.4逐步求精（StepwiseRefinement）10.5分治法（DivideandConquer）10.6贪心法（GreedyAlgorithm）10.7回溯法（BacktrackingAlgorithm）10.8动态规划法（DynamicPro

2、gramming）10.9分支界限法（BranchandBoundAlgorithm）10.10随机化算法（RandomizedAlgorithm）Summary10.1穷举法（ExhaustiveAlgorithm）穷举法(枚举法/试探法)基本思想是：分别列举出各种可能解，测试（试探）其是否满足条件（是否是欲求的解），若是，则输出之。特点是算法简单，但是运算量大。当问题的规模变大，执行的的速度变慢。10.1穷举法（ExhaustiveAlgorithm）[例]解不定方程。不定方程（组）是指独立方程个数少于变量个数而导

3、致方程有多解。如，2x+3y=20是一个不定方程（设x,y为正整数）。解这个方程，就是求出所有的解。不定方程一般都有限定条件，我们这里考虑正整数解的情况。解这个方程，一个简单的做法是，让x和y分别遍取0到20内的正整数，并代入方程计算，若值为20，则表示找到一组解。具体的程序片断如下。for(i=0;i<=20;i++)for(j=0;j<=20;j++)if(2*i+3*j==20)cout<<""<

4、推法与迭代法是两种风格类似的方法，它们都是基于分步递增方式进行求解。（1）递推法（RecurrenceAlgorithm）递推法是针对这样一类问题：问题的解决可以分为若干步骤，每个步骤都产生一个子解（部分结果），每个子解都是由前面若干子解生成。把这种由前面的子解得出后面的子解的规则称为递推关系。例如，对于Fibonacci数列：112358132134…设f(n)表示数列中第n项，则有：f(1)=1f(2)=1f(k)=f(k-1)+f(k-2)递推法实现Fibonacci数列intFibonacci(intn){in

5、tf1,f2,f3;intk;f1=1;f2=1;if(n==1)return1;if(n==2)return1;for(k=3;k<=n;k++){f3=f1+f2;f1=f2;f2=f3;}returnf3;}非递归递推法运用的关键寻找递推关系：递推关系有解析和非解析两种。（1）解析递推关系是指能用一般数学公式描述的关系，也称递推公式。（2）非解析递推关系是指不能用一般的数学公式描述的关系，这类关系的描述，也许本身就是一个递推过程。递推关系必须有始基（最小子解）。如上例中，f1=1,f2=1（2）迭代法（Itera

6、tiveAlgorithm）迭代法和递推法类似，也是递增求解。不同：递推法每步得到的解都是相对于对应问题规模的完整解。迭代法中间步骤得到的解一般只是“近似解”，并不代表子问题的解（常常没有明确的子问题）。当误差达到可接受的范围时，则认为“近似解”就是需要的结果。例：求a的平方根(迭代法)floatSqrt(floata){floatprecision=0.0001;//定义解的精度floatx,x0;x=1;do{x0=x;x=1+(a-1)/(x+1);}while(x-x0>precision

7、

8、x0-x>prec

9、ision);//当最近两个近似解的差的绝对值小于给定精度时结束returnx;}10.3递归（RecursiveAlgorithm）（1）递归与递归程序的概念递归(Recursion)用来解决一类可归纳描述的问题，或说可分解为结构自相似的问题。所谓结构自相似，是指构成问题的部分与问题本身在结构上相似。这类问题具有的特点是：整个问题的解决，可以分为两大部分：一些特殊（基础）情况，有直接的解法，即始基；这部分与原问题“相似”，可用类似（与整个问题的解法类似）的方法解决（即递归），但比原问题的规模小。递归问题在数学中很常见

10、。例如，计算阶乘：F(0)=1F(n)=n!=n*F(n-1)当n>0在该式中，f(n-1)的计算与原问题f(n)的计算“相似”，只是规模较小。例如，算术求和：S(0)=0S(n)=k=S(n-1)+n10.3递归（RecursiveAlgorithm）阶乘的计算，可通过下列的递归程序：longFact(intn){if(n<=0