搜索
《算法导论》参考答案第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;in1;i++){L[i]=A[p+i-1];}for(intj=0;jn2;j++){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.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-5令，生成的全排列个数有，其中不重复的有,所以，所有元素唯一概率为3mn=nm(,)*(1)**(1)Pmnmmmn=−−+(,)/nPmnm要证(,)/11/nPmnmn≥−由于(,)/[()/]nnPmnmmnm≥−故需证：[(易证)/]11/nmnmn−≥−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仍然正确，因为每次循环的过程中还是会运行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.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-321111[]()2(2)2(21)21nnnjnniijjfjrij−+======−=∑∑∑−15.1-415.1-515.2-1最终答案：((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#includeiostreamusingnamespacestd;intfind(int*a,intlen,intn)//修改后的二分查找，若返回值为x，则a[x]=n{intleft=0,right=len,mid=(left+right)/2;while(left=right){if(na[mid])left=mid+1;elseif(na[mid])right=mid-1;elsereturnmid;mid=(left+right)/2;}returnleft;}intmain(){intn,a[100],c[100],i,j,len;//新开一变量len,用来储存每次循环结束后c中已经求出值的元素的最大下标while(cinn){for(i=0;in;i++)cina[i];b[0]=1;c[0]=-1;c[1]=a[0];len=1;//此时只有c[1]求出来，最长递增子序列的长度为1.for(i=1;in;i++){j=find(c,len,a[i]);c[j]=a[i];if(jlen)//要更新len,另外补充一点：由二分查找可知j只可能比len大1len=j;//更新len}coutlenendl;}return0;}15.5-115.5-215.5-315.5-4第16章16.1-116.1-216.1-316.1-416.2-116.2-216.2-316.2-416.2-516.2-616.2-716.3-116.3-216.3-316.3-416.3-516.3-6那就推广到树的结点有三个孩子结点，证明过程同引理16.3的证明。16.3-716.3-8第24章24.1-1同源顶点s的运行过程，见图24-424.1-224.1-324.1-424.1-5*24.1-6修改Bellman-Ford算法，先找到负环上的一个节点，再依次找到负环上的一个节点，再依次找到负环上的其他节点。24.2-1见图24-524.2-2最后一次不影响结果24.2-324.2-424.3-1见图24-624.3-224.3-324.3-424.3-524.3-624.3-724.3-8这种情况下不会破坏已经更新的点的距离。24.4****24.5****第25章25.1-1见图25-125.1-2为了保证递归定义式25.2的正确性25.1-325.1-425.1-525.1-625.1-725.1-825.1-925.1-1025.2-1见图25-425.2-225.2-325.2-425.2-525.2-625.2-725.2-825.2-925.3-125.3-225.3-325.3-425.3-525.3-6