则2nf’(n)=2*（2n-1f’(n-1)）+ n2 即
n2f’(n)= f’(n-1)+n2n
i2= f’(0)+?ii?12i2=1+?ii?12n
n 所以f(n)= 2
n
i2*(1+?ii?12)=2n*(10-n?n6)=10*2n-(n+6)
25) 当n≥1时，f(n)=nf(n-1)+1； f(0)=1 解：f(n)=n!*( f’(0)+ ?1)
i!i?1n= n!*( 1+ ?1)
i!i?1n
2.求解下面的递推式：当n≥2时，f(n)=4f(n/2)+n； f(1)=1。假设n为2的幂，用直接展开法求解递推式。 解：令n?2k f(n)=4f(n/2)+n =4*(4f(nn)?)?n 222n=42f(2)?2n?n
2n=43f(3)?22n?2n?n
2
=…. =4kf(n)?2k?1n???2n?n k2 =4kf(1)?(2k?1???2?1)n =n2?(2k?1)n
6
=2n2?n
3.求解下面的递推式：当n≥2时，f(n)=9f(n/3)+n2； f(1)=1。假设n为3的幂，用直接展开法求解递推式。 解：令n?3k f(n) =9f(n3)?n2
=9(9f(n232)?(n3))?n2
=92f(n232)?n2?n
=93f(n3)?n2?n2?n23
=…. =9kf(n3k)?kn2 =n2?n2log3n
4. 法求解递推式的上界：当n≥4时，f(n)?f(??n??4??)?f(??3n??4??)?n；f(n)=4。 解：
由于递推式为?f(n)??4???f(??n?n?4?4??)?f(??3n??4??)?nn?4 这里
14?34?1 故作猜想f(n)?2f(n2)?n的解为：f(n)?nlogn?4n 故对原递推式做猜想f(n)?cnlogn?4n 由于f(n)?f(??n??3n??4??)?f(??4??)?n 7
n<4时，
当 ?c??n??4??log??n??4???4??n??4???c??3n??4??log??3n??3n??4???4??4???n ?cnnn3n3n3n4log4?44?c4log4?44?n =14cn(logn?log4)?34cn(logn?log34)?5n
?cnlogn?(2?34log3)cn?5n
若使f(n)满足上界为cnlogn?4n则必有
cnlogn?(2?34log3)cn?5n?cnlogn?4n
即?(2?34log3)cn?n?0
所以c?1?1.23
2?34log3故f(n)?1.23nlogn?4n，即上界为1.23nlogn?4n
4. 设计算法，求解问题：有一楼梯共M级，刚开始时你再第一级，若每次只能跨上一级或二级，要走上第M级，共有多少种走法？ int fa(int m) {
int z;
if (m==1) z=1; else if (m==2) z=2;、 else z=fa(n-1)+fa(n-2); return z; }
8
5. 设计算法，一个射击运动员打靶，靶一共有10环，连开10枪打中90环的可能性有多少种？
这道题的思路与字符串的组合很像，用递归解决。一次射击有11种可能，命中1环至10环，或脱靶。 函数功能 ： 求解number次打中sum环的种数
函数参数 ： number为打靶次数，sum为需要命中的环数，result用来保存中间结果，total记录种数
void ShootProblem_Solution(int number, int sum, vector
if(sum < 0 || number * 10 < sum)
//加number * 10 < sum非常重要，它可以减少大量的递归，类似剪枝操作 return;
if(number == 1) //最后一枪 {
if(sum <= 10) //如果剩余环数小于10，只要最后一枪打sum环就
可以了
{
for(unsigned i = 0; i < result.size(); i++) cout< 9 } return; else return; } for(unsigned i = 0; i <= 10; i++) //命中0-10环 { result.push_back(i); ShootProblem_Solution(number-1, sum-i, result, total); //针对剩余 环数递归求解 } void ShootProblem(int number, int sum) { } int main() 10 result.pop_back(); } int total = 0; vector ShootProblem_Solution(number, sum, result, total); cout<<\