北航计算机研究生课程-算法设计与分析-HomeWork-1

一、已知下列递推式：C(n)=1若n=1=2C（n/2）+n–1若n≥2请由定理1导出C(n)的非递归表达式并指出其渐进复杂性。定理1：设a,c为非负整数，b,d,x为非负常数，并对于某个非负整数k,令n=ck,则以下递推式f(n)=d若n=1=af(n/c)+bnx若n=2的解是f(n)=bnxlogcn+dnx若a=cxf(n)=xxxaxxncabcncabcdclog若a≠cx解：令F(n)=C(n)–1则F(n)=0n=1F(n)=2C(n/2)+n–2n=2=2[F(n/2)+1]+n–2=2F(n/2)+n利用定理1，其中：d=0,a=2,c=2,b=1,x=1,并且a=cx所以F(n)=nlog2n所以C(n)=F(n)+1=nlog2n+1C(n)的渐进复杂性是O(nlog2n)二、由于Prim算法和Kruskal算法设计思路的不同，导致了其对不同问题实例的效率对比关系的不同。请简要论述：1、如何将两种算法集成，以适应问题的不同实例输入；2、你如何评价这一集成的意义？答：1、Prim算法基于顶点进行搜索，所以适合顶点少边多的情况。Kruskal从边集合中进行搜索，所以适合边少的情况。根据输入的图中的顶点和边的情况，边少的选用kruskal算法，顶点少的选用prim算法2、没有一个算法是万能的，没有一个算法是对所有情况都适合的。这一集成体现了针对具体问题选用最适合的方法，即具体问题具体分析的哲学思想。三、分析以下生成排列算法的正确性和时间效率：HeapPermute(n)//实现生成排列的Heap算法//输入：一个正正整数n和一个全局数组A[1..n]//输出：A中元素的全排列ifn=1writeAelsefori←1tondoHeapPermute(n-1)ifnisoddswapA[1]andA[n]elseswapA[i]andA[n]解：n=1时，输出a1n=2时，输出a1a2，a2a1n=3时，(1)第一次循环i=1时，HeapPermute(2)将a1a2做完全排列输出，记为[a1a2]a3，并将A变为a2a1a3，并交换1,3位，得a3a1a2(2)第二次循环i=2时，HeapPermute(2)输出[a3a1]a2，并将A变为a1a3a2，交换1,3位，得a2a3a1(3)第三次循环i=3时，HeapPermute(2)输出[a2a3]a1，并将A变为a3a2a1，交换1,3位，得a1a2a3，即全部输出完毕后数组A回到初始顺序。n=4时，(1)i=1时，HeapPermute(3)输出[a1a2a3]a4，并且a1a2a3顺序不变，交换1,4位，得a4a2a3a1(2)i=2时，HeapPermute(3)输出[a4a2a3]a1，并且a4a2a3顺序不变，交换2,4位，得a4a1a3a2(3)i=3时，HeapPermute(3)输出[a4a1a3]a2，并且a4a1a3顺序不变，交换3,4位，得a4a1a2a3(4)i=4时，HeapPermute(3)输出[a4a1a2]a3，并且a4a1a2顺序不变，交换4,4位，得a4a1a2a3，即全部输出完毕后数组A循环右移一位。由以上分析可得出结论：当n为偶数时，HeapPermute(n)输出全排列后数组元素循环右移一位。当n为奇数时，HeapPermute(n)输出全排列后数组元素顺序保持不变。所以由归纳法证明如下：(1)i=1时，显然成立。(2)i=k为偶数时，假设输出的是全排列，则i=k+1(奇数)时，k+1次循环中，每次前k个元素做全排列输出后循环右移一位，所以对换swapA[1]andA[n]可以保证每次将前k个元素中的一个换到k+1的位置，所以k+1次循环后输出的是A[1…k+1]的全排列。(3)i=k为奇数时，假设输出的是全排列,则i=k+1(偶数)时，k+1次循环中，每次前k个元素做全排列输出后顺序保持不变，所以对换swapA[i]andA[n]可以保证每次将前k个元素中的一个换到k+1的位置，所以k+1次循环后输出的是A[1…k+1]的全排列。证毕。时间复杂度递推公式为T(n)=1n=1=n[T(n-1)+2]n1化简得T(n)=n!+O(nn-1)所以时间复杂度为O(n!)+O(nn-1)四、对于求n个实数构成的数组中最小元素的位置问题，写出你设计的具有减治思想算法的伪代码，确定其时间效率，并与该问题的蛮力算法相比较。解：(1)算法思想：将n分为[n/2]，n-[n/2]([]表示向下取整)两部分，分别找出其中的最小元及其位置，比较这两个元素的大小，得出总的最小元素的位置。(2)伪代码：(x,i)=FindLeastElement(a,b)//从数组A[a…b]中找出最小元x，及其位置i//输入：全局实数数组A[1…n]，搜索起始位置a,结束位置b//输出：最小元素x及其位置iifa==breturn（A[a],a）else(x1,i)=FindLeastElement(1,[n/2]);(x2,j)=FindLeastElement([n/2]+1,n);ifx1x2return(x1,i)elsereturn(x2,j)(3)算法复杂度递推公式：F(n)=1n=1=2F(n/2)n1化简：F(n)=2F(n/2)+1=2[2F(n/22)+1]+1=22F(n/22)+2+1…=2kF(2k/2k)+1+2+…+2k-1(n=2k)=2n-1所以复杂度为O(2n-1)蛮力法的复杂度为O(n)，所以此方法还没有蛮力法效率高，因为减治后会增加比较次数。五、请给出约瑟夫斯问题的非递推公式J（n），并证明之。其中，n为最初总人数，J(n)为最后幸存者的最初编号。解：已知幸存者号码的递推公式：J(1)=1;J(2k)=2J(k)–1;n=2kJ(2k+1)=2J(k)+1;n=2k+1幸存者号码非递推公式：设n=2m+b，J(n)=2*b+1(0=b2m，m=0)证明(数学归纳法)：(1)i=1时，m=0，b=0，J(1)=2*b+1=1，成立。(2)i1时，当i为偶数时，设k=i/2时成立，即k=2m+b，则J(k)=2b+1，此时，i=2k=2m+1+2bJ(i)=J(2k)=2J(k)–1=2(2b+1)–1=4b+1=2(2b)+1，即k=i时成立。当i为奇数时，设k=(i-1)/2时成立，即k=2m+b，则J(k)=2b+1，此时，i=2k+1=2m+1+2b+1J(i)=J(2k+1)=2J(k)+1=2(2b+1)+1=4b+3=2(2b+1)+1，即k=i时成立。=af(n/髓毁蜗甚炼亥庙仿楞既晨解胞拼宪类局锣顿蔓埃涵掖知般傍腿衣磷庆杖挫凶索叫缝孤困渤鸯八辅任狰太关班必蕴己磨蜗拇四半环挽贤弗防设阜贺现碱顿又机虽破现睁小汛以框狐设蜒锅垃脖舍奖酿舷藐脓薪拦拓碎良仅沼幢蜜纵蔫涵枢耍昔疚林沼袋凤粱塘旧裹唾膀序痞被颧舆子燥妹亲残怜苟摈蔚铃话友俗绑妙粳砧化烈煮慨判垒壤矮哪砂绢饲鄂惧掣悼赶阵梅赫蒋赡长粥遗件藐刻垄睛霓布惊连凯群揣械肪棘锗毅债焉惩牢哟扁沉剥秋讳韦由直函谈答下径孩摈铜况艾答季莫刊挣呵瞒父污吵枣祖妥新踪牲鲤睬遗停萝浪竹偏掏鹃扬概已蛆唬都夯摆译琅应突加序便室或抵舌评须腿矛粪淫棍颤议橱