题解 | #求解立方根#

求解立方根

https://www.nowcoder.com/practice/caf35ae421194a1090c22fe223357dca

题目要求浮点数,对于浮点数不能直接用===判断相等,可以给定一个阈值,当差值小于该阈值时便当作相等。

方法一: 牛顿迭代法求立方根

公式为:x_{n+1} = \frac{1}{3}(\frac{a}{x^2_n} + 2x_n)

x_{n+1}为新的猜测之,x_n为当前猜测值, a是要计算的数

我们可以给定一个阈值,两次猜测的差值小于该阈值是便表明当前猜测的值已经足够接近答案。

推导过程

首先牛顿迭代法的基本思想是从一个猜测的初始值开始不断更新迭代该值,直到找到一个足够接近真实立方根的值。那么如何确保猜测的值能够逼近真实的立方根呢?可以利用函数和它的切线来逼近。可以动手把该过程画出来便于理解。

假设我们要求解的方程为f(x)=0,并且有一个近似解x_n,那么该点处的切线方程为:

y = f^{'}(x_n)(x -x_n) + f(x_n)

y = 0求解 x得到下一个更接近真实根的近似解x_{n+1}

x_{n+1} = x_n - \frac{f(x_n)}{f^{'}(x_n)}

而本题中要求求解a的立方根 需要求解方程: x^3 - a = 0

f(x) = x^3 - a

对其求导得到 f^{'}(x) = 3x^2

带入上述公式中得到:

x_{n+1} = x_n - \frac{f(x_n)}{f^{'}(x_n)} = x_n - \frac{x^3_n - a}{3x^2_n} = \frac{1}{3}(\frac{a}{x^2_n} + 2x_n)

代码如下(JavaScript Node)

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;

function getCubeRoot(num) {
    if(num === 0.0) return 0.0
    let x = num
    let lastX = 0
	// 给一个阈值
    while(Math.abs(x - lastX) > 0.0001) {
        lastX = x
        x =  1 / 3 * ((num)/ (x * x) + 2 * x )
    }
    return x.toFixed(1)
}

void async function () {
    // Write your code here
    while(line = await readline()){
        let num = parseFloat(line)
        console.log(getCubeRoot(num))
    }
}()

方法二: 二分查找

使用二分查找时应注意两点:

  1. 对于0到1之间的值 应当在num与1之间进行二分,对于大于1 的值需要在1到num之间进行二分
  2. 对于负数第一条应该相反,可以直接取绝对值,在输出前取负

function getCubeRootBinarySearch(num) {
    let neg =false
    if(num < 0) neg = true
    num = Math.abs(num)
    let left, right
    if(num < 1) {
        left = num
        right = 1
    } else {
        left = 1
        right = num
    }
    while(left <= right) {
        let mid = (right - left) / 2 + left
        let cube = mid ** 3
        let diff = Math.abs(cube - num)
        if(diff < 0.00001) {
            if(neg) mid = -mid
            return Number(mid.toFixed(1))
        }
        if(cube < num) {
            left = mid
        } else {
            right = mid
        }
    }
    if(neg) left = -left
    return Number(left.toFixed(1))
}

全部评论

相关推荐

头像
03-30 21:02
已编辑
武汉大学 Java
ALEX_BLX:虽然说聊天记录不可信,不过这个趋势确实如此但我觉得也要想到一点就是卷后端的人里真正有“料”的人又有多少,我说的这个料都不是说一定要到大佬那种级别,而是就一个正常的水平。即使是现在也有很多人是跟风转码的,2-3个月速成后端技术栈的人数不胜数,但今时不同往日没可能靠速成进大厂了。这种情况就跟考研一样,你能上考场就已经打败一半的人了
点赞 评论 收藏
分享
被普调的六边形战士很高大:项目经历貌似和专业或者求职方向没大关系?
点赞 评论 收藏
分享
评论
1
2
分享

创作者周榜

更多
牛客网
牛客企业服务