Error message here!

Hide Error message here!

忘记密码?

Error message here!

请输入正确邮箱

Hide Error message here!

密码丢失?请输入您的电子邮件地址。您将收到一个重设密码链接。

Error message here!

返回登录

Close

计算整数的幂——递归算法

Baby-Lily 2020-01-14 21:11:00 阅读数:17 评论数:0 点赞数:0 收藏数:0

幂运算

计算一个整数的幂,常见的算法是使用N-1次自然乘法,但是下面的递归算法可能会更好一些,如果N是偶数,有X^N = X^(N/2) * X^(N/2),

如果X是奇数,那么有X^N = X^((N-1)/2) * X^((N-1)/2) * X。下面正是这种算法的实现:

long int
Pow(long int X, unsigned int N){
if(N == )
return ;
if(N == )
return X;
if(isEven(N))
return Pow(X*X, N/);
else
return Pow(X*X, N/)*X;
} 

显然,所需要的乘法次数最多是2logN,用为把问题分成了最多需要两次乘法。

版权声明
本文为[Baby-Lily]所创,转载请带上原文链接,感谢
https://www.cnblogs.com/baby-lily/p/12194114.html