1）设计一个递归算法用来计算2^n(n为非负整数) PS：2^n=2^(n-1)+2^(n-1)
问题描述：
1）设计一个递归算法用来计算2^n(n为非负整数) PS：2^n=2^(n-1)+2^(n-1)
2）为(1)算法中产生的【加法次数】建立一个递推关系(recurrence relation)并解决
3)为这个问题设计一个更有效的算法
答
1,定义递归函数:
power(n)
if n=0
return 1
else
return 2*power(n-1)
2,这个递归算法是O(n)的.或者说,计算power(n)的计算次数等于计算power(n-1)的计算次数+1.
3,计算幂最好的方式是分治.利用 2^n = (2^(n/2))^2 递归或递推,这个方法的复杂度降到O(logN)(2)可以详解下吗你只需要考虑计算power(n)需要多少次加法就行了.我们记为C[n].当n=0,直接返回1,没有执行加法.C[0]=0.当n>0,先运行power(n-1),然后执行相加.这里有两种做法.一种是直接按题目给的用加法.那么就是执行两次power(n-1),然后执行一次加法,所以C[n]=C[n-1]*2+1或者像我写的那样用乘法,则计算次数(不是加法了,是乘法)是1次,调用power(n-1)一次,所以是C[n]=C[n-1]+1能用 差分方程的式子来表示吗那抱歉,我没学过差分方程.不过我觉得如果你明白意思,你应该可以用你学过的东西来表达出来的.