算法:分治法求a的n次方

问题描述:

分治的方法求an

算法分析:

如果 n 是偶数,可以分为 (an/2)*(an/2)                 算法复杂度基本降低一半

如果 n 是奇数,可以分为 (an/2)*(an/2)*a   算法复杂度也基本降低一半

如果 n == 1 ,则直接返回 a

 

代码范例:

java:

public static BigInteger calc(BigInteger a,int n)
{
if(n==1)
return a;
if(n%2==0)
return a.pow(n/2).multiply(a.pow(n/2));
return (a.pow(n/2).multiply(a.pow(n/2))).multiply(a);
}

 

c/c++:

int calc(int a,int n)
{
if(n==1)
return a;
if(n%2==0)
return pow(calc(a,n/2),2);
return pow(calc(a,(n-1)/2),2)*a;
}

未经允许不得转载:前后端 » 算法:分治法求a的n次方

赞 (1)
分享到:更多 ()

评论 0

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址