湖南工程学院计算机算法分析与设计期末考试复习资料

《湖南工程学院计算机算法分析与设计期末考试复习资料》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、湖南工程学院计算机算法分析与设计期末考试复习资料算法是指解决问题的一种方法或一个过程。算法是若干指令的有穷序列，满足性质：(1)输入：有外部提供的量作为算法的输入。(2)输出：算法产生至少一个量作为输出。(3)确定性：组成算法的每条指令是清晰，无歧义的。(4)有限性：算法屮每条指令的执行次数是有限的，执行每条指令的时间也是有限的。程序是算法用某种程序设计语言的具体实现。程序可以不满足算法的性质(4)。分治法的设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破,分而治之。直接或间接地调用口身的算法称为递归算法。用函数口身给岀定义的

2、函数称为递归函数。1•阶乘函数阶乘函数可递归地定义为：[1/?=0边界条件[咒(兀一1)!7?>0递归方程边界条件与递归方程是递归函数的二个要素2.Fibonacci数列无穷数列1,1,2,3,5,8,13,21,34,55,•・•…，称为Fibonacci数列。它可以递归地定义为:1n=0F(JT)=<1n=1F(n-I)+F(n-2)n>当一个函数及它的一个变量是由函数自身定义时，称这个函数是双递归函数。Ackerman函数A(n,m)定义如下：A(l,0)=2A(0,m)-1m>0A(/i,0)=n+2n>2A(n,m)=A(A(n-1,m),m一1)

3、/?,m>1Ackerman函数A(n,m)的自变量m的每一个值都定义了一个单变量函数：M=0时，A(n,0)=n+2M=1时，A(n,l)=A(A(n-l,1),0)=A(n-1,1)+2,和A(1,1)=2故A(n,l)=2*nM=2时,A(n,2)=A(A(n-1,2),1)=2A(n-1,2),和A(1,2)=A(A(0,2),1)=A(1,1)=2,故A(n,2)=2An。M二3吋，类似的可以推出M=4时，A(n,4)的增长速度非常快，以至于没有适当的数学式子來表示这一函数。定义单变量的Ackerman函数A(n)为，A(n)=A(n,n)。定义其拟

4、逆函数a(n)为：a(n)=min{kIA(k)^n}o即a(n)是使nWA(k)成立的最小的k值。a(n)在复杂度分析中常遇到。对于通常所见到的正整数n,有a(n)W4。但在理论上a(n)没有上界，随着n的增加，它以难以想象的慢速度趋向正无穷大。6排列问题设计一个递归算法生成n个元素{rl,r2,...,m}的全排列。设R二{rl,r2,...,ni}是要进行排列的n个元素，Ri=R-{ri}0集合X屮元素的全排列记为perm(X)□(ri)perm(X)表示在全排列perm(X)的每一个排列前加上前缀得到的排列。R的全排列可归纳定义如下：当n=l时,per

5、m(R)=(r),其中i•是集合R中唯一的元素;当n>l时，perm(R)由(rl)perm(Rl),(r2)perm(R2),...»(rn)perm(Rn)构成。7整数划分问题在本例屮，如果设p(n)为正整数n的划分数，则难以找到递归关系，因此考虑增加一个白变量：将最大加数nl不大于m的划分个数记作q(n,m)。可以建立q(n,m)的如下递归关系。(3)q(n,n)=l+q(n,n-l);正整数n的划分由nl=n的划分和nl^n-1的划分组成。n=1,m=1nm>l(4)q(n,m)=q(n,m-l)+q(n-m,m),n>m>1;正整数n的

6、最大加数nl不大于m的划分由nl=m的划分和1/、ri）q（njn）=

7、ib,inic){if(n>0){hanoi(n-l,a,c,b);move(a,b);hanoi(n・l,c,b,a);}}递归小结:优点：结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性，因此它为设计算法、调试程序带来很大方便。缺点：递归算法的运行效率较低，无论是耗费的计算吋间还是占用的存储空I'可都比非递归算法要多。分治法的适用条件分治法所能解决的问题一般具有以下几个特征：1•该问题的规模缩小到一定的程度就可以容易地解决；2.该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质3.利用该问题分解出的子问题的解可以合并为该问题的解

8、；4.该问题所分解出的各个子问题是相互