数据结构与算法-ch10Algorithmdesigntechniques.pptVIP

* * Ch10 算法设计技术(Algorithm Design Techniques) 10.1 穷举法（Exhaustive Algorithm） 10.2 递推法与迭代法 （ Recurrence and Iterative Algorithm ） 10.3 递归（ Recursive Algorithm ） 10.4 逐步求精（ Stepwise Refinement ） 10.5 分治法（ Divide and Conquer ） 10.6 贪心法（ Greedy Algorithm ） 10.7 回溯法（ Backtracking Algorithm ） 10.8 动态规划法（ Dynamic Programming ） 10.9 分支界限法（ Branch and Bound Algorithm ） 10.10 随机化算法（ Randomized Algorithm ） Summary 10.1 穷举法（Exhaustive Algorithm） 穷举法(枚举法/试探法) 基本思想是： 分别列举出各种可能解，测试（试探）其是否满足条件（是否是欲求的解），若是，则输出之。 特点是算法简单，但是运算量大。当问题的规模变大，执行的的速度变慢。 10.1 穷举法（Exhaustive Algorithm） [例]解不定方程。不定方程（组）是指独立方程个数少于变量个数而导致方程有多解。 如，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\ni,j; 10.2 递推法与迭代法 （Recurrence and Iterative Algorithm） 递推法与迭代法是两种风格类似的方法，它们都是基于分步递增方式进行求解。 （1）递推法（Recurrence Algorithm） 递推法是针对这样一类问题：问题的解决可以分为若干步骤，每个步骤都产生一个子解（部分结果），每个子解都是由前面若干子解生成。 把这种由前面的子解得出后面的子解的规则称为递推关系。 例如，对于Fibonacci数列： 1 1 2 3 5 8 13 21 34 … 设f(n)表示数列中第n项，则有： f(1) = 1 f(2) = 1 f(k) = f(k-1) + f(k-2) 递推法实现Fibonacci数列 int Fibonacci(int n) { int f1, f2, f3; int k; f1 = 1 ; f2 = 1 ; if ( n==1 ) return 1; if ( n==2 ) return 1; for (k=3; k=n; k++) { f3 = f1 + f2; f1 = f2; f2 = f3; } return f3; } 非递归 递推法运用的关键 寻找递推关系：递推关系有解析和非解析两种。 （1）解析递推关系是指能用一般数学公式描述的关系，也称递推公式。 （2）非解析递推关系是指不能用一般的数学公式描述的关系，这类关系的描述，也许本身就是一个递推过程。 递推关系必须有始基（最小子解）。如上例中，f1=1, f2=1 （2）迭代法（Iterative Algorithm） 迭代法和递推法类似，也是递增求解。 不同： 递推法每步得到的解都是相对于对应问题规模的完整解。 迭代法中间步骤得到的解一般只是“近似解”，并不代表子问题的解（常常没有明确的子问题）。 当误差达到可接受的范围时，则认为“近似解”就是需要的结果。 例：求a的平方根(迭代法) float Sqrt(float a){ float precision=0.0001; //定义解的精度 float x, x0; x=1; do { x0=x; x = 1+(a-1)/(x+1); } while (x-x0precision || x0-xprecision); //当最近两个近似解的