离兮
春芽
共回答了21个问题采纳率:90.5% 举报
d(n)=2^n + n,
p(1)=d(1)=2^1 + 1 = 3,
p(n+1)=d(n+1)+d(n)=2^(n+1)+(n+1) + 2^n + n = 3*2^n + 2n+1,
L(2n-1)=d(2n-1)=2^(2n-1)+(2n-1),
L(2n)=p(2n)=p(2n-1+1)=3*2^(2n-1)+2(2n-1)+1,
L(2n-1)+L(2n)=4*2^(2n-1)+3(2n-1)+1=8*4^(n-1) + 6n - 2
T(2n)=L(1)+L(3)+...+L(2n-1)+L(2)+L(4)+...+L(2n)
=8[1+4+...+4^(n-1)] + 6[1+2+...+n] - 2n
=8[4^n - 1] /(4-1) + 6n(n+1)/2 - 2n
=8(4^n - 1)/3 + 3n(n+1) - 2n
T(2n-1)=T(2n)-L(2n)=8(4^n-1)/3 + 3n(n+1)-2n - 3*2^(2n-1) - 2(2n-1)-1
=8(4^n-1)/3 + 3n(n+1)-2n - (3/2)*4^n - 4n + 1
=(7/6)4^n + 3n^2 - 3n - 5/3
1年前
追问
3
举报
离兮
那就换一种, n =2m为偶数时, m=n/2. T(n)=T(2m)=8(4^m-1)/3 + 3m(m+1) - 2m =8[4^(n/2) - 1]/3 + 3(n/2)(n/2 + 1) - n =8[2^n - 1]/3 + (3/4)n(n+2) - n n=2m-1为奇数时,m=(n+1)/2. T(n)=T(2m-1)=(7/6)4^m + 3m^2 - 3m - 5/3 =(7/6)4^[(n+1)/2] + 3[(n+1)/2]^2 - 3(n+1)/2 - 5/3 =(7/6)2^(n+1) + (3/4)(n+1)^2 - 3(n+1)/2 - 5/3 其实,同一个答案可以有很多种写法. 只要各种写法的答案一致就OK鸟...