1）设计一个递归算法用来计算2^n(n为非负整数) PS：2^n=2^(n-1)+2^(n-1)

来源：学生作业帮编辑：拍题作业网作业帮分类：数学作业时间：2024/04/29 07:46:45

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
再问：能用差分方程的式子来表示吗
再答：那抱歉,我没学过差分方程.不过我觉得如果你明白意思,你应该可以用你学过的东西来表达出来的.

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) 用C语言编写一个递归程序用来计算：1*2+2*3+3*4+...+(n-1)*n 关于扩展欧几里德算法我要用扩展欧几里德算法计算-n*n' % r=1等式中的n',其中n为已知非负奇数,r=2^k,想问在C++中,怎样设计一个递归函数计算1!+2!+.+n!. 输入一个整数n（n>6）,计算1!+2!+3!+……+n!并输出. 证明：n>=1,n为整数.证（（n-1）*n）/2 的奇偶性与 n+1 相同. 已知Sn=1+1/2+1/3+.+1/n(n>1,n为整数),求证S(2^n)>1+n/2(n>=2,n为整数) 2^n/n*(n+1) 非负实数x,四舍五入到个位的值记为,既当n为非负整数时,如果n-1/2≤x∠n+1/2,则〈x〉=n. 对非负实数x“四舍五入”到个位的值记为即：当n为非负整数是,如果n-1/2≤x＜n+1/2,则=n 证明不等式：(1/n)^n+(2/n)^n+(3/n)^n+.+(n/n)^n