数据结构与算法C2

第二章程序设计基本策略与方法递归、逐步求精、分治是基本的算法（程序）设计策略与方法。许多复杂问题，使用它们都可迎刃而解。这几种策略与方法在后面要经常使用，这里先介绍它们的基本思想，进一步的例子将在后面的章节中见到。做为基础，我们先介绍算法的概念2.1算法的基本概念2.1.1算法的概念一、算法的概念一个算法是规则的有穷序列，它为解决某一特定类型的问题规定了一个运算过程，并且具有下列特性：有穷性：一个算法必须在执行有穷步之后结束。确定性：算法的每一步必须是确切定义的，对于每种情况，有待执行的每种动作必须严格地和清楚地规定。可行性：算法应该是可行的，这意味着算法中所有有待实现的运算都是基本的，即它们都可由相应的基本计算装置所理解，并可通过有穷次运算即可完成。输入：一个算法有零个或多个输入，它们是在算法所需的初始量或被加工的对象的表示。这些输入取自特写的对象集合。输出：一个算法有一个或多个输出，它们是与输入有特定关系的量二、什么是“好”的算法通常，从下列几个方面衡量算法的优劣：正确性。也称有效性，是指算法能满足具体问题的要求。亦即对任何合法的输入，算法都会得出正确的结果。可读性。指算法被理解的难易程度。人们现在常把算法的可读性放在比较重要的位置，主要是因为晦涩难懂的算法不易交流、推广使用，也难以修改、扩展与调试，而且可能隐藏较多的错误。可读性实质上强调的是：越简单的东西越美。健壮性（鲁棒性）。是指对非法输入的抵抗能力。它强调的是，如果输入非法数据，算法应能加以识别并做出处理，而不是产生误动作或陷入瘫痪。时间复杂度与空间复杂度。时间复杂度是指算法的运行的时间消耗，同一个问题，不同的算法可能有不同的时间复杂度。2.1.2算法时间复杂度与空间复杂度简单地讲，算法的时间复杂度是指算法的运行的时间消耗的大小，但这里的“运行”，是指抽象的运行，并不是指在具体机上的运行。一个算法在具体计算机上的运行速度，不仅取决于算法本身，而且与目标计算机（运行算法的计算机）的速度有关，如果算法是用非目标指令（如汇编语言、高级语言等）描述的，则运行速度还与描述语言的编译器所生成的目标代码的质量（或解释器本身的质量）有关。算法的时间复杂度指算法自身的抽象运行的时间消耗，与运行算法的目标计算机及描述算法的工具无关一、相关因素算法的时间复杂度与下列因素有关：问题性质：有的问题比较复杂，而有的比较简单；问题规模：同一问题，同一算法，其处理的对象的规模不同，则耗时也不同；算法性质：同一问题，不同的解决方法，效率也不同。一个算法的时间复杂度通常用函数描述（时间复杂度函数）。时间复杂度函数通常可以描述为输入规模的函数。输入规模可以是输入量或输出量，或两者之和，也可以是某种测度（如数组维数、图的边数等），它可用一个或多个量代表下面举一个简单的例子。[例]考虑计算三次多项式ax3+bx2+cx+d一种直接的计算方法是：s=a*x*x*x+b*x*x+c*x+d;该算法共执行6次乘法，3次加法。考察另一种解法：s=a;s=s*x+b;s=s*x+c;s=s*x+d;该算法共进行3次乘法，3次加法。显然该算法的计算量少于前一种方法，尽管其看上去较复杂。第二种算法基于的原理是逐步提取共因子：a*x*x*x+b*x*x+c*x+d=(ax+b)x2+cx+d=((ax+b)x+c)x+d二、复杂度的渐近表示常用的上界函数有log(n),nm,an,n!下面给出几种常见的函数的比较关系：即当n充分大时，下列关系成立：O(a)O(logn)O(n)O(n.logn)O(n2)...O(nm)O(an)O(n!)O(nn)这里，n为自变量，a和m为常数定理2-1若A(n)=amnm+…+a1n+a0是关于n的一个m次多项式，则A(n)=O(nm)三、算法的时间复杂度的分类多项式时间复杂度算法：渐近函数为多项式，或变化率不超过多项式。指数时间复杂度算法：渐近函数变化率超过多项式，这类算法也称NP-困难的算法。2.1.3算法时间复杂度的度量语句频度（FrequencyCount）是指语句被重复执行的次数。即对某语句，若在算法的一次运行中它被执行n次，则它的语句频度为n。语句频度也可称为程序步数我们用算法中的各语句的语句频度之和表示算法的时间复杂度[例1.8]考虑下列子程序，它的功能是求出数组a中各数的大小次序号，存入数组b中的对应位置。例如，若a[]={4,2,3,9,6,8,7},则程序结束后，数组b内容为b[]={3,1,2,7,4,6,5},表示4，2，3，9，6，8，7的大小次序分别为3，1，2，7，4，6，5。voidOrderNumbers(int*a,intn,int*b){inti,j;for(i=0;in;i++)b[i]=1;………………………..(1)：nfor(i=0;in-1;i++)………………………………(2)：n-1for(j=i+1;jn;j++)………………………………(3)：(n-i-1)if(a[i]a[j])………………………………….(4)：(n-i-1)b[j]++;…………………………………..(5)：最多为(n-i-1)elseb[i]++;return;}总的语句频度最大为：n+(n-1)+3∑(n-i-1)=2n-1+3(n-1)n/2=3n2/2+7n/2–1=O(n2)2.2穷举/试探法穷举法的基本思想是，分别列举出各种可能解，测试（试探）其是否满足条件（是否是欲求的解），若是，则输出之。这里举一个解不定方程的例子。不定方程（组）是指因为独立方程个数少于变量个数而导致方程有多解的方程。例如，2x+3y=20就是一个不定方程。解这个方程，就是求出所有的解。不定方程一般都有限定条件，我们这里考虑正整数解的情况。解这个方程，一个简单的做法是，让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;2.3递推法与迭代法递推法与迭代法是两种风格类似的方法，它们都是基于分步递增方式进行求解，在许多其他更深入的算法设计方法中，都要结合这两种方法2.3.1递推法递推法是针对这样一类问题：问题的解决可以分为若干步骤，每个步骤都产生一个子解（部分结果），每个子解都是由前面若干子解生成，它们都与问题规模相关，是相对于所相关的问题规模的完整解。不同的子解，其所相关的问题规模也随子解不同而递增。我们把这种由前面的子解得出后面的子解的规则称为递推关系。例如，对于Fibonacci（1175~？，意大利数学家）数列：112358132134…设f(n)表示数列中第n项，则有：f(1)=1f(2)=1f(k)=f(k-1)+f(k-2)递推法的运用有如下两个关键：寻找递推关系：这是最重要的问题。递推关系有解析和非解析两种。解析递推关系是指能用一般数学公式描述的关系，也称递推公式。非解析递推关系是指不能用一般的数学公式描述的关系，这类关系的描述，也许本身就是一个过程。递推计算：递推计算的具体实现，可有非递归和递归两种。非递归是自底向上计算，即按子解规模的先小后大的次序递推计算，递归计算是指使用递归法计算，其形式上是自顶向下。关于递归法，我们将在后面集中讨论。2.3.2迭代法迭代法和递推法类似，也是递增求解，但不同的是，递推法中，每步得到的解都是相对于对应问题规模的完整解，但对迭代法，中间步骤得到的解一般只是“近似解”，并不代表子问题的解（常常没有明确的子问题）例：求a的平方根floatSqrt(floata){floatprecision=0.0001;//定义解的精度floatx,x0;x=1;do{x0=x;x=1+(a-1)/(x+1);}while(x-x0precision||x0-xprecision);//当最近两个近似解的差的绝对值小于给定精度时结束returnx;}2.4递归2.4.1递归与递归程序的概念递归(Recursion)是一种描述与解决问题的基本方法，用来解决一类可归纳描述的问题，或说可分解为结构自相似的问题。所谓结构自相似，是指构成问题的部分与问题本身在结构上相似。这类问题具有的特点是：整个问题的解决，可以分为两大部分：第一部分：是一些特殊（基础）情况，有直接的解法，即始基；第二部分：这部分与原问题“相似”，可用类似（与整个问题的解法类似）的方法解决（即递归），但比原问题的规模小这类问题在数学中很常见。例如，计算阶乘：F(0)=0F(n)=n*F(n-1)当n0在该式中，f(n-1)的计算与原问题f(n)的计算“相似”，只是规模较小。在看算术求和：也有许多非算术计算问题可用递归方法解决。例如，设一维数组A的元素A[k1]~A[k2]中存放整数，现要求出它们中最大者，递归求法为：a)若k1=k2，则A[k1]即为所求；b)若k1k2，则先按类似的方法，求出A[k1+1]~A[k2]中最大者，设其为m，然后，比较A[k1]和m，二者中最大者即为所求。例如，关于阶乘的计算，可通过下列的递归程序：longFact(intn){if(n=0)return1;//第一部份，始基elsereturnn*Fact(n-1);//第二部份，用实参n-1递归调用}再如，在一维数组中求最大值的程序为：intGetMax(inta[],intk1,intk2){intm;if(k1==k2)returna[k1];m=GetMax(a,k1+1,k2);if(a[k1]m)returna[k1];elsereturnm;}2.4.2递归程序设计要点划分问题、寻找递归：许多问题，并没有明显的递归解法，这就需要寻找递归方案。首先要试着看能否把问题的处理分为两大类情况。一类情况是可以直接解决（不需要递归，为基本情况），另一类情况可按与原问题的解法（即现在正使用的解法）类似的解法进行（称为递归情况）。设计函数、确定参数：使用递归，必须设计为子程序（函数或过程）的形式。子程序的参数尤为重要，决定着递归的实现。递归子程序中的参数，除了应具有一般子程序所需要的参数外，还需要递归参数。设置边界、控制递归：递归中，第一类情况（非递归的情况）就起到循环条件的作用，这是因为，满足第一类情况时，就不递归调用了，本次调用即可结束。把第一类情况的判别条件称为递归控制条件。2.4.3递归程序执行机理一、一般子程序的执行方式对大多数的程序设计语言，子程序的调用执行都基于先进后出存储设备----栈。程序运行时，设置一个栈，称为运行栈。每调用一次子程序，就要为被调程序的各实在参数和临时变量分配存储空间。这种存储空间一般是分配在运行栈中的。子程序结束后，进行相应的退栈，释放本次调用所分配的栈空间。一递归子程序的执行方式二、递归子程序的执行方式递归子程序的执行（调用），仍然遵循一般子程序的执行方式，需要注意的是，将每次递归调用都视为不同子程序的调用，即每次递归调用，都将递归子程序的实在参数和各临时变量进栈，做为栈中的新的一项。据此可知下面的子程序是个不能终止的过程（相当于无限循环），且会无休止地进栈，直至可用内存耗尽Hanoi塔问题出现在19世纪的欧洲，用来比喻世界的寿命。问题是这样的，设有三根钻石杆，分别编为A号、B号和C号，在A号杆上堆叠64个金盘，每个盘大小（半径）不同，只允许小盘在大盘之上。最底层的盘最大。现在要求将A号杆上的盘全部移到C号杆，在移的过程中可以借助B号杆（以B号杆为中转）。规定每次移一个盘，并且在任何时刻，只能移最上面的盘，且大盘不能放在小盘上面。我们现在考虑编写计算机程序，使其给出移盘的过程。很显然，将n个盘子从A移到C，可以按如下步骤进行：借助C，将A上的最上面的n-1个盘子按规定移到B将A上的最底层的一个盘子移到C借助A，将B上的n-1个盘子按规定移到C这是个递归过程。为了编程方