求解递归方程两个,假定n为2的方幂.

来源：学生作业帮编辑：作业帮分类：数学作业时间：2024/07/05 16:43:36

求解递归方程两个,假定n为2的方幂.
不要求非常详细,有必要的几个步骤就可以了
1、T(n)=4*T(n/2)+n
2、T(n)=4*T(n/2)+n^2
两个差不多,答对有高分相送,急.

前一个：
T(n)=4T(n/2)+n可以等价地写成T(2^t)=4T(2^(t-1))+2^t,
所以
T(2^t)+2^t=4T(2^(t-1))+2*2^t=4T(2^(t-1))+4*2^(t-1)=4[T(2^(t-1))+2^(t-1)],
令R(t)=T(2^t)+2^t,则上式说明R(t)=4R(t-1).所以
R(t)=4R(t-1)=(4^2)R(t-2)=...=(4^t)R(0),
所以
T(2^t)=R(t)-2^t=(4^t)R(0)-2^t=(4^t)[T(2^0)+2^0]-2^t=(4^t)[T(1)+1]-2^t=(4^t)T(1)+4^t-2^t,
或者写成
T(n)=(n^2)T(1)+n^2-n,
其中T(1)可取任意常数
后一个：
T(n)=4T(n/2)+n^2可以等价地写成T(2^t)=4T(2^(t-1))+4^t,
所以
T(2^t)-t*4^t=4T(2^(t-1))+4^t-t*4^t=4T(2^(t-1))-(t-1)*4^t=4[T(2^(t-1))-(t-1)*4^(t-1)],
令R(t)=T(2^t)-t*4^t,则上式说明R(t)=4R(t-1).所以
R(t)=4R(t-1)=(4^2)R(t-2)=...=(4^t)R(0),
所以
T(2^t)=R(t)+t*4^t=(4^t)R(0)+t*4^t=(4^t)[T(2^0)-0*2^0]+t*4^t=(4^t)T(1)+t*4^t,
或者写成
T(n)=(n^2)T(1)+(n^2)ln(n)/ln(2),
其中T(1)可取任意常数

C语言编写已知一数列的第n项的通式为f(n)=n*(n+1),分别用非递归法和递归法编程求解该数列第1到1000项的和 matlab利用递归求解差分方程 VB编程：用递归方法求n阶勒让德多项式的值,递归公式为：编程用辗转相除法（不使用递归）实现函数gcd(m,n),其功能为求解正整数m、n的最大公约数. C语言编程用辗转相除法（不使用递归）实现函数gcd(m,n),其功能为求解正整数m、n的最大公约数. 计算1!+2!+3!...+(n-1)!+n!.设计求解该问题的C语言程序,阶乘的计算使用递归函数实现 C语言递归子函数求两个正整数M,N的最大公约数的Euclid算法为：1）\x05记M除以N的余数为r;2）\x05若r 求解方程x的四次方-2x的三次方+2x方=4 已知m,n是方程x方-2tx+t+2=0的两个实数根,求y=m方+n方的最小值. 代换法解递归式证明T(n)=T(n/2)+1的解为O(lgn) 已知关于x的方程x方-(m+2)x+m-2n=0中有两个相等的实数根,且x=1/2是方程的跟,则m+n的值为已知M,N为整数,关于X的三个方程X方-（7-M）X+3+N=0有两个不等的实根 X方+（4+M）X+N+6=0有两个相