文章目录加载中
数值的整次方
# 1. 题目描述
题目:实现函数 double Power(double base, intexponent),求 base 的 exponent 次方。不得使用库函数,同时不需要考虑大数问题
# 2. 思路分析
简单思路:最简单的做法是循环,但是要考虑异常值的检验。比如指数是负数,底数为 0。
优化思路:书上提供了一种复杂度为 $O(logN)$ 的做法。比如我们要求 32 次方,那么只要求出 16 次方再平方即可。依次类推,是递归函数的结构。
递推公式如下:
$$
a^n=\left{
\begin{aligned}
a^{n/2}*a^{n/2} ; n为偶数\
a^{(n - 1)/2}*a^{(n - 1)/2} ; n为奇数
\end{aligned}
\right.
$$
需要注意的是,如果幂是奇数,例如 5 次方,可以先计算 2 次方,结果平方后(4 次方),再乘以自身(5 次方)。按照此思路处理。
# 3. 代码实现
# 简单思路
/**
*
* @param {Number} base
* @param {Number} exp
*/
function pow(base, exp) {
// 规定0的任何次方均为0
if (!base) {
return 0;
}
let result = 1,
absExp = Math.abs(exp);
for (let i = 0; i < absExp; ++i) {
result *= base;
}
// 对于指数小于0的情况,求其倒数
if (exp < 0) {
result = 1 / result;
}
return result;
}
/**
* 以下是测试代码
*/
console.log(pow(2, -2));
console.log(pow(2, 2));
console.log(pow(2, 0));
console.log(pow(0, -9));
# 优化思路
在 Js 中整数除 2 不会自动取整,可以使用Math.floor()
。但更好的做法是使用>>
位运算。
判断奇数可以用%2
判断。但更好的做法是和1
进行&
运算后(除了最后 1 位,都被置 0 了),判断是不是 1
/**
* 求base 的 exp次幂,其中exp永远是正数
* @param {Number} base
* @param {Number} exp
*/
function unsignedPow(base, exp) {
if (exp === 0) {
return 1;
} else if (exp === 1) {
return base;
}
let result = pow(base, exp >> 1);
result *= result;
if (exp & (1 === 1)) {
result *= base;
}
return result;
}
/**
* 求 base的exp次幂
* @param {Number} base
* @param {Number} exp
*/
function pow(base, exp) {
if (!base) {
return 0;
}
let absExp = Math.abs(exp);
return exp < 0 ? 1 / unsignedPow(base, absExp) : unsignedPow(base, absExp);
}
/**
* 以下是测试代码
*/
console.log(pow(2, 2));
console.log(pow(2, 0));
console.log(pow(0, -9));
console.log(pow(2, -2));
本文来自心谭博客:xin-tan.com,经常更新web和算法的文章笔记,前往github查看目录归纳:github.com/dongyuanxin/blog