題目:實作函數double Power(double base,int exponent),求base的exponent次方。不得使用庫函數,同時不需要考慮大樹問題。
這道題目有以下幾點需要注意:
- 0的0次方是無意義的,非法輸入
- 0的負數次方相當于0作為除數,也是無意義的,非法輸入
- base如果非0,如果指數exponent小于0,可以先求base的|exponent|次方,然後再求倒數
- 判斷double類型的base是否等于0不能使用==号。因為計算機表述小樹(包括float和double型小數)都有誤差,不能直接使用等号(==)判斷兩個小數是否相等。如果兩個數的差的絕對值很小,那麼可以認為兩個double類型的數相等。
以下方法錯誤:
double PowerWithUnsingedExponent(double base,unsigned int absExp)
{
if(absExp==0)
return 1;
else if(absExp==1)
return base;
double result=1.0*base;
for(int i=2;i<=absExp;i=i*2)
result*=result;
if(absExp%2==1)//如果指數為奇數,還得再乘一次底數
result*=base;
return result;
}
全面但不夠高效的方法:
#include<iostream>
#include<stdlib.h>
using namespace std;
bool isInvalidInput=false;
double PowerWithUnsingedExponent(double base,unsigned int absExp)
{
double result=1.0;
for(int i=0;i<absExp;i++)
result*=base;
return result;
}
//由于精度原因,double類型的變量不能用等号判斷兩個數是否相等,是以需要寫equsl函數
bool equal(double a,double b)
{
if((a-b>-0.000001)&&(a-b<0.000001))
return true;
else
return false;
}
double Power(double base,int exponent)
{
//如果底數為0且指數小于0,則表明是非法輸入。
if(equal(base,0.0) && exponent<=0)
{
isInvalidInput=true;
return 0;
}
unsigned int absExp;
//判斷指數正負,去指數的絕對值
if(exponent<0)
absExp=(unsigned int)(-exponent);
else
absExp=(unsigned int)exponent;
double result=PowerWithUnsingedExponent(base,absExp);
//如果指數小于0則取倒數
if(exponent<0)
result=1/result;
return result;
}
void main()
{
double a=Power(2.0,13);
cout<<a<<endl;
system("pause");
}
全面而且高效的方法:高效的遞歸和位運算
class Solution {
public:
bool Equal(double a,double b)
{
if((a-b>-0.0000001)&&(a-b<0.0000001))
return true;
else return false;
}
double PowerWithUnsignedExponent(double base,unsigned int exponent)
{
//double result=1.0;
//for(unsigned int i=1;i<=exponent;i++)
// result*=base;
if(exponent==0) return 1;
if(exponent==1) return base;
double result=PowerWithUnsignedExponent(base,exponent>>1);
result*=result;
if(exponent&0x01==1)
result*=base;
return result;
}
double Power(double base, int exponent) {
if(Equal(base,0.0)&&exponent<0)
cout<<"Invaild Input!";
unsigned int absExponent=(unsigned int)(exponent);
if(exponent<0)
absExponent=(unsigned int)(-exponent);
double result=PowerWithUnsignedExponent(base,absExponent);
if(exponent<0)
result=1.0/result;
return result;
}
};