数值的整数次方

数值的整数次方

http://www.nowcoder.com/practice/1a834e5e3e1a4b7ba251417554e07c00

我当然只能想到最low的直接运算解法:

public class Solution {
    public double Power(double base, int exp) {
        if (exp == 0) {
            return 1.0;
        } else if (exp < 0) {
            base = 1.0 / base;
            exp = 0 - exp;
        }
        double ret = 1.0;
        for (int i = 0; i < exp; ++i) {
            ret *= base;
        }
        return ret;
    }
}

这种数学类的题目我一般很讨厌就是难度不大,侮辱性极强,知道解法就很容易,不知道的时候就GG,考的比较偏,什么快速幂什么的对于我这种业余选手实在是第一次听说,好在理解上并不困难,因此这种题目我始终是作为一种开拓思路的心态。

public class Solution {
    public double Power(double base, int exp) {
        if (exp == 0) {
            return 1.0;
        } else if (exp < 0) {
            base = 1.0 / base;
            exp = 0 - exp;
        }
        return p(base, exp);
    }
    double p(double b, int n) {
        if (n == 0) 
            return 1.0;
        double ret = p(b, n / 2);
        if ((n & 1) == 1) { // 奇数
            return ret * ret * b;
        } else {
            return ret * ret;
        }
    }
}

非递归的快速幂:

public class Solution {
    public double Power(double base, int exp) {
        if (exp == 0) {
            return 1.0;
        } else if (exp < 0) {
            base = 1.0 / base;
            exp = 0 - exp;
        }
        double ret = base;
        while (exp > 1) { // 以内ret的起始值是base,因此这里条件是大于1
            ret *= ret;
            if ((exp & 1) == 1) { // 奇数
                ret *= base;
            }
            exp >>= 1;
        }
        return ret;
    }
}

题解中的非递归快速幂的解法如下:

public class Solution {
    public double Power(double base, int exp) {
        if (exp == 0) {
            return 1.0;
        } else if (exp < 0) {
            base = 1.0 / base;
            exp = 0 - exp;
        }
        double x = base, ret = 1.0;
        while (exp > 0) {
            if ((exp & 1) == 1) { // 奇数
                ret *= x;
            }
            x *= x;
            exp >>= 1;
        }
        return ret;
    }
}

题解中的是每次x平方,当exp为奇数时,才变更ret的值,我觉得这个解法首先是正确的,而且实现的也非常巧妙,但是觉得上手有点费解。

全部评论

相关推荐

不愿透露姓名的神秘牛友
07-08 10:39
一个证都没&nbsp;我能填什么
程序员小白条:别人有,你为什么没有,还是这个道理,社会就是比较,竞争,淘汰,你要安逸,那么就要做好淘汰的准备
点赞 评论 收藏
分享
Twilight_m...:表格简历有点难绷。说说个人看法: 1.个人基本情况里好多无意义信息,什么婚姻状况、健康状况、兴趣爱好、户口所在地、身份证号码、邮政编码,不知道的以为你填什么申请表呢。 2.校内实践个人认为对找工作几乎没帮助,建议换成和测开有关的项目,实在没得写留着也行。 3.工作经历完全看不出来是干什么的,起码看着和计算机没啥关系,建议加强描述,写点你在工作期间的实际产出、解决了什么问题。 4.个人简述大而空,看着像AI生成,感觉问题最大。“Python,C,C++成为我打造高效稳定服务的得力工具”、“我渴望凭借自身技术知识与创新能力,推动人工智能技术的应用发展,助力社会实现智能化转型”有种小学作文的美感。而且你确定你个人简述里写的你都会嘛?你AI这块写的什么“深入研究”,发几篇顶会的硕博生都不一定敢这么写。而且你AI这块的能力和软测也完全无关啊。个人简述建议写你对哪些技术栈、哪些语言、哪些生产工具的掌握,写的有条理些,而且最好是和测开强相关的。
点赞 评论 收藏
分享
每晚夜里独自颤抖:要求太多的没必要理
点赞 评论 收藏
分享
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务