第四章作业分析(共4页).doc
精选优质文档-倾情为你奉上本章作业：1.p98:11（实验题）；5；2.p103:7；3.p105：2,3；4.p113:3第四章作业分析p98:习题4.14.1.5.求下列递推式的解的增长次数。（郑雪）a. T(n) = 4T( n/2 ) + n， T(1)=1b. T(n) = 4T( n/2 ) + ，T(1)=1c. T(n) = 4T( n/2 ) + ，T(1)=1解：解：由通用分治递推式：T (n) = a T (n/b) + f(n)，a . a=4, b=2, f(n) = n = n d d=1 b d =2 < a=4T (n)。b . a=4, b=2, f(n) = n2 = n d d=2 b d =2 = a=4T (n)。C . a=4, b=2, f(n) = n3 = n d d=3 b d =8 > a=4T (n)。p103: 习题4.24.2.7、对快速排序在平均情况下的递推公式求解。（罗雨欣）解： = =n+1+ =n+1+ 两边同乘以n得：n=n(n+1)+2 n=n-1时，有：(n-1)=(n-1)n+2 两式相减 - ：n=2n+(n+1) 等式两边同除以n(n+1)有：=+ 令=B(n)，则B(n)=B(n-1)+ (n) 由有B(0)=0， B(1)=1 此式可归纳为B(n)=2，所以B(n)=2A(n+1)-3,其中A(n+1)=， 下面证明1+= ln(n+1)+r(r为常量) Newton幂级数：ln(1+)=-+-+ 于是，= ln(1+)+- 带入x=1,2,3n，就给出：=ln(2)+-+- =ln()+-+- =ln()+-+ 将上面带入x后的所有等式相加有：1+.+= ln(n+1)+(1+)-(1+)+ ，可以确定的是每一个括号中的级数都是收敛的，故我们可以定义=1+= ln(n+1)+r(r为欧拉常数，约为0.577)ln(n+1) A(n+1)=ln(n+1)，B(n)= 2A(n+1)-32 ln(n+1)， =(n+1)B(n)=2(n+1) ln(n+1)2nln n，得证！习题4.3 p105：（罗雨欣） 4.3.2. 当n = 2k 时，用反向替换法求下面的递推方程：log 2 n 当 n > 1 时， （n）= （ ）+ 1 ，（1） = 1 解法1：左边： （n） =（2k）= + 1 = + 1 = k + 1 右边：（ ）+ 1 =（ ）+ 1 =（2k-1）+ 1 = + 1 + 1 = + 2 = k + 1解法2当n=时，用反向替换法求下面的递推方程： 当n>1时，=+1，=1（罗雨欣）解： 因为n=，n>1 将其带入方程可得: =+1 且 =1 做反向替换： =+1 =+2 =+3=+i=+k =1+k 又k= =+14.3. 3、a.证明下面的等式：（罗雨欣） 当n1时，+1= b.请证明，对于大于0的任意奇数，方程=+1是递推关系(4.2)的解。解： a) 对于正整数n易有：n<，k0 k为正整数 <k+1，k0 即有 =k 同样地，对于正整数n有n，k0 k为正整数 k+1，k0 即有 k+1 +1=k+1=，得证； b) 对于大于0的任意奇数n=2k+1，k>0 对于方程=+1有： =+1= =+1 =+1+1=+2 对于递推关系式(4.2) 当n>1时，=+1，=1 将n=2k+1，=+1代入化简： =+1 =+1 =+1 =+1+1=+2 =+1=1 由方程推知结果，再将方程与相应的条件代入递推关系式中得到相同的结果，当然使此递推关系式成立的解不仅为此方程，所以说方程=+1是递推关系式=+1，=1的解。P113 习题4.54.5.3、a.请证明等式=，4.5节两次使用了这个等式。 b.作为M(n)的闭合公式来说，为什么要比好？解： a) 对等式两边取自然对数有：左边=ln()=·lna·lna 右边=ln()=·lnc=·lnc=左边 =得证； b) 对于M(n)的闭合公式来说，显然比较和等指数为实数的表达式更为方便，而比较和则比较麻烦，故用要比处理M(n)的闭合公式更好。专心-专注-专业
