分治法求a的n次方？？？ - 编程论坛

#2

HJin2007-12-20 09:37

int power(int a, int n)
{
    if(n==0)
        return 1;
    if(n&1)
        return a*power(a, n-1);
    else
        return power(a*a, n>>1);

}

int main()
{
    int i;

    for(i=0; i<10; ++i)
        cout<<power(2, i)<<endl;

    return 0;
}

#3

圆圆的鸟蛋2007-12-21 10:31

楼上，，强！！很强调时间效率啊！

#4

木吉他2007-12-21 11:58

double power(double x,int n)
{
  double val=1.0;
  while(n--)
   val*=x;
   return(val);
}

#5

aipb20072007-12-21 20:29

int power(int a,int n){
    int e = 1;
    while (n){
        if (n&1)
            e *= a;
        a *= a;
        n >>= 1;
    }
    return e;
}

和2楼一样，不过是迭代

#6

醉生梦死2007-12-30 23:49

收获了

#7

sunkaidong2007-12-31 13:44

斑竹就是斑竹,都很厉害,收获中...

#8

kidd20052007-12-31 15:42

2 4 5楼的都不明白啊,
可以解释一下吗？

#9

醉生梦死2008-01-01 02:32

我看你是对位运算不熟悉吧，if(n&1)等与if(n%2==0)

#10

醉生梦死2008-01-01 02:33

回复 8# 的帖子

主要是降低了程序的复杂度

#11

traxex2008-01-01 07:09

比如计算a的13次方,先把13表示成( 1101 )
也就是说,3步可以计算出结果,计算次数为(3+2)

a^2*a
(a^2*a)^2
((a^2*a)^2)^2*a
记算a的n次方,先求出比a小,且是2的幂次的一个数A
#include<iostream>
using namespace std;

int power(int a, int n)
{
    int N = 1;
    int result = a;
    while (N < n)
    N <<= 1;
    N >>= 2;

    while (N > 0) {
    if ((N & n) == 1)
        result = result * result * a;
    else
        result = result * result;
    N >>= 1;
    }
    return result;
}

int main(int argc, char *argv[])
{
    int a = 3;
    int n = 5;
    cout << power(a, n) << endl;
}

#12

jxj7772008-01-01 13:19

原帖由 [bold][underline]醉生梦死[/underline][/bold] 于 2008-1-1 02:32 发表 [url=http://bbs.bc-cn.net/redirect.php?goto=findpost&pid=1167341&ptid=193390]

[/url]
我看你是对位运算不熟悉吧，if(n&1)等与if(n%2==0)

这两个语句真的等价吗?