算法导论答案15590

算法导论答案15590

ID:34087762

大小:2.12 MB

页数:63页

时间:2019-03-03

算法导论答案15590_第1页
算法导论答案15590_第2页
算法导论答案15590_第3页
算法导论答案15590_第4页
算法导论答案15590_第5页
资源描述:

《算法导论答案15590》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库

1、《算法导论》参考答案第2章第3章第4章第5章第6章第7章第8章第9章第15章第16章第24章第25章第2章2.1-12.1-22.1-32.1-42.2-12.2-22.2-32.2-42.3-12.3-2voidMerge(int*A,intp,intq,intr){//构建左半部分和右半部分的辅助数组intn1=q-p+1;intn2=r-q;int*L=newint[n1];int*R=newint[n2];for(inti=0;i

2、++){R[j]=A[q+j];}inti=0;intj=0;intk=p-1;while((i<=n1-1)&&(j<=n2-1)){if(L[i]<=R[j]){A[k]=L[i];i++;}else{A[k]=R[j];j++;}k++;}while(i<=n1-1){A[k]=L[i];i++;k++;}while(j<=n2-1){A[k]=R[j];j++;k++;}delete[]L;delete[]R;}2.3-32.3-42.3-52.3-62.3-7第3章3.1-13.1-23.1-33.1-43.

3、1-53.1-63.1-73.1-83.2-13.2-23.2-33.2-43.2-5后者大3.2-6数学归纳法易证3.2-7用数学归纳法证明第4章4.1-14.1-24.1-3T(n)=cnlgn+n4.1-44.1-54.1-64.2-14.2-24.2-34.2-44.2-54.3-14.3-24.3-34.3-4不能运用主方法4.3-5第5章5.1-1因为本身就是一个排序过程5.2-15.2-25.2-35.2-45.2-55.3-15.3-25.3-35.3-45.3-53n令mn=,生成的全排列个数有m,其

4、中不重复的有Pmn(,)=−mm*(1)**(?mn−+1),n所以,所有元素唯一概率为Pmnm(,)/n要证Pmnm(,)/≥−11/nnn由于Pmnm(,)/≥−[(mnm)/]n故需证:[(mnm−≥)/]11/−n易证5.3-6第6章6.1-16.1-26.1-36.1-46.1-56.1-66.1-76.2-1见图6-26.2-26.2-36.2-46.2-5对以i为根结点的子树上每个点用循环语句实现6.2-66.3-1见图6-36.3-26.3-36.4-1见图6-46.4-2HEAPSORT仍然正确,因为

5、每次循环的过程中还是会运行MAX-HEAP的过程。6.4-36.4-46.4-56.5-1据图6-56.5-26.5-36.5-46.5-56.5-66.5-76.5-8第七章7.1-1见图7-17.1-27.1-37.1-47.2-17.2-27.2-37.2-47.2-57.2-67.3-17.3-27.4-17.4-27.4-3纯数学问题,对式子求导即可得。7.4-4见RANDOMIZED-QUICKSORT.ppt7.4-5见快速排序改进算法(7.4-5).pdf7.4-6第八章8.1-18.1-28.1-38

6、.1-48.2-1见图8-28.2-2和8.2-38.2-48.3-1见图8-38.3-28.3-38.3-48.3-5(*)8.4-1见图8-48.4-28.4-33/2,1/28.4-4(*)8.4-5(*)第九章9.1-19.1-29.2-19.3-19.3-29.3-39.3-49.3-59.3-69.3-79.3-89.3-9第15章15.1-115.1-215.1-32nnnj−+nn1fji[]===∑∑rij()2(2)2(21)2∑−=−1ij==11j=115.1-415.1-515.2-1最终答案

7、:((A1A2)((A3A4)(A5A6)))15.2-215.2-315.2-415.2-5用递归15.3-115.3-215.3-315.3-415.3-515.4-115.4-215.4-315.4-415.4-515.4-6#includeusingnamespacestd;intfind(int*a,intlen,intn)//修改后的二分查找,若返回值为x,则a[x]>=n{intleft=0,right=len,mid=(left+right)/2;while(left<=right)

8、{if(n>a[mid])left=mid+1;elseif(n

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。