请问一道简单的编程题

题目，写一个function 计算两个数的power, 
float power (float x, int y) { }返回x^y.
请问怎么能使复杂度为O(lgn).
谢谢

14 个解决方案

#1

float P(float x, int y)
{
    float temp = 1;
    while (y > 0) 
    {   
        if (y%2 == 1)
            temp *= x;     
        x *= x;             
        y >>= 1;       
    }
    return temp;
}

#2

float power(float x, int y)
{
	if(y == 0)
		return 1;
	else if( (y & 1) == 0)
		returnpower(x*x, y/2);
	else
		return x*power(x*x, y/2);
}

#3

float power(float x, int y)
{
    if(y < 0)
        return 1/power(x, -y);
    else if(y == 0)
        return 1;
    else if( (y & 1) == 0)
        return power(x*x, y/2);
    else
        return x*power(x*x, y/2);
}

#4

#include <stdio.h> 
double Power1(double x, int y);
double fun(double x, int y);
void main()
{
	double a=2.3;
	double d=0.0;
	d=fun(a, 6);
	printf("d=%f\n",d);
}
double fun(double x, int y)
{
	if(y<0) {return Power1(1.0/x,-y);}
	else    {return Power1(x,y);}
}
double Power1(double x, int y)
{
    double k=1;
   if(y == 0) return 1;
   if(y ==1) return x;
   if(y%2 == 0){k=Power1(x,y/2); return k*k;}
   else{k=Power1(x,(y-1)/2);return k*k*x;}
}

#5

赞一楼的代码。

#6

支持1楼算法
但修改下
C/C++ code
float P(float x, int y)
{
    float temp = 1.0;
    while (y > 0) 
    {   
        if (y%2 == 1)
            temp *= x;     
        x *= x;             
        y >>= 1;       
    }
    return temp;
}

#7

今天在看STL 源码分析
看到的POWER 算法的过程。我把他翻译成下面的代码

float power(float x, int y) 
{
     float result = 1.0;
     if ( y == 0 ) 
     {
return result;
     }
     else
     {
 while ( (y & 1) == 0 ) //指数为偶数的情况
 {
      y >>= 1;     //  (2)^4 = (4)^2
              x *= x;
 }

result = x;

y >> 1;
while ( n != 0 )// 指数为奇数的情况
{
x *= x;
if ( (y & 1) != 0 )
{
result *= x;
}
y >>= 1;
}

return result;  
    }
}

#8

float power(float x, int y) 
{
	 float result = 1.0;
     if ( y == 0 ) 
     {
		return result;
	 }
	 else
	 {
		 while ( (y & 1) == 0 ) //指数为偶数的情况
		 {
			 y >>= 1;	//  (2)^4 = (4)^2
			 x *= x;
		 }

		result = x;

		y >> 1;
		while ( n != 0 )// 指数为奇数的情况
		{
			x *= x;
			if ( (y & 1) != 0 )
			{
				result *= x;
			}
			y >>= 1;
		}

		return result;		 
	 }
}

#9

经典题目阿

#10

学习了。。

#11

 解释一下，复杂度呢？ 

#12

我也想了解，谢谢LZ.

#13

不明LZ在说什么

#14

简单的题目。

typedef double T;
T power(T base,int exp)
{
T res=1.0;
if(exp<0)
{
cerr<<"exp must be positive."<<endl;
exit(1);
}
if(exp==0)
{
return res;
}
if(exp%2==0)
{
T temp=power(base,exp/2);
return res=temp*temp;
}
else
{
T temp=power(base,exp/2);
return res=temp*temp*base;
}

}