《中科大算法导论第一二次和第四次作业答案.pptx》由会员分享，可在线阅读，更多相关《中科大算法导论第一二次和第四次作业答案.pptx（18页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、2.3-2改写MERGE过程，使之不使用哨兵元素，而是在一旦数组L或R中的所有元素都被复制回数组A后，就立即停止，再将另一个数组中余下的元素复制回数组A中。MERGE(A,p,q,r)1.n1q-p+12.n2 r-q3.create arrays L1.n1 and R1.n24.for i 1 to n15.do Li Ap+i-16.for j 1 to n27.do Rj Aq+j8.i 19.j 110.k p11.while(i=n1)and(j=n2)12.do if Li=Rj13.do Ak=Li14.i+15.else do Ak=Rj16.j+17.k+18.while(
2、i=n1)19.do Ak+=Li+20.while(j0时才进行交换 交换flag=-flag第四次作业第11页/共18页int Partition(int A,int p,int r)int x=Ar,i=p-1;int flag=1;for(int j=p;j=Ai&flag0)/x=Ai时，flag大于0和小于0的数量约为一半，swap(Ai,Aj);if(x=Ai)flag=-flag;/这样就能让i+次数减半。swap(Ai+1,Ar);return i+1 第12页/共18页7.2-3 证明：当数组A包含不同的元素、且按降序排序时，QUICKSORT的运行时间为(n2)。证明：数
3、组元素各不相同，且按降序排列时，每次递归调用都会产生一个元素数目为n-1的分块和一个1的分块。故有T(n)=T(n-1)+(n)有T(n)=T(n-1)+cn+d=T(n-2)+cn+c(n-1)+2d=T(n-3)+cn+c(n-1)+c(n-2)+3d=.=T(1)+cn+c(n-1)+c(n-2)+.+c(1)+nd=T(1)+cn(n+1)/2+nd=(n2)第13页/共18页7.4-3 证明：在q=0,1,.n-1区间上，当q=0或q=n-1时,q2+(n-q-1)2取得最大值。求导，取极值。或者进行变换第14页/共18页8.2-4在O(1)的时间内，回答出输入的整数中有多少个落在区
4、间a.b内。给出的算法的预处理时间为O(n+k)利用计数排序，由于在计数排序中有一个存储数值个数的临时存储区C0.k，利用这个数组即可a.b区间整数个数为Cb-Ca-1第15页/共18页题目已经提示运用桶排序，主要是正确设置桶点均匀分布，则每个桶的尺寸应相等，即每个桶在圆中所占据的面积相等。把圆分为n个部分，第一个部分是以原点为圆心的圆，其他部分是以原点为圆心的圆环。单位圆的面积是12=。那么我们选择一系列的距离d0,d1,d2,.,dn满足d0=0,*d12=/(n),*d22=2*/(n),*d32=3*/(n),.,*dn2=，得到，d0,d1,d2,.,dn=0,sqrt(1/n),s
5、qrt(2/n),.,1这样相当于每个di到di+1所占的面积都是相同的，也即每个左边点会均匀的落入这些区间中。所n个桶为d0,d1,d1,d2,.,dn-1,dn第16页/共18页9.1-1证明：在最坏情况下，利用n+ceil(lgn)-2次比较，即可得到n个元素中的第2小元素。（提示：同时找最小元素）先两两比较，较小的组成新的数组再两两比较，不断如此，从而形成一个倒立的树，终于找出最小的元素，由于最上一层是n/2次比较，这又能够看做一个满二叉树，所以总的比较次数为n/2+n/2-1=n-1，找出一个最小的元素须要n-1次比较，而n个元素中的第2小元素一定跟最小的元素比较过，在这个倒立树中，共同拥有lgn个元素跟最小元素比较过，所以找到第2小元素须要lgn-1次比较，共所以须要n+lgn-2次比较。第17页/共18页谢谢您的观看！第18页/共18页