成都专业建网站公司,温州微信网站开发,wordpress建企业商城,饶阳网站建设记录来自《剑指offer》上的算法题。
题目描述#xff1a; 实现函数 double Power(double base, int exponent), 求 base的 exponent次方。不得使用库函数#xff0c;同时不需要考虑大数问题。 下面是一种解法#xff1a;
// 判断num1是否等于num2
bool equal(double num1,…记录来自《剑指offer》上的算法题。
题目描述 实现函数 double Power(double base, int exponent), 求 base的 exponent次方。不得使用库函数同时不需要考虑大数问题。 下面是一种解法
// 判断num1是否等于num2
bool equal(double num1, double num2){if ((num1 - num2) -0.0000001 (num1 - num2) 0.0000001)return true;elsereturn false;
}
// 求指数是正数的结果
double PowerWithUnsignedExponent(double base, unsigned int exponent){double result 1.0;for (int i 1; i exponent; i)result * base;return result;
}
double Power(double base, int exponent){g_InvalidInput false;// 非法输入if (equal(base, 0.0) exponent 0){g_InvalidInput true;return 0.0;}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;
}
上述解法中使用一个全局变量g_InvalidInput用来判断是否输入非法的输入如输入的基数是0指数是负数那么就是一个非法输入。这里判断两个小数是否相等只能判断它们之差的绝对值是否小于某个数而这也是上述解法中定义函数equal()的原因用来判断输入的数是否为0。
上述解法中函数PowerWithUnsignedExponent()还可以进一步进行优化因为该函数的循环次数等于输入的指数减一如输入指数是32则循环中的乘法要做31次采用下述公式对求a的n次方进行优化
an{an/2∗an/2a(n−1)/2∗a(n−1)/2n是偶数n是奇数a^n = \begin{cases}
a^{n/2} * a^{n/2} // 改进版本
double PowerWithUnsignedExponentOptimz(double base, unsigned int exponent){if (exponent 0)return 0;if (exponent 1)return base;double result PowerWithUnsignedExponentOptimz(base, exponent 1);result * result;if (exponent 0x1 1)// 如果指数是奇数result * base;return result;
}
这个代码是采用了递归方法来实现上述公式同时采用位与运算代替求余运算(%)来判断一个数是否奇数还是偶数这是因为位运算的效率比乘除法及求余运算的效率要更高。
测试例子可以查看我的Github。
