中科大算法导论第一,二次和第四次作业答案

第一次作业2.2-3再次考虑线性查找问题（见练习2.1-3）。在平均情况下，需要检查输入序列中的多少个元素？假定待查找的元素是数组中任何一个元素的可能性是相等的。在最坏情况下有怎样呢？用Θ形式表示的话，线性查找的平均情况和最坏情况运行时间怎样？对你的答案加以说明。线性查找问题输入：一列数A=<a1,a2,…,an>和一个值v。输出：下标i，使得v=A[i]，或者当v不在A中出现时为NIL。平均情况下需要查找(1+2+…+n)/n=(n+1)/2最坏情况下即最后一个元素为待查找元素，需要查找n个。故平均情况和最坏情况的运行时间都为Θ(n)。2.3-2改写MERGE过程，使之不使用哨兵元素，而是在一旦数组L或R中的所有元素都被复制回数组A后，就立即停止，再将另一个数组中余下的元素复制回数组A中。MERGE(A,p,q,r)n1←q-p+1n2←r-qcreatearraysL[1..n1]andR[1..n2]fori←1ton1doL[i]←A[p+i-1]forj←1ton2doR[j]←A[q+j]i←1j←1k←pwhile((i<=n1)and(j<=n2))doifL[i]<=R[j]doA[k]=L[i]i++elsedoA[k]=R[j]j++k++while(i<=n1)doA[k++]=L[i++]while(j<=n2)doA[k++]=R[j++]3.2-3证明等式lg(n!)=Θ(nlgn)。并证明等式n!=ω(2n)和n!=o(nn)。第二次作业3.2-4函数⌈lgn⌉!是否多项式有界？函数⌈lglgn⌉!呢4.1-2证明这个递归的解也是Ω(nlgn)。得到解为Θ(nlgn)。4.1-4证明合并排序算法的“准确”递归式(4.2)的解为Θ(nlgn)7.1-2当数组A[p..r]中的元素均相同时，PARTITION返回的q值是什么？修改PARTITION，使得当数组A[p..r]中所有元素的值相同时，q的值是r.

一种方法：记一个cnt碰上一样的数的时候cnt＋＋对全部相同这种情况cnt=(r-p+1)进行处理直接返回(p+r)/2。

或者修改PARTITION(A,p,r)，增加对A[i]==x时的处理。对于A[i]==x的数据，一半放在x左边，一半放在x右边通过设置一个flag初始为1当flag>0时才进行交换交换flag=-flag第四次作业intPartition(intA[],intp,intr){intx=A[r],i=p-1;intflag=1;for(intj=p;j<r-1;j++){if(x>=A[i]&&flag>0)//x=A[i]时，flag大于0和小于0的数量约为一半，{swap(A[i],A[j]);}if(x==A[i]){flag=-flag;//这样就能让i++次数减半。}}swap(A[i+1],A[r]);returni+1}7.2-3证明：当数组A包含不同的元素、且按降序排序时，QUICKSORT的运行时间为Θ(n2)。证明：数组元素各不相同，且按降序排列时，每次递归调用都会产生一个元素数目为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)7.4-3证明：在q=0,1,...n-1区间上，当q=0或q=n-1时,q2+(n-q-1)2取得最大值。求导，取极值。或者进行变换8.2-4在O(1)的时间内，回答出输入的整数中有多少个落在区间[a...b]内。给出的算法的预处理时间为O(n+k)利用计数排序，由于在计数排序中有一个存储数值个数的临时存储区C[0...k]，利用这个数组即可[a..b]区间整数个数为C[b]-C[a-1]题目已经提示运用桶排序，主要是正确设置桶点均匀分布，则每个桶的尺寸应相等，即每个桶在圆中所占据的面积相等。把圆分为n个部分，第一个部分是以原点为圆心的圆，其他部分是以原点为圆心的圆环。单位圆的面积是π1^2=π。那么我们选择一系列的距离d0,d1,d2,...,dn满足d0=0,π*d1^2=π/(n),π*d2^2=2*π/(n),π*d3^2=3*π/(n),...,π*dn^2=π，得到，[d0,d1,d2,...,dn]=[0,sqrt(1/n),sqrt(2/n),...,1]这样相当于每个di到di+1所占的面积都是相同的，也即每个左边点会均匀的落入这些区间中。所n个桶为[d0,d1],[d1,d2],...,[dn-1,dn]9.1-1证明：在最坏情况下，利用n+ceil(lgn)-2次比较，即可得到n个元素中的第2小元素。（提示：同时找最小元素）先两两比较，较小的组成新的数组再两两比较，不断如此，从而形成一个倒立的树，终于找出最小的元素，由于最上一层是n/2次比较，这又能