面试题 11

1 题目描述

题目：实现函数 double Power(double base，int exponent)，求exponent 次方，不得使用库函数，同时不考虑大数问题。

算法描述

base^exponent
一般情况 base>=0 exponent>=0
特殊情况 base=0 exponent<0 此时计算需要进行 /0 操作，导致错误
特殊情况 base=0 exponent=0，0^0 在数学上没有意义，可以返回 0 或者 1

C 语言实现

#include<stdio.h>
int invalidInput=0;
int equal(double base){
    if(base-0.0>-0.0000001&&base-0.0<0.0000001){
        return 1;
    }else{
        return 0;
    }
}
double powerWithUnsignedExponent(double base,int exponent){
    if(exponent==1) return base;
    if(exponent==0) return 1;
    double result=powerWithUnsignedExponent(base,exponent>>1);
    result=result*result;
    if(exponent&1==1){
       result*=base;
    }
    return result;
}
double Power(double base,int exponent){
    double result=0.0;
    if(equal(base)&&exponent<0){
        invalidInput=1;
        return result;
    }
    unsigned int absExponent=(unsigned int)exponent;
    if(exponent<0){
        absExponent = (unsigned int)(-exponent);
    }
    result=powerWithUnsignedExponent(base,absExponent);
    if(exponent<0){
        result=1/result;
    }
    return result;
}

void main(){
    printf("%f  ",Power(2,3));
    printf("%d\n",invalidInput);

    printf("%f  ",Power(2,-3));
    printf("%d\n",invalidInput);

    printf("%f  ",Power(0,-3));
    printf("%d\n",invalidInput);

    printf("%f  ",Power(0,0));
    printf("%d\n",invalidInput);
}

注意事项

1 代码完成性：功能测试、边界测试、负面测试
2 处理错误的三种方法，通常有 3 种方式将错误信息传递给调用者，函数返回值，设置全局变量和抛出异常。每一种方法都有局限，本例中使用全局变量记录错误信息。
3 使用移位操作代替 *2 操作，使用 &1 代替 奇偶数判定 操作，效率会更高。

a^n = a^(n/2) * a^(n/2)         n为偶数
a^n = a^(n-1/2) * a^(n-1/2)*a   n为奇数

4 用递归的方式可以实现 O(lgn) 时间复杂度求解 a^n。
5 由于计算机表示小数都有误差，不能直接使用等号判断两个小数是否相等，如果两个小数的差的绝对值很小，比如小于0.0000001，就可以认为他们相等。