《剑指offer》面试题11: 数值的整数次方

面试题11: 数值的整数次方

剑指offer面试题11,题目如下

实现函数double power(double base,int exponent),求base的exponent次方,
不得使用库 函数,同时不需要考虑大数问题

看起来这道题是一道很简单的题目,不需要什么算法思想,《剑指offer》书中循序渐进讲解了3种方

法,指出可能会出现的问题

方法一###

直接使用for循环解决问题

public static double power_method_1(double base,int exponent)
{
double result = 1.0;
for(int i = 1;i <= exponent; i++)
result *= base;
return result;
}

如果指数出现负数情况,算法将不能输出正确答案,需要对指数的正负分别讨论

方法二###

当指数出现负数的情况,可以先对指数求绝对值,然后算出次方的结果再求倒数,既然是求倒数就需要考虑到底数(base)是零的情况。

public static double power_method_2(double base,int exponent)
{
if(equal(base, 0.0) && exponent < 0) //处理指数为负数,底数为0
{
return 0.0;
}
double result = 1.0;
int absExponent = exponent;
if(exponent < 0)
absExponent = -exponent;
result = power_method_1(base,absExponent);
if (exponent < 0)
result = 1.0 / result;
return result;
}
public static boolean equal(double num1,double num2)
{
if(Math.abs(num1 - num2) < .0000001)
return true;
return false;
}

注意:在判断底数是否为0的时候,并不是使用base == 0,因为计算机表示小数(float和double型小数)的时候都存在误差,不能直接使用==,如果两个数的差的绝对值很小就能判断为相等。

原书中还提到在提到了设置全局变量来处理异常。

方法三###

如果输入的指数exponent为32,我们在计算结果的时候for循环就需要做31次乘法,可以这样(base2)16;32次方先求平方,再平方的基础上求4次方,8次方,16次方,最后32次方总共5次乘法。

public static double power_method_3(double base,int exponent)
{
if(exponent == 0)
return 1;
if(exponent == 1)
return base;
double result = power_method_3(base, exponent >> 1);
result *= result;
if((exponent & 0x1) == 1)//判断是否为奇数
result *= base;
return result;
}

使用位运算代替%2操作来判断奇偶数,这种方法利用值得借鉴的递归思想,但这种方法和方法一都为考虑到指数负数情况,需要结合方法二来完善。

总结###

看似简单的一道题,需要注意的细节有

  • 代码对测试用例的覆盖
  • 算法性能的优化
上一篇:面世宣言:给 Android 开发者的面试手册


下一篇:Windows Server 2008 R2 主域控制器委派DNS到子域控控制器