剑指offer-11-数值的整数次方 _剑指offer

恢弘志士之气，不宜妄自菲薄。这篇文章主要讲述剑指offer-11-数值的整数次方相关的知识，希望能为你提供帮助。

文章目录

0、问题
1、一般思路
2、最优方法 -- 快速求幂算法
3、完整代码：

0、问题给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。
保证base和exponent不同时为0
1、一般思路把情况考虑完整： 2 ? 5 2^{-5} 2?5, 2 0 2^0 20, 2 5 2^{5} 25
同时，直接进行相乘，也能计算出来，此时未考虑优化问题。
判断double是否相同的方法：equal

const doublemin_value = https://www.songbingjia.com/android/1e-7; bool equal(double num1, double num2) { if(num1 - num2 < - min_value || num1 - num2 > min_value) { return false; } else { return true; } }

equal的另一种实现方法：

int equal(double left, double right) { if((left - right) < min_value & & (left - right) > -min_value) return true; else return false; }

【剑指offer-11-数值的整数次方】只有在下面两个范围内，超过了浮点数表示精度，才认为两个相等，所以这里是

&
&

符号(易错)。

文章图片

将最常见的几种情况考虑完整，依次相乘，可得出下面代码。

double Power(double base, int exponent) { if (equal(base, 0.0) & & exponent < = 0) return 0; //这里已经输入不合法了bool flag_positive = true; if (exponent < 0) { flag_positive = false; exponent = -exponent; } else if (exponent == 0) { return 1; }double ret = 1.0; for (size_t i = 0; i < exponent; i++) { ret *= base; }if (!flag_positive) ret = 1.0 / ret; return ret; }

上述代码，思路比较直观，但仔细分析会发现，中间有可以优化的地方。
2、最优方法 – 快速求幂算法如果指数为32，我们在循环中做31次乘法。换个角度，我们知道了16次方，直接在16次方的基础上平方就可以获知到32次方的值。而16是8次方的值，以此类推，求32次方，只需要做5次乘法：先平方，平方的基础上求得4次方，4次方的基础上求得8次方，8的基础上求得16，16的基础上求得32.
其实上述思路就是【快速求幂算法】，算法思路可以参考原文，算法伪代码为：

POWER_INTEGER(x, n) 1 pow ← 1 2 while (n > 0) 3do if (n mod 2 = 1) 4then pow ← pow * x 5x ← x * x 6n ← n / 2 7 return pow

实现代码见完整代码中Power_quick 部分。
注意：

最开始对while中的if (exponent & 0x1)语句理解错误，需要注意。
编译器的警告信息不能忽略，都要看一下。下面两条在编译器中都提示了，最开始没忽视了。。。
- 最开始把Min_value定义在Solution类中
- if (exponent & 0x1 == 1)，其中 ==的优先级更高，然后才是 &

3、完整代码：

#include < iostream> #include < cstdlib> #include < ctime> const double Min_value = https://www.songbingjia.com/android/1.0e-7; class Solution { bool equal(double num1, double num2) { if (num1 - num2 < -Min_value || num1 - num2 > Min_value) { return false; } else { return true; } }public: //快幂法 double Power_quick(double base, int exponent) { if (equal(base, 0.0) & & exponent < = 0) return 0; bool flag_positive = true; if (exponent < 0) { flag_positive = false; exponent = -exponent; } else if (exponent == 0) { return 1; }double ret = 1.0; int tmp = exponent; while (exponent > 0) { //如果是奇数，需要再继续乘 base，下面类似于取余(%)操作行，需要放在外面 if (exponent & 0x1) //n & 1 等价于 (n % 2) == 1 { ret *= base; // printf("1.ret: %d, exponent = %d, base = %.2lf\\n", exponent & 0x1, exponent, base); }base *= base; exponent > > = 1; n > > = 1 等价于 n /= 2 }if (!flag_positive) ret = 1.0 / ret; return ret; } //依次乘 double Power_order(double base, int exponent) { if (equal(base, 0.0) & & exponent < = 0) return 0; bool flag_positive = true; if (exponent < 0) { flag_positive = false; exponent = -exponent; } else if (exponent == 0) { return 1; }double ret = 1.0; for (size_t i = 0; i < exponent; i++) { ret *= base; }if (!flag_positive) ret = 1.0 / ret; return ret; } }; int main() { Solution ans; int start_time = clock(); double ret = ans.Power_quick(5, 10); printf("value: %.2lf, time: %lu\\n", ret, clock() - start_time); start_time = clock(); ret = ans.Power_quick(5, 11); printf("value: %.2lf, time: %lu\\n", ret, clock() - start_time); start_time = clock(); ret = ans.Power_order(5, 10); printf("value: %.2lf, time: %lu\\n", ret, clock() - start_time); start_time = clock(); ret = ans.Power_order(5, 11); printf("value: %.2lf, time: %lu\\n", ret, clock() - start_time); /// start_time = clock(); ret = ans.Power_quick(5, 30); printf("value: %.2lf, time: %lu\\n", ret, clock() - start_time); start_time = clock(); ret = ans.Power_quick(5, 31); printf("value: %.2lf, time: %lu\\n", ret, clock() - start_time); start_time = clock(); ret = ans.Power_order(5, 30); printf("value: %.2lf, time: %lu\\n", ret, clock() - start_time); start_time = clock(); ret = ans.Power_order(5, 31); printf("value: %.2lf, time: %lu\\n", ret, clock() - start_time); }

测试了一下时间，上面几个时间差不多，暂不知道是什么原因。