资源描述：
《算法分析与设计答案》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、算法分析与设计答案导读：就爱阅读网友为您分享以下“算法分析与设计答案”资讯，希望对您有所帮助，感谢您对92to.com的支持!第一章6、考虑下面算法,回答问题intStery(intn){intS=0;for(i=1;i=n;i++){S=S+ii;}returnS;}1)该算法求的是什么?从1到N的平方和2)该算法基本语句是什么?S=S+ii3)基本语句执行了多少次?37算法分析与设计答案导读：就爱阅读网友为您分享以下“算法分析与设计答案”资讯，希望对您有所帮助，感谢您对92to.com的支持!第一章6、考虑下面算法,回答问题intStery(intn){intS=0;for(i=1
2、;i=n;i++){S=S+ii;}returnS;}1)该算法求的是什么?从1到N的平方和2)该算法基本语句是什么?S=S+ii3)基本语句执行了多少次?37N次4)该算法的效率类型是什么?O(n)5)对该算法进行改进,分析改进的算法效率。利用公式法进行求解intStery1(intn){return(n(n+1)(2n+1))/6;}O(1)6)如果算法不能在改进了,请证明这一点。因为其时间复杂度已经是常数级,不能再小了。7、使用扩展递推技术求解下列递推关系式(参考P15)假定n=2k上式=2=2(2(T(n/32)+n/3)+n)=2(2(2(T(n/33)+n/32)+n/3)
3、+n)=2KT(1)+2k-1(n/3k-1)+2k-2(n/3k-2)+…….+21(n/31)+n=2k+n=n+3n(1-)=n+3n(1-)当然也可以使用通用分支递推式,可快速确定答案。8、考虑下面的递归算法,回答下面问题intQ(intn)//n为正整数{if(n37==1)return1;elsereturnQ(n-1)+2n-1;}1)该算法求的是什么?求一个正整数的平方2)写出n=3时的执行过程;f(3)=f(2)+23–1;f(2)=f(1)+22–1;f(1)=1;回溯:f(2)=1+3=4;f(3)=4+5=9;3)建立该算法的递推关系式,并求解。f(n)=f(n
4、-1)+2n-1;=f(n-2)+2(n-1)-1+2n-1=f(n-3)+2(n-2)-1+2(n-1)-1+2n-1=f(1)+3+5+7+……+2n-1=1+3+5+7+…..+2n-1=(1+2n-1)n/2=n24)将该算法转换为非递归算法。intQ1(intn37){returnnn;}补充习题:1-4设计算法求数组中相差最小的两个元素(称为最接近数)的差。要求给出伪代码描述,并用一组例子进行跟踪验证,写出验证过程。(1)伪代码1.令最小距离min等于数组头两个元素R[0]和R[1]的差的绝对值;2.从i=0循环至in-1,对于每个R[i]2.1分别求其与j=i+1至jn的
5、数的差的绝对值;2.2如果此值小于最小距离,则令新的最小距离为此值;3.输出最小距离。(2)用实例进行跟踪验证R[6]={10,5,11,16,30,14},n=6;Min=10-5=5;i=0,j=1,R[i]-R[j]=10-5=5;j=2,R[i]-R[j]=10-11=1min;min=1;j=3,R[i]-R[j]=10-16=6;j=4,R[i]-R[j]=10-30=20;37j=5,R[i]-R[j]=10-14=4;i=1,j=2,R[i]-R[j]=5-11=6;j=3,R[i]-R[j]=5-16=11;j=4,R[i]-R[j]=5-30=15;j=5,R[i]
6、-R[j]=5-14=9;i=2,j=3,R[i]-R[j]=11-16=5;j=4,R[i]-R[j]=11-30=19;j=5,R[i]-R[j]=11-14=3;i=3,j=4,R[i]-R[j]=16-30=14;j=5,R[i]-R[j]=16-14=2;i=4,j=5,R[i]-R[j]=30-14=16;最后输出min=1第二章1.求平凡下界2.n(logn),分治法3.画出a,b,c中秋中值问题的决策树(p27)4.时间复杂度是O(n),可以从n到1,也可以从1到n,从n开始就看(k/2)下取整下标的元素(也就是堆中的双亲)是否满足大根或者小根的条件,从1开始就看2k和
7、2k+1下标的元素(就是堆中的左右孩子)是否满足堆的条件//复杂度O(n)//大根堆boolisHeap(intdata,intn){inti,j,37k;for(i=0,j=1;jn;i++,j=2i+1){k=data[j];if(j+1n&&data[j+1]data[j])k=data[j+1];if(data[i]k)returnfalse;}returntrue;}//小根堆boolisHeap(intdata,intn){inti
