作业答案合并版

第一章1.结合实际,简述算法设计和分析的目的和意义。解：算法就是一个非确定的计算过程，是一个求解良说明的计算问题的工具。简单的说，算法描述了一个特定的计算过程来实现输入到输出的关系。算法最重要的品质是效率。如果现实社会中，计算机的存储的免费的，计算机的速度是无限快的，那么算法也就没有研究的意义了。但是这两点在现实生活中都不存在，所以研究更有效率的算法是有意义的。举一个很简单的例子，对于矩阵连乘问题，不同的计算顺序可能效率之间相差几十甚至几百倍。对于实际运用中，比如计算天气问题，我们需要一种有效的方法，使得能在可以接受的效率下解决这个问题。这就是研究算法的目的和意义。2.欧几里德算法利用算术基本定理(任何一个正整数去除另一个正整数,必然产生商和余数,且余数大于等于0而严格小于商)求解正整数m;n的最大公因数gcd(m;n)。试完成下列各题:(1)写出欧几里德算法;(2)用循环不变量方法证明欧几里德算法的正确性;(3)最大公因数问题的输入大小为log2a,log2b,分别将算法中进行的求余操作和赋值操作的次数表示成log2a,log2b的函数,并由此得出欧几里德算法的渐近复杂性。解：(1)欧几里德算法实现gcd(a,b)1r=a%b2whiler̸=03do4a=b5b=r6r=a%b7returnb(2)取循环不变量为gcd(a;b)=m是我们所要求的最大公约数初始化：首先在我们迭代之前，a=a,b=b，所以我们的循环不变式成立。保持：在每次迭代一次之后，a=b,b=a%b，现在我们要证明gcd(a;b)=gcd(b;a%b)。设gcd(a;b)=m，可以得到a=mn1,b=mn2且gcd(n1;n2)=1又可以得到a=bk+a%b，所以a%b=mn1mn2k)a%b=m(n1n2k)，所以gcd(b;a%b)=mgcd(n2;(n1n2k))=m。终止：r是一个非负整数，每一次循环一定会使得r减小，也就是说最多经过r次循环后，r会减小到0，使得r=0，然后退出循环。(3)欧几里德算法的渐进复杂性：引理1：设mn，则r=m%nm/2。证：当⌊m/n⌋=1时，r=mnn；1当⌊m/n⌋1时，r=m⌊m/n⌋nnmn；综上所述：r=m%nmin(mn;n)当nm/2时，nmn；当nm/2时，mnn且mnm/2。所以可得：r=m%nmin(mn;n)m/2，引理1得证。对于欧几里德算法，设输入为a，b且ab，连续进行两次循环迭代后。由引理1得：r2=b%(a%b)b/2。迭代2k次之后：r2kb/2k。最后当r2k=1时算法结束，这时k=log2b，总迭代次数最多为2k=2log2b。所以欧几里德算法的时间复杂度为O(log(min(a;b)))。3.理解下面的插入排序算法,并完成后面的分析。插入排序算法InsertSort1fori2ton2do3keyA[i];4ji1;5whilej0且A[j]key6do7A[j+1]A[j];8jj1;9A[j+1]key;(a)证明算法必然停止;(b)利用循环不变量方法,证明算法的正确性。(c)分别分析最坏情况下、最好情况下、平均情况下算法执行的比较操作次数和赋值操作次数,将分析结果表示成n的函数。分析平均复杂度是,假设所有输入服从均匀分布。解：(a)证明：内层while循环从j=i1开始，每次循环jj1，最终到j=0内层循环会退出。外层for循环终止的条件是in。因为每次循环迭代i增加1，那么必然有i=n+1，因此算法必然停止。(b)证明：循环不变式：在每次循环开始前，A[1;


;i1]包含来原来的A[1;


;i1]的元素，并且已经排好序。初始化：当i=2时，A[1;


;i1]=A[1]，已经排好序了，循环不变式成立。保持：已知在循环迭代开始前，A[1;


;i1]已排好序，而循环体的目的是将A[1;


;i1]中大于A[i]的数向后移，再把A[i]插入A[1;


;i1]中，使得A[1;


;i]排好序，这时A[1;


;i]中的元素由原来A[1;


;i1]中元素组成，并且已经排好序了，循环不变式成立。终止：最后i=n+1，并且A[1;


;n]已排好序，而A[1;


;n]就是整个数组，循环不变式成立，因此证毕。2(c)该算法在第5行执行比较操作，第1、3、4、7、8、9行执行赋值操作。最坏情况下：输入数组反向排序时导致最坏情况，必须将每个元素A[i]与整个已排序子数组A[1:i1]中的每个元素进行比较。算法第5行执行的比较次数为：∑ni=2i=(n+2)(n1)2。算法执行的赋值次数为:第1行为n，第3行为n-1，第4行n-1，第7行为∑ni=2(i1)=n(n1)2，第8行为∑ni=2(i1)=n(n1)2，第9行为n-1。因此算法总的赋值次数为n2+3n3。最好情况下：输入数组已经排好序时导致最好的情况，无需移动；算法执行的比较次数为n-1；赋值次数为n+(n1)+(n1)+(n1)=4n3。平均情况下：(a)比较次数：假设插入第k个元素时，其插入的位置为j，1jk。则需要比较k-j+1次，所以其平均比较次数为：1kk∑j=1(kj+1)=1k[k2k(k+1)2+k]=k+12。插入n个元素时，算法总平均比较次数为：n∑k=2(k+12)=12[(n+1)(n+2)2]=14n2+34n+1。(b)赋值次数：假设插入第k个元素时，其插入位置为j，1jk，第7行执行的赋值次数为k-j，因此平均赋值次数为：1kk∑j=1(kj)=1k[k2k(k+1)2]=k12。因此，插入n个元素时，第7行总的赋值次数为：n∑k=2(k12)=12[n(n1)2]=14n214n。则算法总的赋值次数为：n+(n1)+(n1)+2(14n214n)+(n1)=12n2+72n3。4.结合你曾进行过的程序设计过程或算法设计过程,说明算法基本技术、基本算法和问题特征分析三者间的关系。解：对于一个计算问题的解决，我们可以通过采用算法的基本技术对问题进行分析求解，不同的技术分析方法不同，要分析问题可计算否，能行可计算否，然后根据分析的结果，采用基本的算法用计算机语言进行算法实现，最终解决这个计算问题。3第二章1.证明：(f(n))+(g(n))=(f(n)+g(n))解：由已知条件可得：存在正常量c1，c2，n1，使得nn1，有0c1f(n)(f(n))c2f(n)。存在正常量c3，c4，n2，使得nn2，有0c3g(n)(g(n))c4g(n)。取c5=min(c1;c3)，c6=max(c2;c4)，n3=max(n1;n2)由上面的式子可得：存在c5，c6，n3，使得nn3，有0c5f(n)c1f(n)(f(n))c2f(n)c6f(n)。存在c5，c6，n3，使得nn3，有0c5g(n)c3g(n)(g(n))c4g(n)c6g(n)。所以，存在c5，c6，n3，使得nn3，有0c5f(n)+C5g(n)(f(n))+(g(n))c6f(n)+c6g(n)。综上所述：(f(n))+(g(n))=(f(n)+g(n))。2.证明：f(n)=O(g(n)),g(n)=Ω(f(n))解：当f(n)=O(g(n))时，得到存在正常量c1，n1，使得nn1，有0f(n)c1g(n)。取c2=1c1，则存在正常量c2，n1，使得nn1，有0c2f(n)g(n)。就可以得到g(n)=Ω(f(n))。当g(n)=Ω(f(n))时，得到存在正常量c1，n1，使得nn1，有0c1f(n)g(n)。取c2=1c1，则存在正常量c2，n1，使得nn1，有0f(n)c2g(n)。就可以得到f(n)=O(g(n))。3.证明课件中列出的复杂性函数阶的各种性质(传递性、自反性、反对称性)解：传递性：f(n)=(g(n))^g(n)=(h(n)))f(n)=(h(n))。由已知得：存在正常量c1，c2，n1，使得nn1，有0c1g(n)f(n)c2g(n)。存在正常量c3，c4，n2，使得nn2，有0c3h(n)g(n)c4h(n)。我们取c5=c1c3，c6=c2c4，n3=max(n1;n2)由上面的式子可得：存在c5，c6，n3，使得nn3，0c1c3h(n)c1g(n)f(n)c2g(n)c2c4h(n)就可以得到：f(n)=(h(n))，传递性得证。自反性：f(n)=(f(n))。容易找到正常量c1=1，c2=1，n1=1，使得nn1时，有0c1f(n)f(n)c2f(n)。所以可以得到f(n)=(f(n))。反对称性：f(n)=O(g(n)),g(n)=Ω(f(n))。4我们先证明f(n)=O(g(n)))g(n)=Ω(f(n))。由已知得：存在正常量c1，n1，使得nn1，有0f(n)c1g(n)。我们取c2=1c1，则存在正常量c2，n1，使得nn1，有0c2f(n)g(n)。就可以得到g(n)=Ω(f(n))。接下来我们来证明g(n)=Ω(f(n)))f(n)=O(g(n))。由已知得：存在正常量c1，n1，使得nn1，有0c1f(n)g(n)。我们取c2=1c1，则存在正常量c2，n1，使得nn1，有0f(n)c2g(n)。就可以得到f(n)=O(g(n))。4.证明:对任意正整数常数k，logk(n)=o(n)。解：我们先给出原问题的一个等价命题：对任意正整数常数k，limn!1logk(n)n=0。如果该命题成立，则可以得到8c0;9n00使得nn0时，logk(n)n0c成立。由这个可以得到logk(n)cn，即logk(n)=o(n)。利用洛比达法则，对分子分母同时求导，limn!1logk(n)n=limn!1klogk1(n)n连续利用洛比达法则k次，可以得到limn!1logk(n)n=limn!1k!n=0，命题得证。所以原命题logk(n)=o(n)成立。5.证明：logn!=(nlogn)解：我们先证明logn!=O(nlogn)。logn!=n∑i=1login∑i=1logn=nlogn=O(nlogn)。再来证明logn!=Ω(nlogn)。logn!=n∑i=1login∑i=n/2lognn∑i=n/2logn2=n2logn2=n2lognn2log2。当n4时，n2lognn2log214nlogn恒成立。所以logn!=Ω(nlogn)成立。综上所述，logn!=(nlogn)。6.对于任意实数r1，令Hr(n)=11r+12r+13r+


+1nr。证明：Hr(n)=(1)。解：我们先来证明Hr(n)=Ω(1)。显然，Hr(n)1,所以Hr(n)=Ω(1)成立。接下来证明Hr(n)=O(1)。Hr(n)=11r+12r+13r+


+1nr=1+∑ni=21ir1+∫n11xrdx=1+1r1x1rjn1=1+1r1(n1r1)又因为r1)1r0并且n2，所以n1r10。5所以可以得到Hr(n)1，所以Hr(n)=O(1)。综上所述，Hr(n)=(1)，命题得证。7.证明：⌈log(n+1)⌉=⌊logn⌋+1对任意正整数n成立。解：设⌊logn⌋=k0。则klognk+1)2kn2k+1。又因为n是一个正整数，则2kn2k+11可以得到2k+1n+12k+1)log(2k+1)log(n+1)log(2k+1)。又因为log(2k+1)log2k=k所以可以得到klog(n+1)log(2k+1)=k+1。所以⌈log(n+1)⌉=k+1=⌊logn⌋+1，命题得证。8.证明:对于任意正整