美文网首页
算法系列之幂运算

算法系列之幂运算

作者: XieYiwen | 来源:发表于2022-07-25 04:06 被阅读0次

本题来自Leetcode
题目传送门
难度:中等
编程语言:Go

1. 背景

看了不少其他人提交的答案,发现Golang的答案特别少,且很多都存在同一个问题:精度。

Go的浮点数精度范围有限,对于超过精度的返回值会不准确,但貌似很多人并没有意识到这个问题,或者说不知道怎么处理于是略过了这个问题。

本文会按照:题目介绍-> 解题思路分析 -> 源码展示的方式,来完成这一作业。

2. 题目介绍

实现 pow(x, n) ,即计算 x 的整数 n 次幂函数(即x^n )。

样例:

示例 1:
    输入:x = 2.00000, n = 10
    输出:1024.00000
示例 2:
    输入:x = 2.10000, n = 3
    输出:9.26100
示例 3:
    输入:x = 2.00000, n = -2
    输出:0.25000

提示:

  1. -100.0 < x < 100.0

  2. -2^{31} <= n <=2^{31}-1

  3. -10^4 <= x^n <= 10^4

3. 解析思路

简单方法,直接调用内置math函数库。 重复造轮子方法:按照快速降幂的思路,将n折半,计算因子扩大为2次幂。n折半后是奇数,则需要单独✖️计算因子。

所谓降幂,其实就是利用了幂函数的运算法则:x^n =(x2)(n/2) ,来减少需要运算的次数。尤其是在幂n比较大时,具备良好的性能优势。

4. 源码展示

公用方法,保留结果的8位精度。

func roundFloat(r float64) float64 {
    return float64(int(r*10000000)) / 10 / 1000000
}

简单方法实现

func myPowSimple(x float64, n int) float64 {
    return roundFloat(math.Pow(x, float64(n)))
}

快速降幂:

func myPowFast(x float64, n int) float64 {
    switch {
    case n == 0 || x == 1:
         return 1
    case x == 0:
            return 0
    }
    if n < 0 {
        n = -n
        x = 1 / x
    }
    result := 1.0
    for i := n; i > 0; i = i / 2 {
        if i%2 != 0 {
           result *= x
        }
        x *= x
    }
    return roundFloat(result)
}

Leetcode运算结果: 两种方法均得到以下数据:

执行用时: 0ms
内存消耗: 1.9 MB

生活依然要继续,每天拿出半个小时,放下焦虑,用行动来积累更好的自己,我们一起加油!

相关文章

  • 算法系列之幂运算

    本题来自Leetcode题目传送门[https://leetcode.cn/problems/powx-n/]难度...

  • WOJ-315-高级机密

    主要参考了这篇文章:快速幂 蒙格马利算法 蒙哥马利(Montgomery)幂模运算是快速计算a^b%k的一种算法,...

  • powmod 函数 原理

    最近研究了下网易云音乐的登录机制,涉及到了RSA算法,最初在编写幂运算求模这部分时,直接先幂运算然后再求余,发现效...

  • 一张图解决Python运算符优先级问题

    Python运算优先级金字塔图解: 特别注意:幂运算和正负号问题 如果幂运算左侧有负号,幂运算优先级高;如果幂运算...

  • 快速幂

    常规求幂 快速求幂(一般) 快速求幂 (递归) 快速求幂(位运算) 快速求幂(位运算,更简洁)

  • 【python】操作符的优先级

    #总体趋势: 幂运算>一元运算符>算数操作符>比较操作符>逻辑运算符 ##幂运算: 幂运算(**)优先级高于左边的...

  • 【JS算法】简单的位运算

    先来熟悉下位运算 算法231题:给你一个整数 n,请你判断该整数是否是 2 的幂次方 普通解法 位运算解法 2的X...

  • Python常用运算符||运算符的优先级

    一、优先级 1. 算数运算 结论: 先算乘除,后算加减,有幂运算先算幂运算 2. 位运算 3. 比较运算 复习:比...

  • JS逆向:JS 中常见的加密算法及逆向特征

    1. 取盐算法 取盐 算法,也叫 摘要算法,是对数据进行一系列运算后,截取一部分关键值进行校验。因此运算过程 不可...

  • shell-运算

    常用算术运算符 ,-,,/,% ,* (幂运算 5**7= 5的7次方) 1.expr ⚠️:1.不能计算幂运算2...

网友评论

      本文标题:算法系列之幂运算

      本文链接:https://www.haomeiwen.com/subject/ffonirtx.html