目录

创新互联是专业的薛城网站建设公司，薛城接单;提供成都网站建设、网站制作,网页设计,网站设计,建网站,PHP网站建设等专业做网站服务;采用PHP框架,可快速的进行薛城网站开发网页制作和功能扩展;专业做搜索引擎喜爱的网站,专业的做网站团队,希望更多企业前来合作!

1. 数值的整数次方

1.1 运行超时的思路

1.2 思路一:  快速幂 (递归实现)

1.3 思路二:  快速幂 (迭代实现)

---

1. 数值的整数次方

原题链接:

剑指 Offer 16. 数值的整数次方 - 力扣（LeetCode）https://leetcode.cn/problems/shu-zhi-de-zheng-shu-ci-fang-lcof/

我们都知道,  在C语言的一根库中有一个pow函数可以用来求一个数的乘方,  本题就是要求实现类似于pow的功能.  要求实现特定库函数(特别是处理数值和字符串的函数)的功能是一类常见的面试题。这就要求我们在平时编程的时候除了能熟练使用库函数,更重要的是要理解库函数的实现原理。

1.1 运行超时的思路

想必大家第一个想到的思路就是循环.  我们对输入的幂指数进行特殊处理:  使得幂指数大于0.  然后利用for循环将底数乘到最终结果上就可以了!  很遗憾Leetcode 并不想让你这么做,  面试官也不希望看到这种解法.

double myPow(double x, int n){
    //保存结果的变量
    double result = 1.0;
    //为啥用long int 后面讲
    long int a = n;
    //如果幂指数小于0, 取绝对值, 2的-1次方就等于二分之一的一次方嘛
    if(n< 0)
    {
        a = -a;
        x = 1 / x;
    }
    //循环将底数乘到结果上
    int i = 0;
    for(i = 0;i< a;i++)
    {
        result *= x;
    }
    return result;
}

1.2 思路一:  快速幂 (递归实现)

快速幂的本质就是分治,  大家细细品味哈. 

 以上方法不可行,  我们可以换一种思路考虑:  例如,  我们的目标是求出一个数字的32次方，如果我们已经知道了它的16次方，那么只要在16次方的基础上再平方一次就可以了。而16次方是8次方的平方。这样以此类推，我们求32次方只需要做5次乘法:  先求平方，在平方的基础上求4次方，在4次方的基础上求8次方，在8次方的基础上求16次方，最后在16次方的基础上求32次方。对于奇数次方, 我们只需要拿出一个底数出来即可. 
也就是说，我们可以用如下公式求a 的n次方:

同上面一样我们需要对输入的幂指数进行处理:  

将幂指数保存在一个变量,  例如 a 中,  当幂指数小于 0 时,  我们就令 a = -a,  底数x = 1 / x,  就相当于对幂指数取绝对值,  然后把幂指数的负号作用到底数上,  2 的 -1 次方就等于 1/2 的 1 次方嘛.  

注意:  保存幂指数的变量必须选用存储范围更大的 long int,  我们都知道 int 的范围是 

当我们输入的幂指数为 - (2的31次方时),  取绝对值后 int 类型是存不下这个数的. 

解题的时间复杂度:  O(logN),  因为是递归,  函数调用需要函数栈帧,  故空间复杂度:  O(logN).

double recurison(double x, long int n)
{
    //递归的结束条件, 任何数的0次幂都等于1(0除外)
    if(n==0)
    {
        return 1;
    }
    // 将幂指数整除2, 但是我们选用位运算提高效率
    double result = recurison(x, n>>1);
    result *= result;
    //判断奇偶, 奇数就乘以一个底数, 同样使用位运算提高效率
    if((n&1)==1)
    {
        result*=x;
    }
    return result;
}

double myPow(double x, int n){
    double result;
    //对指数进行处理
    long int a = n;
    if(n< 0)
    {
        a = -a;
        x = 1 / x;
    }
    return recurison(x, a);
}

1.3 思路二:  快速幂 (迭代实现)

还是以具体的例子来看:  我们一开始还是对幂指数进行处理使它为整数哈,  当幂指数n为偶数,  例如x ^ 8  我们先算 x * x = x ^ 2,  再算x ^ 2 * x ^ 2 = x ^ 4,  最后算x ^ 4 * x ^ 4 = x ^ 8. 对于奇数呢,  我们将指数进行拆分,  例如 x ^ 10,  指数10 = 1 + 4 + 8  = 2 ^ 0 + 2 ^ 2 + 2 ^ 3,  即 

x ^ 10 = x ^ 1 * x ^ 4 * x ^ 8

依次类推, 直到将幂指数的二进制遍历完毕,  显然result 乘上的值在每一遍历一个二进制位时都要逐步递增:  

偶数自然不用说,  也是满足此规律的.

double myPow(double x, int n){
    //保存结果的变量
    double result = 1.0;
    //对指数进行处理
    long int a = n;
    if(n< 0)
    {
        a = -a;
        x = 1 / x;
    }
    //遍历指数的二进制位, 对指数逐步右移即可
    while(a)
    {
        //如果二进制位为1, 乘上当时的x的二进制位值的次幂
        if((a&1)==1)
        {
            result *= x;
        }
        //下一个二进制位的, x的二进制位值的次幂
        x = x * x;
        //将a右移
        a >>= 1;
    }
    return result;
}

由于作者表达能力有限,  思路可能不是很清晰,  望大佬们海涵.

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧

文章标题：剑指offer----C语言版----第十一天-创新互联
标题路径：http://csdahua.cn/article/hhhse.html